Struct petgraph::unionfind::UnionFind
[−]
[src]
pub struct UnionFind<K> {
// some fields omitted
}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.”
Methods
impl<K> UnionFind<K> where K: IndexType + Add<Output=K>
fn new(n: usize) -> Self
Create a new UnionFind of n disjoint sets.
fn find(&self, x: K) -> K
Return the representative for x.
Panics if x is out of bounds.
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.
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.
fn into_labeling(self) -> Vec<K>
Return a vector mapping each element to its representative.