Package 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 java.lang.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 Class Summary

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

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

Field Summary

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

DEFAULT_EPSILON

Constructor Summary

Constructors

Constructor	Description
KuhnMunkresMinimalWeightBipartitePerfectMatching(Graph<V,E> graph, java.util.Set<? extends V> partition1, java.util.Set<? extends V> partition2)	Construct a new instance of the algorithm.

Method Summary

Modifier and Type	Method	Description
MatchingAlgorithm.Matching<V,E>	getMatching()	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

Constructor Detail

KuhnMunkresMinimalWeightBipartitePerfectMatching

public KuhnMunkresMinimalWeightBipartitePerfectMatching(Graph<V,E> graph,
                                                        java.util.Set<? extends V> partition1,
                                                        java.util.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

getMatching

public MatchingAlgorithm.Matching<V,E> getMatching()

Compute a matching for a given graph.

Specified by:

getMatching in interface MatchingAlgorithm<V,E>

Returns:

a matching