7.3.2.2. networkx.algorithms.bipartite.matching.hopcroft_karp_matching¶

networkx.algorithms.bipartite.matching.hopcroft_karp_matching(G)[source]¶

Returns the maximum cardinality matching of the bipartite graph G.

Parameters:	G : NetworkX graph Undirected bipartite graph
Returns:	matches : dictionary The matching is returned as a dictionary, matches, such that matches[v] == w if node v is matched to node w. Unmatched nodes do not occur as a key in mate.

See also

eppstein_matching

Notes

This function is implemented with the Hopcroft–Karp matching algorithm for bipartite graphs.

References

[R499]

John E. Hopcroft and Richard M. Karp. “An n^{5 / 2} Algorithm for Maximum Matchings in Bipartite Graphs” In: SIAM Journal of Computing 2.4 (1973), pp. 225–231. <https://dx.doi.org/10.1137/0202019>.