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

java.lang.Object
  extended by org.jgrapht.alg.KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>
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
protected static class KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>
          ...
 
Constructor Summary
KuhnMunkresMinimalWeightBipartitePerfectMatching(WeightedGraph<V,E> G, List<? extends V> S, List<? extends V> T)
           
 
Method Summary
 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)
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()
Description copied from interface: MatchingAlgorithm
Returns set of edges making up the matching

Specified by:
getMatching in interface MatchingAlgorithm<V,E>

getMatchingWeight

public double getMatchingWeight()
Description copied from interface: WeightedMatchingAlgorithm
Returns weight of a matching found

Specified by:
getMatchingWeight in interface WeightedMatchingAlgorithm<V,E>
Returns:
weight of a matching found


Copyright © 2013. All rights reserved.