summaryrefslogtreecommitdiff
path: root/nauty/naututil.c
diff options
context:
space:
mode:
authorAndrew Guschin <guschin.drew@gmail.com>2023-08-13 01:27:00 +0400
committerAndrew Guschin <guschin.drew@gmail.com>2023-08-13 06:00:02 -0500
commit58acff54b1cd64cb23b9d0b1a304eb9db768e3eb (patch)
tree87281f776e0015f218aadb5cbfdad43c66406342 /nauty/naututil.c
Initial commit
Diffstat (limited to 'nauty/naututil.c')
-rw-r--r--nauty/naututil.c3233
1 files changed, 3233 insertions, 0 deletions
diff --git a/nauty/naututil.c b/nauty/naututil.c
new file mode 100644
index 0000000..b728561
--- /dev/null
+++ b/nauty/naututil.c
@@ -0,0 +1,3233 @@
+/*****************************************************************************
+* *
+* 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 !MAXN
+DYNALLSTAT(int,workperm,workperm_sz);
+DYNALLSTAT(set,workset,workset_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[] = {1984625421L, 971524688L,1175081625L, 377165387L};
+static const long fuzz2[] = {2001381726L,1615243355L, 191176436L,1212176501L};
+#define FUZZ1(x) ((x) ^ fuzz1[(x)&3L])
+#define FUZZ2(x) ((x) ^ fuzz2[(x)&3L])
+
+#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
+setinter(set *set1, set *set2, int m)
+{
+ setword x;
+ int count,i;
+
+ count = 0;
+ for (i = m; --i >= 0;)
+ {
+ if ((x = (*set1 & *set2)) != 0) count += POPCOUNT(x);
+ ++set1;
+ ++set2;
+ }
+
+ return count;
+}
+
+/*****************************************************************************
+* *
+* setsize(set1,m) = the number of elements in the set set1. *
+* *
+*****************************************************************************/
+
+int
+setsize(set *set1, int m)
+{
+ int count,i;
+ setword x;
+
+ if (m == 1) return POPCOUNT(*set1);
+
+ count = 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
+settolist(set *set1, int m, int *list)
+{
+ int i,j,k,v;
+ setword w;
+
+ k = 0;
+ for (i = 0, v = 0; i < m; ++i, v += WORDSIZE)
+ {
+ w = set1[i];
+ while (w)
+ {
+ TAKEBIT(j,w);
+ list[k++] = v + j;
+ }
+ }
+
+ return k;
+}
+
+/*****************************************************************************
+* *
+* listtoset(list,len,set1,m) Sets set1[0..m-1] to the set {list[0..len-1]} *
+* *
+*****************************************************************************/
+
+void
+listtoset(int *list, int len, set *set1, int m)
+{
+ int i;
+ setword w;
+
+ if (m == 1)
+ {
+ w = 0;
+ for (i = 0; i < len; ++i) w |= bit[list[i]];
+ *set1 = w;
+ }
+ else
+ {
+ EMPTYSET0(set1,m);
+ 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
+flushline(FILE *f)
+{
+ boolean msg;
+ int c;
+
+ msg = FALSE;
+
+ while ((c = getc(f)) != EOF && c != '\n')
+ if (msg)
+ PUTC((char)c,ERRFILE);
+ else if (c != ' ' && c != '\t' && c != '\f' &&
+ c != '\r' && c != ',')
+ {
+ msg = TRUE;
+ fprintf(ERRFILE,"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. *
+* *
+*****************************************************************************/
+
+boolean
+readinteger(FILE *f, int *p)
+{
+ int c,ans,minus;
+
+ GETNWL(c,f);
+ if (!ISDIGIT(c) && c != '-' && c != '+')
+ {
+ if (c != EOF) ungetc(c,f);
+ return FALSE;
+ }
+
+ minus = c == '-';
+ ans = (c == '-' || c == '+' ? 0 : c - '0');
+
+ c = getc(f);
+ while (ISDIGIT(c))
+ {
+ ans *= 10;
+ ans += c - '0';
+ c = getc(f);
+ }
+
+ if (c != EOF) ungetc(c,f);
+
+ *p = (minus ? -ans : ans);
+ 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. *
+* *
+*****************************************************************************/
+
+boolean
+readinteger_sl(FILE *f, int *p)
+{
+ int c,ans,minus;
+
+ GETNW(c,f);
+ if (!ISDIGIT(c) && c != '-' && c != '+')
+ {
+ if (c != EOF) ungetc(c,f);
+ return FALSE;
+ }
+
+ minus = c == '-';
+ ans = (c == '-' || c == '+' ? 0 : c - '0');
+
+ c = getc(f);
+ while (ISDIGIT(c))
+ {
+ ans *= 10;
+ ans += c - '0';
+ c = getc(f);
+ }
+
+ if (c != EOF) ungetc(c,f);
+
+ *p = (minus ? -ans : ans);
+ 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. *
+* *
+*****************************************************************************/
+
+boolean
+readstring(FILE *f, char *s, int slen)
+{
+ int c;
+ char *slim;
+
+ slim = s + slen - 1;
+ GETNWL(c,f);
+ if (c == EOF)
+ {
+ *s = '\0';
+ return FALSE;
+ }
+
+ if (c == '"')
+ {
+ c = getc(f);
+ while (c != '"' && c != '\n' && c != '\r' && c != EOF)
+ {
+ if (s <= slim) *s++ = (char)c;
+ c = getc(f);
+ }
+ if (c != '"' && c != EOF) ungetc(c,f);
+ }
+ else
+ {
+ if (s <= slim) *s++ = (char)c;
+ c = getc(f);
+ while (c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != EOF)
+ {
+ if (s <= slim) *s++ = (char)c;
+ c = getc(f);
+ }
+ 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
+getint(FILE *f)
+{
+ int i,c;
+
+ GETNWL(c,f);
+ 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
+getint_sl(FILE *f)
+{
+ int i,c;
+
+ GETNW(c,f);
+ 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
+putset(FILE *f, set *set1, int *curlenp, int linelength,
+ int m, boolean compress)
+{
+ int slen,j1,j2;
+ char s[40];
+
+ j1 = -1;
+ while ((j1 = nextelement(set1,m,j1)) >= 0)
+ {
+ j2 = j1;
+ if (compress)
+ {
+ while (nextelement(set1,m,j2) == j2 + 1) ++j2;
+ if (j2 == j1+1) j2 = j1;
+ }
+ slen = itos(j1+labelorg,s);
+ if (j2 >= j1 + 2)
+ {
+ s[slen] = ':';
+ slen += 1 + itos(j2+labelorg,&s[slen+1]);
+ }
+
+ if (linelength > 0 && *curlenp + slen + 1 >= linelength)
+ {
+ fprintf(f,"\n ");
+ *curlenp = 3;
+ }
+ fprintf(f," %s",s);
+ *curlenp += slen + 1;
+ j1 = j2;
+ }
+}
+
+/*****************************************************************************
+* *
+* 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
+putset_firstbold(FILE *f, set *set1, int *curlenp, int linelength,
+ int m, boolean compress)
+{
+ int slen,slen1,j1,j2;
+ char s[50],c;
+ boolean bold;
+
+ bold = TRUE;
+ j1 = -1;
+ while ((j1 = nextelement(set1,m,j1)) >= 0)
+ {
+ j2 = j1;
+ if (compress)
+ {
+ while (nextelement(set1,m,j2) == j2 + 1) ++j2;
+ if (j2 == j1+1) j2 = j1;
+ }
+ slen1 = slen = itos(j1+labelorg,s);
+ if (j2 >= j1 + 2)
+ {
+ s[slen] = ':';
+ slen += 1 + itos(j2+labelorg,&s[slen+1]);
+ }
+ c = s[slen1];
+
+ if (linelength > 0 && *curlenp + slen + 1 >= linelength)
+ {
+ fprintf(f,"\n ");
+ *curlenp = 3;
+ }
+ if (bold)
+ {
+ s[slen1] = '\0';
+ fprintf(f," \033[1m%s\033[0m",s);
+ s[slen1] = c;
+ fprintf(f,"%s",&s[slen1]);
+ bold = FALSE;
+ }
+ else
+ fprintf(f," %s",s);
+
+ *curlenp += slen + 1;
+ j1 = j2;
+ }
+}
+
+/*****************************************************************************
+* *
+* 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
+readgraph(FILE *f, graph *g, boolean digraph, boolean prompt,
+ boolean edit, int linelength, int m, int n)
+{
+ int v,c;
+ int curlen,w;
+ graph *gv;
+ boolean neg;
+
+ if (!edit)
+ for (v = 0, gv = g; v < n; ++v, gv += M) EMPTYSET(gv,m);
+
+ v = 0;
+ gv = g;
+ neg = FALSE;
+
+ while (TRUE)
+ {
+ GETNWC(c,f);
+ if (ISDIGIT(c))
+ {
+ ungetc(c,f);
+ readinteger(f,&w);
+ w -= labelorg;
+ if (neg)
+ {
+ neg = FALSE;
+ if (w < 0 || w >= n || (!digraph && w == v))
+ fprintf(ERRFILE,"illegal edge (%d,%d) ignored\n\n",
+ v+labelorg,w+labelorg);
+ else
+ {
+ DELELEMENT(gv,w);
+ if (!digraph) DELELEMENT(GRAPHROW(g,w,M),v);
+ }
+ }
+ else
+ {
+ GETNWC(c,f);
+ if (c == ':')
+ if (w < 0 || w >= n)
+ fprintf(ERRFILE,
+ "illegal vertex number %d ignored\n\n",
+ w+labelorg);
+ else
+ {
+ v = w;
+ gv = GRAPHROW(g,v,M);
+ }
+ else
+ {
+ ungetc(c,f);
+ if (w < 0 || w >= n || (!digraph && w == v))
+ fprintf(ERRFILE,"illegal edge (%d,%d) ignored\n\n",
+ v+labelorg,w+labelorg);
+ else
+ {
+ ADDELEMENT(gv,w);
+ if (!digraph) ADDELEMENT(GRAPHROW(g,w,M),v);
+ }
+ }
+ }
+ }
+ else switch(c)
+ {
+ case ';':
+ neg = FALSE;
+ ++v;
+ if (v >= n) return;
+ gv = GRAPHROW(g,v,M);
+ break;
+ case '?':
+ neg = FALSE;
+ fprintf(PROMPTFILE,"%2d : ",v+labelorg);
+ curlen = 5;
+ putset(PROMPTFILE,gv,&curlen,linelength,M,FALSE);
+ fprintf(PROMPTFILE,";\n");
+ break;
+ case '\n':
+ neg = FALSE;
+ if (prompt) fprintf(PROMPTFILE,"%2d : ",v+labelorg);
+ break;
+ case EOF:
+ case '.':
+ return;
+ case '-':
+ neg = TRUE;
+ break;
+ case '!':
+ do
+ c = getc(f);
+ while (c != '\n' && c != EOF);
+ if (c == '\n') ungetc(c,f);
+ break;
+ default :
+ fprintf(ERRFILE,"illegal char '%c' - use '.' to exit\n\n",
+ (char)c);
+ }
+ }
+}
+
+/**************************************************************************/
+
+void
+ranreg_sg(sparsegraph *sg, 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;
+ boolean ok;
+ int *dd,*ee;
+ size_t *vv,nde,j;
+
+#if MAXN
+ int p[MAXREG*MAXN];
+#else
+ DYNALLSTAT(int,p,p_sz);
+
+ DYNALLOC2(int,p,p_sz,degree,n,"genrang");
+#endif
+
+ nde = (size_t)n * (size_t)degree;
+
+ SG_ALLOC(*sg,n,nde,"ranreg_sg");
+ SG_VDE(sg,vv,dd,ee);
+ DYNFREE(sg->w,sg->wlen);
+
+ sg->nv = n;
+ sg->nde = nde;
+
+ 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
+ {
+ ok = TRUE;
+
+ for (j = nde; j > 0; j -= 2)
+ {
+ i = KRAN(j-1);
+ k = p[i];
+ if (k == p[j-1]) break;
+ p[i] = p[j-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; )
+ {
+ v = p[--j];
+ w = p[--j];
+ if (v != w)
+ {
+ for (i = dd[w]; --i >= 0;) if (ee[vv[w]+i] == v) break;
+ if (i >= 0) { ok = FALSE; break; }
+ }
+ ee[vv[w]+(dd[w]++)] = v;
+ ee[vv[v]+(dd[v]++)] = w;
+ }
+ }
+ 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
+readgraph_sg(FILE *f, sparsegraph *sg, boolean digraph, boolean prompt,
+ int linelength, int n)
+{
+ int i,j,k,vv,ww,c;
+ boolean neg,done;
+ int *d,*e,*evi;
+ echunk *ec,*ecnext,*ec_end;
+ size_t ned,*v,iec,iec_end;
+
+ sg->nv = n;
+ DYNALLOC1(size_t,sg->v,sg->vlen,n,"malloc");
+ DYNALLOC1(int,sg->d,sg->dlen,n,"malloc");
+ DYNFREE(sg->w,sg->wlen);
+ v = sg->v;
+ d = sg->d;
+
+ for (i = 0; i < n; ++i) d[i] = 0;
+
+ ec = &first_echunk;
+ iec = 0;
+ vv = 0;
+ neg = done = FALSE;
+
+ while (!done)
+ {
+ GETNWC(c,f);
+ if (ISDIGIT(c))
+ {
+ ungetc(c,f);
+ readinteger(f,&ww);
+ ww -= labelorg;
+ if (neg)
+ {
+ neg = FALSE;
+ if (ww < 0 || ww >= n || (!digraph && ww == vv))
+ fprintf(ERRFILE,"illegal edge (%d,%d) ignored\n\n",
+ vv+labelorg,ww+labelorg);
+ else
+ {
+ if (iec == ECHUNKSIZE)
+ {
+ if (!ec->next)
+ {
+ ecnext = (echunk*)ALLOCS(1,sizeof(echunk));
+ if (!ecnext) alloc_error("malloc");
+ ecnext->next = NULL;
+ ec->next = ecnext;
+ }
+ ec = ec->next;
+ iec = 0;
+ }
+ ec->edge[iec++] = vv;
+ ec->edge[iec++] = -1 - ww;
+ ++d[vv];
+ if (!digraph && ww != vv) ++d[ww];
+ }
+ }
+ else
+ {
+ GETNWC(c,f);
+ if (c == ':')
+ {
+ if (ww < 0 || ww >= n)
+ fprintf(ERRFILE,
+ "illegal vertex number %d ignored\n\n",
+ ww+labelorg);
+ else
+ vv = ww;
+ }
+ else
+ {
+ ungetc(c,f);
+ if (ww < 0 || ww >= n || (!digraph && ww == vv))
+ fprintf(ERRFILE,"illegal edge (%d,%d) ignored\n\n",
+ vv+labelorg,ww+labelorg);
+ else
+ {
+ if (iec == ECHUNKSIZE)
+ {
+ if (!ec->next)
+ {
+ ecnext = (echunk*)ALLOCS(1,sizeof(echunk));
+ if (!ecnext) alloc_error("malloc");
+ ecnext->next = NULL;
+ ec->next = ecnext;
+ }
+ ec = ec->next;
+ iec = 0;
+ }
+ ec->edge[iec++] = vv;
+ ec->edge[iec++] = ww;
+ ++d[vv];
+ if (!digraph && ww != vv) ++d[ww];
+ }
+ }
+ }
+ }
+ else switch(c)
+ {
+ case ';':
+ neg = FALSE;
+ ++vv;
+ if (vv >= n) done = TRUE;
+ break;
+ case '?':
+ neg = FALSE;
+ fprintf(ERRFILE,"Command \'?\' not implemented.\n\n");
+ break;
+ case '\n':
+ neg = FALSE;
+ if (prompt) fprintf(PROMPTFILE,"%2d : ",vv+labelorg);
+ break;
+ case EOF:
+ case '.':
+ done = TRUE;
+ break;
+ case '-':
+ neg = TRUE;
+ break;
+ case '!':
+ do
+ c = getc(f);
+ while (c != '\n' && c != EOF);
+ if (c == '\n') ungetc(c,f);
+ break;
+ default :
+ fprintf(ERRFILE,"illegal char '%c' - use '.' to exit\n\n",
+ (char)c);
+ }
+ }
+
+ ned = 0;
+ for (i = 0; i < n; ++i) ned += d[i];
+ DYNALLOC1(int,sg->e,sg->elen,ned,"malloc");
+ e = sg->e;
+
+ v[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;
+
+ iec_end = iec;
+ ec_end = ec;
+
+ iec = 0;
+ ec = &first_echunk;
+
+ if (ned != 0) while (TRUE)
+ {
+ vv = ec->edge[iec++];
+ ww = ec->edge[iec++];
+
+ if (ww >= 0)
+ {
+ e[v[vv]+(d[vv]++)] = ww;
+ if (!digraph && ww != vv) e[v[ww] +(d[ww]++)] = vv;
+ }
+ else
+ {
+ ww = -1 - ww;
+ for (i = 0; i < d[vv]; ++i)
+ if (e[v[vv]+i] == ww) break;
+ if (i < d[vv])
+ {
+ e[v[vv]+i] = e[v[vv]+d[vv]-1];
+ --d[vv];
+ }
+ if (!digraph && ww != vv)
+ {
+ for (i = 0; i < d[ww]; ++i)
+ if (e[v[ww]+i] == vv) break;
+ if (i < d[ww])
+ {
+ e[v[ww]+i] = e[v[ww]+d[ww]-1];
+ --d[ww];
+ }
+ }
+ }
+ if (iec == iec_end && ec == ec_end) break;
+ if (iec == ECHUNKSIZE) { iec = 0; ec = ec->next; }
+ }
+
+ sortlists_sg(sg);
+
+ ned = 0;
+ for (i = 0; i < n; ++i)
+ {
+ if (d[i] > 1)
+ {
+ evi = e + v[i];
+ j = 1;
+ for (k = 1; k < d[i]; ++k)
+ if (evi[k] != evi[j-1]) evi[j++] = evi[k];
+ d[i] = j;
+ }
+ ned += d[i];
+ }
+ sg->nde = ned;
+}
+
+/*****************************************************************************
+* *
+* 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
+readgraph_swg(FILE *f, sparsegraph *sg, boolean digraph, boolean prompt,
+ int linelength, int n)
+{
+ int i,j,k,vv,ww,c;
+ boolean neg,done;
+ int *d,*e,*evi;
+ echunkw *ec,*ecnext,*ec_end;
+ size_t ned,*v,iec,iec_end;
+ sg_weight *wt,currwt,defwt,*wvi;
+
+ sg->nv = n;
+ DYNALLOC1(size_t,sg->v,sg->vlen,n,"malloc");
+ DYNALLOC1(int,sg->d,sg->dlen,n,"malloc");
+ v = sg->v;
+ d = sg->d;
+ wt = sg->w;
+
+ for (i = 0; i < n; ++i) d[i] = 0;
+
+ defwt = currwt = 1;
+ ec = &first_echunkw;
+ iec = 0;
+ vv = 0;
+ neg = done = FALSE;
+
+ while (!done)
+ {
+ GETNWC(c,f);
+ if (ISDIGIT(c))
+ {
+ ungetc(c,f);
+ readinteger(f,&ww);
+ ww -= labelorg;
+ if (neg)
+ {
+ neg = FALSE;
+ if (ww < 0 || ww >= n || (!digraph && ww == vv))
+ fprintf(ERRFILE,"illegal edge (%d,%d) ignored\n\n",
+ vv+labelorg,ww+labelorg);
+ else
+ {
+ if (iec == ECHUNKSIZE)
+ {
+ if (!ec->next)
+ {
+ ecnext = (echunkw*)ALLOCS(1,sizeof(echunkw));
+ if (!ecnext) alloc_error("malloc");
+ ecnext->next = NULL;
+ ec->next = ecnext;
+ }
+ ec = ec->next;
+ iec = 0;
+ }
+ ec->edge[iec].v1 = vv;
+ ec->edge[iec].v2 = -1 - ww;
+ ec->edge[iec].wt = currwt;
+ ++iec;
+ currwt = defwt;
+ ++d[vv];
+ if (ww != vv) ++d[ww];
+ }
+ }
+ else
+ {
+ GETNWC(c,f);
+ if (c == ':')
+ {
+ if (ww < 0 || ww >= n)
+ fprintf(ERRFILE,
+ "illegal vertex number %d ignored\n\n",
+ ww+labelorg);
+ else
+ vv = ww;
+ }
+ else
+ {
+ ungetc(c,f);
+ if (ww < 0 || ww >= n || (!digraph && ww == vv))
+ fprintf(ERRFILE,"illegal edge (%d,%d) ignored\n\n",
+ vv+labelorg,ww+labelorg);
+ else
+ {
+ if (iec == ECHUNKSIZE)
+ {
+ if (!ec->next)
+ {
+ ecnext = (echunkw*)ALLOCS(1,sizeof(echunkw));
+ if (!ecnext) alloc_error("malloc");
+ ecnext->next = NULL;
+ ec->next = ecnext;
+ }
+ ec = ec->next;
+ iec = 0;
+ }
+ ec->edge[iec].v1 = vv;
+ ec->edge[iec].v2 = ww;
+ ec->edge[iec].wt = currwt;
+ ++iec;
+ currwt = defwt;
+ ++d[vv];
+ if (ww != vv) ++d[ww];
+ }
+ }
+ }
+ }
+ else switch(c)
+ {
+ case ';':
+ neg = FALSE;
+ ++vv;
+ if (vv >= n) done = TRUE;
+ break;
+ case '?':
+ neg = FALSE;
+ fprintf(ERRFILE,"Command \'?\' not implemented.\n\n");
+ break;
+ case '\n':
+ neg = FALSE;
+ if (prompt) fprintf(PROMPTFILE,"%2d : ",vv+labelorg);
+ break;
+ case EOF:
+ case '.':
+ done = TRUE;
+ break;
+ case '-':
+ neg = TRUE;
+ break;
+ case 'w':
+ readinteger(f,&currwt);
+ if (currwt <= SG_MINWEIGHT)
+ {
+ fprintf(ERRFILE,"Weight too small\n\n");
+ currwt = 1;
+ }
+ break;
+ case 'W':
+ readinteger(f,&currwt);
+ if (currwt <= SG_MINWEIGHT)
+ {
+ fprintf(ERRFILE,"Weight too small\n\n");
+ currwt = 1;
+ }
+ defwt = currwt;
+ break;
+ case '!':
+ do
+ c = getc(f);
+ while (c != '\n' && c != EOF);
+ if (c == '\n') ungetc(c,f);
+ break;
+ default :
+ fprintf(ERRFILE,"illegal char '%c' - use '.' to exit\n\n",
+ (char)c);
+ }
+ }
+
+ ned = 0;
+ for (i = 0; i < n; ++i) ned += d[i];
+ DYNALLOC1(int,sg->e,sg->elen,ned,"malloc");
+ DYNALLOC1(sg_weight,sg->w,sg->wlen,ned,"malloc");
+ e = sg->e;
+ wt = sg->w;
+
+ v[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;
+
+ iec_end = iec;
+ ec_end = ec;
+
+ iec = 0;
+ ec = &first_echunkw;
+
+ if (ned != 0) while (TRUE)
+ {
+ vv = ec->edge[iec].v1;
+ ww = ec->edge[iec].v2;
+ currwt = ec->edge[iec].wt;
+ ++iec;
+
+ if (ww >= 0)
+ {
+ e[v[vv]+d[vv]] = ww;
+ wt[v[vv]+d[vv]] = currwt;
+ ++d[vv];
+ if (ww != vv)
+ {
+ e[v[ww]+d[ww]] = vv;
+ wt[v[ww]+d[ww]] = (digraph ? SG_MINWEIGHT : currwt);
+ ++d[ww];
+ }
+ }
+ else
+ {
+ ww = -1 - ww;
+ for (i = 0; i < d[vv]; ++i)
+ if (e[v[vv]+i] == ww) break;
+ if (i < d[vv])
+ {
+ e[v[vv]+i] = e[v[vv]+d[vv]-1];
+ wt[v[vv]+i] = wt[v[vv]+d[vv]-1];
+ --d[vv];
+ }
+ if (ww != vv)
+ {
+ for (i = 0; i < d[ww]; ++i)
+ if (e[v[ww]+i] == vv) break;
+ if (i < d[ww])
+ {
+ e[v[ww]+i] = e[v[ww]+d[ww]-1];
+ wt[v[ww]+i] = wt[v[ww]+d[ww]-1];
+ --d[ww];
+ }
+ }
+ }
+ if (iec == iec_end && ec == ec_end) break;
+ if (iec == ECHUNKSIZE) { iec = 0; ec = ec->next; }
+ }
+
+ sortlists_sg(sg);
+
+ ned = 0;
+ for (i = 0; i < n; ++i)
+ {
+ if (d[i] > 1)
+ {
+ evi = e + v[i];
+ wvi = wt + v[i];
+ j = 1;
+ for (k = 1; k < d[i]; ++k)
+ {
+ if (evi[k] != evi[j-1])
+ {
+ evi[j] = evi[k];
+ wvi[j] = wvi[k];
+ ++j;
+ }
+ else if (wvi[k] > wvi[j-1])
+ wvi[j-1] = wvi[k];
+ }
+ d[i] = j;
+ }
+ ned += d[i];
+ }
+ sg->nde = ned;
+}
+
+/*****************************************************************************
+* *
+* 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
+putgraph(FILE *f, graph *g, int linelength, int m, int n)
+{
+ int i,curlen;
+ set *pg;
+
+ for (i = 0, pg = g; i < n; ++i, pg += M)
+ {
+ fprintf(f,"%3d : ",i+labelorg);
+ curlen = 7;
+ putset(f,pg,&curlen,linelength,M,FALSE);
+ fprintf(f,";\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
+putgraph_sg(FILE *f, sparsegraph *sg, int linelength)
+{
+ int i,n,curlen,slen;
+ int *d,*e;
+ size_t *v,j;
+ sg_weight *wt;
+ char s[60];
+
+ n = sg->nv;
+ SWG_VDE(sg,v,d,e,wt);
+
+ for (i = 0; i < n; ++i)
+ {
+ fprintf(f,"%3d : ",i+labelorg);
+ curlen = 7;
+
+ for (j = v[i]; j < v[i]+d[i]; ++j)
+ {
+ if (wt && wt[j] != 1)
+ {
+ s[0] = 'w';
+ if (wt[j] == SG_MINWEIGHT)
+ {
+ s[1] = 'X';
+ s[2] = ' ';
+ slen = 3;
+ }
+ else
+ {
+ slen = 2 + itos(wt[j],s+1);
+ s[slen-1] = ' ';
+ }
+ slen += itos(e[j]+labelorg,s+slen);
+ }
+ else
+ slen = itos(e[j]+labelorg,s);
+
+ if (linelength > 0 && curlen + slen + 1 > linelength)
+ {
+ putstring(f,"\n ");
+ curlen = 2;
+ }
+ PUTC(' ',f);
+ putstring(f,s);
+ curlen += slen + 1;
+ }
+ putstring(f,";\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
+putmapping(FILE *f, int *lab1, int org1,int *lab2, int org2,
+ int linelength, int n)
+{
+ int i,curlen,slen;
+ char s[60];
+
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n+2,"putmapping");
+#endif
+
+ for (i = 0; i < n; ++i) workperm[lab1[i]] = lab2[i];
+
+ curlen = 0;
+ for (i = 0; i < n; ++i)
+ {
+ slen = itos(i+org1,s);
+ s[slen++] = '-';
+ slen += itos(workperm[i]+org2,&s[slen]);
+ if (linelength > 0 && curlen + slen + 1 > linelength)
+ {
+ putstring(f,"\n ");
+ curlen = 2;
+ }
+ PUTC(' ',f);
+ putstring(f,s);
+ curlen += slen + 1;
+ }
+ PUTC('\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
+putorbits(FILE *f, int *orbits, int linelength, int n)
+{
+ int i,j;
+ int m,curlen,sz,slen;
+ char s[20];
+
+ m = SETWORDSNEEDED(n);
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n+2,"putorbits");
+ DYNALLOC1(set,workset,workset_sz,m,"putorbits");
+#endif
+
+ for (i = n; --i >= 0;) workperm[i] = 0;
+ for (i = n; --i >= 0;)
+ if ((j = orbits[i]) < i)
+ {
+ workperm[i] = workperm[j];
+ workperm[j] = i;
+ }
+
+ curlen = 0;
+ for (i = 0; i < n; ++i)
+ if (orbits[i] == i)
+ {
+ sz = 0;
+ EMPTYSET(workset,m);
+ j = i;
+ do
+ {
+ ADDELEMENT(workset,j);
+ j = workperm[j];
+ ++sz;
+ }
+ while (j > 0);
+ putset(f,workset,&curlen,linelength-1,m,TRUE);
+ if (sz > 1)
+ {
+ s[0] = ' ';
+ s[1] = '(';
+ slen = 2 + itos(sz,s+2);
+ s[slen++] = ')';
+ s[slen] = '\0';
+ if (linelength > 0 && curlen + slen + 1 >= linelength)
+ {
+ fprintf(f,"\n ");
+ curlen = 3;
+ }
+ fprintf(f,"%s",s);
+ curlen += slen;
+ }
+
+ PUTC(';',f);
+ ++curlen;
+ }
+ PUTC('\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
+putorbitsplus(FILE *f, int *orbits, int linelength, int n)
+{
+ int i,j;
+ int m,curlen,sz,slen;
+ char s[20];
+
+ m = SETWORDSNEEDED(n);
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n+2,"putorbits");
+ DYNALLOC1(set,workset,workset_sz,m,"putorbits");
+#endif
+
+ for (i = n; --i >= 0;) workperm[i] = 0;
+ for (i = n; --i >= 0;)
+ if ((j = orbits[i]) < i)
+ {
+ workperm[i] = workperm[j];
+ workperm[j] = i;
+ }
+
+ curlen = 0;
+ for (i = 0; i < n; ++i)
+ if (orbits[i] == i)
+ {
+ sz = 0;
+ EMPTYSET(workset,m);
+ j = i;
+ do
+ {
+ ADDELEMENT(workset,j);
+ j = workperm[j];
+ ++sz;
+ }
+ while (j > 0);
+ putset_firstbold(f,workset,&curlen,linelength-1,m,TRUE);
+ if (sz > 1)
+ {
+ s[0] = ' ';
+ s[1] = '(';
+ slen = 2 + itos(sz,s+2);
+ s[slen++] = ')';
+ s[slen] = '\0';
+ if (linelength > 0 && curlen + slen + 1 >= linelength)
+ {
+ fprintf(f,"\n ");
+ curlen = 3;
+ }
+ fprintf(f,"%s",s);
+ curlen += slen;
+ }
+
+ PUTC(';',f);
+ ++curlen;
+ }
+ PUTC('\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
+putquotient(FILE *f, graph *g, 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;
+ set *gw;
+
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n+2,"putquotient");
+ DYNALLOC1(set,workset,workset_sz,m,"putquotient");
+#endif
+
+ numcells = 0;
+ for (cell1 = 0; cell1 < n; cell1 = cell2 + 1)
+ {
+ for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}
+ w = lab[cell1];
+ for (i = cell1 + 1; i <= cell2; ++i)
+ if (lab[i] < w) w = lab[i];
+ workperm[numcells++] = w;
+ }
+
+ for (ic = cell1 = 0; ic < numcells; ++ic, cell1 = cell2 + 1)
+ {
+ for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}
+ EMPTYSET(workset,M);
+ for (i = cell1; i <= cell2; ++i) ADDELEMENT(workset,lab[i]);
+ v = workperm[ic];
+ csize = cell2 - cell1 + 1;
+ if (v + labelorg < 10)
+ {
+ s[0] = ' ';
+ curlen = 1;
+ }
+ else
+ curlen = 0;
+ curlen += itos(v+labelorg,&s[curlen]);
+ s[curlen++] = '[';
+ curlen += itos(csize,&s[curlen]);
+ fprintf(f,"%s",s);
+ if (csize < 10)
+ {
+ fprintf(f,"] :");
+ curlen += 4;
+ }
+ else
+ {
+ fprintf(f,"] :");
+ curlen += 3;
+ }
+
+ for (jc = 0; jc < numcells; ++jc)
+ {
+ w = workperm[jc];
+ gw = GRAPHROW(g,w,m);
+ k = setinter(gw,workset,M);
+ if (k == 0 || k == csize)
+ {
+ if (linelength > 0 && curlen + 2 > linelength)
+ {
+ fprintf(f,"\n ");
+ curlen = 4;
+ }
+ if (k == 0) fprintf(f," -");
+ else fprintf(f," *");
+ curlen += 2;
+ }
+ else
+ {
+ i = itos(k,s);
+ if (linelength > 0 && curlen + i + 1 > linelength)
+ {
+ fprintf(f,"\n ");
+ curlen = 4;
+ }
+ fprintf(f," %s",s);
+ curlen += i + 1;
+ }
+ }
+ fprintf(f,"\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
+putquotient_sg(FILE *f, sparsegraph *g, 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;
+ size_t *vv,j;
+
+ n = g->nv;
+ m = SETWORDSNEEDED(n);
+ SG_VDE(g,vv,dd,ee);
+
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n+2,"putquotient");
+ DYNALLOC1(set,workset,workset_sz,m,"putquotient");
+#endif
+
+ numcells = 0;
+ for (cell1 = 0; cell1 < n; cell1 = cell2 + 1)
+ {
+ for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}
+ w = lab[cell1];
+ for (i = cell1 + 1; i <= cell2; ++i)
+ if (lab[i] < w) w = lab[i];
+ workperm[numcells++] = w;
+ }
+
+ for (ic = cell1 = 0; ic < numcells; ++ic, cell1 = cell2 + 1)
+ {
+ for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}
+ EMPTYSET(workset,M);
+ for (i = cell1; i <= cell2; ++i) ADDELEMENT(workset,lab[i]);
+ v = workperm[ic];
+ csize = cell2 - cell1 + 1;
+ if (v + labelorg < 10)
+ {
+ s[0] = ' ';
+ curlen = 1;
+ }
+ else
+ curlen = 0;
+ curlen += itos(v+labelorg,&s[curlen]);
+ s[curlen++] = '[';
+ curlen += itos(csize,&s[curlen]);
+ fprintf(f,"%s",s);
+ if (csize < 10)
+ {
+ fprintf(f,"] :");
+ curlen += 4;
+ }
+ else
+ {
+ fprintf(f,"] :");
+ curlen += 3;
+ }
+
+ for (jc = 0; jc < numcells; ++jc)
+ {
+ w = workperm[jc];
+ k = 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)
+ {
+ fprintf(f,"\n ");
+ curlen = 4;
+ }
+ if (k == 0) fprintf(f," -");
+ else fprintf(f," *");
+ curlen += 2;
+ }
+ else
+ {
+ i = itos(k,s);
+ if (linelength > 0 && curlen + i + 1 > linelength)
+ {
+ fprintf(f,"\n ");
+ curlen = 4;
+ }
+ fprintf(f," %s",s);
+ curlen += i + 1;
+ }
+ }
+ fprintf(f,"\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
+putptn(FILE *f, int *lab, int *ptn, int level, int linelength, int n)
+{
+ int i;
+ int curlen,m;
+
+ m = SETWORDSNEEDED(n);
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"putptn");
+#endif
+
+ PUTC('[',f);
+ curlen = 1;
+ i = 0;
+ while (i < n)
+ {
+ EMPTYSET(workset,m);
+ while (TRUE)
+ {
+ ADDELEMENT(workset,lab[i]);
+ if (ptn[i] > level) ++i;
+ else break;
+ }
+ putset(f,workset,&curlen,linelength-2,m,TRUE);
+ if (i < n-1)
+ {
+ fprintf(f," |");
+ curlen += 2;
+ }
+ ++i;
+ }
+ fprintf(f," ]\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
+putcanon(FILE *f, int *canonlab, graph *canong, int linelength, int m, int n)
+{
+ int i;
+
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n+2,"putcanon");
+#endif
+
+ for (i = 0; i < n; ++i) workperm[i] = canonlab[i];
+ writeperm(f,workperm,TRUE,linelength,n);
+ putgraph(f,canong,linelength,m,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
+putcanon_sg(FILE *f, int *canonlab, sparsegraph *canong, int linelength)
+{
+ int i,n;
+
+ n = canong->nv;
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n+2,"putcanon");
+#endif
+
+ for (i = 0; i < n; ++i) workperm[i] = canonlab[i];
+ writeperm(f,workperm,TRUE,linelength,n);
+ putgraph_sg(f,canong,linelength);
+}
+
+/*****************************************************************************
+* *
+* 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
+readptn(FILE *f, int *lab, int *ptn, int *numcells, boolean prompt, int n)
+{
+ int i,j;
+ int c,v1,v2,m;
+
+ m = SETWORDSNEEDED(n);
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"readptn");
+#endif
+
+ GETNW(c,f);
+ if (c == '=') GETNW(c,f);
+ if (ISDIGIT(c))
+ {
+ ungetc(c,f);
+ readinteger(f,&v1);
+ v1 -= labelorg;
+ if (v1 >= 0 && v1 < n)
+ fixit(lab,ptn,numcells,v1,n);
+ else
+ {
+ fprintf(ERRFILE,"vertex out of range (%d), fixing nothing\n\n",
+ v1+labelorg);
+ unitptn(lab,ptn,numcells,n);
+ }
+ return;
+ }
+ if (c != '[')
+ {
+ ungetc(c,f);
+ fprintf(ERRFILE,"illegal partition, fixing nothing\n\n");
+ unitptn(lab,ptn,numcells,n);
+ return;
+ }
+ EMPTYSET(workset,m);
+ *numcells = 0;
+ for (i = 0; i < n; ++i) ptn[i] = NAUTY_INFINITY;
+ i = 0;
+ j = -1;
+ while (TRUE)
+ {
+ GETNWC(c,f);
+ if (ISDIGIT(c))
+ {
+ ungetc(c,f);
+ readinteger(f,&v1);
+ v1 -= labelorg;
+ GETNWC(c,f);
+ if (c == ':')
+ if (!readinteger(f,&v2))
+ {
+ fprintf(ERRFILE,"unfinished range\n\n");
+ v2 = v1;
+ }
+ else
+ v2 -= labelorg;
+ else
+ {
+ ungetc(c,f);
+ v2 = v1;
+ }
+ while (v1 <= v2)
+ {
+ if (v1 < 0 || v1 >= n || ISELEMENT(workset,v1))
+ fprintf(ERRFILE,"illegal or repeated number : %d\n\n",
+ v1+labelorg);
+ else
+ {
+ ADDELEMENT(workset,v1);
+ lab[++j] = v1;
+ }
+ ++v1;
+ }
+ }
+ else if (c == '|' || c == ']' || c == EOF)
+ {
+ if (j >= i)
+ {
+ ++*numcells;
+ ptn[j] = 0;
+ }
+ if (c == '|')
+ i = j + 1;
+ else if (j == n - 1)
+ return;
+ else
+ {
+ i = j + 1;
+ ++*numcells;
+ for (j = 0; j < n; ++j)
+ if (!ISELEMENT(workset,j)) lab[i++] = j;
+ ptn[n-1] = 0;
+ return;
+ }
+ }
+ else if (c == '\n')
+ {
+ if (prompt) fprintf(PROMPTFILE,"] ");
+ }
+ else
+ fprintf(ERRFILE,"illegal character '%c' in partition\n\n",c);
+ }
+}
+
+/*****************************************************************************
+* *
+* unitptn(lab,ptn,&numcells,n) establishes the partition with one cell. *
+* *
+*****************************************************************************/
+
+void
+unitptn(int *lab,int *ptn, int *numcells, int n)
+{
+ int i;
+
+ for (i = 0; i < n; ++i)
+ {
+ lab[i] = i;
+ ptn[i] = NAUTY_INFINITY;
+ }
+ ptn[n-1] = 0;
+ *numcells = 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
+individualise(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) {};
+
+ *pos = j;
+ if (ptn[j] <= level) return; /* individual already */
+
+ lab[i] = lab[j];
+ lab[j] = v;
+ ptn[j] = level;
+ ++*numcells;
+}
+
+/*****************************************************************************
+* *
+* 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
+cellstarts(int *ptn, int level, set *cell, int m, int n)
+{
+ int i;
+
+ EMPTYSET(cell,m);
+ i = 0;
+ while (i < n)
+ {
+ ADDELEMENT(cell,i);
+ while (ptn[i] > level) ++i;
+ ++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
+fixit(int *lab, int *ptn, int *numcells, int fixedvertex, int n)
+{
+ int i;
+
+ for (i = 1; i < n; ++i)
+ {
+ lab[i] = i;
+ ptn[i] = 1;
+ }
+
+ lab[0] = fixedvertex;
+ lab[fixedvertex] = 0;
+ ptn[0] = 0;
+ ptn[n-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
+sethash(set *s, int n, long seed, int key)
+{
+ int i,j,lsh,rsh;
+ unsigned long l,res,lshmask,salt;
+ setword si;
+
+ lsh = key & 0xF;
+ rsh = 28 - lsh;
+ salt = (key >> 4) & 0x7FFL;
+ res = seed & 0x7FFFFFFFUL;
+ lshmask = (1UL << lsh) - 1;
+
+ j = 0;
+ for (i = 0; ; ++i)
+ {
+ si = s[i];
+ l = SWCHUNK0(si);
+ res = (((res << lsh) ^ ((res >> rsh) & lshmask) ^ l) + salt)
+ & 0x7FFFFFFFUL;
+ res = FUZZ1(res);
+ if ((j += 16) >= n) break;
+#if WORDSIZE > 16
+ l = SWCHUNK1(si);
+ res = (((res << lsh) ^ ((res >> rsh) & lshmask) ^ l) + salt)
+ & 0x7FFFFFFFUL;
+ res = FUZZ1(res);
+ if ((j += 16) >= n) break;
+#if WORDSIZE == 64
+ l = SWCHUNK2(si);
+ res = (((res << lsh) ^ ((res >> rsh) & lshmask) ^ l) + salt)
+ & 0x7FFFFFFFUL;
+ res = FUZZ1(res);
+ if ((j += 16) >= n) break;
+ l = SWCHUNK3(si);
+ res = (((res << lsh) ^ ((res >> rsh) & lshmask) ^ l) + salt)
+ & 0x7FFFFFFFUL;
+ res = FUZZ1(res);
+ 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
+listhash(int *x, int nx, long key)
+{
+ unsigned long lkey,val,accum;
+ int i;
+
+ lkey = (unsigned long)key & 0x7FFFFFFFUL;
+ accum = nx;
+
+ for (i = 0; i < nx; ++i)
+ {
+ val = (unsigned long)x[i] & 0x7FFFFFFFUL;
+ val = (val + lkey) & 0x7FFFFFFFUL;
+ accum += FUZZ1(val);
+ }
+
+ return accum & 0x7FFFFFFFUL;
+}
+
+/*****************************************************************************
+* *
+* 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
+hashgraph_sg(sparsegraph *sg, long key)
+{
+ int n,i;
+ int *d,*e;
+ size_t *v;
+ unsigned long val,accum;
+
+ CHECK_SWG(sg,"hashgraph_sg");
+ accum = n = sg->nv;
+
+ SG_VDE(sg,v,d,e);
+
+ for (i = 0; i < n; ++i)
+ if (d[i] == 0)
+ accum += FUZZ1(i);
+ else
+ {
+ accum = (accum>>7) | ((accum<<24)&0x7FFFFFFFUL);
+ val = listhash(e+v[i],d[i],key);
+ val = (val + i) & 0x7FFFFFFFUL;
+ accum += FUZZ2(val);
+ }
+
+ return (long)(accum & 0x7FFFFFFFUL);
+}
+
+/*****************************************************************************
+* *
+* 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
+hashgraph(graph *g, int m, int n, long key)
+{
+ int i;
+ set *gi;
+ unsigned long val,accum;
+
+ accum = n;
+ for (i = 0, gi = g; i < n; ++i, gi += m)
+ {
+ accum = (accum>>12) | ((accum<<19)&0x7FFFFFFFUL);
+ val = sethash(gi,n,key,(key&0xFL)+i);
+ val = (val + i) & 0x7FFFFFFFUL;
+ accum += FUZZ2(val);
+ }
+
+ return (long)(accum & 0x7FFFFFFFUL);
+}
+
+/*****************************************************************************
+* *
+* 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
+hash(set *setarray, long length, int key)
+{
+ long code;
+ set *sptr;
+
+ code = length;
+ sptr = setarray + length;
+
+ while (--sptr >= setarray)
+ code = (code<<key) ^ ((code>>(32-key)) + *sptr);
+
+ return code;
+}
+
+/*****************************************************************************
+* *
+* readperm is like readvperm without the last argument. It is provided *
+* only for backward compatibility. *
+* *
+*****************************************************************************/
+
+void
+readperm(FILE *f, int *perm, boolean prompt, int n)
+{
+ int nv;
+
+ readvperm(f,perm,prompt,n,&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
+readvperm(FILE *f, int *perm, boolean prompt, int n, int *nv)
+{
+ int i;
+ int m,c,v1,v2;
+
+ m = SETWORDSNEEDED(n);
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"readperm");
+#endif
+
+ EMPTYSET(workset,m);
+
+ i = 0;
+
+ while (TRUE)
+ {
+ GETNWC(c,f);
+ if (c == ';' || c == EOF) break;
+ if (ISDIGIT(c))
+ {
+ ungetc(c,f);
+ readinteger(f,&v1);
+ v1 -= labelorg;
+ GETNWC(c,f);
+ if (c == ':')
+ if (!readinteger(f,&v2))
+ {
+ fprintf(ERRFILE,"unfinished range\n\n");
+ v2 = v1;
+ }
+ else
+ v2 -= labelorg;
+ else
+ {
+ ungetc(c,f);
+ v2 = v1;
+ }
+
+ if (v1 < 0 || v1 >= n || v2 >= n || v1 > v2)
+ {
+ if (v1 < v2)
+ fprintf(ERRFILE,
+ "illegal range in permutation : %d:%d\n\n",
+ v1+labelorg,v2+labelorg);
+ else
+ fprintf(ERRFILE,
+ "illegal number in permutation : %d\n\n",
+ v1+labelorg);
+ }
+ else
+ for (; v1 <= v2; ++v1)
+ {
+ if (!ISELEMENT(workset,v1))
+ {
+ perm[i++] = v1;
+ ADDELEMENT(workset,v1);
+ }
+ else
+ fprintf(ERRFILE,
+ "repeated number in permutation : %d\n\n",
+ v1+labelorg);
+ }
+ }
+ else
+ {
+ if (c == '\n' && prompt)
+ fprintf(PROMPTFILE,"+ ");
+ if (c != '\n')
+ fprintf(ERRFILE,"bad character '%c' in permutation\n\n",
+ (char)c);
+ }
+ }
+
+ *nv = i;
+
+ for (v1 = 0; v1 < n; ++v1)
+ if (!ISELEMENT(workset,v1)) perm[i++] = v1;
+}
+
+/*****************************************************************************
+* *
+* ranperm(perm,n) creates a random permutation in perm. *
+* *
+*****************************************************************************/
+
+void
+ranperm(int *perm, int n)
+{
+ int i,j,t;
+
+ for (i = n; --i >= 0; ) perm[i] = i;
+
+ for (i = n; --i > 0; )
+ {
+ j = KRAN(i+1);
+ t = perm[i];
+ perm[i] = perm[j];
+ perm[j] = t;
+ }
+}
+
+/*****************************************************************************
+* *
+* 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
+relabel(graph *g, 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];
+
+ updatecan(workg,g,perm,0,M,n);
+ if (lab != NULL)
+ {
+#if !MAXN
+ DYNALLOC1(int,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
+relabel_sg(sparsegraph *sg, int *lab, int *perm, sparsegraph *workg)
+{
+ int i,n;
+ sparsegraph *tempsg;
+ sparsegraph tmp;
+
+ n = sg->nv;
+
+ if (workg)
+ {
+ tempsg = copy_sg(sg,workg);
+ updatecan_sg((graph*)tempsg,(graph*)sg,perm,0,SETWORDSNEEDED(n),n);
+ }
+ else
+ {
+ SG_INIT(tmp);
+ tempsg = copy_sg(sg,&tmp);
+ updatecan_sg((graph*)tempsg,(graph*)sg,perm,0,SETWORDSNEEDED(n),n);
+ SG_FREE(tmp);
+ }
+
+ if (lab != NULL)
+ {
+#if !MAXN
+ DYNALLOC1(int,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
+sublabel(graph *g, int *perm, int nperm, graph *workg, int m, int n)
+{
+ long li;
+ int i,j,k;
+ int newm;
+ set *gi,*wgi;
+
+ for (li = (long)m * (long)n; --li >= 0;) workg[li] = g[li];
+
+ newm = SETWORDSNEEDED(nperm);
+
+ for (li = (long)newm * (long)nperm; --li >= 0;) g[li] = 0;
+
+ for (i = 0, gi = (set*)g; i < nperm; ++i, gi += newm)
+ {
+ wgi = GRAPHROW(workg,perm[i],m);
+ for (j = 0; j < nperm; ++j)
+ {
+ k = perm[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
+countcells(int *ptn, int level, int n)
+{
+ int i,cnt;
+
+ 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
+subpartition(int *lab, int *ptn, int n, int *perm, int nperm)
+{
+ int i,j;
+
+#if !MAXN
+ DYNALLOC1(int,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;
+
+ j = -1;
+ for (i = 0; i < n; ++i)
+ {
+ if (workperm[lab[i]] >= 0)
+ {
+ ++j;
+ lab[j] = workperm[lab[i]];
+ ptn[j] = ptn[i];
+ }
+ else if (j >= 0 && ptn[i] < ptn[j])
+ ptn[j] = ptn[i];
+ }
+
+ 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
+sublabel_sg(sparsegraph *sg, int *perm, int nperm, sparsegraph *workg)
+{
+ int i,j,k,n;
+ size_t newnde,kk;
+ sparsegraph *tempsg;
+ sparsegraph tmp;
+ int *d,*e;
+ int *dd,*ee;
+ size_t *v,*vv;
+
+ CHECK_SWG(sg,"sublabel_sg");
+ n = sg->nv;
+
+#if !MAXN
+ DYNALLOC1(int,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;
+
+ newnde = 0;
+ SG_VDE(sg,v,d,e);
+
+ for (i = 0; i < nperm; ++i)
+ {
+ j = perm[i];
+ for (k = 0; k < d[j]; ++k)
+ if (workperm[e[v[j]+k]] >= 0) ++newnde;
+ }
+
+ if (workg)
+ tempsg = workg;
+ else
+ {
+ SG_INIT(tmp);
+ tempsg = &tmp;
+ }
+
+ SG_ALLOC(*tempsg,nperm,newnde,"sublabel_sg");
+ SG_VDE(tempsg,vv,dd,ee);
+
+ kk = 0;
+ for (i = 0; i < nperm; ++i)
+ {
+ j = perm[i];
+ vv[i] = kk;
+ dd[i] = 0;
+ for (k = 0; k < d[j]; ++k)
+ if (workperm[e[v[j]+k]] >= 0)
+ {
+ ee[vv[i]+dd[i]] = workperm[e[v[j]+k]];
+ ++dd[i];
+ }
+ kk += dd[i];
+ }
+ tempsg->nv = nperm;
+ tempsg->nde = newnde;
+
+ copy_sg(tempsg,sg);
+
+ 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
+copycomment(FILE *fin, FILE *fout, int delimiter)
+{
+ int c,backslash;
+
+ backslash = FALSE;
+
+ while ((c = getc(fin)) != EOF && (c != delimiter || backslash))
+ if (backslash)
+ {
+ switch (c)
+ {
+ case '\n':
+ break;
+ case 'n':
+ PUTC('\n',fout);
+ break;
+ case 't':
+ PUTC('\t',fout);
+ break;
+ case 'b':
+ PUTC('\b',fout);
+ break;
+ case 'r':
+ PUTC('\r',fout);
+ break;
+ case 'f':
+ PUTC('\f',fout);
+ break;
+ case '\\':
+ PUTC('\\',fout);
+ break;
+ case '\'':
+ PUTC('\'',fout);
+ break;
+ case '"':
+ PUTC('"',fout);
+ break;
+ default:
+ PUTC(c,fout);
+ }
+ backslash = FALSE;
+ }
+ else if (c == '\\')
+ backslash = TRUE;
+ else
+ PUTC(c,fout);
+}
+
+/*****************************************************************************
+* *
+* 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
+converse_sg(sparsegraph *g1, sparsegraph *g2)
+{
+ int *e1,*d1,*e2,*d2;
+ size_t *v1,*v2,j;
+ int i,k,n;
+
+ CHECK_SWG(g1,"converse_sg");
+ n = g1->nv;
+
+ SG_ALLOC(*g2,n,g1->nde,"converse_sg");
+ g2->nv = n;
+ g2->nde = g1->nde;
+ DYNFREE(g2->w,g2->wlen);
+
+ SG_VDE(g1,v1,d1,e1);
+ SG_VDE(g2,v2,d2,e2);
+
+ 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]];
+
+ v2[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)
+ {
+ k = e1[j];
+ e2[v2[k] + (d2[k]++)] = i;
+ }
+}
+
+/*****************************************************************************
+* *
+* 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
+complement_sg(sparsegraph *g1, sparsegraph *g2)
+{
+ int *e1,*d1,*e2,*d2;
+ size_t *v1,*v2,j,ndec;
+ int i,l,m,n;
+ int loops;
+
+ CHECK_SWG(g1,"complement_sg");
+ n = g1->nv;
+ SG_VDE(g1,v1,d1,e1);
+
+ loops = 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;
+ SG_ALLOC(*g2,n,ndec,"converse_sg");
+ g2->nv = n;
+ SG_VDE(g2,v2,d2,e2);
+
+ m = SETWORDSNEEDED(n);
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"putorbits");
+#endif
+
+ DYNFREE(g2->w,g2->wlen);
+
+ ndec = 0;
+
+ for (i = 0; i < n; ++i)
+ {
+ EMPTYSET(workset,m);
+ for (j = v1[i]; j < v1[i]+d1[i]; ++j) ADDELEMENT(workset,e1[j]);
+ if (loops == 0) ADDELEMENT(workset,i);
+
+ v2[i] = ndec;
+ for (l = 0; l < n; ++l)
+ if (!ISELEMENT(workset,l)) e2[ndec++] = l;
+ d2[i] = ndec - v2[i];
+ }
+ g2->nde = ndec;
+}
+
+/*****************************************************************************
+* *
+* mathon_sg(g1,g2) performs a Mathon doubling operation on g1, *
+* leaving the result in g2. g2 must exist and be initialised. *
+* *
+*****************************************************************************/
+
+void
+mathon_sg(sparsegraph *g1, sparsegraph *g2)
+{
+ int *e1,*d1,*e2,*d2;
+ size_t *v1,*v2,j;
+ int i,k,m,n1,n2;
+
+ CHECK_SWG(g1,"mathon_sg");
+
+ n1 = g1->nv;
+ n2 = 2*n1 + 2;
+ SG_ALLOC(*g2,n2,n2*(size_t)n1,"mathon_sg");
+ g2->nv = n2;
+ g2->nde = n2*(size_t)n1;
+ DYNFREE(g2->w,g2->wlen);
+
+ SG_VDE(g1,v1,d1,e1);
+ SG_VDE(g2,v2,d2,e2);
+
+ m = SETWORDSNEEDED(n1);
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"mathon_sg");
+#endif
+
+ for (i = 0; i < n2; ++i)
+ {
+ v2[i] = i*(size_t)n1;
+ d2[i] = 0;
+ }
+
+ for (i = 0; i < n1; ++i)
+ {
+ e2[v2[0]+(d2[0]++)] = i+1;
+ e2[v2[i+1]+(d2[i+1]++)] = 0;
+ e2[v2[n1+1]+(d2[n1+1]++)] = i+n1+2;
+ e2[v2[i+n1+2]+(d2[i+n1+2]++)] = n1+1;
+ }
+
+ for (i = 0; i < n1; ++i)
+ {
+ EMPTYSET(workset,m);
+ for (j = v1[i]; j < v1[i]+d1[i]; ++j)
+ {
+ k = e1[j];
+ if (k == i) continue; /* ignore loops */
+ ADDELEMENT(workset,k);
+ e2[v2[i+1]+(d2[i+1]++)] = k+1;
+ e2[v2[i+n1+2]+(d2[i+n1+2]++)] = k+n1+2;
+ }
+ for (k = 0; k < n1; ++k)
+ if (k != i && !ISELEMENT(workset,k))
+ {
+ e2[v2[i+1]+(d2[i+1]++)] = k+n1+2;
+ e2[v2[k+n1+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
+mathon(graph *g1, int m1, int n1, graph *g2, int m2, int n2)
+{
+ int i,j,ii,jj;
+ long li;
+ set *rowptr,*gp;
+
+ for (li = (long)m2 * (long)n2; --li >= 0;) g2[li] = 0;
+
+ for (i = 1; i <= n1; ++i)
+ {
+ ii = i + n1 + 1;
+ gp = GRAPHROW(g2,0,m2); /* unnecessarily convoluted code */
+ ADDELEMENT(gp,i); /* needed to avoid compiler bug */
+ gp = GRAPHROW(g2,i,m2); /* in MSDOS version */
+ ADDELEMENT(gp,0);
+ gp = GRAPHROW(g2,n1+1,m2);
+ ADDELEMENT(gp,ii);
+ gp = GRAPHROW(g2,ii,m2);
+ ADDELEMENT(gp,n1+1);
+ }
+
+ for (i = 0, rowptr = g1; i < n1; ++i, rowptr += m1)
+ for (j = 0; j < n1; ++j)
+ if (j != i)
+ {
+ ii = i + n1 + 2;
+ jj = j + n1 + 2;
+ if (ISELEMENT(rowptr,j))
+ {
+ gp = GRAPHROW(g2,i+1,m2);
+ ADDELEMENT(gp,j+1);
+ gp = GRAPHROW(g2,ii,m2);
+ ADDELEMENT(gp,jj);
+ }
+ else
+ {
+ gp = GRAPHROW(g2,i+1,m2);
+ ADDELEMENT(gp,jj);
+ gp = GRAPHROW(g2,ii,m2);
+ ADDELEMENT(gp,j+1);
+ }
+ }
+}
+
+/*****************************************************************************
+* *
+* rangraph(g,digraph,invprob,m,n) makes a random graph (or digraph if *
+* digraph!=FALSE) with edge probability 1/invprob. *
+* *
+*****************************************************************************/
+
+void
+rangraph(graph *g, boolean digraph, int invprob, int m, int n)
+{
+ int i,j;
+ long li;
+ set *row,*col;
+
+ 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)
+ {
+ ADDELEMENT(row,j);
+ ADDELEMENT(col,i);
+ }
+ }
+}
+
+
+/*****************************************************************************
+* *
+* rangraph2(g,digraph,p1,p2,m,n) makes a random graph (or digraph if *
+* digraph!=FALSE) with edge probability p1/p2. *
+* *
+*****************************************************************************/
+
+void
+rangraph2(graph *g, boolean digraph, int p1, int p2, int m, int n)
+{
+ int i,j;
+ long li;
+ set *row,*col;
+
+ 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)
+ {
+ ADDELEMENT(row,j);
+ ADDELEMENT(col,i);
+ }
+}
+
+/*****************************************************************************
+* *
+* 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
+rangraph2_sg(sparsegraph *sg, boolean digraph, int p1, int p2, int n)
+{
+ int i,j,k;
+ int *dd,*ee;
+ double rn,expec,var,sd;
+ int ldeg;
+ size_t *vv,inc,nde;
+
+ sg->nv = n;
+
+ rn = n;
+ expec = (rn*rn-rn)*(double)p1/(double)p2;
+ var = expec*(double)(p2-p1)/(double)p2;
+ if (!digraph) var *= 2.0;
+ sd = 1.0;
+ if (var > 1.0)
+ for (i = 0; i < 19; ++i) sd = (sd + var/sd) / 2.0;
+ inc = sd + 20;
+
+ SG_ALLOC(*sg,n,(size_t)expec+4*inc,"rangraph2_sg");
+ SG_VDE(sg,vv,dd,ee);
+ DYNFREE(sg->w,sg->wlen);
+
+ for (i = 0; i < n; ++i) dd[i] = 0;
+ vv[0] = 0;
+ nde = 0;
+
+ if (!digraph)
+ {
+ for (i = 0; i < n; ++i)
+ {
+ ldeg = 0;
+ for (j = i+1; j < n; ++j)
+ if (KRAN(p2) < p1)
+ {
+ nde += 2;
+ if (nde > sg->elen)
+ {
+ DYNREALLOC(int,sg->e,sg->elen,sg->elen+inc,
+ "rangraph2_sg realloc");
+ ee = sg->e;
+ }
+ ee[vv[i]+ldeg++] = j;
+ ++dd[j];
+ }
+ if (i < n-1) vv[i+1] = vv[i] + dd[i] + ldeg;
+ dd[i] = ldeg;
+ }
+ for (i = 0; i < n; ++i)
+ for (k = 0; k < dd[i]; ++k)
+ {
+ j = ee[vv[i]+k];
+ if (j > i) ee[vv[j]+dd[j]++] = i;
+ }
+ sg->nde = nde;
+ }
+ else
+ {
+ for (i = 0; i < n; ++i)
+ {
+ ldeg = 0;
+ for (j = 0; j < n; ++j)
+ if (j != i && KRAN(p2) < p1)
+ {
+ ++nde;
+ if (nde > sg->elen)
+ {
+ DYNREALLOC(int,sg->e,sg->elen,sg->elen+inc,
+ "rangraph2_sg realloc");
+ ee = sg->e;
+ }
+ ee[vv[i]+ldeg++] = j;
+ }
+ if (i < n-1) vv[i+1] = vv[i] + ldeg;
+ dd[i] = ldeg;
+ }
+ sg->nde = nde;
+ }
+}
+
+/****************************************************************************/
+
+static void
+putsequence(FILE *f, int *x, int linelength, int n)
+/* Write n integers to f with equal values collapsed.
+ * labelorg is used. */
+{
+ char s[60];
+ int j,v1,v2,xval,curlen;
+
+ curlen = 0;
+ v1 = 0;
+ while (v1 < n)
+ {
+ xval = x[v1];
+
+ for (v2 = v1; v2 < n - 1 && x[v2+1] == xval; ++v2) {}
+ j = itos(v1+labelorg,s);
+ if (v2 > v1)
+ {
+ s[j++] = '-';
+ j += itos(v2+labelorg,&s[j]);
+ }
+ s[j++] = ':';
+ j += itos(xval,&s[j]);
+ s[j] = ' ';
+ s[j+1] = '\0';
+ if (linelength > 0 && curlen + j >= linelength)
+ {
+ PUTC('\n',f);
+ curlen = 0;
+ }
+ curlen += j + 1;
+ putstring(f,s);
+ v1 = v2 + 1;
+ }
+ PUTC('\n',f);
+}
+
+/****************************************************************************/
+
+static void
+putnumbers(FILE *f, int *x, int linelength, int n)
+/* Write n integers to f with equal values combined as multiplicities.
+ * labelorg is NOT used. */
+{
+ char s[60];
+ int j,v1,v2,xval,curlen;
+
+ curlen = 0;
+ v1 = 0;
+ while (v1 < n)
+ {
+ xval = x[v1];
+
+ for (v2 = v1; v2 < n - 1 && x[v2+1] == xval; ++v2) {}
+ if (v2 > v1)
+ {
+ j = itos(v2-v1+1,s);
+ s[j++] = '*';
+ }
+ else
+ j = 0;
+
+ j += itos(xval,&s[j]);
+ s[j] = ' ';
+ s[j+1] = '\0';
+ if (linelength > 0 && curlen + j >= linelength)
+ {
+ PUTC('\n',f);
+ curlen = 0;
+ }
+ curlen += j + 1;
+ putstring(f,s);
+ v1 = v2 + 1;
+ }
+ PUTC('\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
+putdegs(FILE *f, graph *g, int linelength, int m, int n)
+{
+ int i;
+ graph *gp;
+
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n+2,"putdegs");
+#endif
+
+ for (i = 0, gp = g; i < n; ++i, gp += M)
+ workperm[i] = setsize(gp,m);
+
+ putsequence(f,workperm,linelength,n);
+}
+
+/*****************************************************************************
+* *
+* 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
+putdegseq(FILE *f, graph *g, int linelength, int m, int n)
+{
+ int i;
+ graph *gp;
+
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n,"putdegs");
+#endif
+
+ for (i = 0, gp = g; i < n; ++i, gp += M)
+ workperm[i] = setsize(gp,m);
+
+ sort1int(workperm,n);
+ putnumbers(f,workperm,linelength,n);
+}
+
+/*****************************************************************************
+* *
+* 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
+putdegs_sg(FILE *f, sparsegraph *sg, int linelength)
+{
+ putsequence(f,sg->d,linelength,sg->nv);
+}
+
+/*****************************************************************************
+* *
+* 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
+putdegseq_sg(FILE *f, sparsegraph *sg, int linelength)
+{
+ int i;
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,sg->nv,"putdegs");
+#endif
+
+ for (i = 0; i < sg->nv; ++i)
+ workperm[i] = sg->d[i];
+
+ sort1int(workperm,sg->nv);
+ putnumbers(f,workperm,linelength,sg->nv);
+}
+
+/*****************************************************************************
+* *
+* 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
+complement(graph *g, int m, int n)
+{
+ boolean loops;
+ int i,j;
+ graph *gp;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"complement");
+#endif
+
+ loops = FALSE;
+ for (i = 0, gp = g; i < n && !loops; ++i, gp += M)
+ if (ISELEMENT(gp,i)) loops = TRUE;
+
+ EMPTYSET(workset,m);
+ 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
+converse(graph *g, int m, int n)
+{
+ int i,j;
+ graph *gi,*gj;
+
+ 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)
+ {
+ FLIPELEMENT(gi,j);
+ FLIPELEMENT(gj,i);
+ }
+}
+
+/*****************************************************************************
+* *
+* naututil_check() checks that this file is compiled compatibly with the *
+* given parameters. If not, call exit(1). *
+* *
+*****************************************************************************/
+
+void
+naututil_check(int wordsize, int m, int n, int version)
+{
+ if (wordsize != WORDSIZE)
+ {
+ fprintf(ERRFILE,"Error: WORDSIZE mismatch in naututil.c\n");
+ exit(1);
+ }
+
+#if MAXN
+ if (m > MAXM)
+ {
+ fprintf(ERRFILE,"Error: MAXM inadequate in naututil.c\n");
+ exit(1);
+ }
+
+ if (n > MAXN)
+ {
+ fprintf(ERRFILE,"Error: MAXN inadequate in naututil.c\n");
+ exit(1);
+ }
+#endif
+
+ if (version < NAUTYREQUIRED)
+ {
+ fprintf(ERRFILE,"Error: naututil.c version mismatch\n");
+ exit(1);
+ }
+}
+
+/*****************************************************************************
+* *
+* naututil_freedyn() - free the dynamic memory in this module *
+* *
+*****************************************************************************/
+
+void
+naututil_freedyn(void)
+{
+ echunk *ec1,*ec2;
+
+#if !MAXN
+ DYNFREE(workperm,workperm_sz);
+ DYNFREE(workset,workset_sz);
+#endif
+ ec1 = first_echunk.next;
+
+ while (ec1)
+ {
+ ec2 = ec1->next;
+ FREES(ec1);
+ ec1 = ec2;
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 09:15:37 +0000