Opened 11 years ago
Closed 11 years ago
#7540 closed enhancement (duplicate)
Speed up shortest_path_all_pairs() and update distance_graph
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | |
Cc: | rbeezer | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
As mentionned in #7533 by Rob Beezer, the function shortest_path_all_pairs() is much slower than computing independently all the distances, which is a bit worrying. Easy explanation ( at least it is an explanation for me, though there may be a deeper one ), distance() is a function from NetworkX while the Floyd-Marshall algorithm is directly written in Python, hence the slowness.
This function is very fundamental and should be improved ! The difference is amazing :
sage: g=graphs.RandomGNP(200,.1) sage: time e=g.shortest_path_all_pairs() CPU times: user 16.51 s, sys: 0.06 s, total: 16.57 s Wall time: 16.60 s sage: time a=[g.distance(i,j) for (i,j) in Subsets(g,2)] CPU times: user 1.06 s, sys: 0.00 s, total: 1.06 s Wall time: 1.06 s
See http://groups.google.com/group/sage-devel/browse_thread/thread/8edd29e9bddc67e5 for discussion.
Change History (3)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
- Description modified (diff)
comment:3 Changed 11 years ago by
- Milestone changed from sage-4.3.1 to sage-duplicate/invalid/wontfix
- Resolution set to duplicate
- Status changed from new to closed
Done in #7966
Note: See
TracTickets for help on using
tickets.
then... use networkx. More precisely,
networkx.all_pairs_shortest_path
andnetworkx.all_pairs_shortest_path_length
.They are not based on Floyd-Marshall (it is also in networkx but way slower)