union_find

build status crate docs

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

Specify union-find-rs as a dependency in your Cargo.toml.

toml [dependencies] union-find-rs = "^0.2"

  1. add the following to the top of your .rs file
    1. rust use union_find_rs::prelude::*;
  2. see the trait UnionFind for the core operations of union-find
  3. see the struct DisjointSets for an implementation of UnionFind

Example

```rust use std::collections::HashSet; use unionfindrs::prelude::*;

let mut sets: DisjointSets = DisjointSets::new();

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

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

// the disjoint sets as a vector of vectors let asvec: Vec> = sets.intoiter().collect();

// there should be 2 disjoint sets, where one of them only contains 9 and the other one // only contains 1 and 4 asserteq!(asvec.len(), 2); assert!( asvec .iter() .any(|set| set == &vec![9].intoiter().collect::>()) ); assert!( asvec .iter() .any(|set| set == &vec![1, 4].intoiter().collect::>()) ); ```