Struct petgraph::unionfind::UnionFind [] [src]

pub struct UnionFind<K> { /* 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
[src]

[src]

Create a new UnionFind of n disjoint sets.

[src]

Return the representative for x.

Panics if x is out of bounds.

[src]

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.

[src]

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.

[src]

Return a vector mapping each element to its representative.

Trait Implementations

impl<K: Debug> Debug for UnionFind<K>
[src]

[src]

Formats the value using the given formatter. Read more

impl<K: Clone> Clone for UnionFind<K>
[src]

[src]

Returns a copy of the value. Read more

1.0.0
[src]

Performs copy-assignment from source. Read more