#10885: Floyd-Warshall algorithm in Cython
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.7
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10885>
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.
