Package elki.utilities.datastructures

Class KuhnMunkresWong

  • Direct Known Subclasses:
    KuhnMunkresStern
    @Reference(authors="J. K. Wong",
           title="A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres\' algorithm",
           booktitle="BIT Numerical Mathematics 19(3)",
           url="https://doi.org/10.1007/BF01930994",
           bibkey="doi:10.1007/BF01930994")
public class KuhnMunkresWong
extends KuhnMunkres
    Kuhn-Munkres optimal matching (aka the Hungarian algorithm), supposedly in a modern variant. This is a popular algorithm to find the best 1:1 matching to minimize the cost. The original version has a worst case of O(n4). By caching minima and storing column and row deltas, as discussed by Wong, the implementation is supposedly able to guarantee O(n³) time complexity. In our experiments, it was substantially faster for large matrixes, computing a 1000x1000 in less than a second, making this often acceptable to run on data sets with a few thousand objects.

    References:

    J. K. Wong
    A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm
    BIT Numerical Mathematics 19(3)

    Since:
    0.8.0
    Author:
    Erich Schubert

    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) double[] cadj
      Column bias offsets
      (package private) double[] radj
      Row adjustment
      (package private) double[] rmin
      Minimum value of non-marked columns, for each row.
      (package private) int[] rptr
      Pointer to the minimum non-marked value, for each row.

    • Constructor Summary

      Constructors 
      Constructor Description
      KuhnMunkresWong()  

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected double costOf​(int i, int j)
      Get the adjusted cost of a single element, for debug output.
      protected double findUncoveredMinimum()
      Find the minimum in the uncovered rows.
      protected void initialCover()
      Select the last zero in each row to make an initial selection, which may already yield a solution.
      protected void initialize​(double[][] cost)
      Initialize, and make a deep copy.
      protected void initUncoveredMinimum()
      Initialize values for finding the minima efficiently.
      private boolean pivot()
      Pivot columns mark to row marks.
      protected void removeCost​(double h)
      Remove cost h (if > 0) found to be unavoidable.
      int[] run​(double[][] cost)
      Perform the Kuhn-Munkres algorithm.
      private void updateStars()
      Update the position of stars.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • radj

        double[] radj
        Row adjustment

      • cadj

        double[] cadj
        Column bias offsets

      • rmin

        double[] rmin
        Minimum value of non-marked columns, for each row.

      • rptr

        int[] rptr
        Pointer to the minimum non-marked value, for each row.

    • Constructor Detail

      • KuhnMunkresWong

        public KuhnMunkresWong()

    • Method Detail

      • run

        public int[] run​(double[][] cost)
        Perform the Kuhn-Munkres algorithm.
        Overrides:
        run in class KuhnMunkres
        Parameters:
        cost - Cost matrix
        Returns:
        Selected columns, per row

      • initialize

        protected void initialize​(double[][] cost)
        Description copied from class: KuhnMunkres
        Initialize, and make a deep copy.
        Overrides:
        initialize in class KuhnMunkres
        Parameters:
        cost - Original cost matrix

      • initialCover

        protected void initialCover()
        Description copied from class: KuhnMunkres
        Select the last zero in each row to make an initial selection, which may already yield a solution.
        Overrides:
        initialCover in class KuhnMunkres

      • initUncoveredMinimum

        protected void initUncoveredMinimum()
        Initialize values for finding the minima efficiently.

      • findUncoveredMinimum

        protected double findUncoveredMinimum()
        Find the minimum in the uncovered rows.
        Returns:
        Minimum in uncovered rows

      • removeCost

        protected void removeCost​(double h)
        Remove cost h (if > 0) found to be unavoidable.
        Parameters:
        h - Cost to remove

      • pivot

        private boolean pivot()
        Pivot columns mark to row marks.
        Returns:
        true if we pivoted.

      • updateStars

        private void updateStars()
        Update the position of stars.

      • costOf

        protected double costOf​(int i,
                        int j)
        Description copied from class: KuhnMunkres
        Get the adjusted cost of a single element, for debug output.
        Overrides:
        costOf in class KuhnMunkres
        Parameters:
        i - row
        j - column
        Returns:
        cost