Opened 10 years ago
Closed 10 years ago
#10905 closed enhancement (fixed)
shortest path all pairs through BFS computations.
Reported by: | ncohen | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7 |
Component: | graph theory | Keywords: | |
Cc: | ylchapuy, mvngu, jason, rlm | 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 10 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
apply both trac_10905.patch and trac10905-efficiency_improvment.patch
comment:4 Changed 10 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 10 years ago by
- Component changed from PLEASE CHANGE to graph theory
- Milestone set to sage-4.7
- Type changed from PLEASE CHANGE to enhancement
Changed 10 years ago by
comment:6 follow-up: ↓ 7 Changed 10 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 in reply to: ↑ 6 Changed 10 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 10 years ago by
- Status changed from needs_review to 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 10 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:10 Changed 10 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
comment:11 Changed 10 years ago by
last patch missing...
Changed 10 years ago by
comment:12 Changed 10 years ago by
I ran some last "sage -t" and forgot it last time... Sorry ^^;
Nathann
comment:13 Changed 10 years ago by
- Reviewers set to Yann Laigle-Chapuy
- Status changed from needs_review to positive_review
Sounds good to me now. Positive review.
comment:14 Changed 10 years ago by
- Description modified (diff)
comment:15 Changed 10 years ago by
- Status changed from positive_review to needs_work
trac_10905.patch needs a proper commit message (use hg qrefresh -e
to change the message).
Changed 10 years ago by
comment:17 Changed 10 years ago by
- Merged in set to sage-4.7.alpha5
- Resolution set to fixed
- Status changed from positive_review to closed
You can... see the following patch