net.cscott.jutil

Class DisjointSet<E>

java.lang.Object

net.cscott.jutil.DisjointSet<E>

public class DisjointSet<E>
extends java.lang.Object

DisjointSet is an implementation of disjoint-set forests using the path compression and union-by-rank heuristics to achieve O(m * alpha(m, n)) runtime, where 'm' is the total number of operations, 'n' is the total number of elements in the set, and 'alpha' denotes the *extremely* slowly-growing inverse Ackermann function.

Version:

$Id: DisjointSet.java,v 1.4 2006-10-30 19:58:05 cananian Exp $

Author:

C. Scott Ananian

Constructor Summary

Constructors

Constructor and Description
DisjointSet() Creates a DisjointSet.

Method Summary

Modifier and Type	Method and Description
java.util.Map<E,E>	asMap() Returns an unmodifiable Map view of the disjoint set, where every element is mapped to its canonical representative.
boolean	contains(java.lang.Object o) Determines if there is a set of more than one element containing o.
E	find(E o) Returns the representative of the (unique) set containing o.
static void	main(java.lang.String[] args) Self-test method.
java.lang.String	toString() Returns a human-readable representation of the DisjointSet.
void	union(E o1, E o2) Unites the dynamic sets that contain o1 and o2, say S1 and S2, into a new set that is the union of these two sets.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjointSet

public DisjointSet()

Creates a DisjointSet.

Method Detail

union

public void union(E o1,
                  E o2)

Unites the dynamic sets that contain o1 and o2, say S1 and S2, into a new set that is the union of these two sets. The two sets are assumed to be disjoint prior to the operation. The representative of the resulting set is the representative of either S1 or S2; if both S1 and S2 were previously singletons, the representative of S1 union S2 is the representative of S2.

find

public E find(E o)

Returns the representative of the (unique) set containing o.

contains

public boolean contains(java.lang.Object o)

Determines if there is a set of more than one element containing o.

asMap

public java.util.Map<E,E> asMap()

Returns an unmodifiable Map view of the disjoint set, where every element is mapped to its canonical representative.

toString

public java.lang.String toString()

Returns a human-readable representation of the DisjointSet.

Overrides:

toString in class java.lang.Object

main

public static void main(java.lang.String[] args)

Self-test method.