Package org.openscience.cdk.group
Class DisjointSetForest
java.lang.Object
org.openscience.cdk.group.DisjointSetForest
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
ConstructorsConstructorDescriptionDisjointSetForest
(int numberOfElements) Initialize a disjoint set forest with a number of elements. -
Method Summary
Modifier and TypeMethodDescriptionint
get
(int i) Get the value of the forest at this index - note that this will not necessarily give the set for that element : usegetSets()
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.toString()
-
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 : usegetSets()
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 elementelementY
- an element
-
getSets
public int[][] getSets()Retrieve the sets as 2D-array of ints.- Returns:
- the sets
-
toString
-