[Nauty] genbg and res/mod

Jernej Azarija jernej.azarija at gmail.com
Thu Nov 26 07:10:29 AEDT 2015


Hello!

I need to use genbg quite a bit and hence would like to be able to
split graph generation into smaller instances.

Based on what is written in geng.c I got the idea that using different
values of mod should give disjoint sets of graphs. Am I correct? The
reason that I am asking this is because it seems that is not the case:

$ genbg -u 6 6 0/1000000
>A genbg n=6+6 e=0:36 d=0:0 D=6:6  class=0/1000000
>Z 251610 graphs generated in 0.21 sec
$ genbg -u 6 6 1/1000000
>A genbg n=6+6 e=0:36 d=0:0 D=6:6  class=1/1000000
>Z 1 graphs generated in 0.08 sec

as well as

$ genbg -u 6 6
>A genbg n=6+6 e=0:36 d=0:0 D=6:6
>Z 251610 graphs generated in 0.22 sec

So I often encounter that some value of res will in fact give the
entire class of graphs and the other values overlap graphs.

$ genbg -u 7 7 0/10
>A genbg n=7+7 e=0:49 d=0:0 D=7:7  class=0/10
>Z 3366061 graphs generated in 8.36 sec
$ genbg -u 7 7 1/10
>A genbg n=7+7 e=0:49 d=0:0 D=7:7  class=1/10
>Z 33642660 graphs generated in 21.16 sec

$ genbg -u 7 7
>A genbg n=7+7 e=0:49 d=0:0 D=7:7
>Z 33642660 graphs generated in 21.01 sec

The same thing seems to happen no matter what value of mod I pick.

$ genbg -u 7 7 1/1000000
>A genbg n=7+7 e=0:49 d=0:0 D=7:7  class=1/1000000
>Z 33642660 graphs generated in 21.16 sec
$ genbg -u 7 7 100/1000000
>A genbg n=7+7 e=0:49 d=0:0 D=7:7  class=100/1000000
>Z 33642660 graphs generated in 19.38 sec


Hence it takes much more time to use res/mod than simply avoiding it.
Am I missing something or is there something wrong with the above
behavior of genbg?

Best,

Jernej


More information about the Nauty mailing list