org.jgrapht.alg.util

## Class UnionFind<T>

• Type Parameters:
T - element type

public class UnionFind<T>
extends Object
An implementation of Union Find data structure. Union Find is a disjoint-set data structure. It supports two operations: finding the set a specific element is in, and merging two sets. The implementation uses union by rank and path compression to achieve an amortized cost of $O(\alpha(n))$ per operation where $\alpha$ is the inverse Ackermann function. UnionFind uses the hashCode and equals method of the elements it operates on.
Since:
Feb 10, 2010
Author:
Tom Conerly
• ### Constructor Summary

Constructors
Constructor and Description
UnionFind(Set<T> elements)
Creates a UnionFind instance with all the elements in separate sets.
• ### Method Summary

All Methods
Modifier and Type Method and Description
void addElement(T element)
Adds a new element to the data structure in its own set.
T find(T element)
Returns the representative element of the set that element is in.
protected Map<T,T> getParentMap()
protected Map<T,Integer> getRankMap()
boolean inSameSet(T element1, T element2)
Tests whether two elements are contained in the same set.
int numberOfSets()
Returns the number of sets.
void reset()
Resets the UnionFind data structure: each element is placed in its own singleton set.
int size()
Returns the total number of elements in this data structure.
String toString()
Returns a string representation of this data structure.
void union(T element1, T element2)
Merges the sets which contain element1 and element2.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
• ### Constructor Detail

• #### UnionFind

public UnionFind(Set<T> elements)
Creates a UnionFind instance with all the elements in separate sets.
Parameters:
elements - the initial elements to include (each element in a singleton set).
• ### Method Detail

public void addElement(T element)
Adds a new element to the data structure in its own set.
Parameters:
element - The element to add.
• #### getParentMap

protected Map<T,T> getParentMap()
Returns:
map from element to parent element
• #### getRankMap

protected Map<T,Integer> getRankMap()
Returns:
map from element to rank
• #### find

public T find(T element)
Returns the representative element of the set that element is in.
Parameters:
element - The element to find.
Returns:
The element representing the set the element is in.
• #### union

public void union(T element1,
T element2)
Merges the sets which contain element1 and element2. No guarantees are given as to which element becomes the representative of the resulting (merged) set: this can be either find(element1) or find(element2).
Parameters:
element1 - The first element to union.
element2 - The second element to union.
• #### inSameSet

public boolean inSameSet(T element1,
T element2)
Tests whether two elements are contained in the same set.
Parameters:
element1 - first element
element2 - second element
Returns:
true if element1 and element2 are contained in the same set, false otherwise.
• #### numberOfSets

public int numberOfSets()
Returns the number of sets. Initially, all items are in their own set. The smallest number of sets equals one.
Returns:
the number of sets
• #### size

public int size()
Returns the total number of elements in this data structure.
Returns:
the total number of elements in this data structure.
• #### reset

public void reset()
Resets the UnionFind data structure: each element is placed in its own singleton set.
• #### toString

public String toString()
Returns a string representation of this data structure. Each component is represented as $\left{v_i:v_1,v_2,v_3,...v_n\right}$, where $v_i$ is the representative of the set.
Overrides:
toString in class Object
Returns:
string representation of this data structure