Opened 12 years ago
Closed 12 years ago
#10885 closed enhancement (fixed)
Floyd-Warshall algorithm in Cython
Reported by: | Nathann Cohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7 |
Component: | graph theory | Keywords: | |
Cc: | Jason Grout, Robert Miller, Minh Van Nguyen | Merged in: | sage-4.7.alpha4 |
Authors: | Nathann Cohen, Yann Laigle-Chapuy | Reviewers: | Nathann Cohen, Yann Laigle-Chapuy |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch implements a Cython version of the Floyd-Warshall algorithm currently available in Sage. Both stay implemented, as the Cython version only deals with unweighted graphs, and prefers to add integer values than Python objects anyway.
The performance improvement is obvious for the all_pairs_shortest_path
method which used by default the Python implementation
The new implementation is now the default.
Meanwhile, the method distance_all_pairs
which already used Cython code is not always improved
sage: g = graphs.PetersenGraph() sage: %timeit g.distance_all_pairs() 625 loops, best of 3: 660 µs per loop sage: %timeit g.distance_all_pairs(algorithm="Floyd-Warshall") 625 loops, best of 3: 263 µs per loop sage: g = graphs.Grid2dGraph(20,20) sage: %timeit g.distance_all_pairs() 5 loops, best of 3: 951 ms per loop sage: %timeit g.distance_all_pairs(algorithm="Floyd-Warshall") 5 loops, best of 3: 3.08 s per loop
Hence the default behaviour of this method does not change, the two algorithms being made available.
Apply :
- trac_10885.patch
- trac10885-efficiency_improvment.patch
- trac10855-efficiency_improvment_bug_correction.patch
- trac_10885-documentation.patch
Attachments (4)
Change History (22)
Changed 12 years ago by
Attachment: | trac_10885.patch added |
---|
comment:1 Changed 12 years ago by
Cc: | Jason Grout added |
---|
comment:2 Changed 12 years ago by
Cc: | Robert Miller added |
---|---|
Status: | new → needs_review |
comment:3 Changed 12 years ago by
Cc: | Minh Van Nguyen added |
---|
comment:4 Changed 12 years ago by
Status: | needs_review → needs_work |
---|
You can easily improve a lot the efficiency by:
- cdefing list gverts = g.verts()
- using g instead of gg._backend._cg
- cdefing two dicts variables for gg._backend.vertex_ints and gg._backend.vertex_labels as well
- in the main triple loop, cdefing two vars dv = dist[v_int] and dw = dist[w_int] as outside as possible
Also anything dealing with prec should only be done it paths=True. This can save half the memory when not needed.
Changed 12 years ago by
Attachment: | trac10885-efficiency_improvment.patch added |
---|
apply after trac_10885.patch
comment:5 Changed 12 years ago by
apply both trac_10885.patch and trac10885-efficiency_improvment.patch
comment:6 Changed 12 years ago by
I left a small bug in my last patch. Apply in order trac_10885.patch trac10885-efficiency_improvment.patch and trac10855-efficiency_improvment_bug_correction.patch
comment:7 Changed 12 years ago by
Authors: | Nathann Cohen → Nathann Cohen, Yann Laigle-Chapuy |
---|---|
Description: | modified (diff) |
Reviewers: | → Nathann Cohen, Yann Laigle-Chapuy |
Status: | needs_work → positive_review |
Greaaaaat !! Thank you for your help ! I still have many tricks to learn :-)
Passes all tests, does its job even faster... Niiiiice !
Nathann
comment:8 follow-up: 9 Changed 12 years ago by
Status: | positive_review → needs_work |
---|
Sorry to bother you, but formally I didn't gave you a positive review.
E.g is there any reason 'floyd_warshall' is a function rather than a method like 'breadth_first_search' ?
You might also add one doctest for the ValueError? and one for paths=False and distances=True.
comment:9 follow-up: 10 Changed 12 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → needs_review |
Replying to ylchapuy:
Sorry to bother you, but formally I didn't gave you a positive review.
Oh. Right. My mistake.
E.g is there any reason 'floyd_warshall' is a function rather than a method like 'breadth_first_search' ?
Well, what would it return ? There is already a shortest_path_all pairs and distance_all_pairs in the Graph method, and Floyd-Warshall is not always the fastest available.
You might also add one doctest for the ValueError? and one for paths=False and distances=True.
Done !
Nathann
Changed 12 years ago by
Attachment: | trac_10885-documentation.patch added |
---|
comment:10 Changed 12 years ago by
Replying to ncohen:
Replying to ylchapuy:
E.g is there any reason 'floyd_warshall' is a function rather than a method like 'breadth_first_search' ?
Well, what would it return ? There is already a shortest_path_all pairs and distance_all_pairs in the Graph method, and Floyd-Warshall is not always the fastest available.
I'm not sure I follow the argument: it does return something, and it's even documented... Maybe call it '_floyd_warshall' if you don't want the user to access it.
I might be wrong but it seems to me Sage convention is to prefer methods instead of functions. Jason, Robert, Minh, any preference on this matter?
You might also add one doctest for the ValueError? and one for paths=False and distances=True.
Done !
Great, and it even removed a bug ;)
Nathann
comment:11 Changed 12 years ago by
I'm not sure I follow the argument: it does return something, and it's even documented... Maybe call it '_floyd_warshall' if you don't want the user to access it.
Well, it can be renamed to _floyd_warshall if you want, but really anybody who would begin to list what is included inside this module will not really care about this _. There are several functions there already, which they are used by methods of the generic_graph file (a python file actually, though there also is a .pyx one).
Oh, and yes it's documented, like always. A patch to get the graph/ to 100% coverage was just finished, and I'm not going to spoil that by forgetting my methods :-p
Nathann
comment:12 Changed 12 years ago by
Status: | needs_review → positive_review |
---|
Ok, I have no strong feelings about this. I'll give this a positive review then.
comment:14 Changed 12 years ago by
Status: | positive_review → needs_work |
---|
In the commit message of trac10855-efficiency_improvment_bug_correction.patch, the ticket number should be fixed.
comment:15 Changed 12 years ago by
Could you update it Yann ? I can not overwrite your patch ^^;
Nathann
Changed 12 years ago by
Attachment: | trac10855-efficiency_improvment_bug_correction.patch added |
---|
comment:16 Changed 12 years ago by
Status: | needs_work → needs_review |
---|
the name of the file is still wrong, but the commit message is now ok...
comment:18 Changed 12 years ago by
Merged in: | → sage-4.7.alpha4 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Passes all long tests !
:-)
Nathann