min_weight_matching#

min_weight_matching(G, maxcardinality=None, weight='weight')[source]#

Computing a minimum-weight maximal matching of G.

Use the maximum-weight algorithm with edge weights subtracted from the maximum weight of all edges.

A matching is a subset of edges in which no node occurs more than once. The weight of a matching is the sum of the weights of its edges. A maximal matching cannot add more edges and still be a matching. The cardinality of a matching is the number of matched edges.

This method replaces the edge weights with 1 plus the maximum edge weight minus the original edge weight.

new_weight = (max_weight + 1) - edge_weight

then runs max_weight_matching() with the new weights. The max weight matching with these new weights corresponds to the min weight matching using the original weights. Adding 1 to the max edge weight keeps all edge weights positive and as integers if they started as integers.

You might worry that adding 1 to each weight would make the algorithm favor matchings with more edges. But we use the parameter maxcardinality=True in max_weight_matching to ensure that the number of edges in the competing matchings are the same and thus the optimum does not change due to changes in the number of edges.

Read the documentation of max_weight_matching for more information.

Parameters:

GNetworkX graph: Undirected graph
maxcardinality: bool: Deprecated since version 2.8: The maxcardinality parameter will be removed in v3.0. It doesn’t make sense to set it to False when looking for a min weight matching because then we just return no edges.

If maxcardinality is True, compute the maximum-cardinality matching with minimum weight among all maximum-cardinality matchings.
weight: string, optional (default=’weight’): Edge data key corresponding to the edge weight. If key not found, uses 1 as weight.

Returns:

matchingset: A minimal weight matching of the graph.