[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