Crate fera_unionfind

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());

Structs

IndexedHashMap	This implements a map that can be used with UnionFind.
UnionFind	A union-find (disjoint-set) struct.

Type Definitions

UnionFindRange

UnionFind with keys in range 0..n.