EDU.purdue.cs.bloat.util

Class UnionFind

java.lang.Object

EDU.purdue.cs.bloat.util.UnionFind

public class UnionFind
extends java.lang.Object

Represents the union-find data structure.

Sometimes we need to group elements into disjoint sets. Two important operations of these sets are finding the set that contains a given element ("find") and uniting two sets ("union"). UnionFind provides an efficient implementation of a data structure that support these operations on disjoint sets of integers.

Each disjoint set is represented by a tree consisting of Nodes. (This Node is a class local to UnionFind and should not be confused with tree.Node.) Each Node knows its parent and child and has a rank associated with it. The parent node is always the root node of the set tree. A Node's rank is essentially the height of the (sub)tree rooted by that node. When the union of two trees is formed, the root with the smaller rank is made to point to the root with the larger rank. Naturally, each Node has an integer "value" associated with it.

A good description of union-find can be found in [Cormen, et. al. 1990].

Constructor Summary

Constructors

Constructor and Description
UnionFind() Constructor.
UnionFind(int size) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
int	find(int a) Returns the integer value associated with the first Node in a set.
EDU.purdue.cs.bloat.util.UnionFind.Node	findNode(int a) Searches the disjoint sets for a given integer.
boolean	isEquiv(int a, int b) Returns true if a and b are in the same set.
void	union(int a, int b) Combines the set that contains a with the set that contains b.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

UnionFind

public UnionFind()

Constructor.

UnionFind

public UnionFind(int size)

Constructor. Make a UnionFind with a given number of disjoint sets.

Method Detail

findNode

public EDU.purdue.cs.bloat.util.UnionFind.Node findNode(int a)

Searches the disjoint sets for a given integer. Returns the set containing the integer a. Sets are represented by a local class Node.

find

public int find(int a)

Returns the integer value associated with the first Node in a set.

isEquiv

public boolean isEquiv(int a,
              int b)

Returns true if a and b are in the same set.

union

public void union(int a,
         int b)

Combines the set that contains a with the set that contains b.