jjil.algorithm
Class EquivalenceClass

java.lang.Object
  jjil.algorithm.EquivalenceClass

public class EquivalenceClass
extends java.lang.Object

EquivalenceClass implements equivalence classes using the efficient union-find algorithm whose complexity grows as the inverse Ackermann's function.

The code here is based on a Wikipedia article en.wikipedia.org/wiki/Connected_Component_Labeling
new EquivalenceClass(int nLabel) creates a new equivalence class with the given label. Note: nLabel must be unique to calls to the constructor.
e.find() returns the equivalence class for class e.
e.union(f) unions class e and class f.
e.getLabel() returns the integer label for e. e.getLabel() == f.getLabel() iff e and f are in the same equivalence class.

Author:

webb

Constructor Summary

EquivalenceClass()
Create a new set

Method Summary

EquivalenceClass	find() Look up the equivalence class for this set.
int	getLabel() Returns the unique label for this equivalence class.
static void	reset() Must be called once when a new set of equivalence classes is to be defined.
void	union(EquivalenceClass y) Unifies this class with another class.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EquivalenceClass

public EquivalenceClass()

Create a new set

Method Detail

find

public EquivalenceClass find()

Look up the equivalence class for this set.

Returns:

this set's equivalence class.

getLabel

public int getLabel()

Returns the unique label for this equivalence class.

Returns:

this equivalence class's label.

reset

public static void reset()

Must be called once when a new set of equivalence classes is to be defined.

union

public void union(EquivalenceClass y)

Unifies this class with another class. After this operation this and y will be in the same equivalence class.

Parameters:

y - the class to unify with.