Opened 6 years ago

Closed 6 years ago

#19252 closed enhancement (fixed)

Faster GridGraph generator

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-6.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:

Status badges

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 dcoudert

  • Branch set to u/dcoudert/grid

comment:2 Changed 6 years ago by dcoudert

  • Commit set to cce82be5502edf1c27580e788bfded32876a043f
  • Status changed from new to needs_review

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:

95aca9etrac #19252: new implementation
cce82betrac #19252: clean documentation of basic graph generators

comment:3 Changed 6 years ago by ncohen

  • 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 git

  • Commit changed from cce82be5502edf1c27580e788bfded32876a043f to 99ecb8bc636e0049ebcfa1db7a85b7eb3f01f174

Branch pushed to git repo; I updated commit sha1. New commits:

99ecb8btrac #19252: implement rviewer's comments

comment:5 Changed 6 years ago by ncohen

  • Status changed from needs_work to positive_review

Okayyyyyyyyyyyyyyy,

Nathann

comment:6 Changed 6 years ago by dcoudert

  • 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 git

  • Commit changed from 99ecb8bc636e0049ebcfa1db7a85b7eb3f01f174 to 81db5e161372eb08a3b902883ab593c1cf3c8cad

Branch pushed to git repo; I updated commit sha1. New commits:

81db5e1trac #19252: correct behavior with trivial cases

comment:8 Changed 6 years ago by dcoudert

  • 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 ncohen

  • Status changed from needs_review to positive_review

Okay (again).

Nathann

comment:10 Changed 6 years ago by ncohen

  • Status changed from positive_review to needs_work

Arg no. Broken doctest. The same.

comment:11 Changed 6 years ago by git

  • Commit changed from 81db5e161372eb08a3b902883ab593c1cf3c8cad to 88436ad0985e38f12da511a23b6cc3d0301c6341

Branch pushed to git repo; I updated commit sha1. New commits:

88436adtrac #19252: get back to original doctest in boost_graph.pyx

comment:12 Changed 6 years ago by dcoudert

  • Status changed from needs_work to needs_review

oupss.

comment:13 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:14 Changed 6 years ago by dcoudert

Thanks.

comment:15 Changed 6 years ago by vbraun

  • Branch changed from u/dcoudert/grid to 88436ad0985e38f12da511a23b6cc3d0301c6341
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.