shortest path all pairs through BFS computations.

[nathanncohen]

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 :

• Floyd-Warshall algorithm in Cython #10885

Apply :

• attachment: trac_10905.patch
• attachment: trac10905-efficiency_improvment.patch
• attachment: trac10905-improve_via_out_neighbors_unsafe.patch
• attachment: trac_10905-doctests.patch

CC: @sagetrac-ylchapuy @sagetrac-mvngu @jasongrout @rlmill

Component: graph theory

Author: Nathann Cohen

Reviewer: Yann Laigle-Chapuy

Merged: sage-4.7.alpha5

Issue created by migration from https://trac.sagemath.org/ticket/10905

[sagetrac-ylchapuy]

comment:2

I do not think I can make them faster than that...

You can... see the following patch

[sagetrac-ylchapuy]

apply after trac_10905.patch

[sagetrac-ylchapuy]

comment:3

Attachment: trac10905-efficiency_improvment.patch.gz

apply both trac_10905.patch and trac10905-efficiency_improvment.patch

[sagetrac-ylchapuy]

comment:4

It could even be around 25% faster using 'out_neighbors_unsafe'.
I don't know if its legible to use it.

[sagetrac-ylchapuy]

Attachment: trac10905-improve_via_out_neighbors_unsafe.patch.gz

[nathanncohen]

comment:6

Something needs to be done about that though :

sage: g = graphs.Grid2dGraph(50,50)
sage: %time d = g.shortest_path_all_pairs()
CPU times: user 6.17 s, sys: 0.25 s, total: 6.42 s
Wall time: 7.68 s
sage: get_memory_usage()
626.47265625
sage: sage: sage: %time d = g.shortest_path_all_pairs()
CPU times: user 9.57 s, sys: 1.32 s, total: 10.89 s
Wall time: 73.24 s
sage: get_memory_usage()
1095.99609375

Pretty... unpleasant :-p

Nathann

[nathanncohen]

comment:7

Pretty... unpleasant :-p

And most probably the weight of dictionary d in which I store the result of the method. Sorry for that :-D

Nathann

[sagetrac-ylchapuy]

comment:8

Now that I stopped playing making it faster some remarks for the review:

• doctest the ValueError (and correct the small bug I guess)
• same remark as reset() doesn't quite forget() #10855 concerning method vs function (might be irrelevant)
• in generic_graph.py, lines 11088-11089: typo one Cython should be Python
• doctest this ValueError too
• doctest the by_weight stuff

otherwise sounds good

[nathanncohen]

comment:10

This patch addresses all the comments, except the by_weight stuff which is already tested in the large block of outputs :

sage: G.shortest_path_all_pairs(by_weight = True)

Nathann

[sagetrac-ylchapuy]

comment:11

last patch missing...

[nathanncohen]

Attachment: trac_10905-doctests.patch.gz

[nathanncohen]

comment:12

I ran some last "sage -t" and forgot it last time... Sorry ^^;

Nathann

[sagetrac-ylchapuy]

Reviewer: Yann Laigle-Chapuy

[sagetrac-ylchapuy]

comment:13

Sounds good to me now. Positive review.

[jdemeyer]

comment:15

attachment: trac_10905.patch needs a proper commit message (use hg qrefresh -e to change the message).

[nathanncohen]

comment:16

Done !

Nathann

[nathanncohen]

Attachment: trac_10905.patch.gz

[jdemeyer]

Merged: sage-4.7.alpha5