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 and Description
DisjointSetForest(int numberOfElements) Initialize a disjoint set forest with a number of elements.

Method Summary

Methods

Modifier and Type	Method and 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 Detail

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 Detail

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