Implementation of Disjoint Set structure, also known as Union-Find.

Documentation

Examples

Reasons to use this implementation:

• It uses single memory allocation to store all tree and all ranks.
• Unique feature: unions operations in parallel threads.
• Unique feature: After initial union operations, it is possible to query roots in parallel.
• Optimization from knowledge that all tags are valid indexes for underlying buffer. Other implementations use safe indexing with bounds checks which is not optimized away.
  • This crate is heavily tested using Miri so it must be safe to use.
• Has 3 flavors suitable for your specific needs:
  • recommended default DisjointSet is suitable for cases when you know amount of nodes ahead of time,
  • DisjointSetArrayU8/DisjointSetArrayU16/DisjointSetArrayU32/DisjointSetArrayU64, for cases when it is preferable to store all datastructure inline without extra heap allocation.
  • DisjointSetDynamic if exact number of nodes isn't known beforehand.
• DisjointSet and DisjointSetDynamic use smaller node tag type to reduce memory usage. It is significant, for example, DisjointSet with u16::MAX nodes use 256 KByte memory, which fits to L2 caches pretty well, while u16::MAX+1 would use approximately 512 KBytes, which is much harder to fit. This optimization is opaque to user so there is no need to think about it.
• Good documentation.
• Good test coverage.

Benchmark results

I benchmarked againts most popular crates with union find implementation on crates.io: union-find and ena. Benchmarked on Core i5 6300HQ.

Labyrinth/aph-disjoint-set serial   time:   [230.91 µs 231.54 µs 232.21 µs]
Labyrinth/aph-disjoint-set parallel time:   [84.909 µs 85.978 µs 87.173 µs]
Labyrinth/Crate Union-Find          time:   [254.05 µs 254.21 µs 254.37 µs]
Labyrinth/Crate eno                 time:   [444.44 µs 444.77 µs 445.11 µs]
Islands/aph-disjoint-set serial     time:   [177.12 µs 183.31 µs 190.54 µs]
Islands/aph-disjoint-set parallel   time:   [132.87 µs 134.11 µs 135.66 µs]
Islands/Crate Union-Find            time:   [167.80 µs 172.37 µs 177.84 µs]
Islands/Crate eno                   time:   [399.41 µs 400.37 µs 401.52 µs]

Benchmarks code available by link.

Contributing

Crate is licensed by either Apache 2.0 or MIT license so by contributing to it you agree to license your code by both licenses.