Package elki.utilities.datastructures.unionfind

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.