Class DisjointSets


  • public class DisjointSets
    extends java.lang.Object
    A data structure that represents a partition of a set into disjoint subsets, and allows merging subsets. Set items are represented by integer indices (which will typically be an index into an array of the objects actually being partitioned). Initially each item is in its own subset. Client code can merge subsets of items as required for the algorithm being performed (e.g. set partitioning or clustering). The current partitioning can be computed at any time, and subset items accessed using the DisjointSets.Subsets accessor.

    See the Wikipedia article on disjoint set data structures.

    Author:
    Martin Davis
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      class  DisjointSets.Subsets
      A representation of a partition of a set of items into disjoint subsets.
    • Constructor Summary

      Constructors 
      Constructor Description
      DisjointSets​(int size)
      Creates a new set containing a given number of items.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean isInSameSubset​(int i, int j)
      Tests if two items are in the same subset.
      void merge​(int i, int j)
      Merges two subsets containing the given items.
      DisjointSets.Subsets subsets()
      Gets a representation of the current partitioning.
      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • DisjointSets

        public DisjointSets​(int size)
        Creates a new set containing a given number of items.
        Parameters:
        size - the number of items contained in the set
    • Method Detail

      • isInSameSubset

        public boolean isInSameSubset​(int i,
                                      int j)
        Tests if two items are in the same subset.
        Parameters:
        i - an item index
        j - another item index
        Returns:
        true if items are in the same subset
      • merge

        public void merge​(int i,
                          int j)
        Merges two subsets containing the given items. Note that the items do not have to be the roots of their respective subsets. If the items are in the same subset the partitioning does not change.
        Parameters:
        i - an item index
        j - another item index
      • subsets

        public DisjointSets.Subsets subsets()
        Gets a representation of the current partitioning. This creates a snapshot of the partitioning; the set can be merged further after this call.
        Returns:
        an representation of the current subset partitioning.