Warning

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

eppstein_matching

eppstein_matching(G)

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, \(matches\), such that matches[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).

See also

hopcroft_karp_matching()