[SciPy-Dev] Graph shortest path

[Warren Weckesser]

On Mon, Dec 19, 2011 at 10:05 AM, Jacob VanderPlas <
vanderplas at astro.washington.edu> wrote:

> As far as I know, networkx uses pure python only.  The cython Dijkstra
> algorithm in scikit-learn is quite a bit faster than anything in networkx
>  Jake
>


You're right, it looks like networkx is currrently pure python (well,
python + numpy).  I'll look into their plans (if any) for cythonizing their
code.  I see on their mailing list that back in August, Aric Hagberg
commented on possibly using the latest version of cython for speeding up
parts of networkx.

Warren



>
> Warren Weckesser wrote:
> >
> >
> > On Mon, Dec 19, 2011 at 6:25 AM, Jacob VanderPlas
> > <vanderplas at astro.washington.edu
> > <mailto:vanderplas at astro.washington.edu>> wrote:
> >
> >     Hello,
> >     A while ago in scikit-learn we implemented an efficient cython graph
> >     shortest-path search using both Dijkstra's algorithm and the
> >     Floyd-Warshall algorithm with Fibonacci heaps.  Currently this is
> >     well-hidden in the scikit-learn utils:
> >
> https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/utils/graph_shortest_path.pyx
> >     This is the kind of basic algorithm that I think belongs in scipy
> >     rather
> >     than scikit-learn.  I know that some developers have been thinking
> >     about
> >     graph tools for scipy: are there ideas about whether/where the
> >     shortest
> >     path search would fit in scipy?
> >
> >
> >
> > Networkx (http://networkx.lanl.gov/) already provides an assortment of
> > data structures and algorithms for graphs.  It is an active,
> > well-documented project.  Personally, I'd rather not start adding code
> > to scipy that duplicates it.   If your code is better/faster/stronger
> > than theirs, why not contribute it to networkx?
> >
> > Warren
> >
> > ------------------------------------------------------------------------
> >
> > _______________________________________________
> > SciPy-Dev mailing list
> > 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20111219/380940bb/attachment.html>