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(\alpha(n))$ per operation where $\alpha$ is the inverse Ackermann function. UnionFind uses the hashCode and equals method of the elements it operates on.

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

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