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

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 <https://github.com/networkx/networkx/pull/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)