# Crate disjoint_sets [−] [src]

Three union-find implementations.

The variants are:

structure element type data? concurrent?
`UnionFind` vector small integer no no
`UnionFindNode` tree tree node yes no
`AUnionFind` array `usize` no yes

All three perform rank-balanced path halving à la Tarjan, using interior mutability.

# Usage

It’s on crates.io, so add this to your `Cargo.toml`:

``````[dependencies]
disjoint-sets = "0.4.2"
``````

`extern crate disjoint_sets;`

This crate supports Rust version 1.15 and later.

# 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() {
// Graph to use:
//
//  0 ------ 1 ------ 2
//  |    6   |    5   |
//  | 8      | 1      | 4
//  |        |        |
//  3 ------ 4 ------ 5
//  |    7   |    2   |
//  | 3      | 12     | 11
//  |        |        |
//  6 ------ 7 ------ 8
//       9        10
let graph = vec![
// Node 0
vec![ Edge { dst: 1, weight: 6 },
Edge { dst: 3, weight: 8 }, ],
// Node 1
vec![ Edge { dst: 2, weight: 5 },
Edge { dst: 4, weight: 1 }, ],
// Node 2
vec![ Edge { dst: 5, weight: 4 }, ],
// Node 3
vec![ Edge { dst: 4, weight: 7 },
Edge { dst: 6, weight: 3 }, ],
// Node 4
vec![ Edge { dst: 5, weight: 2 },
Edge { dst: 7, weight: 12 }, ],
// Node 5
vec![ Edge { dst: 8, weight: 11 }, ],
// Node 6
vec![ Edge { dst: 7, weight: 9 }, ],
// Node 7
vec![ Edge { dst: 8, weight: 10 }, ],
// Node 8
vec![ ],
];

assert_eq! {
vec![ (1, 4), (4, 5), (3, 6), (2, 5),
(0, 1), (3, 4), (6, 7), (7, 8), ],
mst(&graph)
};
}```

## Structs

 AUnionFind Lock-free, concurrent union-find representing a set of disjoint sets. UnionFind Vector-based union-find representing a set of disjoint sets. UnionFindNode Pointer-based union-find representing disjoint sets with associated data.

## Traits

 ElementType A type that can be used as a union-find element.