Package org.openscience.cdk.group

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[][]
    getSets()
    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.
    String
    toString()
     

    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