TUM CCSM Commons

edu.tum.cs.commons.algo
Class UnionFind

java.lang.Object
  extended by edu.tum.cs.commons.collections.ManagedIntArray
      extended by 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.


TUM CCSM Commons

TUM CCSM Commons - 2.7