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)[source]¶ Returns the maximum cardinality matching of the bipartite graph .
Parameters: G (NetworkX graph) – Undirected bipartite graph Returns: matches – The matching is returned as a dictionary, , such that
matches[v] == w
if nodev
is matched to nodew
. 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