Struct red_union_find::UF

pub struct UF<I: Copy> { /* fields omitted */ }

Implements union-find

The UF structure efficiently represents a disjoint set data structure.

The standard rust unsigned primitive types (u8, u16, u32, u64, u128, and usize) make fine index types. You probably should use the smallest type that meets your needs.

UF can be viewed in a lattice. UF::new_reflexive() is the global infimum, and the result of joining all elements with all other elements into one big equiovalence set is the global supremum. equivalence_intersection() is the lattice gcd, and equivalence_union() is the lattice lcm.

Implementations

impl<I> UF<I> where
    I: Into<usize> + Copy + FromPrimitive, 

pub fn new_reflexive(size: I) -> Self

Creates a minimal reflexive UF structure.

Each index i is the sole memeber of its own equivalence set.

pub fn max(&self) -> I

Returns the element beyond the largest represented in ths UF.

pub fn len(&self) -> usize

Number of indices in this UF

pub fn find(&self, i: I) -> I

Returns representative with minimum index from i's equivalence set.

This method purports to immutably use &self, but it really uses interior mutability to implement path-compression in the safe, traditional way. Almost every other method on UF delegates to find, so they are all lying too. The data structure may be physically changing, doing path compression, but these changes don't logically change the outcome of any API calls.

Performance

If you perform n find() operations on a UF with length len(), then these operations will take O(n + len()) operations. So the performance is amortized O(1).

pub fn union(&mut self, i: I, j: I)

Perform union of two indices

Since UF uses interior mutability, the mut attribute here is not strictly necessary. But it communicates to the user that the data structure is logically changing, so it's a worthwhiile part of the API.

Performance

Each call to union performs two find() calls and additionally does O(1) work.

pub fn same_set(&self, i: I, j: I) -> bool

Retrns true if i and j are in the same equivalence set.

pub fn equivalence_union(a: &Self, b: &Self) -> Self

Creates a new UF that represents the union of the two given equivalence relations.

let c = UF::equivalence_union(&a, &b). Then for all i and j, c.same_set(i,j) == a.same_set(i,j) || b.same_set(i,j).

This operation is the lattice infimum over UF.

Performance

O(len())

pub fn equivalence_intersection(a: &Self, b: &Self) -> Self

Creates a new UF that represents the intersection of the two given equivalence relations.

let c = UF::equivalence_intersection(&a, &b). Then for all i and j, c.same_set(i,j) == a.same_set(i,j) && b.same_set(i,j).

This operation is the lattice supremum over UF.

You could also say this function returns the maximal mutual common ancestor of its arguments. No sequence of union() operations will transform a or b into c, there are sequences of union() operations that will transform c into either a or b, and a minimal sequence of union() operations for transforming c to a will have no entries in common with a minimal sequence from c to b.

Performance

I have only been able to prove that the performance is somewhere between O(len()) and O(len()^2). But it seems pretty fast.

If either a or b is mostly pure-reflexive or mostly one big equivalence set, or if a and b are very similar (each of them are a short number of unions away from their common ancestor), then the performance is almost linear.

Creating the result can't be done in less than O(len()) performace. The inner loop that steps through the cycles can't do more than O(len()^2) operations since it won't compare the same two elements twice.

The worst case operation seems to be when there are large sets in both argument UFs, but the intersection has no non-reflexive elements. Imagine two UF's representing the equivalence classes of two prime modular fields, based on primes p1 and p2. Then for large len() (larger than p1*p2), this operation will take about O(len()*(p1+p2)) operations.

pub fn as_permutation(&self) -> Vec<I>

Creates permutation version of a UF

Each equivalence set corresponds to a cycle. Every link in a cycle points downward, except for the smallest which points at the largest element in the cycle.

This representation can be used to do neat algorithmic things with an equivalence class.

pub fn leaders<'a>(&'a self) -> LeadersIter<'a, I>

Returns an iterator over group leader indexes

Trait Implementations

impl<I: Clone + Copy> Clone for UF<I>

pub fn clone(&self) -> UF<I>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<I: Debug + Copy> Debug for UF<I>

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<I> Eq for UF<I> where
    I: Into<usize> + Copy + FromPrimitive + Eq, 

impl<I> PartialEq<UF<I>> for UF<I> where
    I: Into<usize> + Copy + FromPrimitive + PartialEq, 

pub fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.