disjoint-hash-set

A Rust implementation of a disjoint set / union-find data structure for incremental tracking of connected components identified by their hash.

Incorporates rank-based set joins and path compression to ensure the asymptotically optimal time complexity associated with union-find algorithms.

use disjoint_hash_set::DisjointHashSet;

let mut djhs = DisjointHashSet::new();
djhs.link("hello", "hi");
djhs.link("hello", "👋");
assert!(djhs.is_linked("hi", "👋"));

// `DisjointHashSet` can be built from an iterator of edges
let djhs = vec![("a", "b"), ("a", "c"), ("d", "e"), ("f", "f")]
    .into_iter()
    .collect::<DisjointHashSet<_>>();

// Consume djhs to iterate over each disjoint set
let sets = djhs.sets(); // looks like [{"a", "b", "c"}, {"d", "e"}, {"f"}]
assert_eq!(sets.count(), 3);

lib.rs:

A disjoint set / union-find data structure suitable for incremental tracking of connected component identified by their hash.

The total number of components does not need to be known in advance. Connections between components and the components themselves can be added as they are discovered.

Employs rank-based set joins and path compression resulting in the asymptotically optimal time complexity associated with union-find algorithms.

Examples

use disjoint_hash_set::DisjointHashSet;

let mut djhs = DisjointHashSet::new();
djhs.link("hello", "hi");
djhs.link("hello", "👋");
assert!(djhs.is_linked("hi", "👋"));

// `DisjointHashSet` can be built from an iterator of edges
let djhs = vec![("a", "b"), ("a", "c"), ("d", "e"), ("f", "f")]
    .into_iter()
    .collect::<DisjointHashSet<_>>();

// Consume djhs to iterate over each disjoint set
let sets = djhs.sets(); // looks like [{"a", "b", "c"}, {"d", "e"}, {"f"}]
assert_eq!(sets.count(), 3);