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
be a weighted bipartite graph with real weights . This function then produces a matching with cardinalitywhich minimizes the sum of the weights of the edges included in the matching,
, or raises an error if no such matching exists.When
, this is commonly referred to as a perfect matching; here, since we allow and 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 thatmatches[v] == w
if nodev
is matched to nodew
. Unmatched nodes do not occur as a key inmatches
.
- 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.