Opened 6 years ago
Closed 6 years ago
#19252 closed enhancement (fixed)
Faster GridGraph generator
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  88436ad (Commits, GitHub, GitLab)  Commit:  88436ad0985e38f12da511a23b6cc3d0301c6341 
Dependencies:  Stopgaps: 
Description
We use a direct implementation that is way faster than NetworkX.
Before:
sage: %timeit graphs.GridGraph([2,3,4]) 1000 loops, best of 3: 1.44 ms per loop
After:
sage: %timeit graphs.GridGraph([2,3,4]) 10000 loops, best of 3: 209 µs per loop
Change History (15)
comment:1 Changed 6 years ago by
 Branch set to u/dcoudert/grid
comment:2 Changed 6 years ago by
 Commit set to cce82be5502edf1c27580e788bfded32876a043f
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to needs_work
Hello,
there is a broken doctest in boost_graph.pyx
. And your graph is empty on the list [1,1]
. Once this is fixed, you can set the ticket to positive_review
.
Nathann
comment:4 Changed 6 years ago by
 Commit changed from cce82be5502edf1c27580e788bfded32876a043f to 99ecb8bc636e0049ebcfa1db7a85b7eb3f01f174
Branch pushed to git repo; I updated commit sha1. New commits:
99ecb8b  trac #19252: implement rviewer's comments

comment:5 Changed 6 years ago by
 Status changed from needs_work to positive_review
Okayyyyyyyyyyyyyyy,
Nathann
comment:6 Changed 6 years ago by
 Status changed from positive_review to needs_work
Sorry, after pushing this commit, I realized that something was missing. Corrections are on the way.
comment:7 Changed 6 years ago by
 Commit changed from 99ecb8bc636e0049ebcfa1db7a85b7eb3f01f174 to 81db5e161372eb08a3b902883ab593c1cf3c8cad
Branch pushed to git repo; I updated commit sha1. New commits:
81db5e1  trac #19252: correct behavior with trivial cases

comment:8 Changed 6 years ago by
 Status changed from needs_work to needs_review
I have added doctests for trivial cases, and I'm now calling path and grid2d methods when appropriate to get position of vertices.
Should now be properly working. Thanks, David.
comment:9 Changed 6 years ago by
 Status changed from needs_review to positive_review
Okay (again).
Nathann
comment:10 Changed 6 years ago by
 Status changed from positive_review to needs_work
Arg no. Broken doctest. The same.
comment:11 Changed 6 years ago by
 Commit changed from 81db5e161372eb08a3b902883ab593c1cf3c8cad to 88436ad0985e38f12da511a23b6cc3d0301c6341
Branch pushed to git repo; I updated commit sha1. New commits:
88436ad  trac #19252: get back to original doctest in boost_graph.pyx

comment:13 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:14 Changed 6 years ago by
Thanks.
comment:15 Changed 6 years ago by
 Branch changed from u/dcoudert/grid to 88436ad0985e38f12da511a23b6cc3d0301c6341
 Resolution set to fixed
 Status changed from positive_review to closed
The
basic.py
file needs more documentation cleaning since many plot tests use networkx when it is not necessary. May be in another ticket.New commits:
trac #19252: new implementation
trac #19252: clean documentation of basic graph generators