[SciPy-Dev] Graph shortest path

[Ralf Gommers]

On Wed, Dec 21, 2011 at 9:20 AM, Jacob VanderPlas <
vanderplas at astro.washington.edu> wrote:

>
>
> 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.
>
> That's what I thought. I'm +1 for adding this to scipy. Preferably as
scipy.sparse.graph or something like that, not a separate module.

Ralf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20111222/8219e464/attachment.html>