org.jgrapht.alg.matching

## Class KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>

• java.lang.Object
• org.jgrapht.alg.matching.KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>
• Type Parameters:
`V` - the graph vertex type
`E` - the graph edge type
All Implemented Interfaces:
MatchingAlgorithm<V,E>

```public class KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>
extends Object
implements MatchingAlgorithm<V,E>```
Kuhn-Munkres algorithm (named in honor of Harold Kuhn and James Munkres) solving assignment problem also known as hungarian algorithm (in the honor of hungarian mathematicians Dénes K?nig and Jen? Egerváry). It's running time O(V^3).

Assignment problem could be set as follows:

Given complete bipartite graph G = (S, T; E), such that |S| = |T|, and each edge has non-negative cost c(i, j), find perfect matching of minimal cost.

Author:
Alexey Kudinkin

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

`MatchingAlgorithm.Matching<E>, MatchingAlgorithm.MatchingImpl<E>`

• ### Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

`DEFAULT_EPSILON`
• ### Constructor Summary

Constructors
Constructor and Description
```KuhnMunkresMinimalWeightBipartitePerfectMatching(Graph<V,E> graph, Set<? extends V> partition1, Set<? extends V> partition2)```
Construct a new instance of the algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`MatchingAlgorithm.Matching<E>` `computeMatching()`
Compute a matching for a given graph.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Methods inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

`getMatching`
• ### Constructor Detail

• #### KuhnMunkresMinimalWeightBipartitePerfectMatching

```public KuhnMunkresMinimalWeightBipartitePerfectMatching(Graph<V,E> graph,
Set<? extends V> partition1,
Set<? extends V> partition2)```
Construct a new instance of the algorithm.
Parameters:
`graph` - the input graph
`partition1` - the first partition of the vertex set
`partition2` - the second partition of the vertex set
• ### Method Detail

• #### computeMatching

`public MatchingAlgorithm.Matching<E> computeMatching()`
Compute a matching for a given graph.
Specified by:
`computeMatching` in interface `MatchingAlgorithm<V,E>`
Returns:
a matching