[SciPy-Dev] Graph shortest path

[Charles R Harris]

On Mon, Dec 19, 2011 at 9:03 AM, Warren Weckesser <
warren.weckesser at enthought.com> wrote:

>
>
> On Mon, Dec 19, 2011 at 6:25 AM, Jacob VanderPlas <
> 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?
>
>
I think it is useful to have a small collection of fundamental algorithms
and data structures in root packages like numpy/scipy that support a large
computational infrastructure. The spacial index would be an example of
such. Whether or not the proposed algorithm is in that class is something
open to discussion, but it is sometimes the case that folks don't know they
need something because it isn't easily available or is hidden away in some
specialty. There may be other things, say linear assignment, that could be
useful in developing algorithms.

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20111219/7aba9fc9/attachment.html>