Crate disjoint

source ·
Expand description

Tests Coverage Crate Docs

This crate provides fast disjoint-set data structure implementations in 100% safe Rust.

DisjointSet is a very lightweight disjoint-set data structure, with no additional data attached to the set elements. Use this if you manage the data associated to the elements yourself, and just want to keep track which elements are joined.

DisjointSetVec<T> combines a DisjointSet with a Vec<T>, so it manages contiguous data entries T and keeps track of which entries are joined. Use this if you want the disjoint-set data structure to contain some additional data T for each element.

Examples

Disjoint set data structures can be applied to find the minimal spanning forest of an undirected edge-weighted graph. Let’s assume we work with the following graph interface:

trait Edge : Copy {
    fn first_vertex(&self) -> usize;
    fn second_vertex(&self) -> usize;
}

trait Graph {
    type E : Edge;
    fn edges_ordered_by_weight(&self) -> Vec<Self::E>;
    fn number_vertices(&self) -> usize;
    fn new(edges: Vec<Self::E>) -> Self;
}

Then it’s very straight-forward to use the provided DisjointSet struct and its methods is_joined and join to implement Kruskal’s algorithm to find the minimum spanning forest.

use disjoint::DisjointSet;

fn minimum_spanning_forest<G : Graph>(graph: &G) -> G {
    let mut result_edges = Vec::new();
    let mut vertices = DisjointSet::with_len(graph.number_vertices());

    for edge in graph.edges_ordered_by_weight() {
        if !vertices.is_joined(edge.first_vertex(), edge.second_vertex()) {
            vertices.join(edge.first_vertex(), edge.second_vertex());
            result_edges.push(edge);
        }
    }
     
    Graph::new(result_edges)
}

We can even use the fact that join returns true if the elements have not been joined already, to further simplify the algorithm (this variation is sometimes called Quick-Union):

use disjoint::DisjointSet;

fn minimum_spanning_forest_quick_find<G : Graph>(graph: &G) -> G {
    let mut result_edges = Vec::new();
    let mut vertices = DisjointSet::with_len(graph.number_vertices());

    for edge in graph.edges_ordered_by_weight() {
        if vertices.join(edge.first_vertex(), edge.second_vertex()) {
            result_edges.push(edge);
        }
    }
     
    Graph::new(result_edges)
}

Changelog

This crate maintains a changelog.

License

Licensed under either of:

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Macros

Structs

  • DisjointSet
    A disjoint-set data structure for tracking which elements are joined, without managing any additional data associated to the elements.
  • DisjointSetVec
    A data structure for managing a Vec<T> of data together with a DisjointSet to keep track of which data entries are joined.