jpaul.DataStructs
Class UnionFind<E>

java.lang.Object
  jpaul.DataStructs.UnionFind<E>

All Implemented Interfaces:

java.io.Serializable

public class UnionFind<E>
extends java.lang.Object
implements java.io.Serializable

UnionFind is a datastructure for performing unification and lookup operations. It uses 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. The abstract state of the data structure at each moment is determined by the previously executed unifications (union(E, E)). Each element of the universe of discourse is part of exactly one equivalence class. Initially, each elements sits in its own equivalence class; each union(E, E) operation merges the equivalence classes for its arguments. Each look-up operation (find(E)) finds the representative of the equivalence class of its argument, i.e., one of the elements from that equivalence class.

Version:

$Id: UnionFind.java,v 1.9 2006/03/14 02:29:31 salcianu Exp $

Author:

C. Scott Ananian - cananian@alumni.princeton.edu, Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

Serialized Form

Constructor Summary

UnionFind()
Creates a UnionFind.

Method Summary

java.util.Set<E>	allKnownElements() Returns an unmodifiable set containing all elements that this UnionFind structure has knowledge about.
java.util.Collection<java.util.Set<E>>	allNonTrivialEquivalenceClasses() Returns an unmodifiable collection containing all equivalence classes with more than one element.
boolean	areUnified(E e1, E e2) Checks whether the elements e1 and e2 are unified in this union-find structure.
java.util.Set<E>	equivalenceClass(E e) Returns the equivalence class that element e is part of, as an unmodifiable set containing all elements from that class (including e).
E	find(E e) Returns the representative of the equivalence class of e.
java.lang.String	toString() Returns a human-readable representation of the UnionFind.
E	union(E e1, E e2) Unifies the elements e1 and e2 and returns the representative of the resulting equivalence class.
boolean	unUnified(E e) Returns true if the element e has not been unified yet with any DIFFERENT element.

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFind

public UnionFind()

Creates a UnionFind.

Method Detail

union

public E union(E e1,
               E e2)

Unifies the elements e1 and e2 and returns the representative of the resulting equivalence class.

find

public E find(E e)

Returns the representative of the equivalence class of e.

areUnified

public boolean areUnified(E e1,
                          E e2)

Checks whether the elements e1 and e2 are unified in this union-find structure.

unUnified

public boolean unUnified(E e)

Returns true if the element e has not been unified yet with any DIFFERENT element. Complexity: O(1).

allNonTrivialEquivalenceClasses

public java.util.Collection<java.util.Set<E>> allNonTrivialEquivalenceClasses()

Returns an unmodifiable collection containing all equivalence classes with more than one element. Each equivalence class is represented as an unmodifiable set that contains all elements from that class. The reason we return only equivalence classes with more than one element is that this structure does not know about the elements of your universe of discourse that have not been unified with anyone yet: it knows only about the elements that have been unified already.

This method is quite slow: its execution time is at least linear in the size of the underlying forest. Hence, it has a long, inconvenient name!

Note: The returned collection is in fact a set, but maintaining it as a (hash-)set, with the associated .equals on sets would be too expensive.

equivalenceClass

public java.util.Set<E> equivalenceClass(E e)

Returns the equivalence class that element e is part of, as an unmodifiable set containing all elements from that class (including e).

This method is quite slow: its execution time is at least linear in the size of the underlying forest!

allKnownElements

public java.util.Set<E> allKnownElements()

Returns an unmodifiable set containing all elements that this UnionFind structure has knowledge about. It is important to understand that this structure knows only the elements that it was asked to unify via calls to union; it doesn't know the other elements of the universe of discourse.

toString

public java.lang.String toString()

Returns a human-readable representation of the UnionFind.

Overrides:

toString in class java.lang.Object