Opened 10 years ago
Closed 10 years ago
#10885 closed enhancement (fixed)
Floyd-Warshall algorithm in Cython
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7 |
Component: | graph theory | Keywords: | |
Cc: | jason, rlm, mvngu | 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 10 years ago by
comment:1 Changed 10 years ago by
- Cc jason added
comment:2 Changed 10 years ago by
- Cc rlm added
- Status changed from new to needs_review
comment:3 Changed 10 years ago by
- Cc mvngu added
comment:4 Changed 10 years ago by
- Status changed from needs_review to 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.
comment:5 Changed 10 years ago by
apply both trac_10885.patch and trac10885-efficiency_improvment.patch
comment:6 Changed 10 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 10 years ago by
- Description modified (diff)
- Reviewers set to Nathann Cohen, Yann Laigle-Chapuy
- Status changed from needs_work to 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 10 years ago by
- Status changed from positive_review to 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 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to 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 10 years ago by
comment:10 in reply to: ↑ 9 Changed 10 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 10 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 10 years ago by
- Status changed from needs_review to positive_review
Ok, I have no strong feelings about this. I'll give this a positive review then.
comment:13 Changed 10 years ago by
Thank you for your help in optimizing the code :-)
Nathann
comment:14 Changed 10 years ago by
- Status changed from positive_review to needs_work
In the commit message of trac10855-efficiency_improvment_bug_correction.patch, the ticket number should be fixed.
comment:15 Changed 10 years ago by
Could you update it Yann ? I can not overwrite your patch ^^;
Nathann
Changed 10 years ago by
comment:16 Changed 10 years ago by
- Status changed from needs_work to needs_review
the name of the file is still wrong, but the commit message is now ok...
comment:17 Changed 10 years ago by
- Status changed from needs_review to positive_review
Thaaaaaaanks ! :-)
comment:18 Changed 10 years ago by
- Merged in set to sage-4.7.alpha4
- Resolution set to fixed
- Status changed from positive_review to closed
Passes all long tests !
:-)
Nathann