[Nauty] generate all S-free graphs

[Sterten at aol.com]

 >> Given a set S of graphs of small size,
 >> I want to generate efficiently all graphs of size n,
 >> which don't contain any of the graphs from S as induced subgraph.
 >> 
 >> I already have a subroutine, which checks whether
 >> G contains a graph from S.
 >> The property is hereditary : as soon as there is a forbidden
 >> subgraph we can immediately backtrack.
 >> 
 >> Can I modify geng.c easily or will it be difficult for me ?
 >
 >geng.c has facilities for this exact application.  It is
 >explained in the comments at the start of the source code
 >(look for "PRUNE").

you're right, it's in geng.c. I should have read it, instead I
were searching for your "squarefree" routine intending to
replace it.

 >Basically, you write a procedure which
 >returns 1 if there is a forbidden subgraph and 0 if not.
 >This is best done in a separate file (don't modify geng.c).
 >Then compile geng.c with PRUNE defined as the same of your
 >procedure and of course link in your new file.  That's it.
 >
 >Brendan.

first I had to figure out the nauty format
and I was unsure about "define PRUNE at compile time", since
I'm not very experienced with C,but finally I succeeded :-)

all:         1,2,4,11,34,156,1044,12346,274668,12005168   (60s,K6-2,500MHz)
oddholefree: 1,2,4,11,33,148, 907, 8899,137186, 3291746   (77s)
perfect:     1,2,4,11,33,148, 906, 8887,136756, 3269264   (131s)
evenholefree:1,2,4,10,28, 99, 434, 2486, 18521,  177186   (12s)
squarefree:  1,2,4,10,28,100, 441, 2574, 19849,  201682   (12s)
clawfree:    1,2,4,10,26, 85, 302, 1285,  6170,   34294   (5s)
comparability:   not yet, but planned
permutationgraph:
raspail:
asteroidaltriplefree:
bullfree:
dartfree:
diamondfree:
batfree:
...

I'm not sure that the numbers are correct, can someone confirm ?


here is the square-routine as an example:

geng.c was copied to gengsq.c ,
define PRUNE square        was added as first line,
"squarefree" was included in helptext,
and the lines below were added to gengsq.c below its last line.
Then gengsq.c was compiled just as geng.c, thus creating gengsq.exe
Only the first vertex (=last in *g) was checked for squares.

Guenter.


int square(graph *g,int n,int maxn) {
int a[n+1][n+1],e[n+1][n+1],d[n+1];
long int m=1;int i,j,k,u,v,w,x,y,z;set *gi;

for(i=0,gi=(set*)g;i<n;++i,gi+=m)for(j=0;j<n;++j)a[n-i][n-j]=ISELEMENT(gi,j);

for(i=1;i<=n;i++)d[i]=0;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i][j]>0){d[i]++;e[i][d[i]]=j;}

   for(x=1;x<=d[1];x++) {v=e[1][x];
     for(y=x+1;y<=d[1];y++) {w=e[1][y];
       if(a[v][w]<1)
         for(z=1;z<=d[v];z++) {u=e[v][z];
           if(a[w][u]>0 && a[1][u]<1 && u>1)return(1);}
   } } 
return(0);}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20021123/b5b66c13/attachment.html