Class DisjointSetForest

java.lang.Object
org.openscience.cdk.group.DisjointSetForest

public class DisjointSetForest extends Object
Implementation of a union-find data structure, largely copied from code due to Derrick Stolee.
Author:
maclean
Belongs to CDK module:
standard
Keywords:
union-find
  • Constructor Summary

    Constructors
    Constructor
    Description
    DisjointSetForest(int numberOfElements)
    Initialize a disjoint set forest with a number of elements.
  • Method Summary

    Modifier and Type
    Method
    Description
    int
    get(int i)
    Get the value of the forest at this index - note that this will not necessarily give the set for that element : use getSets() after union-ing elements.
    int
    getRoot(int element)
    Travel up the tree that this element is in, until the root of the set is found, and return that root.
    int[][]
    Retrieve the sets as 2D-array of ints.
    void
    makeUnion(int elementX, int elementY)
    Union these two elements - in other words, put them in the same set.
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Constructor Details

    • DisjointSetForest

      public DisjointSetForest(int numberOfElements)
      Initialize a disjoint set forest with a number of elements.
      Parameters:
      numberOfElements - the number of elements in the forest
  • Method Details

    • get

      public int get(int i)
      Get the value of the forest at this index - note that this will not necessarily give the set for that element : use getSets() after union-ing elements.
      Parameters:
      i - the index in the forest
      Returns:
      the value at this index
    • getRoot

      public int getRoot(int element)
      Travel up the tree that this element is in, until the root of the set is found, and return that root.
      Parameters:
      element - the starting point
      Returns:
      the root of the set containing element
    • makeUnion

      public void makeUnion(int elementX, int elementY)
      Union these two elements - in other words, put them in the same set.
      Parameters:
      elementX - an element
      elementY - an element
    • getSets

      public int[][] getSets()
      Retrieve the sets as 2D-array of ints.
      Returns:
      the sets
    • toString

      public String toString()
      Overrides:
      toString in class Object