Repository: scipy/scipy
Pull request: BUG: fix edge counting in shortest_path
<!-- 
Thanks for contributing a pull request! Please ensure that
your PR satisfies the checklist before submitting:
http://scipy.github.io/devdocs/dev/contributor/development_workflow.html#checklist-before-submitting-a-pr

Also, please name and describe your PR as you would write a
commit message:
https://docs.scipy.org/doc/numpy/dev/development_workflow.html#writing-the-commit-message

Note that we are a team of volunteers; we appreciate your
patience during the review process.

Again, thanks for contributing!
-->
#### What does this implement/fix?
In the shortest paths function(with method == 'auto') there was a bug in counting edges for dense graph representation. (non-existent edges marked with np.inf were counted, while existing edges with weight 0 were skipped). This could lead to the selection of a suboptimal algorithm.
I fixed it by splitting it into two cases:
* For dense masked representation I counted number of non-masked elements.
* For dense array representation I changed elements equal to inf and NaN to 0 and then I counted number of elements bigger than 0.

I also got rid of the warnings that popped up when non-existent edges were marked by NaN. Thus this fixes #5144.



Problem statement:
RuntimeWarning on csgraph.shortest_path when edge lengths are NaN
The documentation for scipy.sparse.csgraph says that NaN entries will be treated as non-edges, the same as 0 or inf. But when using csgraph.shortest_path on a graph where some paths are impossible because of NaN edges, irrelevant warning messages are printed. These warning messages don't happen in the other cases.

```
>>> import numpy
>>> import scipy.sparse.csgraph as csgraph
>>> print csgraph.shortest_path(numpy.array([[0,numpy.inf],[numpy.inf,0]]))
[[  0.  inf]
 [ inf   0.]]
>>> print csgraph.shortest_path(numpy.array([[0,0],[0,0]]))
[[  0.  inf]
 [ inf   0.]]
>>> print csgraph.shortest_path(numpy.array([[0, numpy.nan], [numpy.nan, 0]]))
/Users/creidieki/.virtualenvs/bugtest/lib/python2.7/site-packages/numpy/ma/core.py:2200: RuntimeWarning: invalid value encountered in less_equal
  condition = umath.less_equal(mabs(xnew - value), atol + rtol * mabs(value))
bug.py:4: RuntimeWarning: invalid value encountered in greater
  print csgraph.shortest_path(numpy.array([[0,numpy.nan],[numpy.nan,0]]))
bug.py:4: RuntimeWarning: invalid value encountered in less
  print csgraph.shortest_path(numpy.array([[0,numpy.nan],[numpy.nan,0]]))
[[  0.  inf]
 [ inf   0.]]
```

Using numpy v1.9.2, scipy v0.16.0, python 2.7.10 in a clean virtualenv on os x 10.10.4.

Hints from issue discussion:
thanks @creidieki. Those warnings are harmless but very annoying. They should be easy to avoid.

Commit message: BUG: add counting of negative edges

