persistent-equivalence: Persistent equivalence relations (aka union-find)

[ bsd3, data, library ] [ Propose Tags ]

This is a semi-persistent data structure for equivalence relations (known in the imperative world as union-find or disjoint set union). It exhibits optimal performance when used in a linear pattern, but degrades when other access patterns are used.

The basic idea is as given by Conchon and Filliatre in their 2007 paper "A persistent union-find data structure." Unlike the implementation given in the paper, this version is safe with multiple threads, but does not optimize for backtracking.

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1, 0.1.1, 0.2, 0.3
Dependencies array (>=0.3 && <0.4), base (>=3 && <5), diffarray (>=0.1 && <0.2) [details]
License BSD-3-Clause
Author Chris Smith <cdsmith@gmail.com>
Maintainer Chris Smith <cdsmith@gmail.com>
Category Data
Uploaded by ChrisSmith at 2011-06-07T02:38:26Z
Distributions
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 3106 total (14 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]