Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# hopcroft_karp_matching¶

hopcroft_karp_matching(G)[source]

Returns the maximum cardinality matching of the bipartite graph $$G$$.

Parameters: G (NetworkX graph) – Undirected bipartite graph matches – 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. dictionary

Notes

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

References

 [1] 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. .