Opened 8 years ago

Closed 8 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 ncohen)

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 ncohen 8 years ago.
trac10885-efficiency_improvment.patch (8.7 KB) - added by ylchapuy 8 years ago.
apply after trac_10885.patch
trac_10885-documentation.patch (2.3 KB) - added by ncohen 8 years ago.
trac10855-efficiency_improvment_bug_correction.patch (684 bytes) - added by ylchapuy 8 years ago.

Download all attachments as: .zip

Change History (22)

Changed 8 years ago by ncohen

comment:1 Changed 8 years ago by jason

  • Cc jason added

comment:2 Changed 8 years ago by ncohen

  • Cc rlm added
  • Status changed from new to needs_review

Passes all long tests ! :-)

Nathann

comment:3 Changed 8 years ago by mvngu

  • Cc mvngu added

comment:4 Changed 8 years ago by ylchapuy

  • 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.

Changed 8 years ago by ylchapuy

apply after trac_10885.patch

comment:5 Changed 8 years ago by ylchapuy

apply both trac_10885.patch and trac10885-efficiency_improvment.patch

comment:6 Changed 8 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 8 years ago by ncohen

  • Authors changed from Nathann Cohen to Nathann Cohen, Yann Laigle-Chapuy
  • 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: Changed 8 years ago by ylchapuy

  • 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: Changed 8 years ago by ncohen

  • 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 8 years ago by ncohen

comment:10 in reply to: ↑ 9 Changed 8 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 8 years ago by ncohen

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 8 years ago by ylchapuy

  • 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 8 years ago by ncohen

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

Nathann

comment:14 Changed 8 years ago by jdemeyer

  • 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 8 years ago by ncohen

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

Nathann

comment:16 Changed 8 years ago by ylchapuy

  • 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 8 years ago by ncohen

  • Status changed from needs_review to positive_review

Thaaaaaaanks ! :-)

comment:18 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.