max_weight_matching(G, maxcardinality=False, weight='weight')
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.
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 .
Bipartite graphs can also be matched using the functions present in networkx.algorithms.bipartite.matching
.
Undirected graph
If maxcardinality is True, compute the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings.
Edge data key corresponding to the edge weight. If key not found, uses 1 as weight.
A maximal matching of the graph.
Compute a maximum-weighted matching of G.
>>> G = nx.Graph()See :
... edges = [(1, 2, 6), (1, 3, 2), (2, 3, 1), (2, 4, 7), (3, 5, 9), (4, 5, 3)]
... G.add_weighted_edges_from(edges)
... sorted(nx.max_weight_matching(G)) [(2, 4), (5, 3)]
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.matching.max_weight_matching
networkx.algorithms.matching.min_weight_matching
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