Struct UnionFind

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

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 const fn new_empty() -> Self

Create a new UnionFind with no elements.

pub fn len(&self) -> usize

Returns the number of elements in the union-find data-structure.

pub fn is_empty(&self) -> bool

Returns true if there are no elements in the union-find data-structure.

pub fn new_set(&mut self) -> K

Adds a new disjoint set and returns the index of the new set.

The new disjoint set is always added to the end, so the returned index is the same as the number of elements before calling this function.

Time Complexity Takes amortized O(1) time.

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

Return the representative for x.

Panics if x is out of bounds.

pub fn try_find(&self, x: K) -> Option<K>

Return the representative for x or None 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 try_find_mut(&mut self, x: K) -> Option<K>

Return the representative for x or None if x is out of bounds.

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

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

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

Panics if x or y is out of bounds.

pub fn try_equiv(&self, x: K, y: K) -> Result<bool, K>

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

If x or y are out of bounds, it returns Err with the first bad index found.

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 try_union(&mut self, x: K, y: K) -> Result<bool, K>

Unify the two sets containing x and y.

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

If x or y are out of bounds, it returns Err with first found bad index. But if x == y, the result will be Ok(false) even if the indexes go out of bounds.

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

Return a vector mapping each element to its representative.

impl<K> UnionFind<K>

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty UnionFind<K> with at least the specified capacity.

This acts similarly to Vec::with_capacity.

pub fn capacity(&self) -> usize

Returns the total number of elements the UnionFind can hold without reallocating.

Examples

use petgraph::unionfind::UnionFind;

let mut uf: UnionFind<u32> = UnionFind::with_capacity(10);
uf.new_set();
assert!(uf.capacity() >= 10);

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the given UnionFind<K>. The collection may reserve more space to speculatively avoid frequent reallocations. After calling reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.

Panics

Panics if the new capacity exceeds isize::MAX bytes.

Examples

use petgraph::unionfind::UnionFind;

let mut uf: UnionFind<u32> = UnionFind::new(3);
uf.reserve(10);
assert!(uf.capacity() >= 13);

pub fn reserve_exact(&mut self, additional: usize)

Reserves the minimum capacity for at least additional more elements to be inserted in the given UnionFind<K>. Unlike reserve, this will not deliberately over-allocate to speculatively avoid frequent allocations. After calling reserve_exact, capacity will be greater than or equal to self.len() + additional. Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore, capacity can not be relied upon to be precisely minimal. Prefer reserve if future insertions are expected.

Panics

Panics if the new capacity exceeds isize::MAX bytes.

Examples

use petgraph::unionfind::UnionFind;

let mut uf: UnionFind<u32> =  UnionFind::new_empty();
uf.reserve_exact(10);
assert!(uf.capacity() >= 10);

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>

Tries to reserve capacity for at least additional more elements to be inserted in the given UnionFind<K>. The collection may reserve more space to speculatively avoid frequent reallocations. After calling try_reserve, capacity will be greater than or equal to self.len() + additional if it returns Ok(()). Does nothing if capacity is already sufficient. This method preserves the contents even if an error occurs.

Errors

If the capacity overflows, or the allocator reports a failure, then an error is returned.

pub fn try_reserve_exact( &mut self, additional: usize, ) -> Result<(), TryReserveError>

Tries to reserve the minimum capacity for at least additional elements to be inserted in the given UnionFind<K>. Unlike try_reserve, this will not deliberately over-allocate to speculatively avoid frequent allocations. After calling try_reserve_exact, capacity will be greater than or equal to self.len() + additional if it returns Ok(()). Does nothing if the capacity is already sufficient.

Note that the allocator may give the collection more space than it requests. Therefore, capacity can not be relied upon to be precisely minimal. Prefer try_reserve if future insertions are expected.

Errors

If the capacity overflows, or the allocator reports a failure, then an error is returned.

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the UnionFind as much as possible.

The behavior of this method depends on the allocator, which may either shrink the collection in-place or reallocate. The resulting UnionFind might still have some excess capacity, just as is the case for with_capacity. See Vec::shrink_to_fit for more details, since the implementation is based on this method.

Examples

use petgraph::unionfind::UnionFind;

let mut uf: UnionFind<u32> = UnionFind::with_capacity(10);

for _ in 0..3 {
    uf.new_set();
}

assert!(uf.capacity() >= 10);
uf.shrink_to_fit();
assert!(uf.capacity() >= 3);

pub fn shrink_to(&mut self, min_capacity: usize)

Shrinks the capacity of the UnionFind with a lower bound.

The capacity will remain at least as large as both the length and the supplied value.

If the current capacity is less than the lower limit, this is a no-op.

Examples

use petgraph::unionfind::UnionFind;

let mut uf: UnionFind<u32> = UnionFind::with_capacity(10);

for _ in 0..3 {
    uf.new_set();
}

assert!(uf.capacity() >= 10);
uf.shrink_to(4);
assert!(uf.capacity() >= 4);
uf.shrink_to(0);
assert!(uf.capacity() >= 3);

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.

impl<K> Default for UnionFind<K>

fn default() -> Self

Returns the “default value” for a type.