#10885: Floyd-Warshall algorithm in Cython
-------------------------------------------------+--------------------------
Reporter: ncohen | Owner: jason, ncohen,
rlm
Type: enhancement | Status:
positive_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 newvalueoldvalue):
* status: needs_work => positive_review
* reviewer: => Nathann Cohen, Yann Laigle-Chapuy
* author: Nathann Cohen => Nathann Cohen, Yann Laigle-Chapuy
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
> {{{
> sage: g = graphs.PetersenGraph()
> sage: %timeit g.shortest_path_all_pairs()
> 625 loops, best of 3: 555 µs per loop
> sage: %timeit g.shortest_path_all_pairs(by_weight=True)
> 125 loops, best of 3: 6.44 ms per loop
> sage: g = graphs.Grid2dGraph(5,5)
> sage: %timeit g.shortest_path_all_pairs()
> 125 loops, best of 3: 3.77 ms per loop
> sage: %timeit g.shortest_path_all_pairs(by_weight=True)
> 5 loops, best of 3: 133 ms per loop
> sage: g = graphs.Grid2dGraph(15,15)
> sage: %timeit g.shortest_path_all_pairs()
> 5 loops, best of 3: 753 ms per loop
> sage: %timeit g.shortest_path_all_pairs(by_weight=True)
> (still running)
> }}}
> 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.
--
Comment:
Greaaaaat !! Thank you for your help ! I still have many tricks to learn
`:-)`
Passes all tests, does its job even faster... Niiiiice !
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10885#comment:7>
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.
