scipy.sparse.csgraph.shortest_path does not work on scipy.sparse.csr_matrix or lil_matrix

[chiffa]

When called on scipy.sparse.csr_matrix or scipy.sparse.lil_matrix, scipy.sparse.csgraph.shortest_path emits the following error:

File "_shortest_path.pyx", line 134, in scipy.sparse.csgraph._shortest_path.shortest_path (scipy/sparse/csgraph/_shortest_path.c:2172) File "/.../python2.7/site-packages/scipy/sparse/base.py", line 183, in __bool__ raise ValueError("The truth value of an array with more than one " ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all().

[jakevdp]

It looks like a problem with the validation function. I've put a fix in #3467. Thanks for the report!

[chiffa]

Thanks @jakevdp!
I'll patch it locally for now, but I'll wait for your patch to be merged before releasing my code. By the way, could you explain me how to patch my local scipy version to get rid of the bug? I guess I will have to rebuild it all, but what exactly should be done?

[jakevdp]

Yes - this workaround should work:

import numpy as np
from scipy.sparse.csgraph._validation import validate_graph
from scipy.sparse.csgraph import shortest_path

G = ... # G is the graph you're using

directed = True  # this is the default value in shortest_path. Setting it to False
                 # is fine, as long as the same value is used in both places below
G = validate_graph(G, directed, np.float64)
shortest_path(G, directed=directed)

If that doesn't work for you, then my patch is fixing the wrong problem...

[chiffa]

Unfortunately, it didn't work for me. Which means that the problem is elsewhere.

Here is my code:

        _characterise_mat(self.dir_adj_matrix)
        # Matrix of shape (9778, 9778), type <class 'scipy.sparse.lil.lil_matrix'> and has 19468 non-zero terms
        G = validate_graph(self.dir_adj_matrix, True, np.float64)
        dir_reg_path = shortest_path(G, directed=True )
        _characterise(dir_reg_path)

and here is the stack trace:

  File "/.../*.py", line *, in ***
    dir_reg_path = shortest_path(G, directed=True )
  File "_shortest_path.pyx", line 134, in scipy.sparse.csgraph._shortest_path.shortest_path (scipy/sparse/csgraph/_shortest_path.c:2172)
  File "/.../lib/python2.7/site-packages/scipy/sparse/base.py", line 183, in __bool__
    raise ValueError("The truth value of an array with more than one "
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all().

If it can help you, in the same situation, scipy.sparse.csgraph.connected_components works just fine and gives me the expected result.

[jakevdp]

Okay, thanks for following up...

This is the line that's causing the problem:

if ((isspmatrix(csgraph) and np.any(csgraph.data < 0)) or np.any(csgraph < 0)):
    method = 'J'

I think I see the issue now. The logic here is flawed. I think it should say the following:

if ((isspmatrix(csgraph) and np.any(csgraph.data < 0))
    or (not isspmatrix(csgraph) and np.any(csgraph < 0))):
    method = 'J'

A fix for your situation would be to call the function with method='D' explicitly set.

[jakevdp]

I updated the fix, including adding a clarifying comment on why the result of validate_graph had not been stored.

@chiffa, let me know if setting method='D' works for you.

[chiffa]

@jakevdp, yep, this has actually solved the problem, thanks!

[jakevdp]

Great! Again, thanks for reporting this bug.

[chiffa]

Thanks for answering and reacting so fast! Without this function my code would go from ten lines to literally thousands of lines.