Struct union_find_rs::disjoint_sets::DisjointSets

pub struct DisjointSets<T> where
    T: Copy + Eq + Hash,  { /* fields omitted */ }

An implementation of a disjoint-set forest that supports the union-find algorithm.

This implementation uses union-by-rank as well as path-compression heuristics to improve the algorithmic complexity.

See the trait UnionFind, which this struct implements, to see the main operations that this struct supports.

Algorithmic Complexity

As mentioned before, this implementation uses union-by-rank as well as path-compression heuristics to improve the algorithmic complexity.

As noted in the Wikipedia article, this implies that a sequence of m calls to find_set, make_set and union requires O(mα(n)) time where α(n) is the inverse Ackermann function. For all practical purposes, you can think of each operation as being essentially O(1).

Accessing the Disjoint Sets

In order to allow easy access to the disjoint sets stored in the forest, this struct implements IntoIterator:

use union_find_rs::prelude::*;
use std::collections::HashSet;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.make_set(1).unwrap();
sets.make_set(4).unwrap();
sets.make_set(9).unwrap();

sets.union(&4, &9).unwrap();

// `into_iter` returns an iterator whose item is of type `HashSet<T>`
let as_vec: Vec<HashSet<usize>> = sets.into_iter().collect();

// there should be 2 disjoint sets, where one of them only contains `4` and the other one
// only contains `9`
assert_eq!(as_vec.len(), 2);
assert!(
    as_vec
        .iter()
        .any(|set| set == &vec![1].into_iter().collect::<HashSet<usize>>())
);
assert!(
    as_vec
        .iter()
        .any(|set| set == &vec![4, 9].into_iter().collect::<HashSet<usize>>())
);

References

This struct was implemented using ideas from the following:

1. Introduction to Algorithms
2. Disjoint-set data structure

Implementations

impl<T> DisjointSets<T> where
    T: Copy + Eq + Hash, 

pub fn new() -> Self

Creates an empty instance of DisjointSets.

Example

use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::new();

pub fn with_strategy(strategy: FindStrategy) -> Self

Creates an empty instance of DisjointSets with a specific strategy to be used by the find_set operation.

See FindStrategy.

Example

use union_find_rs::prelude::*;

let mut sets_1: DisjointSets<usize> = DisjointSets::with_strategy(FindStrategy::PathCompression);

let mut sets_2: DisjointSets<usize> = DisjointSets::with_strategy(FindStrategy::PathSplitting);

pub fn with_capacity_strategy(capacity: usize, strategy: FindStrategy) -> Self

Creates an empty instance of DisjointSets with a specific strategy to be used by the find_set operation.

See FindStrategy.

Example

use union_find_rs::prelude::*;

let mut sets_1: DisjointSets<usize> = DisjointSets::with_capacity_strategy(512, FindStrategy::PathCompression);

let mut sets_2: DisjointSets<usize> = DisjointSets::with_capacity_strategy(512, FindStrategy::PathSplitting);

pub fn with_capacity(capacity: usize) -> Self

Creates an empty instance of DisjointSets with the specified capacity.

The instance returned by this method will be able to hold at least capacity elements without reallocating. If capacity is 0, the hash map will not allocate.

Example

use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::with_capacity(64);

pub fn len(&self) -> usize

Returns the number of elements in this instance of DisjointSets.

Example

use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.make_set(9).unwrap();

assert_eq!(sets.len(), 1);

pub fn contains(&self, item: &T) -> bool

Returns true if this instance of DisjointSets contains item, false otherwise.

Example

use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.make_set(9).unwrap();

assert_eq!(sets.contains(&9), true);
assert_eq!(sets.contains(&7), false);

pub fn clear(&mut self)

Clears this DisjointSets, removing all data. Keeps the allocated memory for reuse.

Example

use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.make_set(9).unwrap();
assert_eq!(sets.len(), 1);

sets.clear();
assert_eq!(sets.len(), 0);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in this DisjointSets. May reserve more space to avoid frequent reallocations.

Panics

Panics if the new allocation size overflows usize.

Example

use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.reserve(16);

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of this DisjointSets as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.

Example

use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::with_capacity(100);

sets.make_set(4).unwrap();
sets.make_set(9).unwrap();
assert!(100 <= sets.capacity());

sets.shrink_to_fit();
assert!(2 <= sets.capacity());

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold without reallocating. This number is a lower bound; the HashMap<K, V> might be able to hold more, but is guaranteed to be able to hold at least this many.

Example

use union_find_rs::prelude::*;

let mut sets: DisjointSets<usize> = DisjointSets::with_capacity(100);

assert!(100 <= sets.capacity());

Trait Implementations

impl<T> IntoIterator for DisjointSets<T> where
    T: Copy + Eq + Hash, 

In order to allow easy access to the disjoint sets stored in the forest, this struct implements IntoIterator:

use union_find_rs::prelude::*;
use std::collections::HashSet;

let mut sets: DisjointSets<usize> = DisjointSets::new();

sets.make_set(1).unwrap();
sets.make_set(4).unwrap();
sets.make_set(9).unwrap();

sets.union(&4, &9).unwrap();

// `into_iter` returns an iterator whose item is of type `HashSet<T>`
let as_vec: Vec<HashSet<usize>> = sets.into_iter().collect();

// there should be 2 disjoint sets, where one of them only contains `4` and the other one
// only contains `9`
assert_eq!(as_vec.len(), 2);
assert!(as_vec
    .iter()
    .any(|set| set == &vec![1].into_iter().collect::<HashSet<usize>>()));
assert!(as_vec
    .iter()
    .any(|set| set == &vec![4, 9].into_iter().collect::<HashSet<usize>>()));

type Item = HashSet<T>

The type of the elements being iterated over.

type IntoIter = IntoIter<Self::Item>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> UnionFind<T> for DisjointSets<T> where
    T: Copy + Eq + Hash, 

fn make_set(&mut self, item: T) -> Result<()>

See UnionFind for an example.

fn union(&mut self, x: &T, y: &T) -> Result<()>

See UnionFind for an example.

fn find_set(&self, item: &T) -> Result<T>

See UnionFind for an example.