Repository: scipy/scipy
Pull request: MAINT: rename MaximumFlowResult.residual to flow
The attribute `MaximumFlowResult.residual` was poorly named: It in fact
represents the flow function of the maximum flow, whereas the residual
is given by the difference between the input graph and this flow
function. As such, we simply rename it from `residual` to `flow` to
avoid the risk of confusion.

A different possible fix would be to change the attribute to actually be
the residual graph, but that would change its value and therefore lead
to a slightly trickier deprecation. The flow is also useful in itself,
so for now, we simply include that, and let it be up to the user to make
the more or less trivial calculation of the residual if that's ever
needed.

This closes https://github.com/scipy/scipy/issues/14731

I think this is the first time I add a `DeprecationWarning`, so I'd appreciate
if the prospective reviewer could take a look at the form of that.

cc @czgdp1807 @pmla 

Problem statement:
BUG: Incorrect residual graph in scipy.sparse.csgraph.maximum_flow
### Describe your issue.

Consider the reproducing example below. This seems to be the incorrect residual graph from the flow. 1-2 has a 5 capacity, 2-3 has a 1 capacity and 3-0 has a 1 capacity. So, while the flow_value is 1 from 1-0 (which is correctly returned), the residual for 1-2 should be 4. Any insight on this is appreciated! 

### Reproducing Code Example

```python
from scipy.sparse.csgraph import maximum_flow
from scipy.sparse import csr_matrix
matrix = [[0,10,10,0],[0,0,5,0],[0,0,0,1],[1,0,0,0]]
obj = maximum_flow(csr_matrix(matrix), 1, 0)
obj.residual.toarray()
```


### Error message

```shell
array([[ 0,  0,  0, -1],
       [ 0,  0,  1,  0],
       [ 0, -1,  0,  1],
       [ 1,  0, -1,  0]], dtype=int32)
```


### SciPy/NumPy/Python version information

1.7.1 1.21.2 sys.version_info(major=3, minor=7, micro=2, releaselevel='final', serial=0)

Hints from issue discussion:
Version 1.8 will add an additional ``method`` argument. The residual matrix is the same for both methods. Perhaps some who has worked on this could take a look?
You're right, this seems like an instance of incorrect, or at the very least very misleading, naming: The map you're looking at is the flow, and the residual network of the flow would be the one whose capacity is the difference between the original capacities and the flow,

```
>>> matrix - obj.residual.toarray()
array([[ 0, 10, 10,  1],
       [ 0,  0,  4,  0],
       [ 0,  1,  0,  0],
       [ 0,  0,  1,  0]])
```

A nice little sanity-check being that this one has no flow:

```
>>> maximum_flow(csr_matrix(matrix - obj.residual.toarray()), 1, 0)
MaximumFlowResult with value of 0
```

So that's pretty confusing indeed. Maybe enough to warrant a renaming + deprecation cycle?

Commit message: MAINT: rename MaximumFlowResult.residual to flow

The attribute `MaximumFlowResult.residual` was poorly named: It in fact
represents the flow function of the maximum flow, whereas the residual
is given by the difference between the input graph and this flow
function. As such, we simply rename it from `residual` to `flow` to
avoid the risk of confusion.

A different possible fix would be to change the attribute to actually be
the residual graph, but that would change its value and therefore lead
to a slightly trickier deprecation. The flow is also useful in itself,
so for now, we simply include that, and let it be up to the user to make
the more or less trivial calculation of the residual if that's ever
needed.

This closes gh-14731

Patch to review:
diff --git a/scipy/sparse/csgraph/_flow.pyx b/scipy/sparse/csgraph/_flow.pyx
index e11dfb06d5ef..0d1466076b7b 100644
--- a/scipy/sparse/csgraph/_flow.pyx
+++ b/scipy/sparse/csgraph/_flow.pyx
@@ -1,6 +1,7 @@
 # cython: wraparound=False, boundscheck=False
 
 import numpy as np
