Repository: networkx/networkx
Pull request: Fix min_weight_matching to convert edge weights without reciprocal
Fixes #5388 

Add test and then fix code and docs.

Discussion point:  I think we need to remove the `maxcardinality` parameter because it doesn't make sense in a minimum weight matching to allow edges to not be included. You would return a matching with no edges. That would certainly minimize the edge weights.  Inside `min_weight_matching` we should always call `max_weight_matching` with `maxcardinality=True`.

I think this keyword should just be removed. But I deprecated it -- only instead of a warning it raises a NetworkXError telling the user that the concept doesn't make sense and that the parameter would be removed in v3.  But I still think it should just be removed now -- with a note in the release notes.

Thoughts?

Problem statement:
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.

Hints from issue discussion:
Thanks!   You are correct.  

That is a faulty way of thinking about turning a min problem into a max problem. Maximizing over sums of reciprocal weights does not minimizing correctly.  Other options include negating (if the problem doesn't have trouble with negative weights -- which min_weight_matching does not... but shortest_path does). Or perhaps a more robust approach would be to subtract the weights from a little bigger than the maximum of all weights. 
Looking into this bug, I'm pretty sure the keyword argument `maxcardinality` should be deprecated and set to True inside the function. What would `min_weight_matching` mean for `maxcardinality=False`?  It would mean the empty matching or maybe the matching that is just the lowest weight edge. 

I propose that we deprecate `maxcardinality`, and inside the function where we call `max_weight_matching` on the newly weighted edges, we set `maxcardinality=True`.  Luckily this code was only merged Summer 2021 so not too many people will be inconvenienced by this deprecation.

Commit message: Add test and then fix code and docs

Patch to review:
diff --git a/networkx/algorithms/matching.py b/networkx/algorithms/matching.py
index 2a57e9a13bc..10417aa4351 100644
--- a/networkx/algorithms/matching.py
+++ b/networkx/algorithms/matching.py
@@ -227,17 +227,21 @@ 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
+    This method replaces the edge weights with the maximum weight minus
+    the original edge weight. the difference between
+    the maximum weight of all edges (plus 1e-6 to avoid a zero weight edge).
+    `new_weight = (max_weight + 1e-6) - edge_weight`
     then runs :func:`max_weight_matching`.
     Read the documentation of max_weight_matching for more information.
 
@@ -246,9 +250,14 @@ def min_weight_matching(G, maxcardinality=False, weight="weight"):
     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:: 3.0
+            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.
@@ -259,14 +268,20 @@ def min_weight_matching(G, maxcardinality=False, weight="weight"):
     matching : set
         A minimal weight matching of the graph.
     """
+    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 = 1e-6 + 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 ed436aadadc..1dcc69dc697 100644
--- a/networkx/algorithms/tests/test_matching.py
+++ b/networkx/algorithms/tests/test_matching.py
@@ -19,15 +19,13 @@ def test_trivial1(self):
         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 @@ def test_trivial3(self):
             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 @@ def test_trivial4(self):
             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 @@ def test_trivial5(self):
             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 @@ def test_trivial6(self):
         )
 
     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 @@ def test_floating_point_weights(self):
         )
 
     def test_negative_weights(self):
-        """Negative weights"""
         G = nx.Graph()
         G.add_edge(1, 2, weight=2)
         G.add_edge(1, 3, weight=-2)


Code review comments:
diff_hunk: @@ -246,9 +250,14 @@ def min_weight_matching(G, maxcardinality=False, weight="weight"):
     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:: 3.0
+            The `maxcardinality` parameter will be removed in v3.0.
+            It doesn't make sense to set it to false when looking for
path: networkx/algorithms/matching.py
text: @user1:
```suggestion
            It doesn't make sense to set it to False when looking for
```
Just a nit!

diff_hunk: @@ -246,9 +250,14 @@ def min_weight_matching(G, maxcardinality=False, weight="weight"):
     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:: 3.0
path: networkx/algorithms/matching.py
text: @user1:
```suggestion
        .. deprecated:: 2.8
```
The `deprecated` directive is supposed to show when the deprecation was added rather than when it expires