public class MunkresKuhnAlgorithm extends Object implements AssignmentAlgorithm
This implements the improved O(n^3) algorithm by Kuhn and Munkres, as described here: http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
A few definitions: a labeling (AKA potential) of the vertices is a realvalued function l such that weight(x, y) <= l(x) + l(y). Those edges whose weight is equal to the sum of the connected vertices' labelings are called tight.
The equality graph of a labeling is the graph consisting of the tight edges and the vertices they connect.
An alternating path is a path along edges that alternate between X and Y. In the context of the Hungarian algorithm, all alternating paths begin and end in X.
An alternating tree is a set of alternating paths all beginning in the same root in X. In the context of this algorithm, all alternating trees visit each node at most once, i.e. there is at most one incoming and one outgoing edge for each vertex.
The alternating trees in the Hungarian algorithm have the property that all edges from X to Y are matches, so that the current matching can be extracted from the alternating tree by taking every other edge. The basic idea is to evolve a labeling together with the matching. In each iteration, either more vertices are matched, or the labeling is changed such that its egality graph contains more edges useful for the matching (an edge is not very useful if it connects two vertices which are already spanned by the current alternating tree).
The details of this idea are described eloquently by András Frank in http://www.cs.elte.hu/egres/tr/egres0414.pdf
Note that the term exposed simply means "unmatched", and the term weightedcovering refers to the labeling, while orienting edges denotes the building of the alternating tree:
"In a general step, Kuhn’s algorithm also has a weightedcovering π and considers the subgraph Gπ of tight edges (on node set S ∪ T). Let M be a matching in Gπ. Orient the elements of M from T to S while all other edges of Gπ from S to T. Let RS ⊆ S and RT ⊆ T denote the set of nodes exposed by M in S and in T, respectively. Let Z denote the set of nodes reachable in the resulting digraph from RS by a directed path (that can be computed by a breadthfirst search, for example).
If RT ∩ Z is nonempty, then we have obtained a path P consisting of tight edges that alternates in M. The symmetric difference of P and M is a matching M of Gπ consisting of one more edge than M does. The procedure is then iterated with this M. If RT ∩ Z is empty, then revise π as follows. Let ∆ := min{π(u) + π(v) − c(uv): u ∈ Z ∩ S, v ∈ T − Z}. Decrease (increase, respectively) the πvalue of the elements of S ∩ Z (of T ∩ Z, resp.) by ∆. The resulting π is also a weightedcovering. Construct the subgraph of Gπ and iterate the procedure with π and with the unchanged M."
The first clever idea, therefore, is to find an alternating path in the egality graph whose first (and likewise, whose last) edge is not a matching but every other edge is. By inverting the meaning of those edges (matches become nonmatches, and vice versa), there will be one more match in the end.
The second clever idea is that if no such alternating path can be found (in the complete alternating tree using the current matching, starting from an unmatched x as root), then the labeling can be adjusted easily to retain the part of the egality graph which is covered by the tree, but adding one edge to the egality graph such that the first idea catches.
Note that in the implementation, we follow the naming of the aforementioned Matching.pdf, so our S is Frank's S ∩ Z, etc.
Also note that the secret to the O(n^3) instead of the original O(n^4) lies in the use of the slack array, which is really just a cache for the values of ∆.
Copyright 2011 (C) Johannes Schindelin License: GPLv3
Modifier and Type  Field and Description 

protected double[] 
labelingX 
protected double[] 
labelingY 
protected int 
M 
protected int[] 
matchingX 
protected int[] 
matchingY 
protected int 
N 
double 
NO_EDGE_VALUE 
protected int[] 
previousX 
protected int[] 
queue 
protected int 
queueEnd 
protected int 
queueStart 
protected boolean[] 
S 
protected double[] 
slack 
protected int[] 
slackX 
protected boolean[] 
T 
protected double[][] 
weight 
protected int 
x 
Constructor and Description 

MunkresKuhnAlgorithm() 
Modifier and Type  Method and Description 

protected String 
alternatingPath(int y) 
protected void 
augmentPath(int y) 
protected void 
calculate() 
int[][] 
computeAssignments(double[][] costMatrix)
Solve this assignment problem for the given cost matrix.

protected String 
equalityGraph() 
protected void 
extendAlternatingTree(int y,
int z) 
protected int 
findUnmatchedX() 
protected int 
findY() 
double 
getTotalWeight() 
protected void 
initialize() 
protected boolean 
isTight(int x,
int y) 
protected void 
startBreadthFirstSearch(int x) 
protected int 
updateLabels() 
protected boolean 
verifyMatching() 
protected boolean 
verifySlack() 
public final double NO_EDGE_VALUE
protected int M
protected int N
protected double[][] weight
protected int[] matchingY
protected int[] matchingX
protected double[] labelingX
protected double[] labelingY
protected double[] slack
protected int[] slackX
protected boolean[] S
protected boolean[] T
protected int[] previousX
protected int[] queue
protected int x
protected int queueStart
protected int queueEnd
public int[][] computeAssignments(double[][] costMatrix)
AssignmentAlgorithm
The solutions are returned as a 2D array of int. Each solution is an int array of 2 elements:
computeAssignments
in interface AssignmentAlgorithm
costMatrix
 the cost matrix. It is modified heavily by implementation algorithms.public double getTotalWeight()
protected final void initialize()
protected final void calculate()
protected final int findUnmatchedX()
protected final void startBreadthFirstSearch(int x)
protected final int findY()
protected final boolean isTight(int x, int y)
protected final int updateLabels()
protected final void augmentPath(int y)
protected final void extendAlternatingTree(int y, int z)
protected boolean verifySlack()
protected boolean verifyMatching()
protected String equalityGraph()
protected String alternatingPath(int y)
Copyright © 2015–2017 Fiji. All rights reserved.