Opened 12 years ago

Closed 11 years ago

#10905 closed enhancement (fixed)

shortest path all pairs through BFS computations.

Reported by: Nathann Cohen Owned by: tbd
Priority: major Milestone: sage-4.7
Component: graph theory Keywords:
Cc: ylchapuy, Minh Van Nguyen, Jason Grout, Robert Miller Merged in: sage-4.7.alpha5
Authors: Nathann Cohen Reviewers: Yann Laigle-Chapuy
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Jeroen Demeyer)

I do not think I can make them faster than that... Perhaps multithreading ? :-p

sage: g = graphs.PetersenGraph()
sage: %timeit g.shortest_path_all_pairs(algorithm = "BFS")
625 loops, best of 3: 321 µs per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-Cython")
625 loops, best of 3: 466 µs per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-Python")
125 loops, best of 3: 5.51 ms per loop
sage: g = graphs.Grid2dGraph(5,5)
sage: %timeit g.shortest_path_all_pairs(algorithm = "BFS")
125 loops, best of 3: 2.02 ms per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-Cython")
125 loops, best of 3: 3.29 ms per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-Python")
5 loops, best of 3: 117 ms per loop
sage: g = graphs.Grid2dGraph(15,15)
sage: %timeit g.shortest_path_all_pairs(algorithm = "BFS")
5 loops, best of 3: 157 ms per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-Cython")
5 loops, best of 3: 601 ms per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-Python")
Still running..

And for larger values ...

sage: g = graphs.Grid2dGraph(30,30)
sage: %time d=g.shortest_path_all_pairs(algorithm = "BFS")
CPU times: user 2.75 s, sys: 0.01 s, total: 2.76 s
Wall time: 2.76 s
sage: %time d=g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-Cython")
CPU times: user 34.71 s, sys: 0.08 s, total: 34.80 s
Wall time: 34.87 s

Method distance_all_pairs

sage: g = graphs.PetersenGraph()
sage: %timeit g.distance_all_pairs(algorithm="BFS")
625 loops, best of 3: 319 µs per loop
sage: %timeit g.distance_all_pairs(algorithm="Floyd-Warshall")
625 loops, best of 3: 222 µs per loop
sage: g = graphs.Grid2dGraph(20,20)
sage: %timeit g.distance_all_pairs(algorithm="BFS")
5 loops, best of 3: 536 ms per loop
sage: %timeit g.distance_all_pairs(algorithm="Floyd-Warshall")
5 loops, best of 3: 2.76 s per loop

Even improved, it still does not beat Floyd Warshall for small graphs... So for the moment, I made the distance_all_pairs method use BFS for graphs on more than 20 vertices and Floyd Warshall otherwise. Tell me if you think it sound.

sage: g = graphs.PetersenGraph()
sage: %timeit g.distance_all_pairs()
625 loops, best of 3: 222 µs per loop
sage: g = graphs.Grid2dGraph(20,20)
sage: %timeit g.distance_all_pairs()
5 loops, best of 3: 530 ms per loop

Perhaps the reason is that this new method still computes both paths and distances while it is not required for distance_all_pairs...

Nathann

Depends on :

Apply :

Attachments (4)

trac10905-efficiency_improvment.patch (2.4 KB) - added by ylchapuy 12 years ago.
apply after trac_10905.patch
trac10905-improve_via_out_neighbors_unsafe.patch (1.5 KB) - added by ylchapuy 12 years ago.
trac_10905-doctests.patch (2.4 KB) - added by Nathann Cohen 12 years ago.
trac_10905.patch (12.3 KB) - added by Nathann Cohen 11 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 12 years ago by Nathann Cohen

Description: modified (diff)
Status: newneeds_review

comment:2 Changed 12 years ago by ylchapuy

I do not think I can make them faster than that...

You can... see the following patch

Changed 12 years ago by ylchapuy

apply after trac_10905.patch

comment:3 Changed 12 years ago by ylchapuy

apply both trac_10905.patch and trac10905-efficiency_improvment.patch

comment:4 Changed 12 years ago by ylchapuy

It could even be around 25% faster using 'out_neighbors_unsafe'. I don't know if its legible to use it.

comment:5 Changed 12 years ago by ylchapuy

Component: PLEASE CHANGEgraph theory
Milestone: sage-4.7
Type: PLEASE CHANGEenhancement

comment:6 Changed 12 years ago by Nathann Cohen

Something needs to be done about that though :

sage: g = graphs.Grid2dGraph(50,50)
sage: %time d = g.shortest_path_all_pairs()
CPU times: user 6.17 s, sys: 0.25 s, total: 6.42 s
Wall time: 7.68 s
sage: get_memory_usage()
626.47265625
sage: sage: sage: %time d = g.shortest_path_all_pairs()
CPU times: user 9.57 s, sys: 1.32 s, total: 10.89 s
Wall time: 73.24 s
sage: get_memory_usage()
1095.99609375

Pretty... unpleasant :-p

Nathann

comment:7 in reply to:  6 Changed 12 years ago by Nathann Cohen

Pretty... unpleasant :-p

And most probably the weight of dictionary d in which I store the result of the method. Sorry for that :-D

Nathann

comment:8 Changed 12 years ago by ylchapuy

Status: needs_reviewneeds_work

Now that I stopped playing making it faster some remarks for the review:

  • doctest the ValueError? (and correct the small bug I guess)
  • same remark as #10855 concerning method vs function (might be irrelevant)
  • in generic_graph.py, lines 11088-11089: typo one Cython should be Python
  • doctest this ValueError? too
  • doctest the by_weight stuff

otherwise sounds good

comment:9 Changed 12 years ago by Nathann Cohen

Description: modified (diff)
Status: needs_workneeds_review

comment:10 Changed 12 years ago by Nathann Cohen

This patch addresses all the comments, except the by_weight stuff which is already tested in the large block of outputs :

sage: G.shortest_path_all_pairs(by_weight = True)

Nathann

comment:11 Changed 12 years ago by ylchapuy

last patch missing...

Changed 12 years ago by Nathann Cohen

Attachment: trac_10905-doctests.patch added

comment:12 Changed 12 years ago by Nathann Cohen

I ran some last "sage -t" and forgot it last time... Sorry ^^;

Nathann

comment:13 Changed 12 years ago by ylchapuy

Reviewers: Yann Laigle-Chapuy
Status: needs_reviewpositive_review

Sounds good to me now. Positive review.

comment:14 Changed 11 years ago by Jeroen Demeyer

Description: modified (diff)

comment:15 Changed 11 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

trac_10905.patch needs a proper commit message (use hg qrefresh -e to change the message).

comment:16 Changed 11 years ago by Nathann Cohen

Status: needs_workpositive_review

Done !

Nathann

Changed 11 years ago by Nathann Cohen

Attachment: trac_10905.patch added

comment:17 Changed 11 years ago by Jeroen Demeyer

Merged in: sage-4.7.alpha5
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.