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 ncohen)

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 ylchapuy

then... use networkx. More precisely, networkx.all_pairs_shortest_path and networkx.all_pairs_shortest_path_length.

They are not based on Floyd-Marshall (it is also in networkx but way slower)

comment:2 Changed 11 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 11 years ago by ncohen

  • 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.