#10905: shortest path all pairs through BFS computations.
-----------------------------+----------------------------------------------
Reporter: ncohen | Owner: tbd
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: graph theory | Keywords:
Author: Nathann Cohen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Changes (by ncohen):
* status: needs_work => needs_review
Old description:
> 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
>
> Depends on :
> * #10885
New description:
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
Depends on :
* #10885
Apply :
* trac_10905.patch
* trac10905-efficiency_improvment.patch
* trac10905-improve_via_out_neighbors_unsafe.patch
* trac_10905-doctests.patch
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10905#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.
