shortest path all pairs through BFS computations.

[Nathann Cohen]

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​

[ylchapuy]

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

You can... see the following patch

[ylchapuy]

apply after trac_10905.patch

[ylchapuy]

apply both trac_10905.patch and trac10905-efficiency_improvment.patch

[ylchapuy]

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

[Nathann Cohen]

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

[Nathann Cohen]

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

[ylchapuy]

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 #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

[Nathann Cohen]

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

[ylchapuy]

last patch missing...

[Nathann Cohen]

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

Nathann

[ylchapuy]

Sounds good to me now. Positive review.

[Jeroen Demeyer]

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

[Nathann Cohen]

Done !

Nathann