rustworkx.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 for default_weight will be used for all edge weights.

  • default_weight (int) – The int value to use for all edge weights in the graph if weight_fn is not specified. Defaults to 1.

  • 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