Package org.jgrapht.alg.matching

Algorithms for the computation of matchings.

See: Description

Class Summary

Class	Description
EdmondsBlossomShrinking<V,E>	Deprecated Deprecated in favor of the more efficient EdmondsMaximumCardinalityMatching.
EdmondsMaximumCardinalityMatching<V,E>	This implementation of Edmonds' blossom algorithm computes maximum cardinality matchings in undirected graphs.
GreedyMaximumCardinalityMatching<V,E>	A simple class which computes a random, maximum cardinality matching.
GreedyWeightedMatching<V,E>	The greedy algorithm for computing a maximum weight matching in an arbitrary graph.
HopcroftKarpBipartiteMatching<V,E>	Deprecated Deprecated in favor of HopcroftKarpMaximumCardinalityBipartiteMatching
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).
MaximumWeightBipartiteMatching<V,E>	This class finds a maximum weight matching of a simple undirected weighted bipartite graph.
PathGrowingWeightedMatching<V,E>	A linear time 1/2-approximation algorithm for finding a maximum weight matching in an arbitrary graph.

Package org.jgrapht.alg.matching Description

Algorithms for the computation of matchings.