/***************************************************************************** * * * 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 */ typedefstruct echunk {struct echunk *next; int edge[ECHUNKSIZE];} echunk; static TLS_ATTR echunk first_echunk = {NULL,{0}}; typedefstruct 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
/***************************************************************************** * * * 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); elseif (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); returnFALSE;
}
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); returnTRUE;
}
/***************************************************************************** * * * 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); returnFALSE;
}
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); returnTRUE;
}
/***************************************************************************** * * * 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'; returnFALSE;
}
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';
returnTRUE;
}
/***************************************************************************** * * * 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; elsereturn -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; elsereturn -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]);
}
/***************************************************************************** * * * 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];
/***************************************************************************** * * * 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);
}
}
}
} elseswitch(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);
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;
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];
}
}
}
} elseswitch(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;
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];
}
}
}
} elseswitch(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;
} elseif (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;
/***************************************************************************** * * * 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];
/***************************************************************************** * * * 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;
}
/***************************************************************************** * * * 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;
}
/***************************************************************************** * * * 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;
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);
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; elsebreak;
}
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;
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;
}
} elseif (c == '|' || c == ']' || c == EOF)
{ if (j >= i)
{
++*numcells;
ptn[j] = 0;
} if (c == '|')
i = j + 1; elseif (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;
}
} elseif (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;
/***************************************************************************** * * * 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;
}
/***************************************************************************** * * * 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; unsignedlong l,res,lshmask,salt;
setword si;
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)
{ unsignedlong lkey,val,accum; int i;
for (i = 0; i < nx; ++i)
{
val = (unsignedlong)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; unsignedlong 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; unsignedlong 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;
/***************************************************************************** * * * 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;
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. * * *
*****************************************************************************/
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];
} elseif (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;
}
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;
/***************************************************************************** * * * 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;
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;
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;
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;
staticvoid
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;
staticvoid
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;
/***************************************************************************** * * * 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;
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;
/***************************************************************************** * * * 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];
/***************************************************************************** * * * 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;
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 * * *
*****************************************************************************/
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
