V- the graph vertex type
E- the graph edge type
public class HopcroftKarpMaximumCardinalityBipartiteMatching<V,E> extends Object implements MatchingAlgorithm<V,E>
The Hopcroft Karp matching algorithm computes augmenting paths of increasing length, until no augmenting path exists in the graph. At each iteration, the algorithm runs a Breadth First Search from the exposed (free) vertices, until an augmenting path is found. Next, a Depth First Search is performed to find all (vertex disjoint) augmenting paths of the same length. The matching is augmented along all discovered augmenting paths simultaneously.
The original algorithm is described in: Hopcroft, John E.; Karp, Richard M. (1973), "An n5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing 2 (4): 225–231, doi:10.1137/0202019 A coarse overview of the algorithm is given in: http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm
|Constructor and Description|
Constructs a new instance of the Hopcroft Karp bipartite matching algorithm.
|Modifier and Type||Method and Description|
Compute a matching for a given graph.
public HopcroftKarpMaximumCardinalityBipartiteMatching(Graph<V,E> graph, Set<V> partition1, Set<V> partition2)
graph- bipartite graph
partition1- the first partition of vertices in the bipartite graph
partition2- the second partition of vertices in the bipartite graph
Copyright © 2019. All rights reserved.