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:

Status badges

Description (last modified by Nathann Cohen)

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)

trac_10885.patch (14.1 KB) - added by Nathann Cohen 12 years ago.
trac10885-efficiency_improvment.patch (8.7 KB) - added by ylchapuy 12 years ago.
apply after trac_10885.patch
trac_10885-documentation.patch (2.3 KB) - added by Nathann Cohen 12 years ago.
trac10855-efficiency_improvment_bug_correction.patch (684 bytes) - added by ylchapuy 12 years ago.

Download all attachments as: .zip

Change History (22)

Changed 12 years ago by Nathann Cohen

Attachment: trac_10885.patch added

comment:1 Changed 12 years ago by Jason Grout

Cc: Jason Grout added

comment:2 Changed 12 years ago by Nathann Cohen

Cc: Robert Miller added
Status: newneeds_review

Passes all long tests ! :-)

Nathann

comment:3 Changed 12 years ago by Minh Van Nguyen

Cc: Minh Van Nguyen added

comment:4 Changed 12 years ago by ylchapuy

Status: needs_reviewneeds_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 ylchapuy

apply after trac_10885.patch

comment:5 Changed 12 years ago by ylchapuy

apply both trac_10885.patch and trac10885-efficiency_improvment.patch

comment:6 Changed 12 years ago by ylchapuy

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 Nathann Cohen

Authors: Nathann CohenNathann Cohen, Yann Laigle-Chapuy
Description: modified (diff)
Reviewers: Nathann Cohen, Yann Laigle-Chapuy
Status: needs_workpositive_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 Changed 12 years ago by ylchapuy

Status: positive_reviewneeds_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 ; Changed 12 years ago by Nathann Cohen

Description: modified (diff)
Status: needs_workneeds_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 Nathann Cohen

comment:10 in reply to:  9 Changed 12 years ago by ylchapuy

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 Nathann Cohen

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 ylchapuy

Status: needs_reviewpositive_review

Ok, I have no strong feelings about this. I'll give this a positive review then.

comment:13 Changed 12 years ago by Nathann Cohen

Thank you for your help in optimizing the code :-)

Nathann

comment:14 Changed 12 years ago by Jeroen Demeyer

Status: positive_reviewneeds_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 Nathann Cohen

Could you update it Yann ? I can not overwrite your patch ^^;

Nathann

comment:16 Changed 12 years ago by ylchapuy

Status: needs_workneeds_review

the name of the file is still wrong, but the commit message is now ok...

comment:17 Changed 12 years ago by Nathann Cohen

Status: needs_reviewpositive_review

Thaaaaaaanks ! :-)

comment:18 Changed 12 years ago by Jeroen Demeyer

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