Improve Depth First Search in c_graph.pyx

[kliem]

This ticket simply applies the improvements of #31117 to depth first search as well.

Before:

sage: def comp(): 
....:     for n in [5, 10, 50, 100, 500, 1000]: 
....:         G = graphs.Grid2dGraph(n, n)  
....:         print(G)  
....:         %timeit _ = list(G.depth_first_search(start=(0, 0))) 
....:                                                                                                                                                                               
sage: comp()                                                                                                                                                                        
2D Grid Graph for [5, 5]
8.11 µs ± 115 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
2D Grid Graph for [10, 10]
26.9 µs ± 64.3 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
2D Grid Graph for [50, 50]
827 µs ± 1.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
2D Grid Graph for [100, 100]
3.35 ms ± 5.38 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
2D Grid Graph for [500, 500]
115 ms ± 218 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
2D Grid Graph for [1000, 1000]
470 ms ± 882 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

After:

sage: def comp(): 
....:     for n in [5, 10, 50, 100, 500, 1000]: 
....:         G = graphs.Grid2dGraph(n, n)  
....:         print(G)  
....:         %timeit _ = list(G.depth_first_search(start=(0, 0))) 
....:                                                                                                                                                                               
sage: comp()                                                                                                                                                                        
2D Grid Graph for [5, 5]
4.41 µs ± 12.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
2D Grid Graph for [10, 10]
13.2 µs ± 27.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
2D Grid Graph for [50, 50]
409 µs ± 225 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
2D Grid Graph for [100, 100]
1.67 ms ± 7.46 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
2D Grid Graph for [500, 500]
65.8 ms ± 54.2 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
2D Grid Graph for [1000, 1000]
264 ms ± 331 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

Depends on #31117

CC: @dcoudert

Component: graph theory

Author: Jonathan Kliem

Branch/Commit: 78d5536

Reviewer: David Coudert

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

[kliem]

Last 10 new commits:

156d222	further improvement
e56743b	revert last commit because some methods are not in all backends
e4415f9	trac #31117: merged with 9.3.beta5
c342fe6	trac #31117: better bfs
65e677e	implement next_out_neighbor for static sparse
b7e8a20	Merge branch 'u/gh-kliem/next_out_neighbor_for_static_sparse' of git://trac.sagemath.org/sage into public/graphs/31117_BFS
eaf982b	use next_out_neighbor_unsafe
4fd001e	reuse queue
cc0cfd1	account for that the loop is an if-clause now
606c8cf	improvements for depth_first_search

[kliem]

Commit: 606c8cf

[kliem]

Branch: public/31129

[dcoudert]

comment:2

The errors reported by the patchbot are fixed in #31117. This ticket must be rebased to get last commit.

[sagetrac-git]

Changed commit from 606c8cf to 78d5536

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

07eaaa5	inlining makes a difference
c005179	improvements for depth_first_search
78d5536	trac #31117: fix next_in_neighbor_unsafe in static_sparse_backend

[dcoudert]

comment:4

We have a green bot and it's much faster this way. Perfect !

[dcoudert]

Reviewer: David Coudert

[kliem]

comment:5

Thank you.

[kliem]

comment:6

Btw, yield from also gives a significant improvement, I will do this in a follow up.

[vbraun]

Changed branch from public/31129 to 78d5536