disjoint

This crate provides DisjointSet, a [disjoint-set data structure] implemented in 100% safe Rust.

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:

```rust trait Edge : Copy { fn firstvertex(&self) -> usize; fn secondvertex(&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.

```rust use disjoint::DisjointSet;

fn minimumspanningforest(graph: &G) -> G { let mut resultedges = Vec::new(); let mut vertices = DisjointSet::new(graph.numbervertices());

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 cometimes called Quick-Union):

```rust use disjoint::DisjointSet;

fn minimumspanningforestquickfind(graph: &G) -> G { let mut resultedges = Vec::new(); let mut vertices = DisjointSet::new(graph.numbervertices());

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)

} ```

See the [documentation] for more details on how these and other methods work.

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.