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: |
Description (last modified by )
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)
Change History (21)
comment:1 Changed 12 years ago by
Description: | modified (diff) |
---|---|
Status: | new → needs_review |
comment:2 Changed 12 years ago by
Changed 12 years ago by
Attachment: | trac10905-efficiency_improvment.patch added |
---|
apply after trac_10905.patch
comment:3 Changed 12 years ago by
apply both trac_10905.patch and trac10905-efficiency_improvment.patch
comment:4 Changed 12 years ago by
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
Component: | PLEASE CHANGE → graph theory |
---|---|
Milestone: | → sage-4.7 |
Type: | PLEASE CHANGE → enhancement |
Changed 12 years ago by
Attachment: | trac10905-improve_via_out_neighbors_unsafe.patch added |
---|
comment:6 follow-up: 7 Changed 12 years ago by
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 Changed 12 years ago by
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
Status: | needs_review → needs_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
Description: | modified (diff) |
---|---|
Status: | needs_work → needs_review |
comment:10 Changed 12 years ago by
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
Changed 12 years ago by
Attachment: | trac_10905-doctests.patch added |
---|
comment:12 Changed 12 years ago by
I ran some last "sage -t" and forgot it last time... Sorry ^^;
Nathann
comment:13 Changed 12 years ago by
Reviewers: | → Yann Laigle-Chapuy |
---|---|
Status: | needs_review → positive_review |
Sounds good to me now. Positive review.
comment:14 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:15 Changed 11 years ago by
Status: | positive_review → needs_work |
---|
trac_10905.patch needs a proper commit message (use hg qrefresh -e
to change the message).
Changed 11 years ago by
Attachment: | trac_10905.patch added |
---|
comment:17 Changed 11 years ago by
Merged in: | → sage-4.7.alpha5 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
You can... see the following patch