networkx.algorithms.bipartite.matching.minimum_weight_full_matching¶

minimum_weight_full_matching
(G, top_nodes=None, weight='weight')[source]¶ Returns the minimum weight full matching of the bipartite graph
G
.Let \(G = ((U, V), E)\) be a complete weighted bipartite graph with real weights \(w : E \to \mathbb{R}\). This function then produces a maximum matching \(M \subseteq E\) which, since the graph is assumed to be complete, has cardinality
\[\lvert M \rvert = \min(\lvert U \rvert, \lvert V \rvert),\]and which minimizes the sum of the weights of the edges included in the matching, \(\sum_{e \in M} w(e)\).
When \(\lvert U \rvert = \lvert V \rvert\), this is commonly referred to as a perfect matching; here, since we allow \(\lvert U \rvert\) and \(\lvert V \rvert\) to differ, we follow Karp 1 and refer to the matching as full.
 Parameters
G (NetworkX graph) – Undirected bipartite graph
top_nodes (container) – Container with all nodes in one bipartite node set. If not supplied it will be computed.
weight (string, optional (default=’weight’)) – The edge data key used to provide each value in the matrix.
 Returns
matches – The matching is returned as a dictionary,
matches
, such thatmatches[v] == w
if nodev
is matched to nodew
. Unmatched nodes do not occur as a key in matches. Return type
dictionary
 Raises
ValueError – Raised if the input bipartite graph is not complete.
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.