Module org.jgrapht.core
Package org.jgrapht.alg.util

Class UnionFind<T>

java.lang.Object
org.jgrapht.alg.util.UnionFind<T>
Type Parameters:
T - element type
public class UnionFind<T>
extends java.lang.Object
An implementation of Union Find data structure. Union Find is a disjoint-set data structure. It supports two operations: finding the set a specific element is in, and merging two sets. The implementation uses union by rank and path compression to achieve an amortized cost of $O(\alpha(n))$ per operation where $\alpha$ is the inverse Ackermann function. UnionFind uses the hashCode and equals method of the elements it operates on.
Author:
Tom Conerly

  • Constructor Summary

    Constructors 
    Constructor Description
    UnionFind​(java.util.Set<T> elements)
    Creates a UnionFind instance with all the elements in separate sets.

  • Method Summary

    Modifier and Type Method Description
    void addElement​(T element)
    Adds a new element to the data structure in its own set.
    T find​(T element)
    Returns the representative element of the set that element is in.
    protected java.util.Map<T,​T> getParentMap()  
    protected java.util.Map<T,​java.lang.Integer> getRankMap()  
    boolean inSameSet​(T element1, T element2)
    Tests whether two elements are contained in the same set.
    int numberOfSets()
    Returns the number of sets.
    void reset()
    Resets the UnionFind data structure: each element is placed in its own singleton set.
    int size()
    Returns the total number of elements in this data structure.
    java.lang.String toString()
    Returns a string representation of this data structure.
    void union​(T element1, T element2)
    Merges the sets which contain element1 and element2.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • UnionFind

      public UnionFind​(java.util.Set<T> elements)
      Creates a UnionFind instance with all the elements in separate sets.
      Parameters:
      elements - the initial elements to include (each element in a singleton set).

  • Method Details

    • addElement

      public void addElement​(T element)
      Adds a new element to the data structure in its own set.
      Parameters:
      element - The element to add.

    • getParentMap

      protected java.util.Map<T,​T> getParentMap()
      Returns:
      map from element to parent element

    • getRankMap

      protected java.util.Map<T,​java.lang.Integer> getRankMap()
      Returns:
      map from element to rank

    • find

      public T find​(T element)
      Returns the representative element of the set that element is in.
      Parameters:
      element - The element to find.
      Returns:
      The element representing the set the element is in.

    • union

      public void union​(T element1, T element2)
      Merges the sets which contain element1 and element2. No guarantees are given as to which element becomes the representative of the resulting (merged) set: this can be either find(element1) or find(element2).
      Parameters:
      element1 - The first element to union.
      element2 - The second element to union.

    • inSameSet

      public boolean inSameSet​(T element1, T element2)
      Tests whether two elements are contained in the same set.
      Parameters:
      element1 - first element
      element2 - second element
      Returns:
      true if element1 and element2 are contained in the same set, false otherwise.

    • numberOfSets

      public int numberOfSets()
      Returns the number of sets. Initially, all items are in their own set. The smallest number of sets equals one.
      Returns:
      the number of sets

    • size

      public int size()
      Returns the total number of elements in this data structure.
      Returns:
      the total number of elements in this data structure.

    • reset

      public void reset()
      Resets the UnionFind data structure: each element is placed in its own singleton set.

    • toString

      public java.lang.String toString()
      Returns a string representation of this data structure. Each component is represented as $\left{v_i:v_1,v_2,v_3,...v_n\right}$, where $v_i$ is the representative of the set.
      Overrides:
      toString in class java.lang.Object
      Returns:
      string representation of this data structure