Class KuhnMunkresMinimalWeightBipartitePerfectMatching<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - 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>
    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.

    • Field Detail

      • 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 in
        S - first vertex partition of the target bipartite graph
        T - second vertex partition of the target bipartite graph