eppstein_matching¶

eppstein_matching(G)[source]¶

Returns the maximum cardinality matching of the bipartite graph G.

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

Notes

This function is implemented with David Eppstein’s version of the algorithm Hopcroft–Karp algorithm (see hopcroft_karp_matching()), which originally appeared in the Python Algorithms and Data Structures library (PADS).