Opened 8 years ago

Closed 8 years ago

#10905 closed enhancement (fixed)

shortest path all pairs through BFS computations.

Reported by: ncohen Owned by: tbd
Priority: major Milestone: sage-4.7
Component: graph theory Keywords:
Cc: ylchapuy, mvngu, jason, rlm Merged in: sage-4.7.alpha5
Authors: Nathann Cohen Reviewers: Yann Laigle-Chapuy
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

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 :

Apply :

Attachments (4)

trac10905-efficiency_improvment.patch (2.4 KB) - added by ylchapuy 8 years ago.
apply after trac_10905.patch
trac10905-improve_via_out_neighbors_unsafe.patch (1.5 KB) - added by ylchapuy 8 years ago.
trac_10905-doctests.patch (2.4 KB) - added by ncohen 8 years ago.
trac_10905.patch (12.3 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by ylchapuy

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

You can... see the following patch

Changed 8 years ago by ylchapuy

apply after trac_10905.patch

comment:3 Changed 8 years ago by ylchapuy

apply both trac_10905.patch and trac10905-efficiency_improvment.patch

comment:4 Changed 8 years ago by ylchapuy

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

comment:5 Changed 8 years ago by ylchapuy

  • Component changed from PLEASE CHANGE to graph theory
  • Milestone set to sage-4.7
  • Type changed from PLEASE CHANGE to enhancement

comment:6 follow-up: Changed 8 years ago by ncohen

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

comment:7 in reply to: ↑ 6 Changed 8 years ago by ncohen

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

comment:8 Changed 8 years ago by ylchapuy

  • Status changed from needs_review to needs_work

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

comment:9 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:10 Changed 8 years ago by ncohen

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

comment:11 Changed 8 years ago by ylchapuy

last patch missing...

Changed 8 years ago by ncohen

comment:12 Changed 8 years ago by ncohen

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

Nathann

comment:13 Changed 8 years ago by ylchapuy

  • Reviewers set to Yann Laigle-Chapuy
  • Status changed from needs_review to positive_review

Sounds good to me now. Positive review.

comment:14 Changed 8 years ago by jdemeyer

  • Description modified (diff)

comment:15 Changed 8 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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

comment:16 Changed 8 years ago by ncohen

  • Status changed from needs_work to positive_review

Done !

Nathann

Changed 8 years ago by ncohen

comment:17 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.