Template Class GenericUnionFind¶

Class Documentation¶

template<IntegralValue IndexType>
class GenericUnionFind¶

Implements the Union Find data structure to maintain disjoint sets efficiently. Uses path compression and union by rank to achieve running time linear in the number of elements times the inverse Ackermann function.

Public Functions

inline GenericUnionFind(IndexType max_element)¶

Create a new set representation with not more than max_element elements. Initially every element is in its own set.

Parameters:

max_element – maximum number of elements

inline void allToSingletons()¶

Assigns every element to a singleton set. Set id is equal to element id.

inline IndexType find(IndexType u)¶

Find the representative to element @u

Parameters:

u – element

Returns:

representative of set containing @u

inline void merge(IndexType u, IndexType v)¶

Merge the two sets contain @u and @v

Parameters:

• u – element u

• v – element v

inline GenericPartition<IndexType> toPartition()¶

Convert the Union Find data structure to a Partition

Returns:

Partition equivalent to the union find data structure