Opened 11 years ago

Last modified 15 months 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:

Status badges

Description

Change History (11)

comment:1 Changed 11 years ago by ncohen

  • Status changed from new to needs_work

comment:2 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 2 years 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 15 months 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 15 months 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 15 months 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 15 months 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 15 months ago by gh-vipul79321

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

Note: See TracTickets for help on using tickets.