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.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 Map |
nodes
Maps from elements to nodes
|
Constructor and Description |
---|
JGraphUnionFind(Object[] elements)
Constructs a union find structure and initializes it with the specified
elements.
|
Modifier and Type | Method and Description |
---|---|
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. |
protected Map nodes
public JGraphUnionFind(Object[] elements)
elements
- public JGraphUnionFind.Node getNode(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(Object a, Object b)
a
- the first element to compareb
- the second element to comparegetNode(Object)
Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.