[Nauty] genbg and res/mod
Gordon Royle
gordon.royle at uwa.edu.au
Fri Nov 27 01:38:37 AEDT 2015
Hi Jernej
I suggest that you consider using GENREG instead of genbg for this task - it seems to do regular graphs particularly well.
With GENREG you can directly specify
- the number of vertices (36)
- the degree (3)
- the girth (4)
- bipartite-ness
It also permits you to split the computation into as many pieces as you like.
So here’s the command for the first 3 out of 500 parts - you’ll notice that the splitting into cases is not very good, because there is huge variation between the parts
$ genreg 36 3 4 -b -g -m 1 500
GENREG - Generator for regular graphs
36 vertices, degree 3, girth at least 4
Only bipartite graphs.
Part 1 of 500 started...
0 graphs produced.
CPU time: 0.0s
$ genreg 36 3 4 -b -g -m 2 500
GENREG - Generator for regular graphs
36 vertices, degree 3, girth at least 4
Only bipartite graphs.
Part 2 of 500 started...
1040871 graphs produced.
$ genreg 36 3 4 -b -g -m 3 500
GENREG - Generator for regular graphs
36 vertices, degree 3, girth at least 4
Only bipartite graphs.
Part 3 of 500 started...
8789544 graphs produced.
I’m not sure if it has a PRUNE function (Brendan probably knows) but if not, then you’ll have to:
- filter out those with pairs of vertices with more than the required number of common neighbours
- decide how you want to deal with isomorphisms that swap the cells of the bipartition
My brief experiments suggest that this is a big computation, but doable.
Cheers
Gordon
> On 26 Nov 2015, at 9:57 PM, Jernej Azarija <jernej.azarija at gmail.com> wrote:
>
> 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
>>
>>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty
More information about the Nauty
mailing list