## 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
(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.
• ### Fields inherited from class elki.utilities.datastructures.KuhnMunkres

cmark, cost, csel, minc, minr, rmark, rsel, selected
• ### Constructor Summary

Constructors
Constructor Description
KuhnMunkresWong()
• ### 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 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 elki.utilities.datastructures.KuhnMunkres

debugLogMatrix
• ### Methods inherited from class java.lang.Object

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

double[] radj

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.

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