Struct graph::dss::DisjointSetStruct

pub struct DisjointSetStruct<NI: Idx>(/* private fields */);

A thread-safe Disjoint Set Struct implementation, that can be safely shared and accessed across threads.

The implementation is based on the Java implementation [1] which in turn is based on a C++ implementation and some input from a Rust implementation [3].

This implementation is tailored for the graph crate as it needs to support the Idx trait.

[1] Java [2] C++ [3] Rust

Implementations

impl<NI: Idx> DisjointSetStruct<NI>

pub fn new(size: usize) -> Self

Creates a new disjoint-set struct of size elements.

Examples

use graph::prelude::*;

let dss = DisjointSetStruct::new(3);
dss.union(0, 1);
let set0 = dss.find(0);
let set1 = dss.find(1);
assert_eq!(set0, set1);

Trait Implementations

impl<NI: Idx> Components<NI> for DisjointSetStruct<NI>

fn component(&self, node: NI) -> NI

fn to_vec(self) -> Vec<NI>

impl<NI: Idx> UnionFind<NI> for DisjointSetStruct<NI>

fn union(&self, id1: NI, id2: NI)

Joins the set of id1 with the set of id2.

Examples

use graph::prelude::*;

let dss = DisjointSetStruct::new(10);
dss.union(2, 4);
assert_eq!(dss.find(2), 2);
assert_eq!(dss.find(4), 2);

fn find(&self, id: NI) -> NI

Find the set of id.

Examples

use graph::prelude::*;

let dss = DisjointSetStruct::new(10);
assert_eq!(dss.find(4), 4);
dss.union(4, 2);
assert_eq!(dss.find(4), 2);

fn len(&self) -> usize

Returns the number of elements in the dss, also referred to as its ‘length’.

Examples

use graph::prelude::*;

let dss = DisjointSetStruct::<usize>::new(3);
assert_eq!(dss.len(), 3);

fn compress(&self)

Compresses the DSS so that each id stores its root set id.

impl<NI: Idx> Send for DisjointSetStruct<NI>

impl<NI: Idx> Sync for DisjointSetStruct<NI>