Package net.cscott.jutil

Class DisjointSet<E>

java.lang.Object
net.cscott.jutil.DisjointSet<E>
public class DisjointSet<E> extends Object
DisjointSet is an implementation of disjoint-set forests using the path compression and union-by-rank heuristics to achieve O(m * alpha(m, n)) runtime, where 'm' is the total number of operations, 'n' is the total number of elements in the set, and 'alpha' denotes the *extremely* slowly-growing inverse Ackermann function.
Author:
C. Scott Ananian <cananian@alumni.princeton.edu>
Tests:
{@link #union union()} merges the sets of two elements, and {@link #find find()} returns the representative of an element's set, which is the same for every element of the set: 
js> ds = new DisjointSet()
{}
js> ds.union("a", "b"); ds.union("c", "d"); ds.union("b", "c")
js> ds.find("a") == ds.find("d")
true
js> ds.find("e") // an element in no union is its own set
e
js> ds.find("e") == ds.find("a")
false

  • Constructor Summary

    Constructors
    Constructor
    Description
    DisjointSet()
    Creates a DisjointSet.

  • Method Summary

    Modifier and Type
    Method
    Description
    Map<E,E>
    asMap()
    Returns an unmodifiable Map view of the disjoint set, where every element is mapped to its canonical representative.
    boolean
    contains(Object o)
    Determines if there is a set of more than one element containing o.
    E
    find(E o)
    Returns the representative of the (unique) set containing o.
    String
    toString()
    Returns a human-readable representation of the DisjointSet.
    void
    union(E o1, E o2)
    Unites the dynamic sets that contain o1 and o2, say S1 and S2, into a new set that is the union of these two sets.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • DisjointSet

      public DisjointSet()
      Creates a DisjointSet.

  • Method Details

    • union

      public void union(E o1, E o2)
      Unites the dynamic sets that contain o1 and o2, say S1 and S2, into a new set that is the union of these two sets. The two sets are assumed to be disjoint prior to the operation. The representative of the resulting set is the representative of either S1 or S2; if both S1 and S2 were previously singletons, the representative of S1 union S2 is the representative of S2.

    • find

      public E find(E o)
      Returns the representative of the (unique) set containing o.

    • contains

      public boolean contains(Object o)
      Determines if there is a set of more than one element containing o.

    • asMap

      public Map<E,E> asMap()
      Returns an unmodifiable Map view of the disjoint set, where every element is mapped to its canonical representative.

    • toString

      public String toString()
      Returns a human-readable representation of the DisjointSet.
      Overrides:
      toString in class Object