minimum_weight_full_matching#

minimum_weight_full_matching(G, top_nodes=None, weight='weight')[source]#

Returns a minimum weight full matching of the bipartite graph G.

Let G=((U,V),E) be a weighted bipartite graph with real weights w:ER. This function then produces a matching ME with cardinality

|M|=min(|U|,|V|),

which minimizes the sum of the weights of the edges included in the matching, eMw(e), or raises an error if no such matching exists.

When |U|=|V|, this is commonly referred to as a perfect matching; here, since we allow |U| and |V| to differ, we follow Karp [1] and refer to the matching as full.

Parameters:
GNetworkX graph

Undirected bipartite graph

top_nodescontainer

Container with all nodes in one bipartite node set. If not supplied it will be computed.

weightstring, optional (default=’weight’)

The edge data key used to provide each value in the matrix. If None, then each edge has weight 1.

Returns:
matchesdictionary

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 matches.

Raises:
ValueError

Raised if no full matching exists.

ImportError

Raised if SciPy is not available.

Notes

The problem of determining a minimum weight full matching is also known as the rectangular linear assignment problem. This implementation defers the calculation of the assignment to SciPy.

References

[1]

Richard Manning Karp: An algorithm to Solve the m x n Assignment Problem in Expected Time O(mn log n). Networks, 10(2):143–152, 1980.