#union-find #Tarjan

disjoint-sets

Three union-find implementations

15 releases

0.4.2 May 30, 2018
0.4.1 May 30, 2018
0.3.5 May 30, 2018
0.3.4 Jan 30, 2018
0.1.1 Jun 12, 2016

#172 in Data structures

Download history 33/week @ 2019-06-15 70/week @ 2019-06-22 31/week @ 2019-06-29 152/week @ 2019-07-06 22/week @ 2019-07-20 12/week @ 2019-07-27 3/week @ 2019-08-03 16/week @ 2019-08-10 24/week @ 2019-08-17 85/week @ 2019-08-24 46/week @ 2019-08-31 60/week @ 2019-09-07 43/week @ 2019-09-14 122/week @ 2019-09-21

111 downloads per month

MIT/Apache

48KB
827 lines

disjoint-sets: three union-find implementations

Build Status Crates.io License: MIT License: Apache 2.0

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 compression à la Tarjan, using interior mutability.

Usage

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

[dependencies]
disjoint-sets = "0.4.2"

And add this to your crate root:

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)
    };
}

Dependencies