+import warnings
 
 from scipy.sparse import csr_matrix, isspmatrix_csr
 
@@ -17,17 +18,23 @@ class MaximumFlowResult:
     ----------
     flow_value : int
         The value of the maximum flow.
-    residual : csr_matrix
-        The residual graph with respect to the maximum flow.
+    flow : csr_matrix
+        The maximum flow.
     """
 
-    def __init__(self, flow_value, residual):
+    def __init__(self, flow_value, flow):
         self.flow_value = flow_value
-        self.residual = residual
+        self.flow = flow
 
     def __repr__(self):
         return 'MaximumFlowResult with value of %d' % self.flow_value
 
+    @property
+    def residual(self):
+        warnings.warn('the attribute `residual` has been renamed to `flow` ' +
+            'and will be removed in SciPy 1.10.', DeprecationWarning)
+        return self.flow
+
 
 def maximum_flow(csgraph, source, sink, *, method='dinic'):
     r"""
@@ -63,7 +70,7 @@ def maximum_flow(csgraph, source, sink, *, method='dinic'):
     res : MaximumFlowResult
         A maximum flow represented by a ``MaximumFlowResult``
         which includes the value of the flow in ``flow_value``,
-        and the residual graph in ``residual``.
+        and the flow graph in ``flow``.
 
     Raises
     ------
@@ -200,10 +207,10 @@ def maximum_flow(csgraph, source, sink, *, method='dinic'):
 
     At this point, we can find the maximum flow between the added sink and the
     added source and the desired matching can be obtained by restricting the
-    residual graph to the block corresponding to the original graph:
+    flow function to the block corresponding to the original graph:
 
