min_weight_matching(G, maxcardinality=None, weight='weight')
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 :None:None:`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.
Undirected graph
The :None:None:`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.
Edge data key corresponding to the edge weight. If key not found, uses 1 as weight.
A minimal weight matching of the graph.
Computing a minimum-weight maximal matching of G.
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them