[Nauty] genbg and res/mod

[Jernej Azarija]

Dear Brendan,

thank you for your reply. Since you mention undocumented options - is
there any stronger  analogue for -Z?

I would like to generate cubic bipartite graphs of order 36 such that
any two vertices have at most 2 common neighbors. Right now I am
running ./genbg 18 18 -d3 -D3 -Z2 together with a prune function for
the first class. The problem is that such prune is only efficient
after adding ~14 vertices and so not even splitting the search seems
to work.

Best,

Jernej

On Wed, Nov 25, 2015 at 11:55 PM, Brendan McKay
<Brendan.McKay at anu.edu.au> wrote:
> Hi Jernej,  Thanks for your mails.  I'm a bit puzzled as I don't recall that
> problem occurring in version 2.4.
>
> The splitting works by cutting the search tree into lots of pieces, but
> since the tree has unknown structure and can be very irregular there
> can be cases where some pieces turn out to be much larger than
> the others.  There is an undocumented switch that tells it to work
> harder to make the splitting more even, at the cost of additional
> overhead in every run.  Usage like -X1 or -X2.
>
> Cheers, Brendan.
>
>
> On 26/11/2015 7:56 AM, Jernej Azarija wrote:
>>
>> Hello!
>>
>> Thanks for this! It turns out that Ubuntu is shipping version 2.4
>> which apparently does not work properly. mod/res Indeed works fine on
>> a compiled version of nauty 2.5.
>>
>> Best,
>>
>> Jernej
>>
>> On Wed, Nov 25, 2015 at 9:56 PM, Jernej Azarija
>> <jernej.azarija at gmail.com> wrote:
>>>
>>> Hello!
>>>
>>> Thanks for this! It turns out that Ubuntu is shipping version 2.4
>>> which apparently does not work properly. mod/res Indeed works fine on
>>> a compiled version of nauty 2.5.
>>>
>>> Best,
>>>
>>> Jernej
>>>
>>> On Wed, Nov 25, 2015 at 9:24 PM, Sean A. Irvine <sairvin at gmail.com>
>>> wrote:
>>>>
>>>> Which version do you have?  It seems to be working fine for me (with
>>>> 2.5):
>>>>
>>>> $ genbg -u 6 6 0/1000000
>>>>>
>>>>> A genbg n=6+6 e=0:36 d=0:0 D=6:6  class=0/1000000
>>>>> Z 0 graphs generated in 0.00 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 50 graphs generated in 0.00 sec
>>>>
>>>> $ genbg -u 6 6
>>>>>
>>>>> A genbg n=6+6 e=0:36 d=0:0 D=6:6
>>>>> Z 251610 graphs generated in 0.25 sec
>>>>
>>>> On 26 November 2015 at 09:10, Jernej Azarija <jernej.azarija at gmail.com>
>>>> wrote:
>>>>>
>>>>> 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
>>>>> _______________________________________________
>>>>> Nauty mailing list
>>>>> Nauty at anu.edu.au
>>>>> http://mailman.anu.edu.au/mailman/listinfo/nauty
>>
>> _______________________________________________
>> Nauty mailing list
>> Nauty at anu.edu.au
>> http://mailman.anu.edu.au/mailman/listinfo/nauty
>
>