com.tensegrity.generic.util
Class UnionFind

java.lang.Object
  com.tensegrity.generic.util.UnionFind

public class UnionFind

extends java.lang.Object

UnionFind manages a set of disjunct sets. These sets can be searched for a given element in O(log n) time. The union operation on two sets takes O(1). This datastructure is needed for Kruskal‘s algorithm and other graph algorithms. Also geometrical algorithms can make use of it sometimes.

Each set has one of its elements as the canonical element. It is undefined which element of the elements of a particular set happens to be the canonical element.

Version:

$Id: UnionFind.java,v 1.6 2003/08/06 16:33:33 AndreasEbbert Exp $

Author:

S. Rutz

Constructor Summary

UnionFind(int size)
Constructs a union find structure with size sets, each set having one element.

Method Summary

int	find(int e) Finds the canonical element for the given element.
int	numberOfSets() Returns the number of sets in the union-find structure.
void	union(int e, int f) Performs a union operation on two sets which are identified by their canonical element.

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFind

public UnionFind(int size)

Constructs a union find structure with size sets, each set having one element.

Parameters:

size - number of sets to construct initially.

Method Detail

union

public void union(int e,
                  int f)

Performs a union operation on two sets which are identified by their canonical element. One of the sets is chosen as the parent for the other depending on their sizes. This ensure logarithmically growing tree depth.

Parameters:

e - canonical element for set one

f - canonical element for set two

find

public int find(int e)

Finds the canonical element for the given element.

Parameters:

e - element to search for.

Returns:

canonical element for the passed in element.

numberOfSets

public int numberOfSets()

Returns the number of sets in the union-find structure.

Returns:

number of sets in the union-find structure.