Package org.jgrapht.alg.matching

Class HopcroftKarpMaximumCardinalityBipartiteMatching<V,E>

java.lang.Object

org.jgrapht.alg.matching.HopcroftKarpMaximumCardinalityBipartiteMatching<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MatchingAlgorithm<V,E>

public class HopcroftKarpMaximumCardinalityBipartiteMatching<V,E>
extends java.lang.Object
implements MatchingAlgorithm<V,E>

Implementation of the well-known Hopcroft Karp algorithm to compute a matching of maximum cardinality in a bipartite graph. The algorithm runs in $O(|E| \cdot \sqrt{|V|})$ time. This implementation accepts undirected graphs which may contain self-loops and multiple edges. To compute a maximum cardinality matching in general (non-bipartite) graphs, use SparseEdmondsMaximumCardinalityMatching instead.

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

Author:

Joris Kinable

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

MatchingAlgorithm.Matching<V,E>, MatchingAlgorithm.MatchingImpl<V,E>

Field Summary

Fields inherited from interface org.jgrapht.alg.interfaces.MatchingAlgorithm

DEFAULT_EPSILON

Constructor Summary

Constructors

Constructor	Description
HopcroftKarpMaximumCardinalityBipartiteMatching(Graph<V,E> graph, java.util.Set<V> partition1, java.util.Set<V> partition2)	Constructs a new instance of the Hopcroft Karp bipartite matching algorithm.

Method Summary

Modifier and Type	Method	Description
MatchingAlgorithm.Matching<V,E>	getMatching()	Compute a matching for a given graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

HopcroftKarpMaximumCardinalityBipartiteMatching

public HopcroftKarpMaximumCardinalityBipartiteMatching(Graph<V,E> graph,
                                                       java.util.Set<V> partition1,
                                                       java.util.Set<V> partition2)

Constructs a new instance of the Hopcroft Karp bipartite matching algorithm. The input graph must be bipartite. For efficiency reasons, this class does not check whether the input graph is bipartite. Invoking this class on a non-bipartite graph results in undefined behavior. To test whether a graph is bipartite, use GraphTests.isBipartite(Graph).

Parameters:

graph - bipartite graph

partition1 - the first partition of vertices in the bipartite graph

partition2 - the second partition of vertices in the bipartite graph

Method Detail

getMatching

public MatchingAlgorithm.Matching<V,E> getMatching()

Description copied from interface: MatchingAlgorithm

Compute a matching for a given graph.

Specified by:

getMatching in interface MatchingAlgorithm<V,E>

Returns:

a matching