public class JGraphUnionFind
extends java.lang.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.Modifier and Type | Class and Description |
---|---|
class |
JGraphUnionFind.Node
A class that defines the identity of a set.
|
Modifier and Type | Field and Description |
---|---|
protected java.util.Map |
nodes
Maps from elements to nodes
|
Constructor and Description |
---|
JGraphUnionFind(java.lang.Object[] elements)
Constructs a union find structure and initializes it with the specified
elements.
|
Modifier and Type | Method and Description |
---|---|
boolean |
differ(java.lang.Object a,
java.lang.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(java.lang.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. |
public JGraphUnionFind(java.lang.Object[] elements)
elements
- public JGraphUnionFind.Node getNode(java.lang.Object element)
public JGraphUnionFind.Node find(JGraphUnionFind.Node node)
node
. This implementation
provides path compression by halving.public void union(JGraphUnionFind.Node a, JGraphUnionFind.Node b)
a
and b
in constant time
using a union by rank on the tree size.public boolean differ(java.lang.Object a, java.lang.Object b)
a
- the first element to compareb
- the second element to comparegetNode(Object)
Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.