org.conqat.lib.commons.algo

Class UnionFind

java.lang.Object

org.conqat.lib.commons.collections.ManagedIntArray

org.conqat.lib.commons.algo.UnionFind

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

UnionFindWithSize

public class UnionFind
extends ManagedIntArray

Implementation of a simple union find data structure. It implements the "partial path compression" heuristic but does not use "union by rank" but instead uses randomization.

Author:

hummelb

See Also:

Serialized Form

Field Summary

Fields inherited from class org.conqat.lib.commons.collections.ManagedIntArray

array, size

Constructor Summary

Constructors

Constructor and Description
UnionFind() Constructor using random merge order.
UnionFind(boolean noRandom) Constructor.

Method Summary

Modifier and Type	Method and Description
int	addElement() Adds a new element to this union find structure and returns its index.
protected void	connectToRepresentative(int element, int representative) Connects the given element (must also be representative) to the given representative.
int	find(int element) Finds and returns the representative for the given element.
void	union(int element1, int element2) Merges the classes in which element1 and element2 are, by giving them the same representative.

Methods inherited from class org.conqat.lib.commons.collections.ManagedIntArray

addArrayElement, addArrayElements

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFind

public UnionFind()

Constructor using random merge order.

UnionFind

public UnionFind(boolean noRandom)

Constructor.

Parameters:

noRandom - if this is set to true, randomized merging is disabled. In general, randomization should be used, as it prevents a linear time worst case (for each union). However, if the order of elements passed to the union method is already random (due to the underlying data) or the size of the union size set is very small, disabling randomization might cause a huge gain in performance.

Method Detail

find

public int find(int element)

Finds and returns the representative for the given element.

union

public void union(int element1,
                  int element2)

Merges the classes in which element1 and element2 are, by giving them the same representative.

connectToRepresentative

protected void connectToRepresentative(int element,
                                       int representative)

Connects the given element (must also be representative) to the given representative.

addElement

public int addElement()

Adds a new element to this union find structure and returns its index.