#31129 closed enhancement (fixed)

Improve Depth First Search in c_graph.pyx

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.3
Component: graph theory Keywords:
Cc: dcoudert Merged in:
Authors: Jonathan Kliem Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 78d5536 (Commits, GitHub, GitLab) Commit: 78d553636cb4b07d51564de48ce87d1c48b7336e
Dependencies: #31117 Stopgaps:

Status badges

Description (last modified by gh-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)

Change History (7)

comment:1 Changed 11 months ago by gh-kliem

  • Branch set to public/31129
  • Commit set to 606c8cf63af77f03c939c4ab9b7c2537d7dde342
  • Description modified (diff)
  • Status changed from new to needs_review

Last 10 new commits:

156d222further improvement
e56743brevert last commit because some methods are not in all backends
e4415f9trac #31117: merged with 9.3.beta5
c342fe6trac #31117: better bfs
65e677eimplement next_out_neighbor for static sparse
b7e8a20Merge branch 'u/gh-kliem/next_out_neighbor_for_static_sparse' of git://trac.sagemath.org/sage into public/graphs/31117_BFS
eaf982buse next_out_neighbor_unsafe
4fd001ereuse queue
cc0cfd1account for that the loop is an if-clause now
606c8cfimprovements for depth_first_search

comment:2 Changed 11 months ago by dcoudert

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

comment:3 Changed 11 months ago by git

  • Commit changed from 606c8cf63af77f03c939c4ab9b7c2537d7dde342 to 78d553636cb4b07d51564de48ce87d1c48b7336e

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

07eaaa5inlining makes a difference
c005179improvements for depth_first_search
78d5536trac #31117: fix next_in_neighbor_unsafe in static_sparse_backend

comment:4 Changed 11 months ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to positive_review

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

comment:5 Changed 11 months ago by gh-kliem

Thank you.

comment:6 Changed 11 months ago by gh-kliem

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

comment:7 Changed 11 months ago by vbraun

  • Branch changed from public/31129 to 78d553636cb4b07d51564de48ce87d1c48b7336e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.