[SciPy-Dev] Graph shortest path

[Jacob VanderPlas]

Interesting - if networkx is going that direction, they could certainly 
borrow from scikit-learn in this case [ BSD license = :-) ].

In any case, I think the type of problem solved by 
sklearn.utils.graph_shortest_path is similar to that of 
scipy.sparse.cs_graph_components, so there is some precedent for this 
sort of graph functionality in scipy.
  Jake

Warren Weckesser wrote:
>
>
> On Mon, Dec 19, 2011 at 10:05 AM, Jacob VanderPlas 
> <vanderplas at astro.washington.edu 
> <mailto: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>
>     > <mailto: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 <mailto:SciPy-Dev at scipy.org>
>     > http://mail.scipy.org/mailman/listinfo/scipy-dev
>     >
>     _______________________________________________
>     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
>