/***************************************************************************** * * * Main source file for version 2.7 of nauty. * * * * Copyright (1984-2018) Brendan McKay. All rights reserved. Permission * * Subject to the waivers and disclaimers in nauty.h. * * * * CHANGE HISTORY * * 10-Nov-87 : final changes for version 1.2 * * 5-Dec-87 : renamed to version 1.3 (no changes to this file) * * 28-Sep-88 : renamed to version 1.4 (no changes to this file) * * 23-Mar-89 : changes for version 1.5 : * * - add use of refine1 instead of refine for m==1 * * - changes for new optionblk syntax * * - disable tc_level use for digraphs * * - interposed doref() interface to refine() so that * * options.invarproc can be supported * * - declared local routines static * * 28-Mar-89 : - implemented mininvarlevel/maxinvarlevel < 0 options * * 2-Apr-89 : - added invarproc fields in stats * * 5-Apr-89 : - modified error returns from nauty() * * - added error message to ERRFILE * * - changed MAKEEMPTY uses to EMPTYSET * * 18-Apr-89 : - added MTOOBIG and CANONGNIL * * 8-May-89 : - changed firstcode[] and canoncode[] to short * * 10-Nov-90 : changes for version 1.6 : * * - added dummy routine nauty_null (see dreadnaut.c) * * 2-Sep-91 : changes for version 1.7 : * * - moved MULTIPLY into nauty.h * * 27-Mar-92 : - changed 'n' into 'm' in error message in nauty() * * 5-Jun-93 : renamed to version 1.7+ (no changes to this file) * * 18-Aug-93 : renamed to version 1.8 (no changes to this file) * * 17-Sep-93 : renamed to version 1.9 (no changes to this file) * * 13-Jul-96 : changes for version 2.0 : * * - added dynamic allocation * * 21-Oct-98 : - made short into shortish for BIGNAUTY as needed * * 7-Jan-00 : - allowed n=0 * * - added nauty_check() and a call to it * * 12-Feb-00 : - used better method for target cell memory allocation * * - did a little formating of the code * * 27-May-00 : - fixed error introduced on Feb 12. * * - dynamic allocations in nauty() are now deallocated * * before return if n >= 320. * * 16-Nov-00 : - use function prototypes, change UPROC to void. * * - added argument to tcellproc(), removed nvector * * - now use options.dispatch, options.groupopts is gone. * * 22-Apr-01 : - Added code for compilation into Magma * * - Removed nauty_null() and EXTDEFS * * 2-Oct-01 : - Improved error message for bad dispatch vector * * 21-Nov-01 : - use NAUTYREQUIRED in nauty_check() * * 20-Dec-02 : changes for version 2.2: * * - made tcnode0 global * * - added nauty_freedyn() * * 17-Nov-03 : changed INFINITY to NAUTY_INFINITY * * 14-Sep-04 : extended prototypes even to recursive functions * * 16-Oct-04 : disallow NULL dispatch vector * * 11-Nov-05 : changes for version 2.3: * * - init() and cleanup() optional calls * * 23-Nov-06 : changes for version 2.4: * * - use maketargetcell() instead of tcellproc() * * 29-Nov-06 : add extra_autom, extra_level, extra_options * * 10-Dec-06 : remove BIGNAUTY * * 10-Nov-09 : remove shortish and permutation types * * 16-Nov-11 : added Shreier option * * 15-Jan-12 : added TLS_ATTR to static declarations * * 18-Jan-13 : added signal aborting * * 19-Jan-13 : added usercanonproc() * * 14-Oct-17 : corrected code for n=0 * * * *****************************************************************************/ #define ONE_WORD_SETS #include "nauty.h" #include "schreier.h" #ifdef NAUTY_IN_MAGMA #include "cleanup.e" #endif #define NAUTY_ABORTED (-11) #define NAUTY_KILLED (-12) typedef struct tcnode_struct { struct tcnode_struct *next; set *tcellptr; } tcnode; /* aproto: header new_nauty_protos.h */ #ifndef NAUTY_IN_MAGMA #if !MAXN static int firstpathnode0(int*, int*, int, int, tcnode*); static int othernode0(int*, int*, int, int, tcnode*); #else static int firstpathnode(int*, int*, int, int); static int othernode(int*, int*, int, int); #endif static void firstterminal(int*, int); static int processnode(int*, int*, int, int); static void recover(int*, int); static void writemarker(int, int, int, int, int, int); #endif #if MAXM==1 #define M 1 #else #define M m #endif #define OPTCALL(proc) if (proc != NULL) (*proc) /* copies of some of the options: */ static TLS_ATTR boolean getcanon,digraph,writeautoms,domarkers,cartesian,doschreier; static TLS_ATTR int linelength,tc_level,mininvarlevel,maxinvarlevel,invararg; static TLS_ATTR void (*usernodeproc)(graph*,int*,int*,int,int,int,int,int,int); static TLS_ATTR void (*userautomproc)(int,int*,int*,int,int,int); static TLS_ATTR void (*userlevelproc) (int*,int*,int,int*,statsblk*,int,int,int,int,int,int); static TLS_ATTR int (*usercanonproc) (graph*,int*,graph*,unsigned long,int,int,int); static TLS_ATTR void (*invarproc) (graph*,int*,int*,int,int,int,int*,int,boolean,int,int); static TLS_ATTR FILE *outfile; static TLS_ATTR dispatchvec dispatch; /* local versions of some of the arguments: */ static TLS_ATTR int m,n; static TLS_ATTR graph *g,*canong; static TLS_ATTR int *orbits; static TLS_ATTR statsblk *stats; /* temporary versions of some stats: */ static TLS_ATTR unsigned long invapplics,invsuccesses; static TLS_ATTR int invarsuclevel; /* working variables: */ static TLS_ATTR int gca_first, /* level of greatest common ancestor of current node and first leaf */ gca_canon, /* ditto for current node and bsf leaf */ noncheaplevel, /* level of greatest ancestor for which cheapautom==FALSE */ allsamelevel, /* level of least ancestor of first leaf for which all descendant leaves are known to be equivalent */ eqlev_first, /* level to which codes for this node match those for first leaf */ eqlev_canon, /* level to which codes for this node match those for the bsf leaf. */ comp_canon, /* -1,0,1 according as code at eqlev_canon+1 is <,==,> that for bsf leaf. Also used for similar purpose during leaf processing */ samerows, /* number of rows of canong which are correct for the bsf leaf BDM:correct description? */ canonlevel, /* level of bsf leaf */ stabvertex, /* point fixed in ancestor of first leaf at level gca_canon */ cosetindex; /* the point being fixed at level gca_first */ static TLS_ATTR boolean needshortprune; /* used to flag calls to shortprune */ #if !MAXN DYNALLSTAT(set,defltwork,defltwork_sz); DYNALLSTAT(int,workperm,workperm_sz); DYNALLSTAT(set,fixedpts,fixedpts_sz); DYNALLSTAT(int,firstlab,firstlab_sz); DYNALLSTAT(int,canonlab,canonlab_sz); DYNALLSTAT(short,firstcode,firstcode_sz); DYNALLSTAT(short,canoncode,canoncode_sz); DYNALLSTAT(int,firsttc,firsttc_sz); DYNALLSTAT(set,active,active_sz); /* In the dynamically allocated case (MAXN=0), each level of recursion needs one set (tcell) to represent the target cell. This is implemented by using a linked list of tcnode anchored at the root of the search tree. Each node points to its child (if any) and to the dynamically allocated tcell. Apart from the first node of the list, each node always has a tcell good for m up to alloc_m. tcnodes and tcells are kept between calls to nauty, except that they are freed and reallocated if m gets bigger than alloc_m. */ static TLS_ATTR tcnode tcnode0 = {NULL,NULL}; static TLS_ATTR int alloc_m = 0; #else static TLS_ATTR set defltwork[2*MAXM]; /* workspace in case none provided */ static TLS_ATTR int workperm[MAXN]; /* various scratch uses */ static TLS_ATTR set fixedpts[MAXM]; /* points which were explicitly fixed to get current node */ static TLS_ATTR int firstlab[MAXN], /* label from first leaf */ canonlab[MAXN]; /* label from bsf leaf */ static TLS_ATTR short firstcode[MAXN+2], /* codes for first leaf */ canoncode[MAXN+2]; /* codes for bsf leaf */ static TLS_ATTR int firsttc[MAXN+2]; /* index of target cell for left path */ static TLS_ATTR set active[MAXM]; /* used to contain index to cells now active for refinement purposes */ #endif static TLS_ATTR set *workspace,*worktop; /* first and just-after-last addresses of work area to hold automorphism data */ static TLS_ATTR set *fmptr; /* pointer into workspace */ static TLS_ATTR schreier *gp; /* These two for Schreier computations */ static TLS_ATTR permnode *gens; /***************************************************************************** * * * This procedure finds generators for the automorphism group of a * * vertex-coloured graph and optionally finds a canonically labelled * * isomorph. A description of the data structures can be found in * * nauty.h and in the "nauty User's Guide". The Guide also gives * * many more details about its use, and implementation notes. * * * * Parameters - means read-only, means write-only, means both: * * g - the graph * * lab,ptn - used for the partition nest which defines the colouring * * of g. The initial colouring will be set by the program, * * using the same colour for every vertex, if * * options->defaultptn!=FALSE. Otherwise, you must set it * * yourself (see the Guide). If options->getcanon!=FALSE, * * the contents of lab on return give the labelling of g * * corresponding to canong. This does not change the * * initial colouring of g as defined by (lab,ptn), since * * the labelling is consistent with the colouring. * * active - If this is not NULL and options->defaultptn==FALSE, * * it is a set indicating the initial set of active colours. * * See the Guide for details. * * orbits - On return, orbits[i] contains the number of the * * least-numbered vertex in the same orbit as i, for * * i=0,1,...,n-1. * * options - A list of options. See nauty.h and/or the Guide * * for details. * * stats - A list of statistics produced by the procedure. See * * nauty.h and/or the Guide for details. * * workspace - A chunk of memory for working storage. * * worksize - The number of setwords in workspace. See the Guide * * for guidance. * * m - The number of setwords in sets. This must be at * * least ceil(n / WORDSIZE) and at most MAXM. * * n - The number of vertices. This must be at least 1 and * * at most MAXN. * * canong - The canononically labelled isomorph of g. This is * * only produced if options->getcanon!=FALSE, and can be * * given as NULL otherwise. * * * * FUNCTIONS CALLED: firstpathnode(),updatecan() * * * *****************************************************************************/ void nauty(graph *g_arg, int *lab, int *ptn, set *active_arg, int *orbits_arg, optionblk *options, statsblk *stats_arg, set *ws_arg, int worksize, int m_arg, int n_arg, graph *canong_arg) { int i; int numcells; int retval; int initstatus; #if !MAXN tcnode *tcp,*tcq; #endif /* determine dispatch vector */ if (options->dispatch == NULL) { fprintf(ERRFILE,">E nauty: null dispatch vector\n"); fprintf(ERRFILE,"Maybe you need to recompile\n"); exit(1); } else dispatch = *(options->dispatch); if (options->userrefproc) dispatch.refine = options->userrefproc; else if (dispatch.refine1 && m_arg == 1) dispatch.refine = dispatch.refine1; if (dispatch.refine == NULL || dispatch.updatecan == NULL || dispatch.targetcell == NULL || dispatch.cheapautom == NULL) { fprintf(ERRFILE,">E bad dispatch vector\n"); exit(1); } /* check for excessive sizes: */ #if !MAXN if (m_arg > NAUTY_INFINITY/WORDSIZE+1) { stats_arg->errstatus = MTOOBIG; fprintf(ERRFILE,"nauty: need m <= %d, but m=%d\n\n", NAUTY_INFINITY/WORDSIZE+1,m_arg); return; } if (n_arg > NAUTY_INFINITY-2 || n_arg > WORDSIZE * m_arg) { stats_arg->errstatus = NTOOBIG; fprintf(ERRFILE,"nauty: need n <= min(%d,%d*m), but n=%d\n\n", NAUTY_INFINITY-2,WORDSIZE,n_arg); return; } #else if (m_arg > MAXM) { stats_arg->errstatus = MTOOBIG; fprintf(ERRFILE,"nauty: need m <= %d\n\n",MAXM); return; } if (n_arg > MAXN || n_arg > WORDSIZE * m_arg) { stats_arg->errstatus = NTOOBIG; fprintf(ERRFILE, "nauty: need n <= min(%d,%d*m)\n\n",MAXM,WORDSIZE); return; } #endif if (n_arg == 0) /* Special code for zero-sized graph */ { stats_arg->grpsize1 = 1.0; stats_arg->grpsize2 = 0; stats_arg->numorbits = 0; stats_arg->numgenerators = 0; stats_arg->errstatus = 0; stats_arg->numnodes = 1; stats_arg->numbadleaves = 0; stats_arg->maxlevel = 1; stats_arg->tctotal = 0; stats_arg->canupdates = (options->getcanon != 0); stats_arg->invapplics = 0; stats_arg->invsuccesses = 0; stats_arg->invarsuclevel = 0; g = canong = NULL; initstatus = 0; OPTCALL(dispatch.init)(g_arg,&g,canong_arg,&canong, lab,ptn,active,options,&initstatus,m,n); if (initstatus) stats->errstatus = initstatus; if (g == NULL) g = g_arg; if (canong == NULL) canong = canong_arg; OPTCALL(dispatch.cleanup)(g_arg,&g,canong_arg,&canong, lab,ptn,options,stats_arg,m,n); return; } /* take copies of some args, and options: */ m = m_arg; n = n_arg; nautil_check(WORDSIZE,m,n,NAUTYVERSIONID); OPTCALL(dispatch.check)(WORDSIZE,m,n,NAUTYVERSIONID); #if !MAXN DYNALLOC1(set,defltwork,defltwork_sz,2*m,"nauty"); DYNALLOC1(set,fixedpts,fixedpts_sz,m,"nauty"); DYNALLOC1(set,active,active_sz,m,"nauty"); DYNALLOC1(int,workperm,workperm_sz,n,"nauty"); DYNALLOC1(int,firstlab,firstlab_sz,n,"nauty"); DYNALLOC1(int,canonlab,canonlab_sz,n,"nauty"); DYNALLOC1(short,firstcode,firstcode_sz,n+2,"nauty"); DYNALLOC1(short,canoncode,canoncode_sz,n+2,"nauty"); DYNALLOC1(int,firsttc,firsttc_sz,n+2,"nauty"); if (m > alloc_m) { tcp = tcnode0.next; while (tcp != NULL) { tcq = tcp->next; FREES(tcp->tcellptr); FREES(tcp); tcp = tcq; } alloc_m = m; tcnode0.next = NULL; } #endif /* OLD g = g_arg; */ orbits = orbits_arg; stats = stats_arg; getcanon = options->getcanon; digraph = options->digraph; writeautoms = options->writeautoms; domarkers = options->writemarkers; cartesian = options->cartesian; doschreier = options->schreier; if (doschreier) schreier_check(WORDSIZE,m,n,NAUTYVERSIONID); linelength = options->linelength; if (digraph) tc_level = 0; else tc_level = options->tc_level; outfile = (options->outfile == NULL ? stdout : options->outfile); usernodeproc = options->usernodeproc; userautomproc = options->userautomproc; userlevelproc = options->userlevelproc; usercanonproc = options->usercanonproc; invarproc = options->invarproc; if (options->mininvarlevel < 0 && options->getcanon) mininvarlevel = -options->mininvarlevel; else mininvarlevel = options->mininvarlevel; if (options->maxinvarlevel < 0 && options->getcanon) maxinvarlevel = -options->maxinvarlevel; else maxinvarlevel = options->maxinvarlevel; invararg = options->invararg; if (getcanon) if (canong_arg == NULL) { stats_arg->errstatus = CANONGNIL; fprintf(ERRFILE, "nauty: canong=NULL but options.getcanon=TRUE\n\n"); return; } /* initialize everything: */ if (options->defaultptn) { for (i = 0; i < n; ++i) /* give all verts same colour */ { lab[i] = i; ptn[i] = NAUTY_INFINITY; } ptn[n-1] = 0; EMPTYSET(active,m); ADDELEMENT(active,0); numcells = 1; } else { ptn[n-1] = 0; numcells = 0; for (i = 0; i < n; ++i) if (ptn[i] != 0) ptn[i] = NAUTY_INFINITY; else ++numcells; if (active_arg == NULL) { EMPTYSET(active,m); for (i = 0; i < n; ++i) { ADDELEMENT(active,i); while (ptn[i]) ++i; } } else for (i = 0; i < M; ++i) active[i] = active_arg[i]; } g = canong = NULL; initstatus = 0; OPTCALL(dispatch.init)(g_arg,&g,canong_arg,&canong, lab,ptn,active,options,&initstatus,m,n); if (initstatus) { stats->errstatus = initstatus; return; } if (g == NULL) g = g_arg; if (canong == NULL) canong = canong_arg; if (doschreier) newgroup(&gp,&gens,n); for (i = 0; i < n; ++i) orbits[i] = i; stats->grpsize1 = 1.0; stats->grpsize2 = 0; stats->numgenerators = 0; stats->numnodes = 0; stats->numbadleaves = 0; stats->tctotal = 0; stats->canupdates = 0; stats->numorbits = n; EMPTYSET(fixedpts,m); noncheaplevel = 1; eqlev_canon = -1; /* needed even if !getcanon */ if (worksize >= 2 * m) workspace = ws_arg; else { workspace = defltwork; worksize = 2 * m; } worktop = workspace + (worksize - worksize % (2 * m)); fmptr = workspace; /* here goes: */ stats->errstatus = 0; needshortprune = FALSE; invarsuclevel = NAUTY_INFINITY; invapplics = invsuccesses = 0; #if !MAXN retval = firstpathnode0(lab,ptn,1,numcells,&tcnode0); #else retval = firstpathnode(lab,ptn,1,numcells); #endif if (retval == NAUTY_ABORTED) stats->errstatus = NAUABORTED; else if (retval == NAUTY_KILLED) stats->errstatus = NAUKILLED; else { if (getcanon) { (*dispatch.updatecan)(g,canong,canonlab,samerows,M,n); for (i = 0; i < n; ++i) lab[i] = canonlab[i]; } stats->invarsuclevel = (invarsuclevel == NAUTY_INFINITY ? 0 : invarsuclevel); stats->invapplics = invapplics; stats->invsuccesses = invsuccesses; } #if !MAXN #ifndef NAUTY_IN_MAGMA if (n >= 320) #endif { nautil_freedyn(); OPTCALL(dispatch.freedyn)(); nauty_freedyn(); } #endif OPTCALL(dispatch.cleanup)(g_arg,&g,canong_arg,&canong, lab,ptn,options,stats,m,n); if (doschreier) { freeschreier(&gp,&gens); if (n >= 320) schreier_freedyn(); } } /***************************************************************************** * * * firstpathnode(lab,ptn,level,numcells) produces a node on the leftmost * * path down the tree. The parameters describe the level and the current * * colour partition. The set of active cells is taken from the global set * * 'active'. If the refined partition is not discrete, the leftmost child * * is produced by calling firstpathnode, and the other children by calling * * othernode. * * For MAXN=0 there is an extra parameter: the address of the parent tcell * * structure. * * The value returned is the level to return to. * * * * FUNCTIONS CALLED: (*usernodeproc)(),doref(),cheapautom(), * * firstterminal(),nextelement(),breakout(), * * firstpathnode(),othernode(),recover(),writestats(), * * (*userlevelproc)(),(*tcellproc)(),shortprune() * * * *****************************************************************************/ static int #if !MAXN firstpathnode0(int *lab, int *ptn, int level, int numcells, tcnode *tcnode_parent) #else firstpathnode(int *lab, int *ptn, int level, int numcells) #endif { int tv; int tv1,index,rtnlevel,tcellsize,tc,childcount,qinvar,refcode; #if !MAXN set *tcell; tcnode *tcnode_this; tcnode_this = tcnode_parent->next; if (tcnode_this == NULL) { if ((tcnode_this = (tcnode*)ALLOCS(1,sizeof(tcnode))) == NULL || (tcnode_this->tcellptr = (set*)ALLOCS(alloc_m,sizeof(set))) == NULL) alloc_error("tcell"); tcnode_parent->next = tcnode_this; tcnode_this->next = NULL; } tcell = tcnode_this->tcellptr; #else set tcell[MAXM]; #endif ++stats->numnodes; /* refine partition : */ doref(g,lab,ptn,level,&numcells,&qinvar,workperm, active,&refcode,dispatch.refine,invarproc, mininvarlevel,maxinvarlevel,invararg,digraph,M,n); firstcode[level] = (short)refcode; if (qinvar > 0) { ++invapplics; if (qinvar == 2) { ++invsuccesses; if (mininvarlevel < 0) mininvarlevel = level; if (maxinvarlevel < 0) maxinvarlevel = level; if (level < invarsuclevel) invarsuclevel = level; } } tc = -1; if (numcells != n) { /* locate new target cell, setting tc to its position in lab, tcell to its contents, and tcellsize to its size: */ maketargetcell(g,lab,ptn,level,tcell,&tcellsize, &tc,tc_level,digraph,-1,dispatch.targetcell,M,n); stats->tctotal += tcellsize; } firsttc[level] = tc; /* optionally call user-defined node examination procedure: */ OPTCALL(usernodeproc) (g,lab,ptn,level,numcells,tc,(int)firstcode[level],M,n); if (numcells == n) /* found first leaf? */ { firstterminal(lab,level); OPTCALL(userlevelproc)(lab,ptn,level,orbits,stats,0,1,1,n,0,n); if (getcanon && usercanonproc != NULL) { (*dispatch.updatecan)(g,canong,canonlab,samerows,M,n); samerows = n; if ((*usercanonproc)(g,canonlab,canong,stats->canupdates, (int)canoncode[level],M,n)) return NAUTY_ABORTED; } return level-1; } #ifdef NAUTY_IN_MAGMA if (main_seen_interrupt) return NAUTY_KILLED; #else if (nauty_kill_request) return NAUTY_KILLED; #endif if (noncheaplevel >= level && !(*dispatch.cheapautom)(ptn,level,digraph,n)) noncheaplevel = level + 1; /* use the elements of the target cell to produce the children: */ index = 0; for (tv1 = tv = nextelement(tcell,M,-1); tv >= 0; tv = nextelement(tcell,M,tv)) { if (orbits[tv] == tv) /* ie, not equiv to previous child */ { breakout(lab,ptn,level+1,tc,tv,active,M); ADDELEMENT(fixedpts,tv); cosetindex = tv; if (tv == tv1) { #if !MAXN rtnlevel = firstpathnode0(lab,ptn,level+1,numcells+1, tcnode_this); #else rtnlevel = firstpathnode(lab,ptn,level+1,numcells+1); #endif childcount = 1; gca_first = level; stabvertex = tv1; } else { #if !MAXN rtnlevel = othernode0(lab,ptn,level+1,numcells+1, tcnode_this); #else rtnlevel = othernode(lab,ptn,level+1,numcells+1); #endif ++childcount; } DELELEMENT(fixedpts,tv); if (rtnlevel < level) return rtnlevel; if (needshortprune) { needshortprune = FALSE; shortprune(tcell,fmptr-M,M); } recover(ptn,level); } if (orbits[tv] == tv1) /* ie, in same orbit as tv1 */ ++index; } MULTIPLY(stats->grpsize1,stats->grpsize2,index); if (tcellsize == index && allsamelevel == level + 1) --allsamelevel; if (domarkers) writemarker(level,tv1,index,tcellsize,stats->numorbits,numcells); OPTCALL(userlevelproc)(lab,ptn,level,orbits,stats,tv1,index,tcellsize, numcells,childcount,n); return level-1; } /***************************************************************************** * * * othernode(lab,ptn,level,numcells) produces a node other than an ancestor * * of the first leaf. The parameters describe the level and the colour * * partition. The list of active cells is found in the global set 'active'. * * The value returned is the level to return to. * * * * FUNCTIONS CALLED: (*usernodeproc)(),doref(),refine(),recover(), * * processnode(),cheapautom(),(*tcellproc)(),shortprune(), * * nextelement(),breakout(),othernode(),longprune() * * * *****************************************************************************/ static int #if !MAXN othernode0(int *lab, int *ptn, int level, int numcells, tcnode *tcnode_parent) #else othernode(int *lab, int *ptn, int level, int numcells) #endif { int tv; int tv1,refcode,rtnlevel,tcellsize,tc,qinvar; short code; #if !MAXN set *tcell; tcnode *tcnode_this; tcnode_this = tcnode_parent->next; if (tcnode_this == NULL) { if ((tcnode_this = (tcnode*)ALLOCS(1,sizeof(tcnode))) == NULL || (tcnode_this->tcellptr = (set*)ALLOCS(alloc_m,sizeof(set))) == NULL) alloc_error("tcell"); tcnode_parent->next = tcnode_this; tcnode_this->next = NULL; } tcell = tcnode_this->tcellptr; #else set tcell[MAXM]; #endif #ifdef NAUTY_IN_MAGMA if (main_seen_interrupt) return NAUTY_KILLED; #else if (nauty_kill_request) return NAUTY_KILLED; #endif ++stats->numnodes; /* refine partition : */ doref(g,lab,ptn,level,&numcells,&qinvar,workperm,active, &refcode,dispatch.refine,invarproc,mininvarlevel,maxinvarlevel, invararg,digraph,M,n); code = (short)refcode; if (qinvar > 0) { ++invapplics; if (qinvar == 2) { ++invsuccesses; if (level < invarsuclevel) invarsuclevel = level; } } if (eqlev_first == level - 1 && code == firstcode[level]) eqlev_first = level; if (getcanon) { if (eqlev_canon == level - 1) { if (code < canoncode[level]) comp_canon = -1; else if (code > canoncode[level]) comp_canon = 1; else { comp_canon = 0; eqlev_canon = level; } } if (comp_canon > 0) canoncode[level] = code; } tc = -1; /* If children will be required, find new target cell and set tc to its position in lab, tcell to its contents, and tcellsize to its size: */ if (numcells < n && (eqlev_first == level || (getcanon && comp_canon >= 0))) { if (!getcanon || comp_canon < 0) { maketargetcell(g,lab,ptn,level,tcell,&tcellsize,&tc, tc_level,digraph,firsttc[level],dispatch.targetcell,M,n); if (tc != firsttc[level]) eqlev_first = level - 1; } else maketargetcell(g,lab,ptn,level,tcell,&tcellsize,&tc, tc_level,digraph,-1,dispatch.targetcell,M,n); stats->tctotal += tcellsize; } /* optionally call user-defined node examination procedure: */ OPTCALL(usernodeproc)(g,lab,ptn,level,numcells,tc,(int)code,M,n); /* call processnode to classify the type of this node: */ rtnlevel = processnode(lab,ptn,level,numcells); if (rtnlevel < level) /* keep returning if necessary */ return rtnlevel; if (needshortprune) { needshortprune = FALSE; shortprune(tcell,fmptr-M,M); } if (!(*dispatch.cheapautom)(ptn,level,digraph,n)) noncheaplevel = level + 1; /* use the elements of the target cell to produce the children: */ for (tv1 = tv = nextelement(tcell,M,-1); tv >= 0; tv = nextelement(tcell,M,tv)) { breakout(lab,ptn,level+1,tc,tv,active,M); ADDELEMENT(fixedpts,tv); #if !MAXN rtnlevel = othernode0(lab,ptn,level+1,numcells+1,tcnode_this); #else rtnlevel = othernode(lab,ptn,level+1,numcells+1); #endif DELELEMENT(fixedpts,tv); if (rtnlevel < level) return rtnlevel; /* use stored automorphism data to prune target cell: */ if (needshortprune) { needshortprune = FALSE; shortprune(tcell,fmptr-M,M); } if (tv == tv1) { longprune(tcell,fixedpts,workspace,fmptr,M); if (doschreier) pruneset(fixedpts,gp,&gens,tcell,M,n); } recover(ptn,level); } return level-1; } /***************************************************************************** * * * Process the first leaf of the tree. * * * * FUNCTIONS CALLED: NONE * * * *****************************************************************************/ static void firstterminal(int *lab, int level) { int i; stats->maxlevel = level; gca_first = allsamelevel = eqlev_first = level; firstcode[level+1] = 077777; firsttc[level+1] = -1; for (i = 0; i < n; ++i) firstlab[i] = lab[i]; if (getcanon) { canonlevel = eqlev_canon = gca_canon = level; comp_canon = 0; samerows = 0; for (i = 0; i < n; ++i) canonlab[i] = lab[i]; for (i = 0; i <= level; ++i) canoncode[i] = firstcode[i]; canoncode[level+1] = 077777; stats->canupdates = 1; } } /***************************************************************************** * * * Process a node other than the first leaf or its ancestors. It is first * * classified into one of five types and then action is taken appropriate * * to that type. The types are * * * * 0: Nothing unusual. This is just a node internal to the tree whose * * children need to be generated sometime. * * 1: This is a leaf equivalent to the first leaf. The mapping from * * firstlab to lab is thus an automorphism. After processing the * * automorphism, we can return all the way to the closest invocation * * of firstpathnode. * * 2: This is a leaf equivalent to the bsf leaf. Again, we have found an * * automorphism, but it may or may not be as useful as one from a * * type-1 node. Return as far up the tree as possible. * * 3: This is a new bsf node, provably better than the previous bsf node. * * After updating canonlab etc., treat it the same as type 4. * * 4: This is a leaf for which we can prove that no descendant is * * equivalent to the first or bsf leaf or better than the bsf leaf. * * Return up the tree as far as possible, but this may only be by * * one level. * * * * Types 2 and 3 can't occur if getcanon==FALSE. * * The value returned is the level in the tree to return to, which can be * * anywhere up to the closest invocation of firstpathnode. * * * * FUNCTIONS CALLED: isautom(),updatecan(),testcanlab(),fmperm(), * * writeperm(),(*userautomproc)(),orbjoin(), * * shortprune(),fmptn() * * * *****************************************************************************/ static int processnode(int *lab, int *ptn, int level, int numcells) { int i,code,save,newlevel; boolean ispruneok; int sr; code = 0; if (eqlev_first != level && (!getcanon || comp_canon < 0)) code = 4; else if (numcells == n) { if (eqlev_first == level) { for (i = 0; i < n; ++i) workperm[firstlab[i]] = lab[i]; if (gca_first >= noncheaplevel || (*dispatch.isautom)(g,workperm,digraph,M,n)) code = 1; } if (code == 0) { if (getcanon) { sr = 0; if (comp_canon == 0) { if (level < canonlevel) comp_canon = 1; else { (*dispatch.updatecan) (g,canong,canonlab,samerows,M,n); samerows = n; comp_canon = (*dispatch.testcanlab)(g,canong,lab,&sr,M,n); } } if (comp_canon == 0) { for (i = 0; i < n; ++i) workperm[canonlab[i]] = lab[i]; code = 2; } else if (comp_canon > 0) code = 3; else code = 4; } else code = 4; } } if (code != 0 && level > stats->maxlevel) stats->maxlevel = level; switch (code) { case 0: /* nothing unusual noticed */ return level; case 1: /* lab is equivalent to firstlab */ if (fmptr == worktop) fmptr -= 2 * M; fmperm(workperm,fmptr,fmptr+M,M,n); fmptr += 2 * M; if (writeautoms) writeperm(outfile,workperm,cartesian,linelength,n); stats->numorbits = orbjoin(orbits,workperm,n); ++stats->numgenerators; OPTCALL(userautomproc)(stats->numgenerators,workperm,orbits, stats->numorbits,stabvertex,n); if (doschreier) addgenerator(&gp,&gens,workperm,n); return gca_first; case 2: /* lab is equivalent to canonlab */ if (fmptr == worktop) fmptr -= 2 * M; fmperm(workperm,fmptr,fmptr+M,M,n); fmptr += 2 * M; save = stats->numorbits; stats->numorbits = orbjoin(orbits,workperm,n); if (stats->numorbits == save) { if (gca_canon != gca_first) needshortprune = TRUE; return gca_canon; } if (writeautoms) writeperm(outfile,workperm,cartesian,linelength,n); ++stats->numgenerators; OPTCALL(userautomproc)(stats->numgenerators,workperm,orbits, stats->numorbits,stabvertex,n); if (doschreier) addgenerator(&gp,&gens,workperm,n); if (orbits[cosetindex] < cosetindex) return gca_first; if (gca_canon != gca_first) needshortprune = TRUE; return gca_canon; case 3: /* lab is better than canonlab */ ++stats->canupdates; for (i = 0; i < n; ++i) canonlab[i] = lab[i]; canonlevel = eqlev_canon = gca_canon = level; comp_canon = 0; canoncode[level+1] = 077777; samerows = sr; if (getcanon && usercanonproc != NULL) { (*dispatch.updatecan)(g,canong,canonlab,samerows,M,n); samerows = n; if ((*usercanonproc)(g,canonlab,canong,stats->canupdates, (int)canoncode[level],M,n)) return NAUTY_ABORTED; } break; case 4: /* non-automorphism terminal node */ ++stats->numbadleaves; break; } /* end of switch statement */ /* only cases 3 and 4 get this far: */ if (level != noncheaplevel) { ispruneok = TRUE; if (fmptr == worktop) fmptr -= 2 * M; fmptn(lab,ptn,noncheaplevel,fmptr,fmptr+M,M,n); fmptr += 2 * M; } else ispruneok = FALSE; save = (allsamelevel > eqlev_canon ? allsamelevel-1 : eqlev_canon); newlevel = (noncheaplevel <= save ? noncheaplevel-1 : save); if (ispruneok && newlevel != gca_first) needshortprune = TRUE; return newlevel; } /***************************************************************************** * * * Recover the partition nest at level 'level' and update various other * * parameters. * * * * FUNCTIONS CALLED: NONE * * * *****************************************************************************/ static void recover(int *ptn, int level) { int i; for (i = 0; i < n; ++i) if (ptn[i] > level) ptn[i] = NAUTY_INFINITY; if (level < noncheaplevel) noncheaplevel = level + 1; if (level < eqlev_first) eqlev_first = level; if (getcanon) { if (level < gca_canon) gca_canon = level; if (level <= eqlev_canon) { eqlev_canon = level; comp_canon = 0; } } } /***************************************************************************** * * * Write statistics concerning an ancestor of the first leaf. * * * * level = its level * * tv = the vertex fixed to get the first child = the smallest-numbered * * vertex in the target cell * * cellsize = the size of the target cell * * index = the number of vertices in the target cell which were equivalent * * to tv = the index of the stabiliser of tv in the group * * fixing the colour partition at this level * * * * numorbits = the number of orbits of the group generated by all the * * automorphisms so far discovered * * * * numcells = the total number of cells in the equitable partition at this * * level * * * * FUNCTIONS CALLED: itos(),putstring() * * * *****************************************************************************/ static void writemarker(int level, int tv, int index, int tcellsize, int numorbits, int numcells) { char s[30]; #define PUTINT(i) itos(i,s); putstring(outfile,s) #define PUTSTR(x) putstring(outfile,x) PUTSTR("level "); PUTINT(level); PUTSTR(": "); if (numcells != numorbits) { PUTINT(numcells); PUTSTR(" cell"); if (numcells == 1) PUTSTR("; "); else PUTSTR("s; "); } PUTINT(numorbits); PUTSTR(" orbit"); if (numorbits == 1) PUTSTR("; "); else PUTSTR("s; "); PUTINT(tv+labelorg); PUTSTR(" fixed; index "); PUTINT(index); if (tcellsize != index) { PUTSTR("/"); PUTINT(tcellsize); } PUTSTR("\n"); } /***************************************************************************** * * * nauty_check() checks that this file is compiled compatibly with the * * given parameters. If not, call exit(1). * * * *****************************************************************************/ void nauty_check(int wordsize, int m, int n, int version) { if (wordsize != WORDSIZE) { fprintf(ERRFILE,"Error: WORDSIZE mismatch in nauty.c\n"); exit(1); } #if MAXN if (m > MAXM) { fprintf(ERRFILE,"Error: MAXM inadequate in nauty.c\n"); exit(1); } if (n > MAXN) { fprintf(ERRFILE,"Error: MAXN inadequate in nauty.c\n"); exit(1); } #endif if (version < NAUTYREQUIRED) { fprintf(ERRFILE,"Error: nauty.c version mismatch\n"); exit(1); } } /***************************************************************************** * * * extra_autom(p,n) - add an extra automorphism, hard to do correctly * * * *****************************************************************************/ void extra_autom(int *p, int n) { if (writeautoms) writeperm(outfile,p,cartesian,linelength,n); stats->numorbits = orbjoin(orbits,p,n); ++stats->numgenerators; OPTCALL(userautomproc)(stats->numgenerators,p,orbits, stats->numorbits,stabvertex,n); } /***************************************************************************** * * * extra_level(level,lab,ptn,numcells,tv1,index,tcellsize,childcount) * * creates an artificial level in the search. This is dangerous. * * * *****************************************************************************/ void extra_level(int level, int *lab, int *ptn, int numcells, int tv1, int index, int tcellsize, int childcount, int n) { MULTIPLY(stats->grpsize1,stats->grpsize2,index); if (domarkers) writemarker(level,tv1,index,tcellsize,stats->numorbits,numcells); OPTCALL(userlevelproc)(lab,ptn,level,orbits,stats,tv1,index,tcellsize, numcells,childcount,n); } /***************************************************************************** * * * nauty_freedyn() frees all the dynamic memory used in this module. * * * *****************************************************************************/ void nauty_freedyn(void) { #if !MAXN tcnode *tcp,*tcq; tcp = tcnode0.next; while (tcp != NULL) { tcq = tcp->next; FREES(tcp->tcellptr); FREES(tcp); tcp = tcq; } alloc_m = 0; tcnode0.next = NULL; DYNFREE(firsttc,firsttc_sz); DYNFREE(canoncode,canoncode_sz); DYNFREE(firstcode,firstcode_sz); DYNFREE(workperm,workperm_sz); DYNFREE(canonlab,canonlab_sz); DYNFREE(firstlab,firstlab_sz); DYNFREE(defltwork,defltwork_sz); DYNFREE(fixedpts,fixedpts_sz); DYNFREE(active,active_sz); #endif }