[Nauty] Re: nauty-list digest, Vol 1 #116 - 3 msgs

[Sterten at aol.com]

Hello Senlin,

the other post yesterday gave me the idea to convert  the digraph into an 
undirected graph
with isomorphic automorphismgroup.
It seems that this is much faster  than using  options.digraph = TRUE
for some graphs with large  automorphismgroup like the one which you posted.
The program below gave answer 16777216 immediately.
 
Guenter.
 
 
 
// automorphismgroups of digraphs using Nauty. compiled with gcc 3.2
// from DOS-batch-file :
// gcc -O2 -c autd.c 
// gcc autd.o naugraph.o nautil.o nauty.o -O2  -o autd.exe 
// type autd.c >>autd.exe
 
#include <stdio.h>
#define MAXN 3200
#include  "nauty.h"
//int grpsize1,grpsize2;
graph g[MAXN*MAXM];
graph  canong[MAXN*MAXM];
FILE *fin;
nvector  lab[MAXN],ptn[MAXN],orbits[MAXN];
char c[MAXN*MAXN];
 
int main(int argc,char*argv[]) {
static  DEFAULTOPTIONS(options);
statsblk(stats);
setword  workspace[160*MAXM];
int n1,x,y,z,i,j,n=12,m,v,gntk=0;
set  *gv;
options.writeautoms = TRUE;
options.writeautoms =  FALSE;
options.writemarkers = FALSE;
options.getcanon =  TRUE;
options.defaultptn = FALSE;
//active =  NULL;
options.digraph = FALSE;
 

if(argc<2){printf("\nusage: autd infile  k\n");
printf("prints  sizes of automorphismgroups for the digraphs in  infile");
printf(" and  writes these to  stdout\n");
printf("prints graphsizes also, when k>0 is  specified\n");
printf("prints generators, when  k=42\n");
printf("format: n*n  entries of adjacency matrices  ,\n");
printf("terminated by a end-of-line ASCII 10, other  characters\n");
printf("   are  ignored\n\n");
exit(1);}
 
    if((fin=fopen(argv[1],"rb"))==NULL){printf("file-error");exit(1);}
if(argc=3)sscanf(argv[2],"%i",&gntk);
 
    if(gntk==42)options.writeautoms = TRUE;
 

h01:i=-1;
h02:j=fgetc(fin);
if  (feof(fin)){fclose(fin);goto h04;}
if(j==13)goto  h04;
if(j<48 || j>49)goto h02;
if(i>MAXN*MAXN){printf("graph too big !\n");goto h03;}
i++;c[i]=j-48;
goto h02;
 
h04:n=1;if(i<0)goto h03;
h04f:if(n*n<i){n++;goto  h04f;}
 
n1=n;n=n*3;m=(n+WORDSIZE-1)/WORDSIZE;
 
  for(v=0;v<n1;v++){
gv=GRAPHROW(g,v,m);
EMPTYSET(gv,m);ADDELEMENT(gv,v+n1+n1);
for(i=0;i<n1;i++)if(c[v*n1+i])ADDELEMENT(gv,i+n1); } 
 
  for(v=0;v<n1;v++){
gv=GRAPHROW(g,v+n1,m);
EMPTYSET(gv,m);ADDELEMENT(gv,v+n1+n1);
for(i=0;i<n1;i++)if(c[i*n1+v])ADDELEMENT(gv,i); }
 
  for(v=0;v<n1;v++){
gv=GRAPHROW(g,v+n1+n1,m);
EMPTYSET(gv,m);ADDELEMENT(gv,v+n1);ADDELEMENT(gv,v); }
 

for(i=0;i<n;i++){lab[i]=i;ptn[i]=1;}
ptn[n1-1]=0;ptn[n1+n1-1]=0;
 
nauty(g,lab,ptn,NILSET,orbits,&options,&stats,workspace,160*MAXM,m,n,canong);
 
j=stats.grpsize1;v=stats.grpsize2;
if(gntk)printf("%i  ",n1);
printf("%i\n",j);
 
  goto h01;
 
  h03:;
 
 }

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20050313/18550924/attachment.html