MunkresKuhnAlgorithm (ImgLib2 Algorithms 0.16.0 API)

java.lang.Object
- net.imglib2.algorithm.metrics.segmentation.assignment.MunkresKuhnAlgorithm

```
public class MunkresKuhnAlgorithm
extends Object
```
Adapted from fiji.plugin.trackmate.tracking.oldlap.hungarian. Re-licensed as BSD with permission of the author (Johannes Schindelin).
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 ∆.
Copyright 2011 (C) Johannes Schindelin

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()

Constructors
Constructor and Description
`MunkresKuhnAlgorithm()`

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`protected String`	`alternatingPath(int y)`
`protected void`	`augmentPath(int y)`
`protected void`	`calculate()`
`int[][]`	`computeAssignments(double[][] costMatrix)`
`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
```
See Also:

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)

getTotalWeight
```
public double getTotalWeight()
```

initialize
```
protected final void initialize()
```

calculate
```
protected final void calculate()
```

findUnmatchedX
```
protected final int findUnmatchedX()
```

startBreadthFirstSearch

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)

Class MunkresKuhnAlgorithm

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

NO_EDGE_VALUE

M

N

weight

matchingY

matchingX

labelingX

labelingY

slack

slackX

S

T

previousX

queue

x

queueStart

queueEnd

Constructor Detail

MunkresKuhnAlgorithm

Method Detail

computeAssignments

getTotalWeight

initialize

calculate

findUnmatchedX

startBreadthFirstSearch

findY

isTight

updateLabels

augmentPath

extendAlternatingTree

verifySlack

verifyMatching

equalityGraph

alternatingPath