org.jgrapht.alg.util
Class UnionFind<T>

java.lang.Object
  extended by org.jgrapht.alg.util.UnionFind<T>

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
Author:
Tom Conerly

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

UnionFind

public UnionFind(java.util.Set<T> elements)
Creates a UnionFind instance with all of the elements of elements in seperate sets.

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.

union

public void union(T element1,
                  T element2)
Merges the sets which contain element1 and element2.

Parameters:
element1 - The first element to union.
element2 - The second element to union.