networkx.algorithms.matching.max_weight_matching¶
-
max_weight_matching
(G, maxcardinality=False, weight='weight')[source]¶ Compute a maximum-weighted matching of G.
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.
- Parameters
G (NetworkX graph) – Undirected graph
maxcardinality (bool, optional (default=False)) – If maxcardinality is True, compute the maximum-cardinality matching with maximum 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
matching – A maximal matching of the graph.
- Return type
Notes
If G has edges with weight attributes 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 “primal-dual” 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.