Class KuhnMunkres

• java.lang.Object
• elki.utilities.datastructures.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
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.

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