tuffy.util
Class UnionFind<E>

java.lang.Object
  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>

Field Summary

private java.util.HashMap<E,UnionFind.Record<E>>	map
private int	nClusters
private java.util.ArrayList<UnionFind.Record<E>>	records

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

Field Detail

records

private java.util.ArrayList<UnionFind.Record<E>> records

map

private java.util.HashMap<E,UnionFind.Record<E>> map

nClusters

private int nClusters

Constructor Detail

UnionFind

public UnionFind()

Method Detail

getNumClusters

public int getNumClusters()

getRoots

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

makeUnionFind

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

makeUnionFind

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

addSingleton

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

getRecords

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

unionByValue

public E unionByValue(E xx,
                      E yy)

union

public E union(E xx,
               E yy)

unionWithOrder

public E unionWithOrder(E xx,
                        E yy)

clusterSize

public int clusterSize(E x)

clusterWeight

public double clusterWeight(E x)

getPartitionMap

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

getRoot

public E getRoot(E x)

find

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

sameSet

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