union_find

Implementations of the disjoint-set forest data structure that supports the union-find algorithm.

This crate focuses on ease of use and simplicity.

Background / Context

1. Wikipedia article: disjoint-set data structure

Getting Started

1. use union_find::prelude::*; to import everything necessary
2. see the trait UnionFind for the core operations of union-find
3. see the struct DisjointSets for an implementation of UnionFind

Example

use union_find_rs::prelude::*;
use std::collections::HashSet;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.make_set(1).unwrap();
sets.make_set(4).unwrap();
sets.make_set(9).unwrap();

sets.union(1, 4).unwrap();

// the disjoint sets as a vector of vectors
let as_vec: Vec<HashSet<usize>> = sets.into_iter().collect();

// there should be 2 disjoint sets, where one of them only contains `9` and the other one
// only contains `1` and `4`
assert_eq!(as_vec.len(), 2);
assert!(as_vec.iter().any(|set| set.len() == 1 && set.contains(&9)));
assert!(as_vec.iter().any(|set| set.len() == 2
                                && set.contains(&1)
                                && set.contains(&4)));