com.jgraph.algebra
public class JGraphUnionFind extends Object
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. |
Parameters: elements
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
node
. This implementation
provides path compression by halving.a
and b
in constant time
using a union by rank on the tree size.