#10885: Floyd-Warshall algorithm in Cython
-------------------------------------------------+--------------------------
Reporter: ncohen | Owner: jason, ncohen,
rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: graph theory | Keywords:
Author: Nathann Cohen, Yann Laigle-Chapuy | Upstream: N/A
Reviewer: Nathann Cohen, Yann Laigle-Chapuy | Merged:
Work_issues: |
-------------------------------------------------+--------------------------
Changes (by ncohen):
* status: needs_work => needs_review
Old description:
> 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.
New description:
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
--
Comment:
Replying to [comment:8 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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10885#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
