org.jgrapht.alg.matching

Class HopcroftKarpBipartiteMatching<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

MatchingAlgorithm<V,E>

Deprecated.

Deprecated in favor of HopcroftKarpMaximumCardinalityBipartiteMatching

@Deprecated
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 cardinality matching in an undirected simple bipartite graph. To compute a maximum cardinality matching in general (non-bipartite) graphs, use EdmondsMaximumCardinalityMatching instead. 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

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 and Description
HopcroftKarpBipartiteMatching(Graph<V,E> graph, Set<V> partition1, Set<V> partition2) Deprecated. Construct a new instance of the Hopcroft-Karp algorithm for the computation of maximum matchings in bipartite graphs.

Method Summary

Modifier and Type	Method and Description
MatchingAlgorithm.Matching<V,E>	getMatching() Deprecated. 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

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

computeMatching

Constructor Detail

HopcroftKarpBipartiteMatching

public HopcroftKarpBipartiteMatching(Graph<V,E> graph,
                                     Set<V> partition1,
                                     Set<V> partition2)

Deprecated.

Construct a new instance of the Hopcroft-Karp algorithm for the computation of maximum matchings in bipartite graphs.

Parameters:

graph - the input graph

partition1 - the first partition of the vertex set

partition2 - the second partition of the vertex set

Method Detail

getMatching

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

Deprecated.

Compute a matching for a given graph.

Specified by:

getMatching in interface MatchingAlgorithm<V,E>

Returns:

a matching