max_weight_matching¶

max_weight_matching
(G, maxcardinality=False)[source]¶ Compute a maximumweighted matching of G.
A matching is a subset of edges in which no node occurs more than once. The cardinality of a matching is the number of matched edges. The weight of a matching is the sum of the weights of its edges.
Parameters:  G (NetworkX graph) – Undirected graph
 maxcardinality (bool, optional) – If maxcardinality is True, compute the maximumcardinality matching with maximum weight among all maximumcardinality matchings.
Returns: mate – The matching is returned as a dictionary, mate, such that mate[v] == w if node v is matched to node w. Unmatched nodes do not occur as a key in mate.
Return type: dictionary
Notes
If G has edges with ‘weight’ attribute the edge data are used as weight values else the weights are assumed to be 1.
This function takes time O(number_of_nodes ** 3).
If all edge weights are integers, the algorithm uses only integer computations. If floating point weights are used, the algorithm could return a slightly suboptimal matching due to numeric precision errors.
This method is based on the “blossom” method for finding augmenting paths and the “primaldual” method for finding a matching of maximum weight, both methods invented by Jack Edmonds [1].
Bipartite graphs can also be matched using the functions present in
networkx.algorithms.bipartite.matching
.References
[1] “Efficient Algorithms for Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys, 1986.