Package elki.utilities.datastructures

Class KuhnMunkresStern

java.lang.Object

elki.utilities.datastructures.KuhnMunkres

elki.utilities.datastructures.KuhnMunkresWong

elki.utilities.datastructures.KuhnMunkresStern

@Reference(authors="K. L. Stern",
           title="The Hungarian Algorithm for the Assignment Problem",
           booktitle="Online",
           url="http://software-and-algorithms.blogspot.com/2012/09/the-hungarian-algorithm-for-assignment.html",
           bibkey="web/Stern12")
public class KuhnMunkresStern
extends KuhnMunkresWong

A version of Kuhn-Munkres inspired by the implementation of Kevin L. Stern. This approach shares some ideas of KuhnMunkresWong, but works on columns instead of rows first. So far, we have not found a good reference why this works much faster is practice; but it does.

References:

K. L. Stern
The Hungarian Algorithm for the Assignment Problem
http://software-and-algorithms.blogspot.com/2012/09/the-hungarian-algorithm-for-assignment.html

Since:

0.8.0

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field	Description
private double[]	cmin	Minimum value of non-marked row, for each column.
private int[]	cptr	Pointer to the minimum non-marked value, for each column; but initially to the starting row.

Fields inherited from class elki.utilities.datastructures.KuhnMunkresWong

cadj, radj, rmin, rptr

Fields inherited from class elki.utilities.datastructures.KuhnMunkres

cmark, cost, csel, minc, minr, rmark, rsel, selected

Constructor Summary

Constructors

Constructor	Description
KuhnMunkresStern()

Method Summary

Modifier and Type	Method	Description
protected double	findUncoveredMinimum()	Find the minimum in the uncovered rows.
protected void	initUncoveredMinimum()	Initialize values for finding the minima efficiently.
protected void	removeCost(double h)	Remove cost h (if > 0) found to be unavoidable.
int[]	run(double[][] cost)	Perform the Kuhn-Munkres algorithm.

Methods inherited from class elki.utilities.datastructures.KuhnMunkresWong

costOf, initialCover, initialize

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

cptr

private int[] cptr

Pointer to the minimum non-marked value, for each column; but initially to the starting row.

cmin

private double[] cmin

Minimum value of non-marked row, for each column.

Constructor Detail

KuhnMunkresStern

public KuhnMunkresStern()

Method Detail

run

public int[] run(double[][] cost)

Description copied from class: KuhnMunkresWong

Perform the Kuhn-Munkres algorithm.

Overrides:

run in class KuhnMunkresWong

Parameters:

cost - Cost matrix

Returns:

Selected columns, per row

initUncoveredMinimum

protected void initUncoveredMinimum()

Description copied from class: KuhnMunkresWong

Initialize values for finding the minima efficiently.

Overrides:

initUncoveredMinimum in class KuhnMunkresWong

findUncoveredMinimum

protected double findUncoveredMinimum()

Description copied from class: KuhnMunkresWong

Find the minimum in the uncovered rows.

Overrides:

findUncoveredMinimum in class KuhnMunkresWong

Returns:

Minimum in uncovered rows

removeCost

protected void removeCost(double h)

Description copied from class: KuhnMunkresWong

Remove cost h (if > 0) found to be unavoidable.

Overrides:

removeCost in class KuhnMunkresWong

Parameters:

h - Cost to remove