-    >>> flow = maximum_flow(graph_flow, 0, i+j+1, method='dinic')
-    >>> matching = flow.residual[1:i+1, i+1:i+j+1]
+    >>> result = maximum_flow(graph_flow, 0, i+j+1, method='dinic')
+    >>> matching = result.flow[1:i+1, i+1:i+j+1]
     >>> print(matching.toarray())
     [[0 1 0 0]
      [1 0 0 0]
@@ -251,18 +258,18 @@ def maximum_flow(csgraph, source, sink, *, method='dinic'):
     rev_edge_ptr = _make_edge_pointers(m)
     if method == 'edmonds_karp':
         tails = _make_tails(m)
-        residual = _edmonds_karp(m.indptr, tails, m.indices,
-                                 m.data, rev_edge_ptr, source, sink)
+        flow = _edmonds_karp(m.indptr, tails, m.indices,
+                             m.data, rev_edge_ptr, source, sink)
     elif method == 'dinic':
-        residual = _dinic(m.indptr, m.indices, m.data, rev_edge_ptr,
-                          source, sink)
+        flow = _dinic(m.indptr, m.indices, m.data, rev_edge_ptr,
+                      source, sink)
     else:
         raise ValueError('{} method is not supported yet.'.format(method))
-    residual_array = np.asarray(residual)
-    residual_matrix = csr_matrix((residual_array, m.indices, m.indptr),
-                                 shape=m.shape)
-    source_flow = residual_array[m.indptr[source]:m.indptr[source + 1]]
-    return MaximumFlowResult(source_flow.sum(), residual_matrix)
+    flow_array = np.asarray(flow)
+    flow_matrix = csr_matrix((flow_array, m.indices, m.indptr),
+                             shape=m.shape)
+    source_flow = flow_array[m.indptr[source]:m.indptr[source + 1]]
+    return MaximumFlowResult(source_flow.sum(), flow_matrix)
 
 
 def _add_reverse_edges(a):
@@ -402,7 +409,7 @@ cdef ITYPE_t[:] _edmonds_karp(
     Returns
     -------
     flow : memoryview of length :math:`|E|`
-        The residual graph with respect to a maximum flow.
+        The flow graph with respect to a maximum flow.
 
     """
     cdef ITYPE_t n_verts = edge_ptr.shape[0] - 1
@@ -569,7 +576,7 @@ cdef bint _augment_paths(
         For a given vertex ``v``, ``progress[v]`` is the index of the next
         edge to be visited from ``v``.
     flows : memoryview of length :math:`|E|`
-        The residual graph with respect to a maximum flow.
+        The flow graph with respect to a maximum flow.
     stack : memoryview of length (:math:`|E|`, 2)
         Stack used during depth-first search.
 
@@ -643,7 +650,7 @@ cdef ITYPE_t[:] _dinic(
     Returns
     -------
     flows : memoryview of length :math:`|E|`
-        The residual graph with respect to a maximum flow.
+        The flow graph with respect to a maximum flow.
 
     """
     cdef ITYPE_t n_verts = edge_ptr.shape[0] - 1
diff --git a/scipy/sparse/csgraph/tests/test_flow.py b/scipy/sparse/csgraph/tests/test_flow.py
index dff4768b8208..2afb4153cbbb 100644
--- a/scipy/sparse/csgraph/tests/test_flow.py
+++ b/scipy/sparse/csgraph/tests/test_flow.py
@@ -67,8 +67,8 @@ def test_simple_graph(method):
     graph = csr_matrix([[0, 5], [0, 0]])
     res = maximum_flow(graph, 0, 1, method=method)
     assert res.flow_value == 5
-    expected_residual = np.array([[0, 5], [-5, 0]])
-    assert_array_equal(res.residual.toarray(), expected_residual)
+    expected_flow = np.array([[0, 5], [-5, 0]])
+    assert_array_equal(res.flow.toarray(), expected_flow)
 
 
 @pytest.mark.parametrize('method', methods)
@@ -78,8 +78,8 @@ def test_bottle_neck_graph(method):
     graph = csr_matrix([[0, 5, 0], [0, 0, 3], [0, 0, 0]])
     res = maximum_flow(graph, 0, 2, method=method)
     assert res.flow_value == 3
-    expected_residual = np.array([[0, 3, 0], [-3, 0, 3], [0, -3, 0]])
-    assert_array_equal(res.residual.toarray(), expected_residual)
+    expected_flow = np.array([[0, 3, 0], [-3, 0, 3], [0, -3, 0]])
+    assert_array_equal(res.flow.toarray(), expected_flow)
 
 
 @pytest.mark.parametrize('method', methods)
@@ -98,15 +98,15 @@ def test_backwards_flow(method):
                         [0, 0, 0, 0, 0, 0, 0, 0]])
     res = maximum_flow(graph, 0, 7, method=method)
     assert res.flow_value == 20
-    expected_residual = np.array([[0, 10, 0, 0, 10, 0, 0, 0],
-                                  [-10, 0, 10, 0, 0, 0, 0, 0],
-                                  [0, -10, 0, 10, 0, 0, 0, 0],
-                                  [0, 0, -10, 0, 0, 0, 0, 10],
-                                  [-10, 0, 0, 0, 0, 10, 0, 0],
-                                  [0, 0, 0, 0, -10, 0, 10, 0],
-                                  [0, 0, 0, 0, 0, -10, 0, 10],
-                                  [0, 0, 0, -10, 0, 0, -10, 0]])
-    assert_array_equal(res.residual.toarray(), expected_residual)
+    expected_flow = np.array([[0, 10, 0, 0, 10, 0, 0, 0],
+                              [-10, 0, 10, 0, 0, 0, 0, 0],
+                              [0, -10, 0, 10, 0, 0, 0, 0],
+                              [0, 0, -10, 0, 0, 0, 0, 10],
+                              [-10, 0, 0, 0, 0, 10, 0, 0],
+                              [0, 0, 0, 0, -10, 0, 10, 0],
+                              [0, 0, 0, 0, 0, -10, 0, 10],
+                              [0, 0, 0, -10, 0, 0, -10, 0]])
+    assert_array_equal(res.flow.toarray(), expected_flow)
 
 
 @pytest.mark.parametrize('method', methods)
