org.jgrapht.alg

Class KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>

java.lang.Object

org.jgrapht.alg.KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MatchingAlgorithm<V,E>, WeightedMatchingAlgorithm<V,E>

public class KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>
extends Object
implements WeightedMatchingAlgorithm<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

Modifier and Type	Class and Description
protected static class	KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E> The actual implementation.

Constructor Summary

Constructors

Constructor and Description
KuhnMunkresMinimalWeightBipartitePerfectMatching(WeightedGraph<V,E> G, List<? extends V> S, List<? extends V> T) Construct a new instance of the algorithm.

Method Summary

Modifier and Type	Method and Description
Set<E>	getMatching() Returns set of edges making up the matching
double	getMatchingWeight() Returns weight of a matching found

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

KuhnMunkresMinimalWeightBipartitePerfectMatching

public KuhnMunkresMinimalWeightBipartitePerfectMatching(WeightedGraph<V,E> G,
                                                        List<? extends V> S,
                                                        List<? extends V> T)

Construct a new instance of the algorithm.

Parameters:

G - target weighted bipartite graph to find matching in

S - first vertex partition of the target bipartite graph

T - second vertex partition of the target bipartite graph

Method Detail

getMatching

public Set<E> getMatching()

Returns set of edges making up the matching

Specified by:

getMatching in interface MatchingAlgorithm<V,E>

Returns:

a matching

getMatchingWeight

public double getMatchingWeight()

Returns weight of a matching found

Specified by:

getMatchingWeight in interface WeightedMatchingAlgorithm<V,E>

Returns:

weight of a matching found