networkx.algorithms.bipartite.matching.minimum_weight_full_matching

minimum_weight_full_matching(G, top_nodes=None, weight='weight')

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 : E \to \mathbb{R}$. This function then produces a matching $M \subseteq E$ with cardinality

$$\lvert M \rvert = \min(\lvert U \rvert, \lvert V \rvert),$$

which minimizes the sum of the weights of the edges included in the matching, $\sum_{e \in M} w(e)$, or raises an error if no such matching exists.

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 that matches[v] == w if node v is matched to node w. Unmatched nodes do not occur as a key in matches.

Return type

dictionary

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.