Crate union_find

An implementation of the Union-Find datastructure.

This crate implements 2 variations of the union find datastructure. QuickFindUf implements an always O(1) find while QuickUnionUf has a union operation that is always O(1).

There is also the option whether the union operation joins the underlying tree structure by size or by rank via the UnionBySize, UnionByRank, UnionByRankSize and UnionBySizeRank structs that need to be passed to the Union Find datastructure.

use union_find::{UnionFind, UnionBySize, QuickUnionUf};

// build a union find datastructure for 10 elements with quick unions,
// merge the unions by size.
let mut uf = QuickUnionUf::<UnionBySize>::new(10);

// initially each element is in it's own set
for i in 0..10 {
    assert_eq!(uf.find(i), i);
}

// join sets containing 0 and 1
assert!(uf.union(0,1));

assert_eq!(uf.find(0), 0);
assert_eq!(uf.find(1), 0);
for i in 2..10 {
    assert_eq!(uf.find(i), i);
}

Structs

QuickFindUf

Union-Find implementation with quick find operation.

QuickUnionUf

Union-Find implementation with quick union operation.

UnionByRank

Operates the union with using the rank of the sets as weight.

UnionByRankSize

Operates the union with using the rank and the size of the sets as weight.

UnionBySize

Operates the union with using the size of the sets as weight.

UnionBySizeRank

Operates the union with using the size and the rank of the sets as weight.

Enums

UnionResult

Return value of the Union::union.

Traits

Union

The value that can be contained with Union.

UnionFind

APIs for Union-Find operation.