|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.jgrapht.alg.KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>
public class KuhnMunkresMinimalWeightBipartitePerfectMatching<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.
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 |
---|
public KuhnMunkresMinimalWeightBipartitePerfectMatching(WeightedGraph<V,E> G, List<? extends V> S, List<? extends V> T)
G
- target weighted bipartite graph to find matching inS
- first vertex partition of the target bipartite graphT
- second vertex partition of the target bipartite graphMethod Detail |
---|
public Set<E> getMatching()
MatchingAlgorithm
getMatching
in interface MatchingAlgorithm<V,E>
public double getMatchingWeight()
WeightedMatchingAlgorithm
getMatchingWeight
in interface WeightedMatchingAlgorithm<V,E>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |