org.jgrapht.alg
Class HopcroftKarpBipartiteMatching<V,E>
java.lang.Object
org.jgrapht.alg.HopcroftKarpBipartiteMatching<V,E>
- All Implemented Interfaces:
- MatchingAlgorithm<V,E>
public class HopcroftKarpBipartiteMatching<V,E>
- extends Object
- implements MatchingAlgorithm<V,E>
This class is an implementation of the Hopcroft-Karp algorithm which finds a
maximum matching in an undirected simple bipartite graph. The algorithm runs
in O(|E|*√|V|) time. 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 Note: the behavior of
this class is undefined when the input isn't a bipartite graph, i.e. when
there are edges within a single partition!
- Author:
- Joris Kinable
Method Summary |
Set<E> |
getMatching()
Returns set of edges making up the matching |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
HopcroftKarpBipartiteMatching
public HopcroftKarpBipartiteMatching(UndirectedGraph<V,E> graph,
Set<V> partition1,
Set<V> partition2)
getMatching
public Set<E> getMatching()
- Description copied from interface:
MatchingAlgorithm
- Returns set of edges making up the matching
- Specified by:
getMatching
in interface MatchingAlgorithm<V,E>
Copyright © 2013. All rights reserved.