Package org.jgrapht.alg
Class KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>
- java.lang.Object
-
- org.jgrapht.alg.KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MatchingAlgorithm<V,E>
,WeightedMatchingAlgorithm<V,E>
@Deprecated public class KuhnMunkresMinimalWeightBipartitePerfectMatching<V,E> extends java.lang.Object implements WeightedMatchingAlgorithm<V,E>
Deprecated.UseKuhnMunkresMinimalWeightBipartitePerfectMatching
instead.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
Nested Classes Modifier and Type Class Description protected static class
KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E>
Deprecated.The actual implementation.-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
MatchingAlgorithm.Matching<E>, MatchingAlgorithm.MatchingImpl<E>
-
-
Field Summary
Fields Modifier and Type Field Description private java.util.List<? extends V>
firstPartition
Deprecated.private WeightedGraph<V,E>
graph
Deprecated.private int[]
matching
Deprecated.private java.util.List<? extends V>
secondPartition
Deprecated.-
Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm
DEFAULT_EPSILON
-
-
Constructor Summary
Constructors Constructor Description KuhnMunkresMinimalWeightBipartitePerfectMatching(WeightedGraph<V,E> G, java.util.List<? extends V> S, java.util.List<? extends V> T)
Deprecated.Construct a new instance of the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description MatchingAlgorithm.Matching<E>
computeMatching()
Deprecated.Compute a matching for a given graph.java.util.Set<E>
getMatching()
Deprecated.Returns set of edges making up the matchingdouble
getMatchingWeight()
Deprecated.Returns weight of a matching found
-
-
-
Field Detail
-
graph
private final WeightedGraph<V,E> graph
Deprecated.
-
firstPartition
private final java.util.List<? extends V> firstPartition
Deprecated.
-
secondPartition
private final java.util.List<? extends V> secondPartition
Deprecated.
-
matching
private final int[] matching
Deprecated.
-
-
Constructor Detail
-
KuhnMunkresMinimalWeightBipartitePerfectMatching
public KuhnMunkresMinimalWeightBipartitePerfectMatching(WeightedGraph<V,E> G, java.util.List<? extends V> S, java.util.List<? extends V> T)
Deprecated.Construct a new instance of the algorithm.- Parameters:
G
- target weighted bipartite graph to find matching inS
- first vertex partition of the target bipartite graphT
- second vertex partition of the target bipartite graph
-
-
Method Detail
-
getMatching
public java.util.Set<E> getMatching()
Deprecated.Returns set of edges making up the matching- Specified by:
getMatching
in interfaceMatchingAlgorithm<V,E>
- Returns:
- a matching
-
getMatchingWeight
public double getMatchingWeight()
Deprecated.Returns weight of a matching found- Specified by:
getMatchingWeight
in interfaceWeightedMatchingAlgorithm<V,E>
- Returns:
- weight of a matching found
-
computeMatching
public MatchingAlgorithm.Matching<E> computeMatching()
Deprecated.Compute a matching for a given graph.- Specified by:
computeMatching
in interfaceMatchingAlgorithm<V,E>
- Returns:
- a matching
-
-