Package org.jgrapht.alg.util

Class 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

      All Methods Instance Methods Concrete Methods 
      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 Detail

      • 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 Detail

      • 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