#10905: shortest path all pairs through BFS computations.
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: tbd
Type: PLEASE CHANGE | Status: new
Priority: major | Milestone:
Component: PLEASE CHANGE | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
I do not think I can make them faster than that... Perhaps multithreading
? :-p
{{{
sage: g = graphs.PetersenGraph()
sage: %timeit g.shortest_path_all_pairs(algorithm = "BFS")
625 loops, best of 3: 321 µs per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-
Cython")
625 loops, best of 3: 466 µs per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-
Python")
125 loops, best of 3: 5.51 ms per loop
}}}
{{{
sage: g = graphs.Grid2dGraph(5,5)
sage: %timeit g.shortest_path_all_pairs(algorithm = "BFS")
125 loops, best of 3: 2.02 ms per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-
Cython")
125 loops, best of 3: 3.29 ms per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-
Python")
5 loops, best of 3: 117 ms per loop
}}}
{{{
sage: g = graphs.Grid2dGraph(15,15)
sage: %timeit g.shortest_path_all_pairs(algorithm = "BFS")
5 loops, best of 3: 157 ms per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-
Cython")
5 loops, best of 3: 601 ms per loop
sage: %timeit g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-
Python")
Still running..
}}}
And for larger values ...
{{{
sage: g = graphs.Grid2dGraph(30,30)
sage: %time d=g.shortest_path_all_pairs(algorithm = "BFS")
CPU times: user 2.75 s, sys: 0.01 s, total: 2.76 s
Wall time: 2.76 s
sage: %time d=g.shortest_path_all_pairs(algorithm = "Floyd-Warshall-
Cython")
CPU times: user 34.71 s, sys: 0.08 s, total: 34.80 s
Wall time: 34.87 s
}}}
Method ``distance_all_pairs``
{{{
sage: g = graphs.PetersenGraph()
sage: %timeit g.distance_all_pairs(algorithm="BFS")
625 loops, best of 3: 319 µs per loop
sage: %timeit g.distance_all_pairs(algorithm="Floyd-Warshall")
625 loops, best of 3: 222 µs per loop
sage: g = graphs.Grid2dGraph(20,20)
sage: %timeit g.distance_all_pairs(algorithm="BFS")
5 loops, best of 3: 536 ms per loop
sage: %timeit g.distance_all_pairs(algorithm="Floyd-Warshall")
5 loops, best of 3: 2.76 s per loop
}}}
Even improved, it still does not beat Floyd Warshall for small graphs...
So for the moment, I made the ``distance_all_pairs`` method use BFS for
graphs on more than 20 vertices and Floyd Warshall otherwise. Tell me if
you think it sound.
{{{
sage: g = graphs.PetersenGraph()
sage: %timeit g.distance_all_pairs()
625 loops, best of 3: 222 µs per loop
sage: g = graphs.Grid2dGraph(20,20)
sage: %timeit g.distance_all_pairs()
5 loops, best of 3: 530 ms per loop
}}}
Perhaps the reason is that this new method still computes both paths and
distances while it is not required for distance_all_pairs...
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10905>
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.
