#disjoint-set #union-find #graph-algorithms #set-operations

aph_disjoint_set

Disjoint set implementation with optimized memory usage and ability to detach elements

2 releases

0.1.1 Jun 17, 2023
0.1.0 Jun 17, 2023

#984 in Data structures

MIT/Apache

140KB
3K SLoC

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:
  • 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.

No runtime deps