/* gentree version 1.2; Brendan McKay Aug 2017 */ /* This program is a wrapper for the program FreeTrees.c written * by Gang Li & Frank Ruskey. See below for their original * comments. */ /* TODO: splitlevinc */ #define USAGE \ "gentreeg [-D#] [-Z#:#] [-ulps] [-q] n [res/mod] [file]" #define HELPTEXT \ " Generate (unrooted) trees.\n\ \n\ n : the number of vertices\n\ res/mod : only generate subset res out of subsets 0..mod-1\n\ \n\ -D# : an upper bound for the maximum degree\n\ -Z#:# : bounds for the diameter\n\ \n\ -s : use sparse6 output (default)\n\ -p : write a parent array\n\ -l : write a level array \n\ -u : do not output any graphs, just generate and count them\n\ \n\ -q : suppress auxiliary output\n\ \n\ See program text for much more information.\n" /************************************************************** Counts for n=1..45: 1: 1 2: 1 3: 1 4: 1 5: 2 6: 3 7: 6 8: 11 9: 23 10: 47 11: 106 12: 235 13: 551 14: 1301 15: 3159 16: 7741 17: 19320 18: 48629 19: 123867 20: 317955 21: 823065 22: 2144505 23: 5623756 24: 14828074 25: 39299897 26: 104636890 27: 279793450 28: 751065460 29: 2023443032 30: 5469566585 31: 14830871802 32: 40330829030 33: 109972410221 34: 300628862480 35: 823779631721 36: 2262366343746 37: 6226306037178 38: 17169677490714 39: 47436313524262 40: 131290543779126 41: 363990257783343 42: 1010748076717151 43: 2810986483493475 44: 7828986221515605 45: 21835027912963086 ********************************/ /* Comments on original program by original authors */ /*==============================================================*/ /* program: freetree.c */ /* purpose: generating all free trees */ /* input : n -- number of nodes */ /* m -- max degree */ /* lb,ub -- lower and upper bound on diameter */ /* res/mod -- splitting into parts */ /* output : listing of free trees in relex order */ /* date : September 1995, updated Sept 2000 */ /* programmers: Gang Li & Frank Ruskey */ /* algorithm: From the paper: G. Li and F. Ruskey, "The */ /* Advantages of Forward Thinking in Generating Rooted and */ /* Free Trees", 10th Annual ACM-SIAM Symposium on Discrete */ /* Algorithms (SODA), (1999) S939-940. See the web page at */ /* http://www.theory.csc.UVic.CA/~fruskey/ */ /* Publications/RootedFreeTree.html */ /* more info: See */ /* http://www.theory.csc.UVic.CA/~cos/inf/FreeTrees.html */ /*==============================================================*/ #define MAXN 128 /* max size of the tree. Check MAXOUTLEN if more than 1000 */ #include "gtools.h" /***************************************************************** OUTPROC feature. By defining the C preprocessor variable OUTPROC at compile time (for Unix the syntax is -DOUTPROC=procname on the cc command), gentreeg can be made to call void OUTPROC(FILE *f, int *par, int n) instead of the usual output routines. par[1..n] is the parent array of the tree. The edges in 1..n labelling are {j,par[j]} for j=2..n. WARNING: The vertices are 1..n, not 0..n-1, and also par[] uses elements 1..n, not 0..n-1. Your procedure can be in a separate file so long as it is linked with gentreeg. PRUNE feature. By defining the C preprocessor variable PRUNE at compile time, gentreeg can be made to call int PRUNE(int *par, int n) for each tree. The meaning of par[] is above and n is the number of vertices. If a non-zero value is returned, the tree is rejected: it is not included in the count, and output routines including OUTPROC are not called. SUMMARY If the C preprocessor variable SUMMARY is defined at compile time, the procedure/macro SUMMARY(nauty_counter nout, double cpu) is called just before the program exits. The purpose is to allow reporting of statistics collected by PRUNE or OUTPROC. The values nout and cpu are the output count and cpu time as reported on the >Z line. Output should be written to stderr. CALLING FROM A PROGRAM It is possible to call gentreeg from another program instead of using it as a stand-alone program. The main requirement is to change the name of the main program to be other than "main". This is done by defining the preprocessor variable GENTREEG_MAIN. You might also like to define OUTPROC to be the name of a procedure to receive the graphs. To call the program you need to define an argument list argv[] consistent with the usual one; don't forget that argv[0] is the command name and not the first argument. The value of argc is the number of strings in argv[]; that is, one more than the number of arguments. EFFICIENCY Note that the trees are generated much faster than they can be written. A substantial time saving can be achieved using one of the above methods instead of writing the trees and then reading them into another program. */ static int par[MAXN+1], /* parent position of i */ maxchild, /* max number of children */ chi[MAXN+1], /* number of children of a node */ nextp[MAXN+1], /* next good pos to add nodes */ rChi[MAXN+1], /* the right most child of node i */ ub; /* upper bound on something */ static nauty_counter nout; /* number of trees */ static FILE *outfile; static int splitlevel,splitcount,mod,res; /* -s res/mod */ static int nv; /* number of vertices */ static int mindiam; static int maxdeg; static int maxdiam; /* MAXOUTLEN must be at least the longest output line length */ #define MAXOUTLEN (10 + 4*MAXN) static char outstring[MAXOUTLEN]; void (*outproc)(FILE *f, int vpar[], int n); #ifdef OUTPROC extern void OUTPROC(FILE *f, int vpar[], int n); #endif #ifdef PRUNE extern int PRUNE(int vpar[], int n); #endif void WritePar(FILE *f, int vpar[], int n) /* Write parent array */ { int i,j; char *pout,*p,one[8]; size_t len; pout = outstring; for (i=1;i<=nv;++i) { j = vpar[i]; if (j == 0) *(pout++) = '0'; else { for (p = one; j > 0; j /= 10) *(p++) = '0' + j%10; while (--p >= one) *(pout++) = *p; } if (i < nv) *(pout++) = ' '; else *(pout++) = '\n'; } len = pout - outstring; if (fwrite(outstring,sizeof(char),len,f) != len) gt_abort(">E gentreeg: fwrite() failed\n"); } static void WriteLev(FILE *f, int vpar[], int n) /* Write levels array */ { int i,j; char *pout,*p,one[8]; size_t len; int lev[MAXN+1]; lev[1]=0; for ( i=2; i<=nv; ++i ) lev[i] = lev[vpar[i]]+1; pout = outstring; for (i=1;i<=nv;++i) { j = lev[i]; if (j == 0) *(pout++) = '0'; else { for (p = one; j > 0; j /= 10) *(p++) = '0' + j%10; while (--p >= one) *(pout++) = *p; } if (i < nv) *(pout++) = ' '; else *(pout++) = '\n'; } len = pout - outstring; if (fwrite(outstring,sizeof(char),len,f) != len) gt_abort(">E gentreeg: fwrite() failed\n"); } static void DontWrite(FILE *f, int vpar[], int n) /* Null print routine */ { } static void WriteS6(FILE *f, int vpar[], int n) /* Write in sparse6 format */ { char *pout; int nb,i,j,lastj,x,k,r,rr,topbit; size_t len; pout = outstring; *pout++ = ':'; encodegraphsize(n,&pout); for (i = n-1, nb = 0; i != 0 ; i >>= 1, ++nb) {} topbit = 1 << (nb-1); k = 6; x = 0; lastj = 0; for (j = 1; j < n; ++j) { i = vpar[j+1] - 1; if (j == lastj) { x <<= 1; if (--k == 0) { *pout++ = 63 + x; k = 6; x = 0; } } else { x = (x << 1) | 1; if (--k == 0) { *pout++ = 63 + x; k = 6; x = 0; } if (j > lastj+1) { for (r = 0, rr = j; r < nb; ++r, rr <<= 1) { if (rr & topbit) x = (x << 1) | 1; else x <<= 1; if (--k == 0) { *pout++ = 63 + x; k = 6; x = 0; } } x <<= 1; if (--k == 0) { *pout++ = 63 + x; k = 6; x = 0; } } lastj = j; } for (r = 0, rr = i; r < nb; ++r, rr <<= 1) { if (rr & topbit) x = (x << 1) | 1; else x <<= 1; if (--k == 0) { *pout++ = 63 + x; k = 6; x = 0; } } } if (k != 6) *pout++ = 63 + ((x << k) | ((1 << k) - 1)); *pout++ = '\n'; len = pout - outstring; if (fwrite(outstring,sizeof(char),len,f) != len) gt_abort(">E gentreeg: fwrite() failed\n"); } static void WriteIt(int level) { if (level < splitlevel && res != 0) return; #ifdef PRUNE if (PRUNE(par,nv)) return; #endif ++nout; (*outproc)(outfile,par,nv); } static boolean good( int p, int h, int t ) { if (p==2 && mindiam<=2 && t==0) return TRUE; if (t == 1) { if (2*h>=mindiam+1 && 2*h <= maxdiam+1) { if ((p-1)*2 >= nv) return TRUE; else if (p - h-1 == 1) { if (par[p]> 2) return TRUE; } else if ((p - h-1 >=2) && ((par[h+2]>2) || (par[h+3]>2))) return TRUE; } } else if (nv-p >= h && 2*h>=mindiam) { if (maxdiam==nv-1 && nv%2==0) return 2*h<=maxdiam+1; else return 2*h <= maxdiam; } return FALSE; } /* good */ static void Gen( int level, int p, int s, int cL, int h, int l, int n, int f, int g ) /* The main generation procedure. */ { int hh,flag,entry,temp; if (level == splitlevel) { if (splitcount-- != 0) return; splitcount = mod - 1; } if (p > n) if (f == 0) { if (good(p-1,h,0)) Gen(level+1, p, 2, p-2,h,n,nv,1,0); if (good(p-1,h,1)) Gen(level+1, p, 2, p-3,h,n,nv,1,1); } else { WriteIt(level);} else { if (cL == 0) { if ( p< ub+2 ) par[p] = p-1; else { Gen(level+1, p, p-1, 1, h, l, n, f, g ); return; } } else if (par[p-cL] < s) par[p]=par[p-cL]; else { par[p] = cL + par[p-cL]; if (g==1) { if (((l-1)*2 < n) && (p-cL<=l) && ( ((p-cL+1l))) { /*case 3*/ s= par[p]; cL= p-s; par[p] = par[par[p]]; } else if (par[p-cL]==2) par[p]=1; } } if (s!=0 || p<=ub+1) { chi[par[p]] = chi[par[p]] + 1; temp = rChi[par[p]]; rChi[par[p]] = p; if (chi[par[p]] <= ((par[p]==1)?maxchild:maxchild-1)) { if (chi[par[p]] < (par[p]==1?maxchild:maxchild-1)) nextp[p] = par[p]; else nextp[p] = nextp[par[p]]; Gen(level+1, p+1, s, cL,h,l,n,f,g ); } chi[par[p]] = chi[par[p]] - 1; rChi[par[p]] = temp; } if (s==0 && 2*(p-2)=2)) || ((f==1) && (entry>=1))) && (flag==0)) { if (s==0) h = p-2; if (p<=l+h-g) hh = 0; if ((f==0) || (hh==1)) { /*s = par[p]; par[p] = par[s];*/ par[p] = entry; chi[entry] = chi[entry] + 1; temp = rChi[par[p]]; rChi[par[p]] = p; if (chi[entry] >= (entry==1?maxchild:maxchild-1)) nextp[p] = nextp[entry]; if (f == 0) Gen(level+1,p+1,temp,p-temp,h,0,nv-h+1,f,g); else if (hh == 1) Gen(level+1,p+1,temp,p-temp,h,l,n,f,g); chi[entry] = chi[entry] - 1; rChi[par[p]] = temp; entry = nextp[entry]; nextp[p] = entry; } else flag= 1; } if (f == 0) { if (good(p-1,h,0)) Gen(level+1,p,2,p-2,h,p-1,nv,1,0); if (good(p-1,h,1)) Gen(level+1,p,2,p-3,h,p-1,nv,1,1); } } } /* Gen */ /**************************************************************************/ /**************************************************************************/ #ifdef GENTREEG_MAIN int GENTREEG_MAIN(int argc, char *argv[]) #else int main(int argc, char *argv[]) #endif { char *arg; boolean badargs,uswitch,sswitch,pswitch,lswitch,Zswitch; boolean qswitch,Dswitch,gotmr,gotf; long Z1,Z2; char *outfilename,sw; int i,j,argnum; int splitlevinc; double t1,t2; char msg[201]; HELP; PUTVERSION; badargs = FALSE; uswitch = sswitch = pswitch = lswitch = Zswitch = FALSE; qswitch = Dswitch = gotmr = gotf = FALSE; outfilename = NULL; splitlevinc = 0; argnum = 0; for (j = 1; !badargs && j < argc; ++j) { arg = argv[j]; if (arg[0] == '-' && arg[1] != '\0') { ++arg; while (*arg != '\0') { sw = *arg++; SWBOOLEAN('u',uswitch) else SWBOOLEAN('s',sswitch) else SWBOOLEAN('p',pswitch) else SWBOOLEAN('l',lswitch) else SWRANGE('Z',":-",Zswitch,Z1,Z2,"gentreeg -Z") else SWBOOLEAN('q',qswitch) else SWINT('D',Dswitch,maxdeg,"gentreeg -D") #ifdef PLUGIN_SWITCHES PLUGIN_SWITCHES #endif else badargs = TRUE; } } else if (arg[0] == '-' && arg[1] == '\0') gotf = TRUE; else { if (argnum == 0) { if (sscanf(arg,"%d",&nv) != 1) badargs = TRUE; ++argnum; } else if (gotf) badargs = TRUE; else { if (!gotmr) { if (sscanf(arg,"%d/%d",&res,&mod) == 2) { gotmr = TRUE; continue; } } if (!gotf) { outfilename = arg; gotf = TRUE; continue; } } } } if (argnum == 0) badargs = TRUE; else if (nv < 1 || nv > MAXN) { fprintf(stderr,">E gentreeg: n must be in the range 1..%d\n",MAXN); exit(1); } if (!gotmr) { mod = 1; res = 0; } if (!Dswitch || maxdeg >= nv) maxdeg = nv - 1; if (!Zswitch || Z2 >= nv) Z2 = nv - 1; if (!Zswitch || Z1 <= 1) Z1 = (nv == 1 ? 0 : nv == 2 ? 1 : 2); mindiam = Z1; maxdiam = Z2; if (!badargs && (maxdiam < mindiam || maxdiam < (nv == 1 ? 0 : nv == 2 ? 1 : 2))) gt_abort(">E gentreeg: impossible diameter bounds\n"); if (!badargs && maxdeg < (nv == 1 ? 0 : nv == 2 ? 1 : 2)) gt_abort(">E gentreeg: impossible degree bound\n"); if (!badargs && (res < 0 || res >= mod)) gt_abort(">E gentreeg: must have 0 <= res < mod\n"); if (badargs) { fprintf(stderr,">E Usage: %s\n",USAGE); GETHELP; exit(1); } if ((lswitch!=0) + (pswitch!=0) + (sswitch!=0) + (uswitch!=0) > 1) gt_abort(">E gentreeg: -uslp are incompatible\n"); #ifdef OUTPROC outproc = OUTPROC; #else if (uswitch) outproc = DontWrite; else if (lswitch) outproc = WriteLev; else if (pswitch) outproc = WritePar; else outproc = WriteS6; #endif #ifdef PLUGIN_INIT PLUGIN_INIT #endif if (qswitch) outfile = stdout; else if (!gotf || outfilename == NULL) { outfilename = "stdout"; outfile = stdout; } else if ((outfile = fopen(outfilename,"w")) == NULL) { fprintf(stderr, ">E gentree: can't open %s for writing\n",outfilename); gt_abort(NULL); } if (!qswitch) { msg[0] = '\0'; if (strlen(argv[0]) > 75) fprintf(stderr,">A %s",argv[0]); else CATMSG1(">A %s",argv[0]); CATMSG2(" Z=%d:%d",mindiam,maxdiam); CATMSG2(" D=%d n=%d",maxdeg,nv); if (mod > 1) CATMSG2(" class=%d/%d",res,mod); CATMSG0("\n"); fputs(msg,stderr); fflush(stderr); } t1 = CPUTIME; nout = 0; if (nv == 1) { if (res == 0) { par[1] = 0; WriteIt(0); } } else if (nv == 2) { if (res == 0) { par[1] = 0; par[2] = 1; WriteIt(0); } } else { if (mod > 1 && nv > 3) { splitlevel = nv/2; splitcount = res; } else { splitlevel = -1; mod = 1; } if ( maxdeg > 0 ) maxchild = maxdeg; else maxchild = -1; ub = (maxdiam+1)/2; for(i=1;i<=nv;i++) chi[i]=0; par[1] = 0; par[2] = 1; nextp[1]=0; nextp[2]=1;chi[1]=1; Gen( 0, 3, 0, 0, ub, 0, nv-ub+1, 0, 0 ); } t2 = CPUTIME; #ifdef SUMMARY SUMMARY(nout,t2-t1); #endif if (!qswitch) { fprintf(stderr,">Z " COUNTER_FMT " trees generated in %3.2f sec\n",nout,t2-t1); } #ifdef GENTREEG_MAIN return 0; #else exit(0); #endif }