max_weight_matching(G, maxcardinality=False, weight='weight')¶
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.
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.
matching – A maximal matching of the graph.
- Return type
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
“Efficient Algorithms for Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys, 1986.