Expand description
This crate contains two basic union-find implementations:
UnionFind, a basic single-threaded union-find data-structure.concurrent::UnionFind, a concurrent union-find data-structure.
Both structures are fairly rudimentary and are customized to be used in an egraph-related setting. In particular, they do “union by min id”, which is a strategy that does not guarantee the same asymptotic complexity as the main techniques in the literature (e.g. union by rank). Union by min is a heuristic introduced to reduce the number of ids perturbed during congruence closure. There’s likely more to do in this area but for now it seems to work well enough. It doesn’t hurt that it’s also simpler to implement.
Modules§
- concurrent
- A concurrent implementation of a union-find datastructure.
Structs§
- Union
Find - A basic implementation of a union-find datastructure.