6 releases
0.2.1 | Dec 29, 2021 |
---|---|
0.2.0 | Dec 29, 2021 |
0.1.3 | Dec 28, 2021 |
#1405 in Data structures
81 downloads per month
Used in graphbench
41KB
519 lines
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
Getting Started
Specify union-find-rs
as a dependency in your Cargo.toml
.
[dependencies]
union-find-rs = "^0.2"
- add the following to the top of your
.rs
file-
use union_find_rs::prelude::*;
-
- see the trait
UnionFind
for the core operations of union-find - see the struct
DisjointSets
for an implementation ofUnionFind
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>>())
);