Package elki.utilities.datastructures

Class KuhnMunkres

  • Direct Known Subclasses:
    KuhnMunkresWong
    @Reference(authors="H. W. Kuhn",title="The Hungarian method for the assignment problem",booktitle="Naval Research Logistics Quarterly 2",url="https://doi.org/10.1002/nav.3800020109",bibkey="doi:10.1002/nav.3800020109") @Reference(authors="J. Munkres",title="Algorithms for the Assignment and Transportation Problems",booktitle="Journal of the Society for Industrial and Applied Mathematics 5(1)",url="https://doi.org/10.1137/0105003",bibkey="doi:10.1137/0105003")
public class KuhnMunkres
extends java.lang.Object
    Kuhn-Munkres optimal matching (aka the Hungarian algorithm). 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) albeit sometimes given as O(n³). Empirically, this version is O(n³), too, but literature seems to disagree. For an improved O(n³) version, see KuhnMunkresWong.

    As a rule of thumb, a 1000x1000 problem may take around 30-60 seconds depending on your CPU, a 10kx10k problem may hence take 8-16 hours already.

    References:

    H. W. Kuhn
    The Hungarian method for the assignment problem
    Naval Research Logistics Quarterly 2

    J. Munkres
    Algorithms for the Assignment and Transportation Problems
    Journal of the Society for Industrial and Applied Mathematics 5(1)

    TODO: also implement the Jonker-Volgenant variant!

    Since:
    0.8.0
    Author:
    Erich Schubert

    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) int[] cmark
      Column marks.
      (package private) double[][] cost
      Cost matrix
      (package private) int[] csel
      Selected ("starred") row per column, -1 if not selected.
      private static Logging LOG
      Class logger
      (package private) int minc
      Position of uncovered minimum column
      (package private) int minr
      Position of uncovered minimum row
      (package private) int[] rmark
      Row marks, used only temporary.
      (package private) int[] rsel
      Selected ("starred") column per row, -1 if not selected.
      (package private) int selected
      Number of selected zeros.

    • Constructor Summary

      Constructors 
      Constructor Description
      KuhnMunkres()  

    • 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 void debugLogMatrix​(java.util.logging.Level l, long maxit, java.lang.String msg)
      Debug logging of the matrix.
      private 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[][] ocost)
      Initialize, and make a deep copy.
      private boolean pivot()
      Pivot columns mark to row marks.
      private 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

      • LOG

        private static final Logging LOG
        Class logger

      • cost

        double[][] cost
        Cost matrix

      • selected

        int selected
        Number of selected zeros.

      • rsel

        int[] rsel
        Selected ("starred") column per row, -1 if not selected.

      • csel

        int[] csel
        Selected ("starred") row per column, -1 if not selected.

      • rmark

        int[] rmark
        Row marks, used only temporary.

      • cmark

        int[] cmark
        Column marks.

      • minr

        int minr
        Position of uncovered minimum row

      • minc

        int minc
        Position of uncovered minimum column

    • Constructor Detail

      • KuhnMunkres

        public KuhnMunkres()

    • Method Detail

      • run

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

      • initialize

        protected void initialize​(double[][] ocost)
        Initialize, and make a deep copy.
        Parameters:
        ocost - Original cost matrix

      • initialCover

        protected void initialCover()
        Select the last zero in each row to make an initial selection, which may already yield a solution.

      • findUncoveredMinimum

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

      • removeCost

        private 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.

      • debugLogMatrix

        protected void debugLogMatrix​(java.util.logging.Level l,
                              long maxit,
                              java.lang.String msg)
        Debug logging of the matrix.
        Parameters:
        l - Log level
        maxit - Iteration countdown
        msg - Message prefix

      • costOf

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