jBNC Toolbox

jbnc.graphs
Class DisjointSets

java.lang.Object
  extended byjbnc.graphs.DisjointSets

public class DisjointSets
extends java.lang.Object

Maintains a collection of disjoint sets.

Coremen TH, Leiserson CE, Rivest RL. Introduction to Algorithms . McGrow-Hill, 1990.

Since:
June 1, 1999
Author:
Jarek Sacha

Field Summary
protected  java.util.LinkedList sets
          List of disjoint sets.
 
Method Summary
 java.lang.Object findSet(java.lang.Object x)
          Returns a pointer to the representative of the (unique) set containing x .
static void main(java.lang.String[] argv)
          Test the class operation.
 void makeSet(java.lang.Object x)
          Create a new set whose only member (and thus representative) is pointed by x .
 void union(java.lang.Object x, java.lang.Object y)
          Unites the dynamic sets that contain x and y , say S x and Sy , into a new set that is the union of these sets.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

sets

protected java.util.LinkedList sets
List of disjoint sets.

Method Detail

main

public static void main(java.lang.String[] argv)
Test the class operation.

Parameters:
argv - Description of Parameter

makeSet

public void makeSet(java.lang.Object x)
             throws java.lang.Exception
Create a new set whose only member (and thus representative) is pointed by x . Since sets are disjoint, we require that x not already be in a set.

Parameters:
x - Description of Parameter
Throws:
java.lang.Exception - Description of Exception

union

public void union(java.lang.Object x,
                  java.lang.Object y)
           throws java.lang.Exception
Unites the dynamic sets that contain x and y , say S x and Sy , into a new set that is the union of these sets. The representative of the resulting set is some member of Sx U Sy . Original sets Sx and Sy are destroyed.

Parameters:
x - Description of Parameter
y - Description of Parameter
Throws:
java.lang.Exception - Description of Exception

findSet

public java.lang.Object findSet(java.lang.Object x)
Returns a pointer to the representative of the (unique) set containing x .

Parameters:
x - Description of Parameter
Returns:
Description of the Returned Value

SourceForge.net Logo