

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object jpaul.DataStructs.UnionFind<E>
public class UnionFind<E>
UnionFind
is a datastructure for performing
unification and lookup operations. It uses the path compression
and unionbyrank 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* slowlygrowing
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 lookup operation
(find(E)
) finds the representative of the equivalence class
of its argument, i.e., one of the elements from that equivalence
class.
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 unionfind 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 humanreadable 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 

public UnionFind()
UnionFind
.
Method Detail 

public E union(E e1, E e2)
e1
and e2
and
returns the representative of the resulting equivalence class.
public E find(E e)
e
.
public boolean areUnified(E e1, E e2)
e1
and
e2
are unified in this unionfind structure.
public boolean unUnified(E e)
e
has not been
unified yet with any DIFFERENT element. Complexity: O(1).
public java.util.Collection<java.util.Set<E>> allNonTrivialEquivalenceClasses()
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.
public java.util.Set<E> equivalenceClass(E e)
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!
public java.util.Set<E> allKnownElements()
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.
public java.lang.String toString()
toString
in class java.lang.Object


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 