A Disjoint-Set data structure (aka Union-Find w/ Rank)
Some interesting lecture notes regarding Union-Find.
Usage
Setup
In Cargo.toml
, add this crate as a dependency.
...
[]
= { = "0.1" }
...
API
Example 1
Task: Create a UnionFind data structure of arbitrary size that contains usize
at its elements. Then, union a few elements and capture the state of the data structure after that.
Solution:
use ;
// Create a UnionFind data structure of arbitrary size that contains subsets of usizes.
let mut uf1 = new;
// Note: Trivial subsets (i.e. singletons) are ignored in the data structure because they can always be calculated based on the state and the context.
println!;
uf1.union;
uf1.union;
uf1.union;
uf1.union;
println!;
let mut hs1 = new;
hs1.insert;
hs1.insert;
hs1.insert;
hs1.insert;
let mut hs2 = new;
hs2.insert;
hs2.insert;
let subsets = uf1.into_subsets;
assert_eq!;
assert!;
assert!;
// Iterate over the subsets.
for partition in uf1
Example 2
Task: Create a UnionFind data structure of size at least 10
, that contains u16
at its elements.
Note: The size business only helps for reducing the number of memory reallocations required. Therefore, it is not too special and is totally optional.
Solution:
// Create a UnionFind data structure of a fixed size that contains subsets of u16.
let mut uf2 = with_capacity;
println!;