@@ -122,13 +122,13 @@ def test_example_from_clrs_chapter_26_1(method):
                         [0, 0, 0, 0, 0, 0]])
     res = maximum_flow(graph, 0, 5, method=method)
     assert res.flow_value == 23
-    expected_residual = np.array([[0, 12, 11, 0, 0, 0],
-                                  [-12, 0, 0, 12, 0, 0],
-                                  [-11, 0, 0, 0, 11, 0],
-                                  [0, -12, 0, 0, -7, 19],
-                                  [0, 0, -11, 7, 0, 4],
-                                  [0, 0, 0, -19, -4, 0]])
-    assert_array_equal(res.residual.toarray(), expected_residual)
+    expected_flow = np.array([[0, 12, 11, 0, 0, 0],
+                              [-12, 0, 0, 12, 0, 0],
+                              [-11, 0, 0, 0, 11, 0],
+                              [0, -12, 0, 0, -7, 19],
+                              [0, 0, -11, 7, 0, 4],
+                              [0, 0, 0, -19, -4, 0]])
+    assert_array_equal(res.flow.toarray(), expected_flow)
 
 
 @pytest.mark.parametrize('method', methods)
@@ -141,8 +141,8 @@ def test_disconnected_graph(method):
                         [0, 0, 0, 0]])
     res = maximum_flow(graph, 0, 3, method=method)
     assert res.flow_value == 0
-    expected_residual = np.zeros((4, 4), dtype=np.int32)
-    assert_array_equal(res.residual.toarray(), expected_residual)
+    expected_flow = np.zeros((4, 4), dtype=np.int32)
+    assert_array_equal(res.flow.toarray(), expected_flow)
 
 
 @pytest.mark.parametrize('method', methods)
@@ -155,10 +155,17 @@ def test_add_reverse_edges_large_graph(method):
     graph = csr_matrix((data, indices, indptr), shape=(n, n))
     res = maximum_flow(graph, 0, n - 1, method=method)
     assert res.flow_value == 1
-    expected_residual = graph - graph.transpose()
-    assert_array_equal(res.residual.data, expected_residual.data)
-    assert_array_equal(res.residual.indices, expected_residual.indices)
-    assert_array_equal(res.residual.indptr, expected_residual.indptr)
+    expected_flow = graph - graph.transpose()
+    assert_array_equal(res.flow.data, expected_flow.data)
+    assert_array_equal(res.flow.indices, expected_flow.indices)
+    assert_array_equal(res.flow.indptr, expected_flow.indptr)
+
+
+def test_residual_raises_deprecation_warning():
+    graph = csr_matrix([[0, 5, 0], [0, 0, 3], [0, 0, 0]])
+    res = maximum_flow(graph, 0, 2)
+    with pytest.deprecated_call():
+        res.residual
 
 
 @pytest.mark.parametrize("a,b_data_expected", [


Code review comments:
diff_hunk: @@ -17,17 +18,23 @@ class MaximumFlowResult:
     ----------
     flow_value : int
         The value of the maximum flow.
-    residual : csr_matrix
-        The residual graph with respect to the maximum flow.
+    flow : csr_matrix
+        The maximum flow.
     """
 
-    def __init__(self, flow_value, residual):
+    def __init__(self, flow_value, flow):
         self.flow_value = flow_value
-        self.residual = residual
+        self.flow = flow
 
     def __repr__(self):
         return 'MaximumFlowResult with value of %d' % self.flow_value
 
+    @property
+    def residual(self):
+        warnings.warn('the attribute `residual` has been renamed to `flow` ' +
+            'and will be removed in SciPy 1.10.', DeprecationWarning)
path: scipy/sparse/csgraph/_flow.pyx
text: @user1:
We are missing `stacklevel` here
```suggestion
        warnings.warn(
            "The attribute `residual` has been renamed to `flow`"
            " and will be removed in SciPy 1.10.",
            DeprecationWarning, stacklevel=2
        )
```