JGraph
v5.13.0.0


com.jgraph.algebra
Class JGraphUnionFind

java.lang.Object
  extended by com.jgraph.algebra.JGraphUnionFind

public class JGraphUnionFind
extends Object

Implements a union find structure that uses union by rank and path compression. The union by rank guarantees worst case find time of O(log N), while Tarjan shows that in combination with path compression (halving) the average time for an arbitrary sequence of m >= n operations is O(m*alpha(m,n)), where alpha is the inverse of the Ackermann function, defined as follows: alpha(m,n) = min{i >= 1 | A(i, floor(m/n)) > log n} for m >= n >= 1 Which yields almost constant time for each individual operation.


Nested Class Summary
 class JGraphUnionFind.Node
          A class that defines the identity of a set.
 
Field Summary
protected  Map nodes
          Maps from elements to nodes
 
Constructor Summary
JGraphUnionFind(Object[] elements)
          Constructs a union find structure and initializes it with the specified elements.
 
Method Summary
 boolean differ(Object a, Object b)
          Returns true if element a and element b are not in the same set.
 JGraphUnionFind.Node find(JGraphUnionFind.Node node)
          Returns the set that contains node.
 JGraphUnionFind.Node getNode(Object element)
          Returns the node that represents element.
 void union(JGraphUnionFind.Node a, JGraphUnionFind.Node b)
          Unifies the sets a and b in constant time using a union by rank on the tree size.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

nodes

protected Map nodes
Maps from elements to nodes

Constructor Detail

JGraphUnionFind

public JGraphUnionFind(Object[] elements)
Constructs a union find structure and initializes it with the specified elements.

Parameters:
elements -
Method Detail

getNode

public JGraphUnionFind.Node getNode(Object element)
Returns the node that represents element.


find

public JGraphUnionFind.Node find(JGraphUnionFind.Node node)
Returns the set that contains node. This implementation provides path compression by halving.


union

public void union(JGraphUnionFind.Node a,
                  JGraphUnionFind.Node b)
Unifies the sets a and b in constant time using a union by rank on the tree size.


differ

public boolean differ(Object a,
                      Object b)
Returns true if element a and element b are not in the same set. This uses getNode and then find to determine the elements set.

Parameters:
a - the first element to compare
b - the second element to compare
Returns:
Returns true if a and b are in the same set
See Also:
getNode(Object)

JGraph
v5.13.0.0


Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.