Package com.mxgraph.analysis
Class mxUnionFind
java.lang.Object
com.mxgraph.analysis.mxUnionFind
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
Nested ClassesModifier and TypeClassDescriptionclass
A class that defines the identity of a set. -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected Map
<Object, mxUnionFind.Node> Maps from elements to nodes -
Constructor Summary
ConstructorsConstructorDescriptionmxUnionFind
(Object[] elements) Constructs a union find structure and initializes it with the specified elements. -
Method Summary
Modifier and TypeMethodDescriptionboolean
Returns true if element a and element b are not in the same set.find
(mxUnionFind.Node node) Returns the set that containsnode
.Returns the node that represents element.void
Unifies the setsa
andb
in constant time using a union by rank on the tree size.
-
Field Details
-
nodes
Maps from elements to nodes
-
-
Constructor Details
-
mxUnionFind
Constructs a union find structure and initializes it with the specified elements.- Parameters:
elements
-
-
-
Method Details
-
getNode
Returns the node that represents element. -
find
Returns the set that containsnode
. This implementation provides path compression by halving. -
union
Unifies the setsa
andb
in constant time using a union by rank on the tree size. -
differ
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:
-