Patch to review:
diff --git a/scipy/sparse/csgraph/_shortest_path.pyx b/scipy/sparse/csgraph/_shortest_path.pyx
index 2c752f485d99..9f1a0d595756 100644
--- a/scipy/sparse/csgraph/_shortest_path.pyx
+++ b/scipy/sparse/csgraph/_shortest_path.pyx
@@ -166,12 +166,17 @@ def shortest_path(csgraph, method='auto',
         issparse = isspmatrix(csgraph)
         if issparse:
             Nk = csgraph.nnz
+            edges = csgraph.data
+        elif np.ma.isMaskedArray(csgraph):
+            Nk = csgraph.count()
+            edges = csgraph.compressed()
         else:
-            Nk = np.sum(csgraph > 0)
+            edges = csgraph[np.isfinite(csgraph)]
+            edges = edges[edges != 0]
+            Nk = edges.size
 
         if indices is not None or Nk < N * N / 4:
-            if ((issparse and np.any(csgraph.data < 0))
-                      or (not issparse and np.any(csgraph < 0))):
+            if (np.any(edges < 0)):
                 method = 'J'
             else:
                 method = 'D'
diff --git a/scipy/sparse/csgraph/tests/test_shortest_path.py b/scipy/sparse/csgraph/tests/test_shortest_path.py
index 946ad06cde84..4e7556b0578d 100644
--- a/scipy/sparse/csgraph/tests/test_shortest_path.py
+++ b/scipy/sparse/csgraph/tests/test_shortest_path.py
@@ -311,3 +311,10 @@ def test_buffer(method):
     G = scipy.sparse.csr_matrix([[1.]])
     G.data.flags['WRITEABLE'] = False
     shortest_path(G, method=method)
+
+
+def test_NaN_warnings():
+    with pytest.warns(None) as record:
+        shortest_path(np.array([[0, 1], [np.nan, 0]]))
+    for i in range(len(record)):
+        assert record[i].category is not RuntimeWarning


Code review comments:
diff_hunk: @@ -166,12 +166,17 @@ def shortest_path(csgraph, method='auto',
         issparse = isspmatrix(csgraph)
         if issparse:
             Nk = csgraph.nnz
+            edges = csgraph.data
path: scipy/sparse/csgraph/_shortest_path.pyx
text: @user1:
This will fail for certain sparse matrix formats. CSR, CSC, and COO should work, but DIA, LIL, BSR, and DOK are likely to cause trouble. I'd add a test first to confirm the bug, then add a conditional `csgraph.tocoo()` conversion before extracting edges.

@author:
While I was writing a test for this bug I found that `floyd_warshall` throws ValueError when graph is passed as sparse matrix other than LIL, CSR or CSC.

Here is the code that produces this error:

```
G_dense = np.array([[0, 2, 1],
                    [0, -1, 0],
                    [0, 0, 0]])
G_sparse = coo_matrix(G_dense)
shortest_path(G_sparse)
```
Traceback:
```
  File "_shortest_path.pyx", line 189, in scipy.sparse.csgraph._shortest_path.shortest_path
  File "_shortest_path.pyx", line 298, in scipy.sparse.csgraph._shortest_path.floyd_warshall
  File "/home/piurko/TCS/PZ/scipy/scipy/sparse/csgraph/_validation.py", line 29, in validate_graph
    csgraph = csgraph_to_dense(csgraph, null_value=null_value_out)
  File "_tools.pyx", line 320, in scipy.sparse.csgraph._tools.csgraph_to_dense
ValueError: csgraph must be lil, csr, or csc format
```
For this reason I'm not sure what to do with the test you asked for. Should I just run `shortest_path` function with some graph (for which other algorithm than FW will be selected) in every sparse matrix format?



@user1:
Oh, I didn't realize we had that restriction in place. Seems a bit too strict, but that's an issue for another time.

It should be sufficient to test with a LIL-format matrix.

diff_hunk: @@ -311,3 +311,10 @@ def test_buffer(method):
     G = scipy.sparse.csr_matrix([[1.]])
     G.data.flags['WRITEABLE'] = False
     shortest_path(G, method=method)
+
+
+def test_NaN_warnings():
+    with pytest.warns(None) as record:
+        shortest_path(np.array([[0, 1], [np.nan, 0]]))
+    for i in range(len(record)):
+        assert record[i].category is not RuntimeWarning
path: scipy/sparse/csgraph/tests/test_shortest_path.py
text: @user1:
```
for r in record:
  assert r.category ...
```

diff_hunk: @@ -166,12 +166,17 @@ def shortest_path(csgraph, method='auto',
         issparse = isspmatrix(csgraph)
         if issparse:
             Nk = csgraph.nnz
+            edges = csgraph.data
+        elif np.ma.isMaskedArray(csgraph):
+            Nk = csgraph.count()
+            edges = csgraph.compressed()
         else:
-            Nk = np.sum(csgraph > 0)
+            edges = csgraph[np.isfinite(csgraph)]
+            edges = edges[edges != 0]
+            Nk = edges.size
 
         if indices is not None or Nk < N * N / 4:
-            if ((issparse and np.any(csgraph.data < 0))
-                      or (not issparse and np.any(csgraph < 0))):
+            if (np.any(edges < 0)):
path: scipy/sparse/csgraph/_shortest_path.pyx
text: @user1:
the outer parens aren't needed here.