fiji.plugin.trackmate.tracking.oldlap.hungarian

## Class MunkresKuhnAlgorithm

• java.lang.Object
• fiji.plugin.trackmate.tracking.oldlap.hungarian.MunkresKuhnAlgorithm
• All Implemented Interfaces:
AssignmentAlgorithm

```public class MunkresKuhnAlgorithm
extends Object
implements AssignmentAlgorithm```
This implements optimal matching between two sets given a weight matrix (where the goal is to minimize the cumulative weight of the matches).

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 real-valued 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/egres-04-14.pdf

Note that the term exposed simply means "unmatched", and the term weighted-covering refers to the labeling, while orienting edges denotes the building of the alternating tree:

"In a general step, Kuhn’s algorithm also has a weighted-covering π 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 breadth-first search, for example).

If RT ∩ Z is non-empty, 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 weighted-covering. 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 non-matches, 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 ∆.

Author:
Johannes Schindelin
• ### Field Summary

Fields
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 Summary

Constructors
Constructor and Description
`MunkresKuhnAlgorithm()`
• ### Method Summary

All Methods
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()`
• ### Methods inherited from class java.lang.Object

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

• #### NO_EDGE_VALUE

`public final double NO_EDGE_VALUE`
Constant Field Values
• #### M

`protected int M`
• #### N

`protected int N`
• #### weight

`protected double[][] weight`
• #### matchingY

`protected int[] matchingY`
• #### matchingX

`protected int[] matchingX`
• #### labelingX

`protected double[] labelingX`
• #### labelingY

`protected double[] labelingY`
• #### slack

`protected double[] slack`
• #### slackX

`protected int[] slackX`
• #### S

`protected boolean[] S`
• #### T

`protected boolean[] T`
• #### previousX

`protected int[] previousX`
• #### queue

`protected int[] queue`
• #### x

`protected int x`
• #### queueStart

`protected int queueStart`
• #### queueEnd

`protected int queueEnd`
• ### Constructor Detail

• #### MunkresKuhnAlgorithm

`public MunkresKuhnAlgorithm()`
• ### Method Detail

• #### computeAssignments

`public int[][] computeAssignments(double[][] costMatrix)`
Description copied from interface: `AssignmentAlgorithm`
Solve this assignment problem for the given cost matrix.

The solutions are returned as a 2D array of int. Each solution is an int array of 2 elements:

1. the first int is the index of the source object (line index in the cost matrix)
2. the second int is the index of the target object (column index in the cost matrix)
Specified by:
`computeAssignments` in interface `AssignmentAlgorithm`
Parameters:
`costMatrix` - the cost matrix. It is modified heavily by implementation algorithms.
Returns:
an array of solutions, as arrays of 2 ints.
• #### getTotalWeight

`public double getTotalWeight()`
• #### initialize

`protected final void initialize()`
• #### calculate

`protected final void calculate()`
• #### findUnmatchedX

`protected final int findUnmatchedX()`

`protected final void startBreadthFirstSearch(int x)`
• #### findY

`protected final int findY()`
• #### isTight

```protected final boolean isTight(int x,
int y)```
• #### updateLabels

`protected final int updateLabels()`
• #### augmentPath

`protected final void augmentPath(int y)`
• #### extendAlternatingTree

```protected final void extendAlternatingTree(int y,
int z)```
• #### verifySlack

`protected boolean verifySlack()`
• #### verifyMatching

`protected boolean verifyMatching()`
• #### equalityGraph

`protected String equalityGraph()`
• #### alternatingPath

`protected String alternatingPath(int y)`