scale.common
Class DisjointSet

java.lang.Object
  scale.common.DisjointSet

Direct Known Subclasses:

ECR

public class DisjointSet
extends java.lang.Object

A class which implements the data structure for Disjoint Sets.

$Id: DisjointSet.java,v 1.22 2005-03-24 13:57:13 burrill Exp $

Copyright 2008 by the Scale Compiler Group,
Department of Computer Science
University of Massachusetts,
Amherst MA. 01003, USA
All Rights Reserved.

The disjoint-set data structure was introduced by Tarjan for performing very quick find-union operations. A disjoint-set data structure maintains a collection S = {S1,S2,...,Sk} of disjoint dynamic sets. Each set is identified by a representative, which is some member of the set.

We implement the fast version which represents the sets as trees and uses path compression and union by rank to achieve good performance. The worst case running time is essentially linear w.r.t the total number of operations (actually it is the total no. of operations times the inverse of Ackermann's function).

Disjoint-sets are discussed in the book Data Structures and Network Algorithms by Tarjan. They are also described in Chapter 22 of Introduction to Algorithms by Cormen et. al. (aka, CLR).

Note that the list of elements in the disjoint set is only valid for the representative element. We only maintain the list of elements when the set represents more than one value. We do this to save space because many sets will only represent a single element. Thus, the code is a little difficult to read because we try to only create the vector structure when absolutly necessary.

Constructor Summary

DisjointSet()
Create a new disjoint set whose only member is this element.

Method Summary

void	addElements(Vector<java.lang.Object> v) Add the list of elements reprensented by this disjoint set to the vector.
boolean	equivalent(DisjointSet obj) Two disjoint sets are equivalent if they have the same representative element.
DisjointSet	find() Return a pointer to the representative of this set.
java.lang.Object	getElement(int i) Return the i-th element of the set.
java.util.Enumeration<java.lang.Object>	getElements() Return the list of elements reprensented by this disjoint set.
protected boolean	isRepresentative() Returns true if this is the element that is the representative of the set (i.e., the parent of the tree that maintains all the elements of this set).
int	size() Return the number of elements represented by this disjoint set.
DisjointSet	union(DisjointSet y) Combine this dynamic set with another.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjointSet

public DisjointSet()

Create a new disjoint set whose only member is this element.

Method Detail

union

public DisjointSet union(DisjointSet y)

Combine this dynamic set with another. We return the element that is the representative element in the combined set.

Parameters:

y - a member of (another) disjoint set.

Returns:

the representative object of the unioned set.

find

public DisjointSet find()

Return a pointer to the representative of this set.

Returns:

the representative of this set.

isRepresentative

protected boolean isRepresentative()

Returns true if this is the element that is the representative of the set (i.e., the parent of the tree that maintains all the elements of this set).

Returns:

true if this is the representative.

size

public int size()

Return the number of elements represented by this disjoint set. We look at the representative element to find the total.

getElement

public java.lang.Object getElement(int i)

Return the i-th element of the set.

getElements

public java.util.Enumeration<java.lang.Object> getElements()

Return the list of elements reprensented by this disjoint set. We look at the representative element to get the list.

addElements

public void addElements(Vector<java.lang.Object> v)

Add the list of elements reprensented by this disjoint set to the vector. We look at the representative element to get the list.

equivalent

public boolean equivalent(DisjointSet obj)

Two disjoint sets are equivalent if they have the same representative element.

Parameters:

obj - the object we check equality with

Returns:

true if the objects are in the same disjoint set.