Class WeightedQuickUnionInteger


  • @Reference(authors="R. Sedgewick",
               title="Algorithms in C, Parts 1-4",
               booktitle="",
               bibkey="DBLP:books/daglib/0004943")
    public class WeightedQuickUnionInteger
    extends java.lang.Object
    Union-find algorithm for primitive integers, with optimizations.

    This is the weighted quick union approach, weighted by count and using path-halving for optimization.

    Reference:

    R. Sedgewick
    1.3 Union-Find Algorithms
    Algorithms in C, Parts 1-4

    Since:
    0.7.1
    Author:
    Erich Schubert
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int INITIAL_SIZE
      Initial size.
      private int[] parent
      Parent element
      private int used
      Number of used indexes.
      private int[] weight
      Weight, for optimization.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int find​(int cur)
      Find the parent of an object.
      it.unimi.dsi.fastutil.ints.IntList getRoots()
      Collect all component root elements.
      boolean isConnected​(int first, int second)
      Test if two components are connected.
      int nextIndex​(int weight)
      Occupy the next unused index.
      int size()
      Number of allocated indexes.
      int union​(int first, int second)
      Join the components of elements p and q.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • used

        private int used
        Number of used indexes.
      • parent

        private int[] parent
        Parent element
      • weight

        private int[] weight
        Weight, for optimization.
    • Constructor Detail

      • WeightedQuickUnionInteger

        public WeightedQuickUnionInteger()
        Constructor.
      • WeightedQuickUnionInteger

        public WeightedQuickUnionInteger​(int size)
        Constructor.
    • Method Detail

      • nextIndex

        public int nextIndex​(int weight)
        Occupy the next unused index.
        Parameters:
        weight - Initial weight.
        Returns:
        Next unused index.
      • find

        public int find​(int cur)
        Find the parent of an object.
        Parameters:
        cur - Current entry
        Returns:
        Parent entry
      • union

        public int union​(int first,
                         int second)
        Join the components of elements p and q.
        Parameters:
        first - First element
        second - Second element
        Returns:
        Component id.
      • isConnected

        public boolean isConnected​(int first,
                                   int second)
        Test if two components are connected.
        Parameters:
        first - First element
        second - Second element
        Returns:
        true if they are in the same component.
      • getRoots

        public it.unimi.dsi.fastutil.ints.IntList getRoots()
        Collect all component root elements.
        Returns:
        Root elements
      • size

        public int size()
        Number of allocated indexes.
        Returns:
        Index number.