|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.jgrapht.alg.util.UnionFind<T>
public class UnionFind<T>
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.
Constructor Summary | |
---|---|
UnionFind(java.util.Set<T> elements)
Creates a UnionFind instance with all of the elements of elements in seperate sets. |
Method Summary | |
---|---|
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. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public UnionFind(java.util.Set<T> elements)
Method Detail |
---|
public void addElement(T element)
element
- The element to add.protected java.util.Map<T,T> getParentMap()
protected java.util.Map<T,java.lang.Integer> getRankMap()
public T find(T element)
element
- The element to find.
public void union(T element1, T element2)
element1
- The first element to union.element2
- The second element to union.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |