Module org.jgrapht.core
Package org.jgrapht.alg.matching
Algorithms for the computation of matchings.
-
Class Summary Class Description DenseEdmondsMaximumCardinalityMatching<V,E> This implementation of Edmonds' blossom algorithm computes maximum cardinality matchings in undirected graphs.DenseEdmondsMaximumCardinalityMatching.Levels Storage of the forest, even and odd levels.DenseEdmondsMaximumCardinalityMatching.SimpleMatching Simple representation of a matchingGreedyMaximumCardinalityMatching<V,E> The greedy algorithm for computing a maximum cardinality matching.GreedyWeightedMatching<V,E> The greedy algorithm for computing a maximum weight matching in an arbitrary graph.HopcroftKarpMaximumCardinalityBipartiteMatching<V,E> Implementation of the well-known Hopcroft Karp algorithm to compute a matching of maximum cardinality in a bipartite graph.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).KuhnMunkresMinimalWeightBipartitePerfectMatching.KuhnMunkresMatrixImplementation<V,E> The actual implementation.MaximumWeightBipartiteMatching<V,E> Maximum weight matching in bipartite graphs.PathGrowingWeightedMatching<V,E> A linear time $\frac{1}{2}$-approximation algorithm for finding a maximum weight matching in an arbitrary graph.SparseEdmondsMaximumCardinalityMatching<V,E> Edmonds' blossom algorithm for maximum cardinality matching in general undirected graphs.SparseEdmondsMaximumCardinalityMatching.Algorithm<V,E> The actual implementation as an inner class.SparseEdmondsMaximumCardinalityMatching.VertexPartition Special integer vertex union-find.SparseEdmondsMaximumCardinalityMatching.VertexPartition.Item -
Enum Summary Enum Description SparseEdmondsMaximumCardinalityMatching.Algorithm.Label Even, odd and unlabeled labels.