com.mxgraph.analysis

## Class mxUnionFind

- java.lang.Object
- - com.mxgraph.analysis.mxUnionFind

-     public class mxUnionFind
      extends java.lang.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

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `class` | `mxUnionFind.Node` A class that defines the identity of a set.

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected java.util.Map<java.lang.Object,mxUnionFind.Node>` | `nodes` Maps from elements to nodes

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `mxUnionFind(java.lang.Object[] elements)` Constructs a union find structure and initializes it with the specified elements.

  - ### Method Summary

    Methods
    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.
    `mxUnionFind.Node` | `find(mxUnionFind.Node node)` Returns the set that contains `node`.
    `mxUnionFind.Node` | `getNode(java.lang.Object element)` Returns the node that represents element.
    `void` | `union(mxUnionFind.Node a, mxUnionFind.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 java.util.Map<java.lang.Object,mxUnionFind.Node> nodes

      Maps from elements to nodes

  - ### Constructor Detail

    - #### mxUnionFind

          public mxUnionFind(java.lang.Object[] elements)

      Constructs a union find structure and initializes it with the specified elements.
      Parameters:
        `elements` -

  - ### Method Detail

    - #### getNode

          public mxUnionFind.Node getNode(java.lang.Object element)

      Returns the node that represents element.

    - #### find

          public mxUnionFind.Node find(mxUnionFind.Node node)

      Returns the set that contains `node`. This implementation provides path compression by halving.

    - #### union

          public void union(mxUnionFind.Node a,
                   mxUnionFind.Node b)

      Unifies the sets `a` and `b` in constant time using a union by rank on the tree size.

    - #### differ

          public boolean differ(java.lang.Object a,
                       java.lang.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)`

Copyright (c) 2010 Gaudenz Alder. All rights reserved.