From c3e1e7f4c6a4edb968494cd4775574ad26f2a96b Mon Sep 17 00:00:00 2001 From: Dan Schult Date: Fri, 1 Apr 2022 15:35:43 -0400 Subject: Fix min_weight_matching to convert edge weights without reciprocal (#5394) * Add test and then fix code and docs * Correct and improve docs. Change 1e-6 to 1 to maintain integers. Include argument in docstring for why adding the 1 doesn't impact the min --- doc/developer/deprecations.rst | 1 + doc/release/release_dev.rst | 4 +++ networkx/algorithms/matching.py | 55 +++++++++++++++++++++++------- networkx/algorithms/tests/test_matching.py | 30 +++++++++------- 4 files changed, 66 insertions(+), 24 deletions(-) diff --git a/doc/developer/deprecations.rst b/doc/developer/deprecations.rst index 77d81453..a155ab76 100644 --- a/doc/developer/deprecations.rst +++ b/doc/developer/deprecations.rst @@ -114,3 +114,4 @@ Version 3.0 * In ``algorithms/distance_measures.py`` remove ``extrema_bounding``. * In ``utils/misc.py`` remove ``dict_to_numpy_array1`` and ``dict_to_numpy_array2``. * In ``utils/misc.py`` remove ``to_tuple``. +* In ``algorithms/matching.py``, remove parameter ``maxcardinality`` from ``min_weight_matching``. diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst index 53b5562b..dc624067 100644 --- a/doc/release/release_dev.rst +++ b/doc/release/release_dev.rst @@ -46,6 +46,10 @@ Improvements API Changes ----------- +- [`#5394 `_] + The function ``min_weight_matching`` no longer acts upon the parameter ``maxcardinality`` + because setting it to False would result in the min_weight_matching being no edges + at all. The only resonable option is True. The parameter will be removed completely in v3.0. Deprecations ------------ diff --git a/networkx/algorithms/matching.py b/networkx/algorithms/matching.py index 2a57e9a1..fda0b42c 100644 --- a/networkx/algorithms/matching.py +++ b/networkx/algorithms/matching.py @@ -227,28 +227,49 @@ def is_perfect_matching(G, matching): @not_implemented_for("multigraph") @not_implemented_for("directed") -def min_weight_matching(G, maxcardinality=False, weight="weight"): +def min_weight_matching(G, maxcardinality=None, weight="weight"): """Computing a minimum-weight maximal matching of G. - Use reciprocal edge weights with the maximum-weight algorithm. + Use the maximum-weight algorithm with edge weights subtracted + from the maximum weight of all edges. 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 method replaces the weights with their reciprocal and - then runs :func:`max_weight_matching`. - Read the documentation of max_weight_matching for more information. + This method replaces the edge weights with 1 plus the maximum edge weight + minus the original edge weight. + + new_weight = (max_weight + 1) - edge_weight + + then runs :func:`max_weight_matching` with the new weights. + The max weight matching with these new weights corresponds + to the min weight matching using the original weights. + Adding 1 to the max edge weight keeps all edge weights positive + and as integers if they started as integers. + + You might worry that adding 1 to each weight would make the algorithm + favor matchings with more edges. But we use the parameter + `maxcardinality=True` in `max_weight_matching` to ensure that the + number of edges in the competing matchings are the same and thus + the optimum does not change due to changes in the number of edges. + + Read the documentation of `max_weight_matching` for more information. Parameters ---------- G : NetworkX graph Undirected graph - maxcardinality: bool, optional (default=False) - If maxcardinality is True, compute the maximum-cardinality matching - with minimum weight among all maximum-cardinality matchings. + maxcardinality: bool + .. deprecated:: 2.8 + The `maxcardinality` parameter will be removed in v3.0. + It doesn't make sense to set it to False when looking for + a min weight matching because then we just return no edges. + + If maxcardinality is True, compute the maximum-cardinality matching + with minimum weight among all maximum-cardinality matchings. weight: string, optional (default='weight') Edge data key corresponding to the edge weight. @@ -258,15 +279,25 @@ def min_weight_matching(G, maxcardinality=False, weight="weight"): ------- matching : set A minimal weight matching of the graph. + + See Also + -------- + max_weight_matching """ + if maxcardinality not in (True, None): + raise nx.NetworkXError( + "The argument maxcardinality does not make sense " + "in the context of minimum weight matchings." + "It is deprecated and will be removed in v3.0." + ) if len(G.edges) == 0: - return max_weight_matching(G, maxcardinality, weight) + return max_weight_matching(G, maxcardinality=True, weight=weight) G_edges = G.edges(data=weight, default=1) - min_weight = min(w for _, _, w in G_edges) + max_weight = 1 + max(w for _, _, w in G_edges) InvG = nx.Graph() - edges = ((u, v, 1 / (1 + w - min_weight)) for u, v, w in G_edges) + edges = ((u, v, max_weight - w) for u, v, w in G_edges) InvG.add_weighted_edges_from(edges, weight=weight) - return max_weight_matching(InvG, maxcardinality, weight) + return max_weight_matching(InvG, maxcardinality=True, weight=weight) @not_implemented_for("multigraph") diff --git a/networkx/algorithms/tests/test_matching.py b/networkx/algorithms/tests/test_matching.py index ed436aad..1dcc69dc 100644 --- a/networkx/algorithms/tests/test_matching.py +++ b/networkx/algorithms/tests/test_matching.py @@ -19,15 +19,13 @@ class TestMaxWeightMatching: assert nx.max_weight_matching(G) == set() assert nx.min_weight_matching(G) == set() - def test_trivial2(self): - """Self loop""" + def test_selfloop(self): G = nx.Graph() G.add_edge(0, 0, weight=100) assert nx.max_weight_matching(G) == set() assert nx.min_weight_matching(G) == set() - def test_trivial3(self): - """Single edge""" + def test_single_edge(self): G = nx.Graph() G.add_edge(0, 1) assert edges_equal( @@ -37,8 +35,7 @@ class TestMaxWeightMatching: nx.min_weight_matching(G), matching_dict_to_set({0: 1, 1: 0}) ) - def test_trivial4(self): - """Small graph""" + def test_two_path(self): G = nx.Graph() G.add_edge("one", "two", weight=10) G.add_edge("two", "three", weight=11) @@ -51,8 +48,7 @@ class TestMaxWeightMatching: matching_dict_to_set({"one": "two", "two": "one"}), ) - def test_trivial5(self): - """Path""" + def test_path(self): G = nx.Graph() G.add_edge(1, 2, weight=5) G.add_edge(2, 3, weight=11) @@ -70,8 +66,20 @@ class TestMaxWeightMatching: nx.min_weight_matching(G, 1), matching_dict_to_set({1: 2, 3: 4}) ) - def test_trivial6(self): - """Small graph with arbitrary weight attribute""" + def test_square(self): + G = nx.Graph() + G.add_edge(1, 4, weight=2) + G.add_edge(2, 3, weight=2) + G.add_edge(1, 2, weight=1) + G.add_edge(3, 4, weight=4) + assert edges_equal( + nx.max_weight_matching(G), matching_dict_to_set({1: 2, 3: 4}) + ) + assert edges_equal( + nx.min_weight_matching(G), matching_dict_to_set({1: 4, 2: 3}) + ) + + def test_edge_attribute_name(self): G = nx.Graph() G.add_edge("one", "two", weight=10, abcd=11) G.add_edge("two", "three", weight=11, abcd=10) @@ -85,7 +93,6 @@ class TestMaxWeightMatching: ) def test_floating_point_weights(self): - """Floating point weights""" G = nx.Graph() G.add_edge(1, 2, weight=math.pi) G.add_edge(2, 3, weight=math.exp(1)) @@ -99,7 +106,6 @@ class TestMaxWeightMatching: ) def test_negative_weights(self): - """Negative weights""" G = nx.Graph() G.add_edge(1, 2, weight=2) G.add_edge(1, 3, weight=-2) -- cgit v1.2.1