Struct petgraph::unionfind::UnionFind [−][src]
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
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.
Returns true
if the given elements belong to the same set, and returns
false
otherwise.
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.
Return a vector mapping each element to its representative.
Trait Implementations
Auto Trait Implementations
impl<K> RefUnwindSafe for UnionFind<K> where
K: RefUnwindSafe,
impl<K> UnwindSafe for UnionFind<K> where
K: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more