disjoint-sets: three union-find implementations
This library provides three disjoint set data structures:
UnionFind
: An array-based union-find
where clients represent elements as small unsigned integers.
UnionFindNode
: A tree-based
union-find where each set can have associated ata, and where
clients represent elements as opaque tree nodes.
AUnionFind
: Like UnionFind
, but Sync
for sharing between
threads.
All three perform rank-balanced path compression à la Tarjan, using
interior mutability.
Usage
It’s on crates.io, so add
this to your Cargo.toml
:
[dependencies]
disjoint-sets = "*"
And add this to your crate root:
extern crate disjoint_sets;
Examples
Kruskal’s algorithm to find the minimum spanning tree of a graph:
use disjoint_sets::UnionFind;
type Node = usize;
type Weight = usize;
struct Edge {
dst: Node,
weight: Weight,
}
type Graph = Vec<Vec<Edge>>;
fn edges_by_weight(graph: &Graph) -> Vec<(Node, Node, Weight)> {
let mut edges = vec![];
for (src, dsts) in graph.iter().enumerate() {
for edge in dsts {
edges.push((src, edge.dst, edge.weight));
}
}
edges.sort_by_key(|&(_, _, weight)| weight);
edges
}
fn mst(graph: &Graph) -> Vec<(Node, Node)> {
let mut result = vec![];
let mut uf = UnionFind::new(graph.len());
for (src, dst, _) in edges_by_weight(graph) {
if !uf.equiv(src, dst) {
uf.union(src, dst);
result.push((src, dst));
}
}
result
}
fn main() {
let graph = vec![
vec![ Edge { dst: 1, weight: 6 },
Edge { dst: 3, weight: 8 }, ],
vec![ Edge { dst: 2, weight: 5 },
Edge { dst: 4, weight: 1 }, ],
vec![ Edge { dst: 5, weight: 4 }, ],
vec![ Edge { dst: 4, weight: 7 },
Edge { dst: 6, weight: 3 }, ],
vec![ Edge { dst: 5, weight: 2 },
Edge { dst: 7, weight: 12 }, ],
vec![ Edge { dst: 8, weight: 11 }, ],
vec![ Edge { dst: 7, weight: 9 }, ],
vec![ Edge { dst: 8, weight: 10 }, ],
vec![ ],
];
assert_eq! {
vec![ (1, 4), (4, 5), (3, 6), (2, 5),
(0, 1), (3, 4), (6, 7), (7, 8), ],
mst(&graph)
};
}