[SciPy-Dev] Graph shortest path

[Jacob VanderPlas]

Ralf Gommers wrote:
>
>
> On Wed, Dec 21, 2011 at 1:59 AM, Aric Hagberg <aric.hagberg at gmail.com 
> <mailto:aric.hagberg at gmail.com>> wrote:
>
>     On Tue, Dec 20, 2011 at 12:06 AM, Gael Varoquaux
>     <gael.varoquaux at normalesup.org
>     <mailto: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. 
>
>
> This only makes sense if other libraries are prepared to add a 
> dependency on NetworkX. Is that the case?
scikit-learn will likely not add dependency on networkx.  One of our 
goals is to keep dependencies to a minimum: numpy and scipy for 
algorithms, adding matplotlib for examples.  We'd love to see some core 
graph algorithms developed and maintained in scipy which can be used by 
scikit-learn, networkx, and other libraries.
  Jake
>
> Ralf
>  
>
>      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
>     _______________________________________________
>     SciPy-Dev mailing list
>     SciPy-Dev at scipy.org <mailto:SciPy-Dev at scipy.org>
>     http://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>