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 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

Constructors

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

Method Summary

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()
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(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 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.

Parameters:

element1 - The first element to union.

element2 - The second element to union.