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

GNetworkX graph

Undirected bipartite graph


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.


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.


Raised if no full matching exists.


Raised if SciPy is not available.


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.



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.