persistent-equivalence: Persistent equivalence relations (aka union-find)
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.
Downloads
- persistent-equivalence-0.1.1.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
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 | 3197 total (0 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] |