[SciPy-Dev] Graph shortest path

[Aric Hagberg]

On Tue, Dec 20, 2011 at 12:06 AM, Gael Varoquaux
<gael.varoquaux at normalesup.org> wrote:
> On Mon, Dec 19, 2011 at 08:38:07PM -0700, Aric Hagberg wrote:
>> There are some that I would definitely agree are useful in SciPy (or
>> in a very SciPy sparse friendly NetworkX class?).  For example I don't
>> think there is a (reverse) Cuthill-McKee ordering algorithm in SciPy.
>> I implemented one using NetworkX
>> https://networkx.lanl.gov/trac/browser/networkx/networkx/utils/rcm.py
>> but it would be great to have one that worked directly on a SciPy sparse matrix.
>
> Yes, RCM is a good example. PyAMG had to implement one for linear-algebra
> purposes.
>
>> If any other SciPy folks want to explore the possibilites of
>> high-performance graph algorithms that work directly on sparse matrices
>> I'm interested and would be willing to help with design and code.
>
> Would you rather see these algorithms living in scipy or networkX? If
> scipy was to grow a small set of graph-based algorithms, would you use
> them in networkX?

I would certainly consider using any algorithms developed in SciPy as
part of NetworkX. We already use SciPy for some of the  linear algebra
operations (like computing PageRank).

If we could develop a NetworkX graph class that simply and efficiently
used SciPy sparse matrices for the data-store and implemented the API,
then it might make sense for the algorithms to live in NetworkX.  Then
the existing NetworkX algorithms could be used too.  You can already
do that now but as you pointed out there are copies made into a less
efficient storage structure, e.g.

In [1]: import scipy.sparse

In [2]: import networkx as nx

In [3]: A=scipy.sparse.lil_matrix((5,5))

In [4]: A.setdiag([1,1,1,1],k=1) # path 0-1-2-3-4

In [5]: G=nx.Graph(A)  # <- copy of lil matrix to networkx dictionaries

In [6]: nx.connected_components(G)
Out[6]: [[0, 1, 2, 3, 4]]


Aric