max_weight_matching#
- max_weight_matching(graph, weight_prop=None, max_cardinality=True, verify_optimum_flag=False)#
Compute a maximum-weighted matching in the general undirected weighted graph given by “edges”. If max_cardinality is true, only maximum-cardinality matchings are considered as solutions.
The algorithm is based on “Efficient Algorithms for Finding Maximum Matching in Graphs” by Zvi Galil, ACM Computing Surveys, 1986.
Based on networkx implementation <networkx/networkx>
With reference to the standalone protoype implementation from: <http://jorisvr.nl/article/maximum-matching>
<http://jorisvr.nl/files/graphmatching/20130407/mwmatching.py>
The function takes time O(n**3)
- Parameters:
graph (GraphView) – The graph to compute the maximum weight matching for
weight_prop (str, optional) – The property on the edge to use for the weight. If not provided,
max_cardinality (bool) – If set to True, consider only maximum-cardinality matchings. Defaults to True. If True, finds the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings, otherwise, finds the maximum weight matching irrespective of cardinality.
verify_optimum_flag (bool) – Whether the optimum should be verified. Defaults to False. If true prior to returning, an additional routine to verify the optimal solution was found will be run after computing the maximum weight matching. If it’s true and the found matching is not an optimal solution this function will panic. This option should normally be only set true during testing.
- Returns:
The matching
- Return type: