Package org.jgrapht.alg.util
Class UnionFind<T>
- java.lang.Object
-
- org.jgrapht.alg.util.UnionFind<T>
-
- Type Parameters:
T
- element type
public class UnionFind<T> extends java.lang.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(a(n)) per operation where a is the inverse Ackermann function. UnionFind uses the hashCode and equals method of the elements it operates on.- Since:
- Feb 10, 2010
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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 java.util.Map<T,T>
getParentMap()
protected java.util.Map<T,java.lang.Integer>
getRankMap()
void
union(T element1, T element2)
Merges the sets which contain element1 and element2.
-
-
-
Constructor Detail
-
UnionFind
public UnionFind(java.util.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
-
addElement
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 java.util.Map<T,T> getParentMap()
- Returns:
- map from element to parent element
-
getRankMap
protected java.util.Map<T,java.lang.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.
-
-