Package org.graph4j.util

Class UnionFind

java.lang.Object
org.graph4j.util.UnionFind
public class UnionFind extends Object
A union-find data structure (also called disjoint-set or merge–find) stores a collection of disjoint (non-overlapping) sets. The elements of this data structure are graph vertex indices. Initially, all the vertices are added as singletons (one element sets).

The time complexity of the union(int, int) operation is O(1), while find(int) has a complexity O(a(n)) where a is is the inverse Ackermann function. The inverse Ackermann function grows extremely slow, so this factor is 4 or less for practical values of n.

Author:
Cristian Frăsinaru

  • Constructor Summary

    Constructors
    Constructor
    Description
    UnionFind(int numVertices)
    Creates a union-find data structures having numVertices singleton sets, each containing one vertex index, from 0 to numVertices-1.
    UnionFind(int numVertices, boolean pathCompression)
    Creates a union-find data structures having numVertices singleton sets, each containing one vertex index, from 0 to numVertices-1.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    find(int vi)
    Finds the root of the set containing the given vertex index.
    int
    getParent(int vi)
     
    int
    numSets()
    Returns the number of disjoint sets in the data structure.
    protected void
    setParent(int vi, int parentId)
     
    void
    union(int root1, int root2)
    Performs the union of the two sets represented by root1 and root2.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • UnionFind

      public UnionFind(int numVertices)
      Creates a union-find data structures having numVertices singleton sets, each containing one vertex index, from 0 to numVertices-1.
      Parameters:
      numVertices - the number of vertices in the graph.

    • UnionFind

      public UnionFind(int numVertices, boolean pathCompression)
      Creates a union-find data structures having numVertices singleton sets, each containing one vertex index, from 0 to numVertices-1.
      Parameters:
      numVertices - the number of vertices in the graph.
      pathCompression - true if the find method should use the path compression.

  • Method Details

    • find

      public int find(int vi)
      Finds the root of the set containing the given vertex index. The root of a set S is the vertex index r such parent[vi]=r for all vi in S. The method performs also path compression.
      Parameters:
      vi - a vertex index.
      Returns:
      the root of the set containing vi.

    • union

      public void union(int root1, int root2)
      Performs the union of the two sets represented by root1 and root2. The new set is represented by the root of the set containing more elements.
      Parameters:
      root1 - the root of the first set.
      root2 - the root of the second set.

    • numSets

      public int numSets()
      Returns the number of disjoint sets in the data structure.
      Returns:
      the number of sets.

    • getParent

      public int getParent(int vi)

    • setParent

      protected void setParent(int vi, int parentId)