Make nauty's geng work as a generator

[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. attachment: trac_11340-nauty-geng-generator-v2.patch

CC: @nathanncohen @sagetrac-fidelbarrera

Component: graph theory

Author: Rob Beezer

Reviewer: Nathann Cohen

Merged: sage-4.7.1.alpha2

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

[rbeezer]

Attachment: trac_11340-nauty-geng-generator.patch.gz

[rbeezer]

Author: Rob Beezer

[nathanncohen]

comment:2

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

[rbeezer]

comment:3

Attachment: trac_11340-nauty-geng-generator-v2.patch.gz

Replying to @nathanncohen:

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

[nathanncohen]

comment:4

Goooooooood to go ! :-)

Thanks !!

Nathann

[rbeezer]

comment:5

Replying to @nathanncohen:

Goooooooood to go ! :-)

Thanks for the quick review!

Rob

[nathanncohen]

comment:6

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

[kiwifb]

Reviewer: Nathann Cohen

[jdemeyer]

Merged: sage-4.7.1.alpha2