Class DisjointSets


  • public class DisjointSets
    extends 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
    • 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.