aph_disjoint_set 0.1.1

Disjoint set implementation with optimized memory usage and ability to detach elements.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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

[Documentation][2]

[Examples][3]

# 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`][6] is suitable for cases when you know amount of nodes ahead of time,
    + [`DisjointSetArrayU8`][7]/[`DisjointSetArrayU16`][8]/[`DisjointSetArrayU32`][9]/[`DisjointSetArrayU64`][10], for cases
        when it is preferable to store all datastructure inline without extra heap allocation.
    + [`DisjointSetDynamic`][11] if exact number of nodes isn't known beforehand.
* [`DisjointSet`][6] and [`DisjointSetDynamic`][11] 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][4] and [ena][5].
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][12].

# 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.

[1]: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
[2]: https://docs.rs/aph_disjoint_set/latest/aph_disjoint_set/
[3]: https://docs.rs/aph_disjoint_set/latest/aph_disjoint_set/#examples
[4]: https://crates.io/crates/union-find
[5]: https://crates.io/crates/ena
[6]: https://docs.rs/aph_disjoint_set/latest/aph_disjoint_set/struct.DisjointSet.html
[7]: https://docs.rs/aph_disjoint_set/latest/aph_disjoint_set/struct.DisjointSetArrayU8.html
[8]: https://docs.rs/aph_disjoint_set/latest/aph_disjoint_set/struct.DisjointSetArrayU16.html
[9]: https://docs.rs/aph_disjoint_set/latest/aph_disjoint_set/struct.DisjointSetArrayU32.html
[10]: https://docs.rs/aph_disjoint_set/latest/aph_disjoint_set/struct.DisjointSetArrayU64.html
[11]: https://docs.rs/aph_disjoint_set/latest/aph_disjoint_set/struct.DisjointSetDynamic.html
[12]: https://foss.heptapod.net/angelicos_phosphoros/aph-disjoint-set/-/tree/branch/default/benches