#union-find #disjoint-set #union #find #sets #disjoint #set

union-find-rs

Disjoint-set forest implementation to support the union-find algorithm in Rust

6 releases

0.2.1 Dec 29, 2021
0.2.0 Dec 29, 2021
0.1.3 Dec 28, 2021

#6 in #disjoint


Used in graphbench

MIT license

41KB
519 lines

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.

[dependencies]
union-find-rs = "^0.2"
  1. add the following to the top of your .rs file
    1. 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

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

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 == &vec![9].into_iter().collect::<HashSet<usize>>())
);
assert!(
    as_vec
        .iter()
        .any(|set| set == &vec![1, 4].into_iter().collect::<HashSet<usize>>())
);

No runtime deps