[Nauty-list] generating some graphs

[Brendan McKay]

Further to this question, the command
    geng 21 -c -b 36:36 -d3 -D4 > out.txt
takes most of a week to run and produces many millions of graphs,
hardly any of them semi-regular.  As I said before, the best
approach is to use genbg.  However, here is a way to use geng
for such a problem with reasonable efficiency.

With a little calculation, we can see that connected bipartite
graphs on 21 vertices and 36 edges with mmindeg >= 3 and maxdeg <= 4
are (3,4)-semiregular iff they have no adjacent vertices of degree 4.
Therefore, we can generate them by filtering out any partial
graph with an adjacent pair vertices of degree 4.  geng has a 
facility for such filtering.  Make a file no44.c as below,
then compile it into geng like this:

cc -o no44 -O3 -DPREPRUNE=no44 geng.c nauty1.o nautil1.o naugraph1.o gtools.o no44.c

Now you can run it:
   % no44 -d3D4bc 21 36 -u
   >A no44 -cbd3D4 n=21 e=36
   >Z 22651 graphs generated in 37.39 sec
 
Cheers, Brendan.

-----------------no44.c-----------------------------
/* no44.c - filter for geng 
 * Removes graphs that have two adjacent vertices of degree at least 4 
 * Link with geng or genbg using -DPREPRUNE=no44
*/

#include "nauty.h"

int
no44(graph *g, int n, int maxn)
{
    int j,k;
    setword x;

    x = g[n-1];
    if (POPCOUNT(x) <= 3) return;

    while (x)
    {
	TAKEBIT(j,x);
	if (POPCOUNT(g[j]) >= 4) return 1;
    }

    return 0;
}
----------------------------------------------------

* Brendan McKay <bdm at cs.anu.edu.au> [070907 09:06]:
> I think it is just being slow, but I'll check.  The difference between
> the two computers is probably just different i/o buffer size.
> 
> In any case, for bipartite graphs with known partition it is much
> faster to use genbg:
> 
>   % genbg -cu -d3:4 -D3:4 12 9
>   >A genbg n=12+9 e=36:36 d=3:4 D=3:4 c
>   >Z 22651 graphs generated in 11.21 sec
> 
> Brendan.
> 
> * zstanic at matf.bg.ac.yu <zstanic at matf.bg.ac.yu> [070907 03:54]:
> > I am trying to generate some connected (3,4)-semiregular bipartite graphs
> > on 21 vertices and 36 edges. In this purpose I run the following command:
> > 
> > geng 21 -c -b 36:36 -d3 -D4 > out.txt
...