/****************************************************************************** * * miscellaneous utilities for use with nauty 2 . 8 . * * None of these procedures are needed by nauty , but all are by dreadnaut . * * * * Copyright ( 1984 - 2022 ) Brendan McKay . All rights reserved . * * Subject to waivers and disclaimers in nauty . h . * * * * CHANGE HISTORY * * 10 - Nov - 87 : final changes for version 1 . 2 * * 5 - Dec - 87 : changes made for version 1 . 3 : * * - added procedures readinteger ( ) and readstring ( ) * * - replaced all uses of fscanf ( ) by appropriate uses * * of readinteger ( ) or readstring ( ) * * - " N : " is now illegal in readgraph ( ) if N is too large * * or too small * * 28 - Sep - 88 : renamed to version 1 . 4 ( no changes to this file ) * * 23 - Mar - 89 : changes for version 1 . 5 : * * - declared key in hash ( ) * * - changed file name to naututil . c * * 29 - Mar - 89 : - declared workperm [ ] and workset [ ] , and modified * * many routines to use them . * * - added putmapping ( ) * * - reworked some code in mathon ( ) and rangraph ( ) * * 3 - Apr - 89 : - changed putorbits ( ) to use O ( n ) algorithm * * 5 - Apr - 89 : - modifed readgraph ( ) to not require fresh line * * - changed MAKEEMPTY uses to EMPTYSET uses * * 26 - Apr - 89 : - moved ptncode ( ) and equitable ( ) to nautaux . c * * - added putquotient ( ) * * 18 - Aug - 89 : - modified putset ( ) to use " i : j " syntax optionally * * - modified putorbits ( ) to use putset ( ) * * - modified calling sequence for mathon ( ) * * 19 - Aug - 90 : - changed delimeter arg of copycomment to int * * 14 - Oct - 90 : renamed to version 1 . 6 ( no changes to this file ) * * 23 - Jan - 91 : changes for version 1 . 7 : * * - fixed bug in complement ( ) * * 27 - Aug - 92 : - made linelength < = 0 mean no line breaks * * 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 * * - added limit parameter to readstring * * - added readvperm ( ) and sublabel ( ) * * 31 - Aug - 96 : - converted from RAN to KRAN * * 6 - Feb - 97 : - corrected DYNALLOC1 call in putmapping * * 10 - Dec - 97 : - KRAN now initialises automatically * * 9 - Jan - 00 : - added naututil_check ( ) * * 12 - Feb - 00 : - some minor code formatting * * 16 - Nov - 00 : - changes as listed in nauty . h * * 23 - Apr - 01 : changes for version 2 . 1 : * * - removed EXTDEFS * * 2 - Jun - 01 : - added converse ( ) * * 21 - Nov - 01 : use NAUTYREQUIRED in naututil_check ( ) * * 11 - Apr - 03 : changes for version 2 . 2 : * * - added rangraph2 ( ) * * 17 - Nov - 03 : changed INFINITY to NAUTY_INFINITY * * 10 - Dec - 06 : removed BIGNAUTY * * 4 - Nov - 09 : added readgraph_sg , putgraph_sg , putcanon_sg * * 10 - Nov - 09 : removed shortish and permutation types * * 14 - Nov - 09 : added relabel_sg ( ) , putdegs_sg ( ) , sublabel_sg ( ) * * 19 - Nov - 09 : added individualise ( ) * * 20 - Nov - 09 : added hashgraph_sg ( ) , listhash ( ) , hashgraph ( ) * * 19 - Dec - 09 : added ranreg_sg ( ) , rangraph2_sg ( ) * * 21 - May - 10 : conform to type changes in sparsegraph * * 5 - Jun - 10 : add mathon_sg ( ) * * 10 - Jun - 10 : add putquotient_sg ( ) and complement_sg ( ) * * 26 - Jan - 11 : fix nde error in sublabel_sg ( ) * * 15 - Jan - 12 : add TLS_ATTR attributes * * 3 - Mar - 12 : add putorbitsplus ( ) and putset_firstbold ( ) * * : write orbit sizes if not trivial * * 17 - Mar - 12 : move seed definition to naututil . h * * 20 - Sep - 12 : allow quoted strings in readstring ( ) * * 20 - Sep - 12 : the first argument of ungetc is int , not char * * 4 - Mar - 13 : remove a side - effect issue in setinter ( ) * * 17 - Dec - 15 : add readgraph_swg ( ) and update putgraph_sg ( ) * * 22 - Jan - 16 : add readintger_sl ( ) and getint_sl ( ) * * 29 - Feb - 16 : add subpartition ( ) * * 6 - Apr - 16 : add countcells ( ) , make subpartition return a count * * * #define ONE_WORD_SETS#include "naututil.h" /* which includes nauty.h, nautinv.h and stdio.h */ #include "nausparse.h" #if MAXM==1 #define M 1 #else #define M m#endif #if !MAXNint ,workperm,workperm_sz);#else static TLS_ATTR int workperm[MAXN+2 ]; /* used for scratch purposes */ static TLS_ATTR set workset[MAXM]; /* used for scratch purposes */ #endif #define ECHUNKSIZE 1000 /* should be a multiple of 2 */ typedef struct echunk {struct echunk *next; int edge[ECHUNKSIZE];} echunk;static TLS_ATTR echunk first_echunk = {NULL,{0 }};typedef struct echunkw {struct echunkw *next; \struct {int v1,v2; sg_weight wt;} edge[ECHUNKSIZE];} echunkw;static TLS_ATTR echunkw first_echunkw = {NULL,{{0 ,0 ,0 }}};#ifdef NLMAP#define GETNW(c,f) do c = getc(f); while (c==' ' ||c=='\t' )#define GETNWC(c,f) do c = getc(f); while (c==' ' ||c==',' ||c=='\t' )#define GETNWL(c,f) do c = getc(f); while (c==' ' ||c=='\n' ||c=='\t' )#else #define GETNW(c,f) do c = getc(f); while (c==' ' ||c=='\t' ||c=='\r' )#define GETNWC(c,f) do c = getc(f); while (c==' ' ||c==',' ||c=='\t' ||c=='\r' )#define GETNWL(c,f) do c = getc(f); while (c==' ' ||c=='\n' ||c=='\t' ||c=='\r' )#endif #define ISDIGIT(c) ((c) >= '0' && (c) <= '9' )static const long fuzz1[] = {1984625421 L, 971524688 L,1175081625 L, 377165387 L};static const long fuzz2[] = {2001381726 L,1615243355 L, 191176436 L,1212176501 L};#define FUZZ1(x) ((x) ^ fuzz1[(x)&3 L])#define FUZZ2(x) ((x) ^ fuzz2[(x)&3 L])#define SORT_OF_SORT 1 #define SORT_NAME sort1int#define SORT_TYPE1 int #include "sorttemplates.c" /* define sort1int(a,n) */ /****************************************************************************** * * setinter ( set1 , set2 , m ) = the number of elements in the intersection of * * the sets set1 and set2 . * * * int int m)int count,i;0 ;for (i = m; --i >= 0 ;)if ((x = (*set1 & *set2)) != 0 ) count += POPCOUNT(x);return count;/****************************************************************************** * * setsize ( set1 , m ) = the number of elements in the set set1 . * * * int int m)int count,i;if (m == 1 ) return POPCOUNT(*set1);0 ;for (i = m; --i >= 0 ;) count += POPCOUNT(set1[i]);return count;/****************************************************************************** * * setolist ( set1 , m , list ) Puts all the elements of the set into * * list [ 0 . . . ] and returns the number of elements as function value . * * * int int m, int *list)int i,j,k,v;0 ;for (i = 0 , v = 0 ; i < m; ++i, v += WORDSIZE)while (w)return k;/****************************************************************************** * * listtoset ( list , len , set1 , m ) Sets set1 [ 0 . . m - 1 ] to the set { list [ 0 . . len - 1 ] } * * * void int *list, int len, set *set1, int m)int i;if (m == 1 )0 ;for (i = 0 ; i < len; ++i) w |= bit[list[i]];else for (i = 0 ; i < len; ++i) ADDELEMENT0(set1,list[i]);/****************************************************************************** * * flushline ( f ) reads from f until ' \ n ' or EOF . * * If non - trivial characters are skipped , the user is informed . * * * void int c;FALSE ;while ((c = getc(f)) != EOF && c != '\n' )if (msg)char )c,ERRFILE);else if (c != ' ' && c != '\t' && c != '\f' &&'\r' && c != ',' )TRUE ;"input skipped : '%c" ,(char )c);if (msg) fprintf(ERRFILE,"'\n\n" );/****************************************************************************** * * readinteger ( f , & i ) reads an optionally - signed integer from f , preceded by * * any amount of white space . The function value returned is TRUE if an * * integer was found , FALSE otherwise . * * * int *p)int c,ans,minus;if (!ISDIGIT(c) && c != '-' && c != '+' )if (c != EOF) ungetc(c,f);return FALSE ;'-' ;'-' || c == '+' ? 0 : c - '0' );while (ISDIGIT(c))10 ;'0' ;if (c != EOF) ungetc(c,f);return TRUE ;/****************************************************************************** * * readinteger_sl ( f , & i ) reads an optionally - signed integer from f , preceded * * by any amount of white space except newlines . The function value * * returned is TRUE if an integer was found , FALSE otherwise . * * * int *p)int c,ans,minus;if (!ISDIGIT(c) && c != '-' && c != '+' )if (c != EOF) ungetc(c,f);return FALSE ;'-' ;'-' || c == '+' ? 0 : c - '0' );while (ISDIGIT(c))10 ;'0' ;if (c != EOF) ungetc(c,f);return TRUE ;/****************************************************************************** * * readstring ( f , s , slen ) reads a string from f . First any amount of white * * space is skipped ( including newlines ) . If the next character is a * * double - quote , everything after that before the next double - quote or * * newline is put into s . If the next character is not a double - quote , * * everything before the next white space is put into s . A nul is added , * * but no more than slen characters are ever put into s . The function * * value is TRUE if a string was found and FALSE otherwise . * * * char *s, int slen)int c;char *slim;1 ;if (c == EOF)'\0' ;return FALSE ;if (c == '"' )while (c != '"' && c != '\n' && c != '\r' && c != EOF)if (s <= slim) *s++ = (char )c;if (c != '"' && c != EOF) ungetc(c,f);else if (s <= slim) *s++ = (char )c;while (c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != EOF)if (s <= slim) *s++ = (char )c;if (c != EOF) ungetc(c,f);if (s <= slim) *s = '\0' ;else *slim = '\0' ;return TRUE ;/****************************************************************************** * * getint ( f ) reads an integer from f , optionally preceded by ' = ' * * and white space . - 1 is returned if the attempt was unsuccessful . * * * int int i,c;if (c != '=' ) ungetc(c,f);if (readinteger(f,&i)) return i;else return -1 ;/****************************************************************************** * * getint_sl ( f ) reads an integer from f , optionally preceded by ' = ' and * * white space other than newlines . - 1 is returned if the attempt was * * unsuccessful . * int int i,c;if (c != '=' ) ungetc(c,f);if (readinteger_sl(f,&i)) return i;else return -1 ;/****************************************************************************** * * putset ( f , set1 , curlenp , linelength , m , compress ) writes the set set1 to * * file f using at most linelength characters per line ( excluding ' \ n ' ) . * * A value of linelength < = 0 dictates no line breaks at all . * * * curlenp is the number of characters on the line so far ; it is updated . * * A range j1 , j1 + 1 , . . . , j2 for j2 - j1 > = 2 is written as " j1 : j2 " if compress * * is nonzero ( eg . TRUE ) ; otherwise each element is written separately . * * No final ' \ n ' is written . labelorg is used . * * * * FUNCTIONS CALLED : nextelement ( ) , itos ( ) * * * void int *curlenp, int linelength,int m, boolean compress)int slen,j1,j2;char s[40 ];1 ;while ((j1 = nextelement(set1,m,j1)) >= 0 )if (compress)while (nextelement(set1,m,j2) == j2 + 1 ) ++j2;if (j2 == j1+1 ) j2 = j1;if (j2 >= j1 + 2 )':' ;1 + itos(j2+labelorg,&s[slen+1 ]);if (linelength > 0 && *curlenp + slen + 1 >= linelength)"\n " );3 ;" %s" ,s);1 ;/****************************************************************************** * * putset_firstbold ( f , set1 , curlenp , linelength , m , compress ) is the same as * * putset ( f , set1 , curlenp , linelength , m , compress ) except that the first * * element of the set is written bold . This is only useful when output is * * to a device that interprets ANSI control sequences . * * * * FUNCTIONS CALLED : nextelement ( ) , itos ( ) * * * void int *curlenp, int linelength,int m, boolean compress)int slen,slen1,j1,j2;char s[50 ],c;TRUE ;1 ;while ((j1 = nextelement(set1,m,j1)) >= 0 )if (compress)while (nextelement(set1,m,j2) == j2 + 1 ) ++j2;if (j2 == j1+1 ) j2 = j1;if (j2 >= j1 + 2 )':' ;1 + itos(j2+labelorg,&s[slen+1 ]);if (linelength > 0 && *curlenp + slen + 1 >= linelength)"\n " );3 ;if (bold)'\0' ;" \033[1m%s\033[0m" ,s);"%s" ,&s[slen1]);FALSE ;else " %s" ,s);1 ;/****************************************************************************** * * readgraph ( f , g , digraph , prompt , edit , linelength , m , n ) reads a graph g from f . * * Commands : ( There is always a " current vertex " v , initially labelorg ; * * n is an unsigned integer . ) * * n : add edge ( v , n ) * * - n : delete edge ( v , n ) * * n : : set v : = n , and exit if v > = n . * * ? : type neighbours of vertex v * * ; : increment v , and exit if v > = n . * * . : exit * * ! : skip rest of input line * * * * If digraph = = FALSE , loops are illegal and ( x , y ) = > ( y , x ) * * If edit = = FALSE , the graph is initialized to empty . * * If prompt = = TRUE , prompts are written to PROMPTFILE . * * linelength is a limit on the number of characters per line caused by ' ? ' * * A value of linelength < = 0 dictates no line breaks at all . * * labelorg is used . * * * * FUNCTIONS CALLED : putset ( ) * * * void int linelength, int m, int n)int v,c;int curlen,w;if (!edit)for (v = 0 , gv = g; v < n; ++v, gv += M) EMPTYSET(gv,m);0 ;FALSE ;while (TRUE )if (ISDIGIT(c))if (neg)FALSE ;if (w < 0 || w >= n || (!digraph && w == v))"illegal edge (%d,%d) ignored\n\n" ,else if (!digraph) DELELEMENT(GRAPHROW(g,w,M),v);else if (c == ':' )if (w < 0 || w >= n)"illegal vertex number %d ignored\n\n" ,else else if (w < 0 || w >= n || (!digraph && w == v))"illegal edge (%d,%d) ignored\n\n" ,else if (!digraph) ADDELEMENT(GRAPHROW(g,w,M),v);else switch (c)case ';' :FALSE ;if (v >= n) return ;break ;case '?' :FALSE ;"%2d : " ,v+labelorg);5 ;FALSE );";\n" );break ;case '\n' :FALSE ;if (prompt) fprintf(PROMPTFILE,"%2d : " ,v+labelorg);break ;case EOF:case '.' :return ;case '-' :TRUE ;break ;case '!' :do while (c != '\n' && c != EOF);if (c == '\n' ) ungetc(c,f);break ;default :"illegal char '%c' - use '.' to exit\n\n" ,char )c);/**************************************************************************/ void int degree, int n)/* Make a random regular simple undirected graph. * For MAXN ! = 0 , the maximum degree is MAXREG . * sg must be initialised long i,k,v,w;int *dd,*ee;#if MAXNint p[MAXREG*MAXN];#else int ,p,p_sz);int ,p,p_sz,degree,n,"genrang" );#endif "ranreg_sg" );for (i = j = 0 ; i < n; ++i)for (k = 0 ; k < degree; ++k) p[j++] = i;for (i = 0 ; i < n; ++i) vv[i] = i*(size_t)degree;do TRUE ;for (j = nde; j > 0 ; j -= 2 )1 );if (k == p[j-1 ]) break ;2 ]; p[j-2 ] = k;if (j > 0 ) { ok = FALSE ; continue ; }for (i = 0 ; i < n; ++i) dd[i] = 0 ;for (j = nde; j > 0 ; )if (v != w)for (i = dd[w]; --i >= 0 ;) if (ee[vv[w]+i] == v) break ;if (i >= 0 ) { ok = FALSE ; break ; }while (!ok);/****************************************************************************** * * readgraph_sg ( f , sg , digraph , prompt , linelength , n ) reads a graph g from f . * * Commands : ( There is always a " current vertex " v , initially labelorg ; * * n is an unsigned integer . ) * * n : add edge ( v , n ) * * - n : delete edge ( v , n ) * * n : : set v : = n , and exit if v > = n . * * ? : type neighbours of vertex v * * NOT IMPLEMENTED * * * * ; : increment v , and exit if v > = n . * * . : exit * * ! : skip rest of input line * * sg must be initialised * * * * If digraph = = FALSE , loops are illegal and ( x , y ) = > ( y , x ) * * If prompt = = TRUE , prompts are written to PROMPTFILE . * * linelength is a limit on the number of characters per line caused by ' ? ' * * A value of linelength < = 0 dictates no line breaks at all . * * labelorg is used . * * * void int linelength, int n)int i,j,k,vv,ww,c;int *d,*e,*evi;"malloc" );int ,sg->d,sg->dlen,n,"malloc" );for (i = 0 ; i < n; ++i) d[i] = 0 ;0 ;0 ;FALSE ;while (!done)if (ISDIGIT(c))if (neg)FALSE ;if (ww < 0 || ww >= n || (!digraph && ww == vv))"illegal edge (%d,%d) ignored\n\n" ,else if (iec == ECHUNKSIZE)if (!ec->next)1 ,sizeof (echunk));if (!ecnext) alloc_error("malloc" );0 ;1 - ww;if (!digraph && ww != vv) ++d[ww];else if (c == ':' )if (ww < 0 || ww >= n)"illegal vertex number %d ignored\n\n" ,else else if (ww < 0 || ww >= n || (!digraph && ww == vv))"illegal edge (%d,%d) ignored\n\n" ,else if (iec == ECHUNKSIZE)if (!ec->next)1 ,sizeof (echunk));if (!ecnext) alloc_error("malloc" );0 ;if (!digraph && ww != vv) ++d[ww];else switch (c)case ';' :FALSE ;if (vv >= n) done = TRUE ;break ;case '?' :FALSE ;"Command \'?\' not implemented.\n\n" );break ;case '\n' :FALSE ;if (prompt) fprintf(PROMPTFILE,"%2d : " ,vv+labelorg);break ;case EOF:case '.' :TRUE ;break ;case '-' :TRUE ;break ;case '!' :do while (c != '\n' && c != EOF);if (c == '\n' ) ungetc(c,f);break ;default :"illegal char '%c' - use '.' to exit\n\n" ,char )c);0 ;for (i = 0 ; i < n; ++i) ned += d[i];int ,sg->e,sg->elen,ned,"malloc" );0 ] = 0 ;for (i = 1 ; i < n; ++i) v[i] = v[i-1 ] + d[i-1 ];for (i = 0 ; i < n; ++i) d[i] = 0 ;0 ;if (ned != 0 ) while (TRUE )if (ww >= 0 )if (!digraph && ww != vv) e[v[ww] +(d[ww]++)] = vv;else 1 - ww;for (i = 0 ; i < d[vv]; ++i)if (e[v[vv]+i] == ww) break ;if (i < d[vv])1 ];if (!digraph && ww != vv)for (i = 0 ; i < d[ww]; ++i)if (e[v[ww]+i] == vv) break ;if (i < d[ww])1 ];if (iec == iec_end && ec == ec_end) break ;if (iec == ECHUNKSIZE) { iec = 0 ; ec = ec->next; }0 ;for (i = 0 ; i < n; ++i)if (d[i] > 1 )1 ;for (k = 1 ; k < d[i]; ++k)if (evi[k] != evi[j-1 ]) evi[j++] = evi[k];/****************************************************************************** * * readgraph_swg ( f , sg , digraph , prompt , linelength , n ) reads a sparse weighted * * graph g from f . * * Commands : ( There is always a " current vertex " v , initially labelorg ; * * n is an unsigned integer , w is a weight . ) * * n : add edge ( v , n ) * * - n : delete edge ( v , n ) * * n : : set v : = n , and exit if v > = n . * * ? : type neighbours of vertex v * * NOT IMPLEMENTED * * * * ; : increment v , and exit if v > = n . * * . : exit * * ! : skip rest of input line * * w # : set the weight for the next edge only * * W # : set the weight from now on * * sg must be initialised * * * * If digraph = = FALSE , loops are illegal and ( x , y ) = > ( y , x ) * * For digraphs , an unspecified opposite edge has weight SG_MINWEIGHT * * If edges are inserted more than once , the largest weight counts . * * If prompt = = TRUE , prompts are written to PROMPTFILE . * * linelength is a limit on the number of characters per line caused by ' ? ' * * A value of linelength < = 0 dictates no line breaks at all . * * labelorg is used . * * * void int linelength, int n)int i,j,k,vv,ww,c;int *d,*e,*evi;"malloc" );int ,sg->d,sg->dlen,n,"malloc" );for (i = 0 ; i < n; ++i) d[i] = 0 ;1 ; 0 ;0 ;FALSE ;while (!done)if (ISDIGIT(c))if (neg)FALSE ;if (ww < 0 || ww >= n || (!digraph && ww == vv))"illegal edge (%d,%d) ignored\n\n" ,else if (iec == ECHUNKSIZE)if (!ec->next)1 ,sizeof (echunkw));if (!ecnext) alloc_error("malloc" );0 ;1 - ww;if (ww != vv) ++d[ww];else if (c == ':' )if (ww < 0 || ww >= n)"illegal vertex number %d ignored\n\n" ,else else if (ww < 0 || ww >= n || (!digraph && ww == vv))"illegal edge (%d,%d) ignored\n\n" ,else if (iec == ECHUNKSIZE)if (!ec->next)1 ,sizeof (echunkw));if (!ecnext) alloc_error("malloc" );0 ;if (ww != vv) ++d[ww];else switch (c)case ';' :FALSE ;if (vv >= n) done = TRUE ;break ;case '?' :FALSE ;"Command \'?\' not implemented.\n\n" );break ;case '\n' :FALSE ;if (prompt) fprintf(PROMPTFILE,"%2d : " ,vv+labelorg);break ;case EOF:case '.' :TRUE ;break ;case '-' :TRUE ;break ;case 'w' :if (currwt <= SG_MINWEIGHT)"Weight too small\n\n" );1 ;break ;case 'W' :if (currwt <= SG_MINWEIGHT)"Weight too small\n\n" );1 ;break ;case '!' :do while (c != '\n' && c != EOF);if (c == '\n' ) ungetc(c,f);break ;default :"illegal char '%c' - use '.' to exit\n\n" ,char )c);0 ;for (i = 0 ; i < n; ++i) ned += d[i];int ,sg->e,sg->elen,ned,"malloc" );"malloc" );0 ] = 0 ;for (i = 1 ; i < n; ++i) v[i] = v[i-1 ] + d[i-1 ];for (i = 0 ; i < n; ++i) d[i] = 0 ;0 ;if (ned != 0 ) while (TRUE )if (ww >= 0 )if (ww != vv)else 1 - ww;for (i = 0 ; i < d[vv]; ++i)if (e[v[vv]+i] == ww) break ;if (i < d[vv])1 ];1 ];if (ww != vv)for (i = 0 ; i < d[ww]; ++i)if (e[v[ww]+i] == vv) break ;if (i < d[ww])1 ];1 ];if (iec == iec_end && ec == ec_end) break ;if (iec == ECHUNKSIZE) { iec = 0 ; ec = ec->next; }0 ;for (i = 0 ; i < n; ++i)if (d[i] > 1 )1 ;for (k = 1 ; k < d[i]; ++k)if (evi[k] != evi[j-1 ])else if (wvi[k] > wvi[j-1 ])1 ] = wvi[k];/****************************************************************************** * * putgraph ( f , g , linelength , m , n ) writes a list of the edges of g to f * * using at most linelength characters per line ( excluding ' \ n ' ) . * * A value of linelength < = 0 dictates no line breaks at all within the * * list for each vertex . * * labelorg is used . * * * * FUNCTIONS CALLED : putset ( ) * * * void int linelength, int m, int n)int i,curlen;for (i = 0 , pg = g; i < n; ++i, pg += M)"%3d : " ,i+labelorg);7 ;FALSE );";\n" );/****************************************************************************** * * putgraph_sg ( f , sg , linelength ) writes a list of the edges of g to f * * using at most linelength characters per line ( excluding ' \ n ' ) . * * A value of linelength < = 0 dictates no line breaks at all within the * * list for each vertex . * * labelorg is used . * * * void int linelength)int i,n,curlen,slen;int *d,*e;char s[60 ];for (i = 0 ; i < n; ++i)"%3d : " ,i+labelorg);7 ;for (j = v[i]; j < v[i]+d[i]; ++j)if (wt && wt[j] != 1 )0 ] = 'w' ;if (wt[j] == SG_MINWEIGHT)1 ] = 'X' ;2 ] = ' ' ;3 ;else 2 + itos(wt[j],s+1 );1 ] = ' ' ;else if (linelength > 0 && curlen + slen + 1 > linelength)"\n " );2 ;' ' ,f);1 ;";\n" );/****************************************************************************** * * putmapping ( f , lab1 , org1 , lab2 , org2 , linelength , n ) writes n pairs * * ( lab1 [ i ] + org1 ) - ( lab2 [ i ] + org2 ) to file f in increasing order of lab1 [ i ] . * * lab1 and lab2 are assumed to be permutations . At most linelength * * characters ( excluding ' \ n ' ) are written per line . * * A value of linelength < = 0 dictates no line breaks at all . * * * * FUNCTIONS CALLED : itos ( ) , putstring ( ) * * * void int *lab1, int org1,int *lab2, int org2,int linelength, int n)int i,curlen,slen;char s[60 ];#if !MAXNint ,workperm,workperm_sz,n+2 ,"putmapping" );#endif for (i = 0 ; i < n; ++i) workperm[lab1[i]] = lab2[i];0 ;for (i = 0 ; i < n; ++i)'-' ;if (linelength > 0 && curlen + slen + 1 > linelength)"\n " );2 ;' ' ,f);1 ;'\n' ,f);/****************************************************************************** * * putorbits ( f , orbits , linelength , n ) writes the orbits to f as lists * * of integers separated by semicolons . No more than linelength characters * * ( excluding ' \ n ' ) are written per line . * * A value of linelength < = 0 dictates no line breaks at all . * * labelorg is used . * * * * FUNCTIONS CALLED : itos ( ) , putset ( ) * * * void int *orbits, int linelength, int n)int i,j;int m,curlen,sz,slen;char s[20 ];#if !MAXNint ,workperm,workperm_sz,n+2 ,"putorbits" );"putorbits" );#endif for (i = n; --i >= 0 ;) workperm[i] = 0 ;for (i = n; --i >= 0 ;)if ((j = orbits[i]) < i)0 ;for (i = 0 ; i < n; ++i)if (orbits[i] == i)0 ;do while (j > 0 );1 ,m,TRUE );if (sz > 1 )0 ] = ' ' ;1 ] = '(' ;2 + itos(sz,s+2 );')' ;'\0' ;if (linelength > 0 && curlen + slen + 1 >= linelength)"\n " );3 ;"%s" ,s);';' ,f);'\n' ,f);/****************************************************************************** * * putorbitsplus ( f , orbits , linelength , n ) is the same as * * putorbits ( f , orbits , linelength , n ) except that the first element of each * * orbit is written bold . This only works if output is to a device that * * interprets ANSI controls . * * * * FUNCTIONS CALLED : itos ( ) , putset ( ) * * * void int *orbits, int linelength, int n)int i,j;int m,curlen,sz,slen;char s[20 ];#if !MAXNint ,workperm,workperm_sz,n+2 ,"putorbits" );"putorbits" );#endif for (i = n; --i >= 0 ;) workperm[i] = 0 ;for (i = n; --i >= 0 ;)if ((j = orbits[i]) < i)0 ;for (i = 0 ; i < n; ++i)if (orbits[i] == i)0 ;do while (j > 0 );1 ,m,TRUE );if (sz > 1 )0 ] = ' ' ;1 ] = '(' ;2 + itos(sz,s+2 );')' ;'\0' ;if (linelength > 0 && curlen + slen + 1 >= linelength)"\n " );3 ;"%s" ,s);';' ,f);'\n' ,f);/****************************************************************************** * * putquotient ( f , g , lab , ptn , level , linelength , m , n ) writes the quotient matrix * * of g defined by the partition at the given level . Precisely , for each * * cell W , it writes the number w of the least vertex in W , then the size * * of W , then the number of times w is joined FROM each cell . A complete * * join is written as " * " , while an empty join is written as " - " . No more * * than linelength characters ( excluding ' \ n ' ) are written per line unless * * linelength is very small . A value of linelength < = 0 dictates no line * * breaks at all . labelorg is used . * * * * FUNCTIONS CALLED : itos ( ) * * * void int *lab, int *ptn, int level,int linelength, int m, int n)int i;char s[50 ];int ic,curlen,v,w,cell1,cell2,numcells,jc,csize,k;#if !MAXNint ,workperm,workperm_sz,n+2 ,"putquotient" );"putquotient" );#endif 0 ;for (cell1 = 0 ; cell1 < n; cell1 = cell2 + 1 )for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}for (i = cell1 + 1 ; i <= cell2; ++i)if (lab[i] < w) w = lab[i];for (ic = cell1 = 0 ; ic < numcells; ++ic, cell1 = cell2 + 1 )for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}for (i = cell1; i <= cell2; ++i) ADDELEMENT(workset,lab[i]);1 ;if (v + labelorg < 10 )0 ] = ' ' ;1 ;else 0 ;'[' ;"%s" ,s);if (csize < 10 )"] :" );4 ;else "] :" );3 ;for (jc = 0 ; jc < numcells; ++jc)if (k == 0 || k == csize)if (linelength > 0 && curlen + 2 > linelength)"\n " );4 ;if (k == 0 ) fprintf(f," -" );else fprintf(f," *" );2 ;else if (linelength > 0 && curlen + i + 1 > linelength)"\n " );4 ;" %s" ,s);1 ;"\n" );/****************************************************************************** * * putquotient_sg ( f , g , lab , ptn , level , linelength ) writes the quotient matrix * * of g defined by the partition at the given level . Precisely , for each * * cell W , it writes the number w of the least vertex in W , then the size * * of W , then the number of times w is joined FROM each cell . A complete * * join is written as " * " , while an empty join is written as " - " . No more * * than linelength characters ( excluding ' \ n ' ) are written per line unless * * linelength is very small . A value of linelength < = 0 dictates no line * * breaks at all . labelorg is used . * * * * Weughts are ignored . * * * void int *lab, int *ptn,int level, int linelength)int i,m,n;char s[50 ];int ic,curlen,v,w,cell1,cell2,numcells,jc,csize,k;int *dd,*ee;#if !MAXNint ,workperm,workperm_sz,n+2 ,"putquotient" );"putquotient" );#endif 0 ;for (cell1 = 0 ; cell1 < n; cell1 = cell2 + 1 )for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}for (i = cell1 + 1 ; i <= cell2; ++i)if (lab[i] < w) w = lab[i];for (ic = cell1 = 0 ; ic < numcells; ++ic, cell1 = cell2 + 1 )for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}for (i = cell1; i <= cell2; ++i) ADDELEMENT(workset,lab[i]);1 ;if (v + labelorg < 10 )0 ] = ' ' ;1 ;else 0 ;'[' ;"%s" ,s);if (csize < 10 )"] :" );4 ;else "] :" );3 ;for (jc = 0 ; jc < numcells; ++jc)0 ;for (j = vv[w]; j < vv[w]+dd[w]; ++j)if (ISELEMENT(workset,ee[j])) ++k;if (k == 0 || k == csize)if (linelength > 0 && curlen + 2 > linelength)"\n " );4 ;if (k == 0 ) fprintf(f," -" );else fprintf(f," *" );2 ;else if (linelength > 0 && curlen + i + 1 > linelength)"\n " );4 ;" %s" ,s);1 ;"\n" );/****************************************************************************** * * putptn ( f , lab , ptn , level , linelength , n ) writes the partition at the given * * level as sorted lists of integers separated by semicolons . No more than * * linelength characters ( excluding ' \ n ' ) are written per line . * * A value of linelength < = 0 dictates no line breaks at all . * * labelorg is used . * * * void int *lab, int *ptn, int level, int linelength, int n)int i;int curlen,m;#if !MAXN"putptn" );#endif '[' ,f);1 ;0 ;while (i < n)while (TRUE )if (ptn[i] > level) ++i;else break ;2 ,m,TRUE );if (i < n-1 )" |" );2 ;" ]\n" );/****************************************************************************** * * putcanon ( f , canonlab , canong , linelength , m , n ) writes the label canonlab * * and the graph canong to f , using at most linelength characters * * ( excluding ' \ n ' ) per line . labelorg is used . * * A value of linelength < = 0 dictates no line breaks at all . * * * void int *canonlab, graph *canong, int linelength, int m, int n)int i;#if !MAXNint ,workperm,workperm_sz,n+2 ,"putcanon" );#endif for (i = 0 ; i < n; ++i) workperm[i] = canonlab[i];TRUE ,linelength,n);/****************************************************************************** * * putcanon_sg ( f , canonlab , canong , linelength ) writes the label canonlab * * and the graph canong to f , using at most linelength characters * * ( excluding ' \ n ' ) per line . labelorg is used . * * A value of linelength < = 0 dictates no line breaks at all . * * * void int *canonlab, sparsegraph *canong, int linelength)int i,n;#if !MAXNint ,workperm,workperm_sz,n+2 ,"putcanon" );#endif for (i = 0 ; i < n; ++i) workperm[i] = canonlab[i];TRUE ,linelength,n);/****************************************************************************** * * readptn ( f , lab , ptn , & numcells , prompt , n ) reads a partition from f * * and establishes it in ( lab , ptn ) . * * The format can be just a number , which is fixed alone , or an arbitrary * * partition [ . . . | . . . | . . . ] . Ranges x : y can be used . * * labelorg is used . * * * void int *lab, int *ptn, int *numcells, boolean prompt, int n)int i,j;int c,v1,v2,m;#if !MAXN"readptn" );#endif if (c == '=' ) GETNW(c,f);if (ISDIGIT(c))if (v1 >= 0 && v1 < n)else "vertex out of range (%d), fixing nothing\n\n" ,return ;if (c != '[' )"illegal partition, fixing nothing\n\n" );return ;0 ;for (i = 0 ; i < n; ++i) ptn[i] = NAUTY_INFINITY;0 ;1 ;while (TRUE )if (ISDIGIT(c))if (c == ':' )if (!readinteger(f,&v2))"unfinished range\n\n" );else else while (v1 <= v2)if (v1 < 0 || v1 >= n || ISELEMENT(workset,v1))"illegal or repeated number : %d\n\n" ,else else if (c == '|' || c == ']' || c == EOF)if (j >= i)0 ;if (c == '|' )1 ;else if (j == n - 1 )return ;else 1 ;for (j = 0 ; j < n; ++j)if (!ISELEMENT(workset,j)) lab[i++] = j;1 ] = 0 ;return ;else if (c == '\n' )if (prompt) fprintf(PROMPTFILE,"] " );else "illegal character '%c' in partition\n\n" ,c);/****************************************************************************** * * unitptn ( lab , ptn , & numcells , n ) establishes the partition with one cell . * * * void int *lab,int *ptn, int *numcells, int n)int i;for (i = 0 ; i < n; ++i)1 ] = 0 ;1 ;/****************************************************************************** * * individualise ( lab , ptn , level , v , & pos , & numcells , n ) individualises vertex v . * * numcells is updated and the position of the possibly - new singleton is * * returned in pos . * * * void int *lab,int *ptn, int level,int v, int *pos, int *numcells, int n)int i,j;for (i = 0 ; i < n; ++i) if (lab[i] == v) break ;for (j = i; j > 0 && ptn[j-1 ] > level; --j) {};if (ptn[j] <= level) return ; /* individual already */ /****************************************************************************** * * cellstarts ( ptn , level , cell , m , n ) sets the set cell to contain the indices * * of the starts in ptn of the partition at level level . * * * void int *ptn, int level, set *cell, int m, int n)int i;0 ;while (i < n)while (ptn[i] > level) ++i;/****************************************************************************** * * fixit ( lab , ptn , & numcells , fixedvertex , n ) establishes the partition * * with one cell { fixedvertex } and all the other vertices ( if any ) in * * another cell . * * * void int *lab, int *ptn, int *numcells, int fixedvertex, int n)int i;for (i = 1 ; i < n; ++i)1 ;0 ] = fixedvertex;0 ;0 ] = 0 ;1 ] = 0 ;if (n == 1 ) *numcells = 1 ;else *numcells = 2 ;/****************************************************************************** * * sethash ( s , n , seed , key ) is a function whose value depends only on the * * set s , a long seed , and an integer key . It is intended to be independent * * of the word size provided long ints have at least 32 bits , and also * * independent of m . n is the underlying universal set size , NOT the * * number of setwords in the set . * * 31 bits of seed and 15 bits of key are significant . * * The result is in 0 . . 2 ^ 31 - 1 . * * * long int n, long seed, int key)int i,j,lsh,rsh;unsigned long l,res,lshmask,salt;0 xF;28 - lsh;4 ) & 0 x7FFL;0 x7FFFFFFFUL;1 UL << lsh) - 1 ;0 ;for (i = 0 ; ; ++i)0 x7FFFFFFFUL;if ((j += 16 ) >= n) break ;#if WORDSIZE > 16 0 x7FFFFFFFUL;if ((j += 16 ) >= n) break ;#if WORDSIZE == 64 0 x7FFFFFFFUL;if ((j += 16 ) >= n) break ;0 x7FFFFFFFUL;if ((j += 16 ) >= n) break ;#endif #endif return res;/****************************************************************************** * * listhash ( x , nx , key ) is a function whose value depends on the SET of values * * in the first ' nx ' entries of the array ' x ' , and the value of key . * * Machine - independent if long ints have at least 32 bits , otherwise not . * * The result is in 0 . . 2 ^ 31 - 1 . * * * long int *x, int nx, long key)unsigned long lkey,val,accum;int i;unsigned long )key & 0 x7FFFFFFFUL;for (i = 0 ; i < nx; ++i)unsigned long )x[i] & 0 x7FFFFFFFUL;0 x7FFFFFFFUL;return accum & 0 x7FFFFFFFUL;/****************************************************************************** * * hashgraph_sg ( sg , key ) is a function whose value depends on the sparse * * graph or digraph sg . * * Machine - independent if long ints have at least 32 bits , otherwise not . * * The result is in 0 . . 2 ^ 31 - 1 . * * * long long key)int n,i;int *d,*e;unsigned long val,accum;"hashgraph_sg" );for (i = 0 ; i < n; ++i)if (d[i] == 0 )else 7 ) | ((accum<<24 )&0 x7FFFFFFFUL);0 x7FFFFFFFUL;return (long )(accum & 0 x7FFFFFFFUL);/****************************************************************************** * * hashgraph ( g , m , n , key ) is a function whose value depends on the * * graph or digraph sg . * * Machine - independent if long ints have at least 32 bits , otherwise not . * * The result is in 0 . . 2 ^ 31 - 1 . * * * long int m, int n, long key)int i;unsigned long val,accum;for (i = 0 , gi = g; i < n; ++i, gi += m)12 ) | ((accum<<19 )&0 x7FFFFFFFUL);0 xFL)+i);0 x7FFFFFFFUL;return (long )(accum & 0 x7FFFFFFFUL);/****************************************************************************** * * hash ( setarray , length , key ) is a function whose value depends only on the * * first ' length ' entries of the array ' setarray ' , and the value of key . * * key should be in the range 1 . . 31 and preferably odd . * * This works best if long ints have at least 32 bits , but it ' s valid anyway . * * Not machine - indpendent ! Use sethash ( ) in preference . * * * long long length, int key)long code;while (--sptr >= setarray)32 -key)) + *sptr);return code;/****************************************************************************** * * readperm is like readvperm without the last argument . It is provided * * only for backward compatibility . * * * void int *perm, boolean prompt, int n)int nv;/****************************************************************************** * * readvperm ( f , perm , prompt , n , nv ) reads a permutation of order n from * * f , terminated by a semicolon . Any repeated or illegal numbers or * * characters are reported then ignored . Missing numbers are filled in * * in numerical order . A prompt is issued for each line if prompt ! = FALSE . * * labelorg is used . * nv is set equal to the number of numbers actually * * given . Ranges like v1 : v2 are allowed . * * * void int *perm, boolean prompt, int n, int *nv)int i;int m,c,v1,v2;#if !MAXN"readperm" );#endif 0 ;while (TRUE )if (c == ';' || c == EOF) break ;if (ISDIGIT(c))if (c == ':' )if (!readinteger(f,&v2))"unfinished range\n\n" );else else if (v1 < 0 || v1 >= n || v2 >= n || v1 > v2)if (v1 < v2)"illegal range in permutation : %d:%d\n\n" ,else "illegal number in permutation : %d\n\n" ,else for (; v1 <= v2; ++v1)if (!ISELEMENT(workset,v1))else "repeated number in permutation : %d\n\n" ,else if (c == '\n' && prompt)"+ " );if (c != '\n' )"bad character '%c' in permutation\n\n" ,char )c);for (v1 = 0 ; v1 < n; ++v1)if (!ISELEMENT(workset,v1)) perm[i++] = v1;/****************************************************************************** * * ranperm ( perm , n ) creates a random permutation in perm . * * * void int *perm, int n)int i,j,t;for (i = n; --i >= 0 ; ) perm[i] = i;for (i = n; --i > 0 ; )1 );/****************************************************************************** * * relabel ( g , perm , lab , workg , m , n ) replaces g by g ^ perm , using workg as * * scratch space . If lab ! = NULL , it is taken as a labelling vector and * * also permuted . * * * void int *lab, int *perm, graph *workg, int m, int n)long li;int i;for (li = (long )M * (long )n; --li >= 0 ;) workg[li] = g[li];0 ,M,n);if (lab != NULL)#if !MAXNint ,workperm,workperm_sz,n+2 ,"relabel" );#endif for (i = 0 ; i < n; ++i) workperm[perm[i]] = i;for (i = 0 ; i < n; ++i) lab[i] = workperm[lab[i]];/****************************************************************************** * * relabel_sg ( g , perm , lab , workg , m , n ) replaces g by g ^ perm , using workg as * * scratch space . If lab ! = NULL , it is taken as a labelling vector and * * also permuted . * * * void int *lab, int *perm, sparsegraph *workg)int i,n;if (workg)0 ,SETWORDSNEEDED(n),n);else 0 ,SETWORDSNEEDED(n),n);if (lab != NULL)#if !MAXNint ,workperm,workperm_sz,n+2 ,"relabel_sg" );#endif for (i = 0 ; i < n; ++i) workperm[perm[i]] = i;for (i = 0 ; i < n; ++i) lab[i] = workperm[lab[i]];/****************************************************************************** * * sublabel ( g , perm , nperm , workg , m , n ) replaces g by g ^ perm , using workg as * * scratch space . perm is a partial vector , of length nperm , where it is * * known that the elements of perm are distinct . * * * void int *perm, int nperm, graph *workg, int m, int n)long li;int i,j,k;int newm;for (li = (long )m * (long )n; --li >= 0 ;) workg[li] = g[li];for (li = (long )newm * (long )nperm; --li >= 0 ;) g[li] = 0 ;for (i = 0 , gi = (set*)g; i < nperm; ++i, gi += newm)for (j = 0 ; j < nperm; ++j)if (ISELEMENT(wgi,k)) ADDELEMENT(gi,j);/****************************************************************************** * * countcells ( ptn , level , n ) finds the number of elements of ptn [ 0 . . n - 1 ] * * that are < = level . * * * int int *ptn, int level, int n)int i,cnt;0 ;for (i = 0 ; i < n; ++i) if (ptn[i] <= level) ++cnt;return cnt;/****************************************************************************** * * subpartion ( lab , ptn , n , perm , nperm ) replaces the partition ( lab , ptn ) of * * 0 . . n - 1 by the induced partition of 0 . . nperm - 1 , using the partial * * ordering of 0 . . n - 1 given in perm [ 0 . . nperm - 1 ] . * * Return the new number of cells . * * * #define DEB(str,x) fprintf(stderr,"%s=%d\n" ,str,x);int int *lab, int *ptn, int n, int *perm, int nperm)int i,j;#if !MAXNint ,workperm,workperm_sz,n+2 ,"subpartition" );#endif for (i = 0 ; i < n; ++i) workperm[i] = -1 ;for (i = 0 ; i < nperm; ++i) workperm[perm[i]] = i;1 ;for (i = 0 ; i < n; ++i)if (workperm[lab[i]] >= 0 )else if (j >= 0 && ptn[i] < ptn[j])return countcells(ptn,0 ,nperm);/****************************************************************************** * * sublabel_sg ( sg , perm , nperm , workg ) replaces g by g ^ perm , using workg as * * scratch space . perm is a partial vector , of length nperm , where it is * * known that the elements of perm are distinct . * * * void int *perm, int nperm, sparsegraph *workg)int i,j,k,n;int *d,*e;int *dd,*ee;"sublabel_sg" );#if !MAXNint ,workperm,workperm_sz,n+2 ,"relabel_sg" );#endif for (i = 0 ; i < n; ++i) workperm[i] = -1 ;for (i = 0 ; i < nperm; ++i) workperm[perm[i]] = i;0 ;for (i = 0 ; i < nperm; ++i)for (k = 0 ; k < d[j]; ++k)if (workperm[e[v[j]+k]] >= 0 ) ++newnde;if (workg)else "sublabel_sg" );0 ;for (i = 0 ; i < nperm; ++i)0 ;for (k = 0 ; k < d[j]; ++k)if (workperm[e[v[j]+k]] >= 0 )if (!workg) SG_FREE(tmp);/****************************************************************************** * * copycomment ( fin , fout , delimiter ) copies fin to fout until either EOF or * * the character ' delimiter ' is read . The delimiter itself isn ' t written . * * Escape sequences \ n , \ t , \ b , \ r , \ f , \ \ , \ ' , \ " , \ \ n are recognised . Otherwise , * * ' \ ' is ignored . * * * void int delimiter)int c,backslash;FALSE ;while ((c = getc(fin)) != EOF && (c != delimiter || backslash))if (backslash)switch (c)case '\n' :break ;case 'n' :'\n' ,fout);break ;case 't' :'\t' ,fout);break ;case 'b' :'\b' ,fout);break ;case 'r' :'\r' ,fout);break ;case 'f' :'\f' ,fout);break ;case '\\' :'\\' ,fout);break ;case '\' ': '\' ',fout); break ;case '"' :'"' ,fout);break ;default :FALSE ;else if (c == '\\' )TRUE ;else /****************************************************************************** * * converse_sg ( g1 , g2 ) performs a digraph converse operation on g1 , * * leaving the result in g2 . g2 must exist and be initialised . * * If g1 is an undirected graph , g2 will be the same . * * * void int *e1,*d1,*e2,*d2;int i,k,n;"converse_sg" );"converse_sg" );for (i = 0 ; i < n; ++i) d2[i] = 0 ;for (i = 0 ; i < n; ++i)for (j = v1[i]; j < v1[i]+d1[i]; ++j) ++d2[e1[j]];0 ] = 0 ;for (i = 1 ; i < n; ++i) v2[i] = v2[i-1 ] + d2[i-1 ];for (i = 0 ; i < n; ++i) d2[i] = 0 ;for (i = 0 ; i < n; ++i)for (j = v1[i]; j < v1[i]+d1[i]; ++j)/****************************************************************************** * * complement_sg ( g1 , g2 ) sets g2 to the complement of g1 . * * If g1 has loops then the loop set is also complemented ; otherwise * * no loops are created . g2 must exist and be initialised . * * * void int *e1,*d1,*e2,*d2;int i,l,m,n;int loops;"complement_sg" );0 ;for (i = 0 ; i < n; ++i)for (j = v1[i]; j < v1[i] + d1[i]; ++j)if (e1[j] == i) ++loops;if (loops > 1 ) ndec = n*(size_t)n - g1->nde;else ndec = n*(size_t)n - n - g1->nde; "converse_sg" );#if !MAXN"putorbits" );#endif 0 ;for (i = 0 ; i < n; ++i)for (j = v1[i]; j < v1[i]+d1[i]; ++j) ADDELEMENT(workset,e1[j]);if (loops == 0 ) ADDELEMENT(workset,i);for (l = 0 ; l < n; ++l)if (!ISELEMENT(workset,l)) e2[ndec++] = l;/****************************************************************************** * * mathon_sg ( g1 , g2 ) performs a Mathon doubling operation on g1 , * * leaving the result in g2 . g2 must exist and be initialised . * * * void int *e1,*d1,*e2,*d2;int i,k,m,n1,n2;"mathon_sg" );2 *n1 + 2 ;"mathon_sg" );#if !MAXN"mathon_sg" );#endif for (i = 0 ; i < n2; ++i)0 ;for (i = 0 ; i < n1; ++i)0 ]+(d2[0 ]++)] = i+1 ;1 ]+(d2[i+1 ]++)] = 0 ;1 ]+(d2[n1+1 ]++)] = i+n1+2 ;2 ]+(d2[i+n1+2 ]++)] = n1+1 ;for (i = 0 ; i < n1; ++i)for (j = v1[i]; j < v1[i]+d1[i]; ++j)if (k == i) continue ; /* ignore loops */ 1 ]+(d2[i+1 ]++)] = k+1 ;2 ]+(d2[i+n1+2 ]++)] = k+n1+2 ;for (k = 0 ; k < n1; ++k)if (k != i && !ISELEMENT(workset,k))1 ]+(d2[i+1 ]++)] = k+n1+2 ;2 ]+(d2[k+n1+2 ]++)] = i+1 ;/****************************************************************************** * * mathon ( g1 , m1 , n1 , g2 , m2 , n2 ) performs a Mathon doubling operation on g1 , * * leaving the result in g2 . * * m1 , n1 and m2 , n2 are the values of m , n before and after the operation . * * * void int m1, int n1, graph *g2, int m2, int n2)int i,j,ii,jj;long li;for (li = (long )m2 * (long )n2; --li >= 0 ;) g2[li] = 0 ;for (i = 1 ; i <= n1; ++i)1 ;0 ,m2); /* unnecessarily convoluted code */ /* needed to avoid compiler bug */ /* in MSDOS version */ 0 );1 ,m2);1 );for (i = 0 , rowptr = g1; i < n1; ++i, rowptr += m1)for (j = 0 ; j < n1; ++j)if (j != i)2 ;2 ;if (ISELEMENT(rowptr,j))1 ,m2);1 );else 1 ,m2);1 );/****************************************************************************** * * rangraph ( g , digraph , invprob , m , n ) makes a random graph ( or digraph if * * digraph ! = FALSE ) with edge probability 1 / invprob . * * * void int invprob, int m, int n)int i,j;long li;for (li = (long )m * (long )n; --li >= 0 ;) g[li] = 0 ;for (i = 0 , row = g; i < n; ++i, row += m)if (digraph)for (j = 0 ; j < n; ++j)if (KRAN(invprob) == 0 ) ADDELEMENT(row,j);else for (j = i + 1 , col = GRAPHROW(g,j,m); j < n; ++j, col += m)if (KRAN(invprob) == 0 )/****************************************************************************** * * rangraph2 ( g , digraph , p1 , p2 , m , n ) makes a random graph ( or digraph if * * digraph ! = FALSE ) with edge probability p1 / p2 . * * * void int p1, int p2, int m, int n)int i,j;long li;for (li = (long )m * (long )n; --li >= 0 ;) g[li] = 0 ;for (i = 0 , row = g; i < n; ++i, row += m)if (digraph)for (j = 0 ; j < n; ++j)if (KRAN(p2) < p1) ADDELEMENT(row,j);else for (j = i + 1 , col = GRAPHROW(g,j,m); j < n; ++j, col += m)if (KRAN(p2) < p1)/****************************************************************************** * * rangraph2_sg ( sg , digraph , p1 , p2 , n ) makes a random graph ( or digraph if * * digraph ! = FALSE ) with edge probability p1 / p2 . sg must be initialised . * * * void int p1, int p2, int n)int i,j,k;int *dd,*ee;double rn,expec,var,sd;int ldeg;double )p1/(double )p2;double )(p2-p1)/(double )p2;if (!digraph) var *= 2 .0 ;1 .0 ;if (var > 1 .0 )for (i = 0 ; i < 19 ; ++i) sd = (sd + var/sd) / 2 .0 ;20 ;4 *inc,"rangraph2_sg" );for (i = 0 ; i < n; ++i) dd[i] = 0 ;0 ] = 0 ;0 ;if (!digraph)for (i = 0 ; i < n; ++i)0 ;for (j = i+1 ; j < n; ++j)if (KRAN(p2) < p1)2 ;if (nde > sg->elen)int ,sg->e,sg->elen,sg->elen+inc,"rangraph2_sg realloc" );if (i < n-1 ) vv[i+1 ] = vv[i] + dd[i] + ldeg;for (i = 0 ; i < n; ++i)for (k = 0 ; k < dd[i]; ++k)if (j > i) ee[vv[j]+dd[j]++] = i;else for (i = 0 ; i < n; ++i)0 ;for (j = 0 ; j < n; ++j)if (j != i && KRAN(p2) < p1)if (nde > sg->elen)int ,sg->e,sg->elen,sg->elen+inc,"rangraph2_sg realloc" );if (i < n-1 ) vv[i+1 ] = vv[i] + ldeg;/****************************************************************************/ static void int *x, int linelength, int n)/* Write n integers to f with equal values collapsed. char s[60 ];int j,v1,v2,xval,curlen;0 ;0 ;while (v1 < n)for (v2 = v1; v2 < n - 1 && x[v2+1 ] == xval; ++v2) {}if (v2 > v1)'-' ;':' ;' ' ;1 ] = '\0' ;if (linelength > 0 && curlen + j >= linelength)'\n' ,f);0 ;1 ;1 ;'\n' ,f);/****************************************************************************/ static void int *x, int linelength, int n)/* Write n integers to f with equal values combined as multiplicities. char s[60 ];int j,v1,v2,xval,curlen;0 ;0 ;while (v1 < n)for (v2 = v1; v2 < n - 1 && x[v2+1 ] == xval; ++v2) {}if (v2 > v1)1 ,s);'*' ;else 0 ;' ' ;1 ] = '\0' ;if (linelength > 0 && curlen + j >= linelength)'\n' ,f);0 ;1 ;1 ;'\n' ,f);/****************************************************************************** * * putdegs ( f , g , linelength , m , n ) writes the degree of each vertex of g to * * file f , using at most linelength characters per line ( excluding ' \ n ' ) . * * A value of linelength < = 0 dictates no line breaks at all . * * labelorg is used . * * * * FUNCTIONS CALLED : itos ( ) , putstring ( ) , setsize ( ) * * * void int linelength, int m, int n)int i;#if !MAXNint ,workperm,workperm_sz,n+2 ,"putdegs" );#endif for (i = 0 , gp = g; i < n; ++i, gp += M)/****************************************************************************** * * putdegseq ( f , g , linelength , m , n ) writes the sorted degree sequence of g * * file f , using at most linelength characters per line ( excluding ' \ n ' ) . * * A value of linelength < = 0 dictates no line breaks at all . * * * void int linelength, int m, int n)int i;#if !MAXNint ,workperm,workperm_sz,n,"putdegs" );#endif for (i = 0 , gp = g; i < n; ++i, gp += M)/****************************************************************************** * * putdegs_sg ( f , sg , linelength ) writes the degree of each vertex of sg to * * file f , using at most linelength characters per line ( excluding ' \ n ' ) . * * A value of linelength < = 0 dictates no line breaks at all . * * labelorg is used . * * * * FUNCTIONS CALLED : itos ( ) , putstring ( ) , * * * void int linelength)/****************************************************************************** * * putdegseq_sg ( f , sg , linelength ) writes the sorted degree sequence of sg to * * file f , using at most linelength characters per line ( excluding ' \ n ' ) . * * A value of linelength < = 0 dictates no line breaks at all . * * * void int linelength)int i;#if !MAXNint ,workperm,workperm_sz,sg->nv,"putdegs" );#endif for (i = 0 ; i < sg->nv; ++i)/****************************************************************************** * * complement ( g , m , n ) replaces the graph g by its complement * * No loops are created unless there are loops present , in which case the * * loops are also complemented . * * * void int m, int n)int i,j;#if !MAXN"complement" );#endif FALSE ;for (i = 0 , gp = g; i < n && !loops; ++i, gp += M)if (ISELEMENT(gp,i)) loops = TRUE ;for (i = 0 ; i < n; ++ i) ADDELEMENT(workset,i);for (i = 0 , gp = g; i < n; ++i, gp += M)for (j = 0 ; j < M; ++j) gp[j] = workset[j] & ~gp[j];if (!loops) DELELEMENT(gp,i);/****************************************************************************** * * converse ( g , m , n ) replaces the digraph g by its converse . * * There is no effect on an undirected graph . * * * void int m, int n)int i,j;for (i = 0 , gi = g; i < n; ++i, gi += M)for (j = i+1 , gj = gi+M; j < n; ++j, gj += M)if ((ISELEMENT(gi,j)!=0 ) + (ISELEMENT(gj,i)!=0 ) == 1 )/****************************************************************************** * * naututil_check ( ) checks that this file is compiled compatibly with the * * given parameters . If not , call exit ( 1 ) . * * * void int wordsize, int m, int n, int version)if (wordsize != WORDSIZE)"Error: WORDSIZE mismatch in naututil.c\n" );exit (1 );#if MAXNif (m > MAXM)"Error: MAXM inadequate in naututil.c\n" );exit (1 );if (n > MAXN)"Error: MAXN inadequate in naututil.c\n" );exit (1 );#endif if (version < NAUTYREQUIRED)"Error: naututil.c version mismatch\n" );exit (1 );/****************************************************************************** * * naututil_freedyn ( ) - free the dynamic memory in this module * * * void void )#if !MAXN#endif while (ec1)
Messung V0.5 in Prozent C=98 H=65 G=83
¤ Dauer der Verarbeitung: 0.113 Sekunden
(vorverarbeitet am 2026-06-29)
¤ *© Formatika GbR, Deutschland
