Struct petgraph::unionfind::UnionFind

[+] Show declaration

pub struct UnionFind<K> { /* fields omitted */ }

[−] Expand description

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.”

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.

pub fn equiv(&self, x: K, y: K) -> bool[−]

Returns true if the given elements belong to the same set, and returns false otherwise.

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>[+]

[+] Show hidden undocumented items

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>[+]

[+] Show hidden undocumented items

fn fmt(&self, f: &mut Formatter) -> Result[−]

Formats the value using the given formatter.