Repository: networkx/networkx

Issue:
min_weight_matching gives incorrect results
<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->

Consider the following graph:
```python
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)
nx.min_weight_matching(G)
```

### Current Behavior
<!--- Tell us what happens instead of the expected behavior -->
The program returns `{(2, 1), (4, 3)}`
### Expected Behavior
<!--- Tell us what should happen -->
There are two maximal matchings in the graph, (1,2)(3,4) with weight 1+4=5, and (1,4)(2,3) with weight 2+2=4. The minimum weight maximal matching should be (1,4)(2,3) which has weight 4.
### Steps to Reproduce
<!--- Provide a minimal example that reproduces the bug -->
Run the code provided
### Environment
<!--- Please provide details about your local environment -->
Python version: 3.9
NetworkX version: 2.7.1


### Additional context
<!--- Add any other context about the problem here, screenshots, etc. -->
From the documentation and the code, `min_weight_matching` is simply taking the reciprocal of the weights and uses `max_weight_matching`. This logic seems to be faulty in this example: 1/1+1/4>1/2+1/2. 

Discussion:
mjschwenne: Reading about this bug reminded me of #4836 since they are both a similar issue with converting a maximal algorithm to take the minimum. While I haven't had the time yet to work on that issue, it is still on my mind. I wonder if other functions which take a minimal approach using a maximal algorithm have this issue. It might be a good idea to check if these are part of a large problem. I *should* start to get some free time in the coming week and try to compile a list to test. 
dschult: Sorry this took so long...  I've been worried whether adding 1 to each edge weight to avoid an edge with zero weight would change the max_weight_matching by favoring matchings with more edges in them. It took me a little bit to figure out that all the matchings that we compare in `max_weight_matching` using option `maxcardinality=True` have the same number of edges (cardinality). So adding a constant to the edge weights doesn't affect which matching is optimal. I switched from adding 1e-6 to adding 1 because it would allow integer edge weights to still be integer values. 

I've fixed the documentation errors/suggestions, so I think this is ready for re-review. 

Patch:
diff --git a/doc/developer/deprecations.rst b/doc/developer/deprecations.rst
index 77d814532..a155ab765 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 53b5562bb..dc6240670 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 2a57e9a13..fda0b42cd 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")


Test patch:
diff --git a/networkx/algorithms/tests/test_matching.py b/networkx/algorithms/tests/test_matching.py
index ed436aada..1dcc69dc6 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)