fera-unionfind

Union-find (disjoint-set) data structure.

This crate is part of the fera project.

License

Licensed under Mozilla Public License 2.0. Contributions will be accepted under the same license.

lib.rs:

Union-find (disjoint-set) data structure implementation.

This implementation use path compression and rank heuristic. With default type parameters the parents and ranks are stored in a std::collections::HashMap. If the keys are in range 0..n, use UnionFindRange.

The keys should implement Copy. If the keys does not implement Copy, references to the keys stored elsewhere should be used.

This crate can be used through fera crate.

Examples

use fera_unionfind::UnionFind;

// Explicit type to make it clear
let mut s: UnionFind<&'static str> = UnionFind::new();

s.make_set("red");
s.make_set("green");
s.make_set("blue");

assert_eq!(3, s.num_sets());
assert!(!s.in_same_set("red", "green"));
assert!(!s.in_same_set("red", "blue"));

s.union("red", "blue");

assert_eq!(2, s.num_sets());
assert!(!s.in_same_set("red", "green"));
assert!(s.in_same_set("red", "blue"));

Using non Copy keys.

use fera_unionfind::UnionFind;

// This is invalid. String does not implement copy.
// let mut x: UnionFind<String> = UnionFind::new();
// Lets store the keys in a vector and use references (references are Copy).
let v = vec!["red".to_string(), "green".to_string(), "blue".to_string()];

// The type of s is Union<&'a String> where 'a is the lifetime of v.
let mut s = UnionFind::new();

s.make_set(&v[0]);
s.make_set(&v[1]);
s.make_set(&v[2]);

assert_eq!(3, s.num_sets());
assert!(!s.in_same_set(&v[0], &v[1]));
assert!(!s.in_same_set(&v[0], &v[2]));

s.union(&v[0], &v[2]);

assert_eq!(2, s.num_sets());
assert!(!s.in_same_set(&v[0], &v[1]));
assert!(s.in_same_set(&v[0], &v[2]));

Using keys in the range 0..n.

use fera_unionfind::UnionFindRange;

let mut s = UnionFindRange::with_keys_in_range(..5);

// It is not necessary to call UnionFind::make_set

assert_eq!(5, s.num_sets());
assert!(!s.in_same_set(0, 1));
assert!(!s.in_same_set(0, 2));

s.union(0, 2);

assert_eq!(4, s.num_sets());
assert!(!s.in_same_set(0, 1));
assert!(s.in_same_set(0, 2));

s.reset();
assert_eq!(5, s.num_sets());