Warning
The documentation for retworkx has migrated to:
https://qiskit.org/documentation/retworkx
These docs will no longer be updated.
retworkx.max_weight_matching¶
- max_weight_matching(graph, /, max_cardinality=False, weight_fn=None, default_weight=1, verify_optimum=False)¶
Compute a maximum-weighted matching for a
PyGraph
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 function takes time \(O(n^3)\) where
n
is the number of nodes in the graph.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.
- Parameters
graph (PyGraph) – The undirected graph to compute the max weight matching for. Expects to have no parallel edges (multigraphs are untested currently).
max_cardinality (bool) – If True, compute the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings. Defaults False.
weight_fn (callable) – An optional callable that will be passed a single argument the edge object for each edge in the graph. It is expected to return an
int
weight for that edge. For example, if the weights are all integers you can use:lambda x: x
. If not specified the value fordefault_weight
will be used for all edge weights.default_weight (int) – The
int
value to use for all edge weights in the graph ifweight_fn
is not specified. Defaults to1
.verify_optimum (bool) – A boolean flag to run a check that the found solution is optimum. If set to true an exception will be raised if the found solution is not optimum. This is mostly useful for testing.
- Returns
A set of tuples ofthe matching, Note that only a single direction will be listed in the output, for example:
{(0, 1),}
.- Return type
set
- 1
“Efficient Algorithms for Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys, 1986.