Struct petgraph::unionfind::UnionFind

pub struct UnionFind<K> {
    parent: Vec<K>,
    rank: Vec<u8>,
}

UnionFind<K> is a disjoint-set data structure. It tracks set membership of n elements indexed from 0 to n - 1. The scalar type is K which must be an unsigned integer type.

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Too awesome not to quote:

“The amortized time per operation is O(α(n)) where α(n) is the inverse of f(x) = A(x, x) with A being the extremely fast-growing Ackermann function.”

Fields

parent: Vec<K>

rank: Vec<u8>

Implementations

impl<K> UnionFind<K>

where K: IndexType,

pub fn new(n: usize) -> Self

Create a new UnionFind of n disjoint sets.

pub fn find(&self, x: K) -> K

Return the representative for x.

Panics if x is out of bounds.

pub fn find_mut(&mut self, x: K) -> K

Return the representative for x.

Write back the found representative, flattening the internal datastructure in the process and quicken future lookups.

Panics if x is out of bounds.

unsafe fn find_mut_recursive(&mut self, x: K) -> K

pub fn union(&mut self, x: K, y: K) -> bool

Unify the two sets containing x and y.

Return false if the sets were already the same, true if they were unified.

Panics if x or y is out of bounds.

pub fn into_labeling(self) -> Vec<K>

Return a vector mapping each element to its representative.

Trait Implementations

impl<K: Clone> Clone for UnionFind<K>

fn clone(&self) -> UnionFind<K>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug> Debug for UnionFind<K>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.