Opened 10 years ago

Closed 10 years ago

#11340 closed defect (fixed)

Make nauty's geng work as a generator

Reported by: rbeezer Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-4.7.1
Component: graph theory Keywords:
Cc: ncohen, fidelbarrera Merged in: sage-4.7.1.alpha2
Authors: Rob Beezer Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rbeezer)

Output produced by nauty's geng program can be quite large. Currently, an entire list is created and returned. The 1,018,997,864 graphs on n=11 vertices can overwhelm RAM when produced all at once. This patch reorganizes the nauty_geng() command to produce a generator, so graphs can be created, tested and then discarded or saved - which would be the typical use of this command. Of course, for smaller values of n it is still possible to quickly build a list from the generator.

This also upgrades the system call, since os.popen() is deprecated in Python.

Apply:

  1. trac_11340-nauty-geng-generator-v2.patch

Attachments (2)

trac_11340-nauty-geng-generator.patch (6.6 KB) - added by rbeezer 10 years ago.
trac_11340-nauty-geng-generator-v2.patch (6.9 KB) - added by rbeezer 10 years ago.

Download all attachments as: .zip

Change History (10)

Changed 10 years ago by rbeezer

comment:1 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • Cc ncohen fidelbarrera added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 follow-up: Changed 10 years ago by ncohen

Nice patch ! :-)

Everything seems perfect, and I just have a question : what about removing the options which change the output, as the method would not be able to cast them to Sage graph ? If it is just in case the user would like to change the output with "debug = True", what about : "do not set an option to change this default or results will be unpredictable, unless debug is set to True" ?

Nathann

Changed 10 years ago by rbeezer

comment:3 in reply to: ↑ 2 Changed 10 years ago by rbeezer

  • Description modified (diff)

Replying to ncohen:

I just have a question : what about removing the options which change the output, as the method would not be able to cast them to Sage graph ?

Nathann - thanks for having a look at this. That's a good point - no reason to advertise options that would be harmful. I had not taken such a close look at what I was putting there.

v2 patch is standalone, it removes these options from the list, and adds a bit more commentary about these options. I also spruced up the doctests a bit. No changes to the code.

Thanks, Rob

comment:4 follow-up: Changed 10 years ago by ncohen

  • Status changed from needs_review to positive_review

Goooooooood to go ! :-)

Thanks !!

Nathann

comment:5 in reply to: ↑ 4 Changed 10 years ago by rbeezer

Replying to ncohen:

Goooooooood to go ! :-)

Thanks for the quick review!

Rob

comment:6 Changed 10 years ago by ncohen

I try to keep the tickets waiting for review in the Graph section to the bare minimum : those I can not review myself :-D

Nathann

comment:7 Changed 10 years ago by fbissey

  • Reviewers set to Nathann Cohen

comment:8 Changed 10 years ago by jdemeyer

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