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 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(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.
    boolean
    contains(T element)
    Returns true if the given value is an element in this UnionFind data structure.
    T
    find(T element)
    Returns the representative element of the set that element is in.
    protected Map<T,T>
    getParentMap()
     
    protected Map<T,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.
    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(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 Map<T,T> getParentMap()
      Returns:
      map from element to parent element

    • getRankMap

      protected Map<T,Integer> getRankMap()
      Returns:
      map from element to rank

    • contains

      public boolean contains(T element)
      Returns true if the given value is an element in this UnionFind data structure.
      Parameters:
      element - a value that might be in this
      Returns:
      true if this contains the given value

    • 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 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 Object
      Returns:
      string representation of this data structure