diff options
| author | Andrew Guschin <guschin@altlinux.org> | 2024-03-31 18:36:27 +0500 |
|---|---|---|
| committer | Andrew Guschin <guschin@altlinux.org> | 2024-03-31 18:36:27 +0500 |
| commit | f7aa97e10a2fbddb76e1893b7deb193ad56e7192 (patch) | |
| tree | dab29cd1166edee5c096bdfc45d1c6ab509107f8 /graph-checker/nauty/naututil.c | |
| parent | b294692a8251eb9c4ea8f3e78651d88fc6efd792 (diff) | |
latest version
Diffstat (limited to 'graph-checker/nauty/naututil.c')
| -rw-r--r-- | graph-checker/nauty/naututil.c | 3233 |
1 files changed, 3233 insertions, 0 deletions
diff --git a/graph-checker/nauty/naututil.c b/graph-checker/nauty/naututil.c new file mode 100644 index 0000000..b728561 --- /dev/null +++ b/graph-checker/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; + } +} |