org.jgrapht.alg
Class HopcroftKarpBipartiteMatching<V,E>

java.lang.Object
  extended by 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

Constructor Summary
HopcroftKarpBipartiteMatching(UndirectedGraph<V,E> graph, Set<V> partition1, Set<V> partition2)
           
 
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
 

Constructor Detail

HopcroftKarpBipartiteMatching

public HopcroftKarpBipartiteMatching(UndirectedGraph<V,E> graph,
                                     Set<V> partition1,
                                     Set<V> partition2)
Method Detail

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.