edu.tum.cs.commons.algo
Class UnionFind

java.lang.Object
  edu.tum.cs.commons.collections.ManagedIntArray
      edu.tum.cs.commons.algo.UnionFind

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.

Version:

$Rev: 26283 $

Author:

hummelb, $Author: juergens $

Rating:

GREEN Hash: CF81A002CA0755AAD2BB6B1A6C75BA03

Field Summary

Fields inherited from class edu.tum.cs.commons.collections.ManagedIntArray

array, size

Constructor Summary

UnionFind()

Method Summary

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 edu.tum.cs.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()

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.