tuffy.util
Class UnionFind<E>

java.lang.Object
  extended by tuffy.util.UnionFind<E>

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

Union-Find Data structure. By calling the makeUnionFind(S) a one element set is made for every object s contained in S Objects are stored within Records which are put in trees. A Set can be recognised by a toplevel record (with a parent pointing to null) This not a general "Set handling" class, but made for being used with for example Kruskal's Algortihm. See http://en.wikipedia.org/wiki/Disjoint-set_data_structure for more info! ------------------------------------- Implements makeUnionFind(S) in O(n), Union in O(log n), or O(1) if you a record representing a set, and find(u) called n times yieald an amortized running time of per calling of O(a(n)) ~= O(1).


Nested Class Summary
 class UnionFind.Record<E>
           
 
Constructor Summary
UnionFind()
           
 
Method Summary
 void addSingleton(E node, java.lang.Double wts)
           
 int clusterSize(E x)
           
 double clusterWeight(E x)
           
 UnionFind.Record<E> find(UnionFind.Record<E> rec)
           
 int getNumClusters()
           
 java.util.HashMap<E,E> getPartitionMap()
           
 java.util.ArrayList<UnionFind.Record<E>> getRecords()
           
 E getRoot(E x)
           
 java.util.HashSet<E> getRoots()
           
 void makeUnionFind(java.util.List<E> Set)
           
 void makeUnionFind(java.util.List<E> Set, java.util.HashMap<E,java.lang.Double> wts)
           
 boolean sameSet(UnionFind.Record<E> r1, UnionFind.Record<E> r2)
           
 E union(E xx, E yy)
           
 E unionByValue(E xx, E yy)
           
 E unionWithOrder(E xx, E yy)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

UnionFind

public UnionFind()
Method Detail

addSingleton

public void addSingleton(E node,
                         java.lang.Double wts)

clusterSize

public int clusterSize(E x)

clusterWeight

public double clusterWeight(E x)

find

public UnionFind.Record<E> find(UnionFind.Record<E> rec)

getNumClusters

public int getNumClusters()

getPartitionMap

public java.util.HashMap<E,E> getPartitionMap()

getRecords

public java.util.ArrayList<UnionFind.Record<E>> getRecords()

getRoot

public E getRoot(E x)

getRoots

public java.util.HashSet<E> getRoots()

makeUnionFind

public void makeUnionFind(java.util.List<E> Set)

makeUnionFind

public void makeUnionFind(java.util.List<E> Set,
                          java.util.HashMap<E,java.lang.Double> wts)

sameSet

public boolean sameSet(UnionFind.Record<E> r1,
                       UnionFind.Record<E> r2)

union

public E union(E xx,
               E yy)

unionByValue

public E unionByValue(E xx,
                      E yy)

unionWithOrder

public E unionWithOrder(E xx,
                        E yy)