Opened 10 years ago

Last modified 3 weeks ago

#7676 needs_work enhancement

shortest_path_all pairs in Cython through Floyd Warshall

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-wishlist
Component: graph theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Change History (11)

comment:1 Changed 10 years ago by ncohen

  • Status changed from new to needs_work

comment:2 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 14 months ago by embray

  • Milestone changed from sage-6.4 to sage-wishlist

According to https://ask.sagemath.org/question/44823/sage-floyd-algorithm-in-cython/ SciPy? already includes an implementation of this that is quite fast, and should probably be used over any implementation in Sage.

comment:7 Changed 3 weeks ago by gh-vipul79321

If nobody else is currently working on this can I go ahead and implement shortest_path_all pair using Floyd warshall algorithm ?

comment:8 Changed 3 weeks ago by dcoudert

The first step is to survey the many algorithms we already have with data structures and specific conditions (e.g., weighted, multi edges, loops, etc.).

comment:9 Changed 3 weeks ago by gh-vipul79321

I have surveyed all the algorithm and data structure sage has. All pair shortest path works only for an unweighted graph. Although we can use boost interface for this purpose. But I think sage should have its own implementation of Floyd Warshall algorithmhttps://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm for a weighted graph with positive or negative edge weights(but with no negative cycles).

comment:10 Changed 3 weeks ago by dcoudert

I don't think sage should have it's own implementation if the one of Boost is fast enough. You can give it a try, but I'm not sure you can produce something faster than 'Floyd-Warshall_Boost'.

Note that we already have a (slow) Python implementation 'Floyd-Warshall-Python' for weighted graphs, and a Cython implementation 'Floyd-Warshall-Cython' but for unweighted graphs only.

comment:11 Changed 3 weeks ago by gh-vipul79321

Thanks for your helpful suggestion. I will look into it.

Note: See TracTickets for help on using tickets.