Page MenuHomePhorge
Files F27032942

gtools.c
No OneTemporary
Actions

Authored By
Unknown
Size
68 KB
Referenced Files
None
Subscribers
None

gtools.c
View Options

/* gtools.c : Common routines for gtools programs. */
/* Version 4.2, Oct 2017. */
/* Todo: size check if MAXN>0; option to free memory */
#include "gtools.h"
#ifndef SEEK_SET
#define SEEK_SET 0
#define SEEK_CUR 1
#define SEEK_END 2
#endif
TLS_ATTR size_t ogf_linelen;
TLS_ATTR boolean is_pipe;
#if HAVE_FSEEKO
#define FSEEK_VER fseeko
#define FTELL_VER ftello
#define OFF_T_VER off_t
#else
#if !FTELL_DEC
extern long ftell(FILE*);
extern int fseek(FILE*,long,int);
#endif
#define FSEEK_VER fseek
#define FTELL_VER ftell
#define OFF_T_VER long
#endif
#if !POPEN_DEC
extern FILE *popen(const char*,const char*);
#endif
/*
Version 1.1: Fixed sparse6 input for powers of 2. May 9, 1998
Version 1.2: Added "cmd: ..." option for opengraphfile().
Fixed readg() bug (could not be invisible). Oct 5, 1998
Version 1.3: Added "is_pipe". June 20, 2002
Version 1.4: Stuff for autoconf. August 30, 2002
Version 1.5: Unlocked stdio for efficiency. October 31, 2004
Also fwrite() in place of fputs() for writeline().
Version 1.6: i/o for sparsegraph; use of s6len; improve allocations
Version 1.7: Add stringcounts()
Add very long size code (see formats.txt)
Version 1.8: Add gtools_check()
Version 1.9: Add writepc_sg(), readpc_sg() and readpcle_sg()
Add planar_code options to opengraphfile()
Version 2.4: Add writeec_sg(), readec_sg() (MISSING!)
Add edge_code options to opengraphfile()
Version 2.5: Remove sortints(), not used
Version 2.6: Add sgtog6() and writeg6_sg()
Version 2.7: Add lots of explicit casts.
Fix planar code output for n > 255.
Version 3.0: Procedures for incremental sparse6 format.
Add checkgline()
Version 4.0: Procedures for digraph6 format.
Version 4.1: Made encodegraphsize() external.
Version 4.2: Fixes for null graphs; thanks to Kevin Ryde.
*/
#define B(i) (1 << ((i)-1))
#define M(i) ((1 << (i))-1)
/*********************************************************************
opengraphfile(filename,codetype,assumefixed,position)
opens and positions a file for reading graphs.
filename = the name of the file to open
(NULL means stdin, assumed already open)
If filename starts with "cmd:", the remainder is taken
to be a command to open a subshell for, using a pipe.
codetype = returns a code for the format.
This is a combination of SPARSE6, GRAPH6, PLANARCODE,
PLANARCODELE, PLANARCODEBE, EDGECODE, DIGRAPH6,
UNKNOWN_TYPE and HAS_HEADER.
If a header is present, that overrides the data.
If there is no header, the first graph is examined.
assumefixed = nonzero if files other than stdin or pipes should be
assumed to be seekable and have equal record sizes.
Ignored if there is a sparse6 header or the first
graph has sparse6 format.
position = the number of the record to position to
(the first is number 1; 0 and -NOLIMIT also mean
to position at start). planar_code files can only
be positioned at the start.
If the file starts with ">", there must be a header.
Otherwise opengraphfile() fails.
The value returned is a file pointer or NULL.
If assumedfixed is not zero and position > 1, the global variable
ogf_linelen is set to the length (including \n) of the length of the
first record. UPDATE
The global variable is_pipe is set to whether the input file is a pipe.
**********************************************************************/
FILE*
opengraphfile(char *filename, int *codetype, int assumefixed, long position)
{
FILE *f;
int c,bl,firstc;
long i,l;
OFF_T_VER pos,pos1,pos2;
boolean bad_header;
is_pipe = FALSE;
if (filename == NULL)
{
f = stdin;
assumefixed = FALSE;
}
else
{
if (filename[0] == 'c' && filename[1] == 'm'
&& filename[2] == 'd' && filename[3] == ':')
{
#if !HAVE_POPEN
gt_abort
(">E The \"cmd:\" option is not available in this version.\n");
#else
filename += 4;
while (*filename == ' ') ++filename;
f = popen(filename,"r");
#endif
assumefixed = FALSE;
is_pipe = TRUE;
}
else
f = fopen(filename,"r");
if (f == NULL)
{
fprintf(stderr,">E opengraphfile: can't open %s\n",filename);
return NULL;
}
}
FLOCKFILE(f);
firstc = c = GETC(f);
if (c == EOF)
{
*codetype = GRAPH6;
FUNLOCKFILE(f);
return f;
}
if (c != '>')
{
*codetype = firstc == ':' ? SPARSE6 : firstc == '&' ? DIGRAPH6 : GRAPH6;
ungetc(c,f);
}
else
{
bad_header = FALSE;
if ((c = GETC(f)) == EOF || c != '>')
bad_header = TRUE;
if (!bad_header && ((c = GETC(f)) == EOF ||
(c != 'g' && c != 's' && c != 'p')))
bad_header = TRUE;
if (!bad_header && c == 'g')
{
if ((c = GETC(f)) == EOF || c != 'r' ||
(c = GETC(f)) == EOF || c != 'a' ||
(c = GETC(f)) == EOF || c != 'p' ||
(c = GETC(f)) == EOF || c != 'h' ||
(c = GETC(f)) == EOF || c != '6' ||
(c = GETC(f)) == EOF || c != '<' ||
(c = GETC(f)) == EOF || c != '<')
bad_header = TRUE;
else
*codetype = GRAPH6 | HAS_HEADER;
}
else if (!bad_header && c == 'd')
{
if ((c = GETC(f)) == EOF || c != 'i' ||
(c = GETC(f)) == EOF || c != 'g' ||
(c = GETC(f)) == EOF || c != 'r' ||
(c = GETC(f)) == EOF || c != 'a' ||
(c = GETC(f)) == EOF || c != 'p' ||
(c = GETC(f)) == EOF || c != 'h' ||
(c = GETC(f)) == EOF || c != '6' ||
(c = GETC(f)) == EOF || c != '<' ||
(c = GETC(f)) == EOF || c != '<')
bad_header = TRUE;
else
*codetype = DIGRAPH6 | HAS_HEADER;
}
else if (!bad_header && c == 'e')
{
if ((c = GETC(f)) == EOF || c != 'd' ||
(c = GETC(f)) == EOF || c != 'g' ||
(c = GETC(f)) == EOF || c != 'e' ||
(c = GETC(f)) == EOF || c != '_' ||
(c = GETC(f)) == EOF || c != 'c' ||
(c = GETC(f)) == EOF || c != 'o' ||
(c = GETC(f)) == EOF || c != 'd' ||
(c = GETC(f)) == EOF || c != 'e' ||
(c = GETC(f)) == EOF || c != '<' ||
(c = GETC(f)) == EOF || c != '<')
bad_header = TRUE;
else
*codetype = EDGECODE | HAS_HEADER;
}
else if (!bad_header && c == 's')
{
if ((c = GETC(f)) == EOF || c != 'p' ||
(c = GETC(f)) == EOF || c != 'a' ||
(c = GETC(f)) == EOF || c != 'r' ||
(c = GETC(f)) == EOF || c != 's' ||
(c = GETC(f)) == EOF || c != 'e' ||
(c = GETC(f)) == EOF || c != '6' ||
(c = GETC(f)) == EOF || c != '<' ||
(c = GETC(f)) == EOF || c != '<')
bad_header = TRUE;
else
*codetype = SPARSE6 | HAS_HEADER;
}
else if (!bad_header && c == 'p')
{
if ((c = GETC(f)) == EOF || c != 'l' ||
(c = GETC(f)) == EOF || c != 'a' ||
(c = GETC(f)) == EOF || c != 'n' ||
(c = GETC(f)) == EOF || c != 'a' ||
(c = GETC(f)) == EOF || c != 'r' ||
(c = GETC(f)) == EOF || c != '_' ||
(c = GETC(f)) == EOF || c != 'c' ||
(c = GETC(f)) == EOF || c != 'o' ||
(c = GETC(f)) == EOF || c != 'd' ||
(c = GETC(f)) == EOF || c != 'e')
bad_header = TRUE;
else
{
if ((c = GETC(f)) == EOF)
bad_header = TRUE;
else if (c == ' ')
{
if ((bl = GETC(f)) == EOF || (bl != 'l' && bl != 'b') ||
(c = GETC(f)) == EOF || c != 'e' ||
(c = GETC(f)) == EOF || c != '<' ||
(c = GETC(f)) == EOF || c != '<')
bad_header = TRUE;
else if (bl == 'l')
*codetype = PLANARCODELE | HAS_HEADER;
else
*codetype = PLANARCODEBE | HAS_HEADER;
}
else if (c == '<')
{
if ((c = GETC(f)) == EOF || c != '<')
bad_header = TRUE;
else
*codetype = PLANARCODE | HAS_HEADER;
}
else
bad_header = TRUE;
}
}
if (bad_header)
{
fprintf(stderr,">E opengraphfile: illegal header in %s\n",
filename == NULL ? "stdin" : filename);
*codetype = UNKNOWN_TYPE | HAS_HEADER;
FUNLOCKFILE(f);
return NULL;
}
}
if (position <= 1) return f;
if (*codetype&PLANARCODEANY)
{
fprintf(stderr,
">E opengraphfile: planar_code files can only be opened at the start\n");
*codetype = UNKNOWN_TYPE | HAS_HEADER;
FUNLOCKFILE(f);
fclose(f);
return NULL;
}
if (*codetype&EDGECODE)
{
fprintf(stderr,
">E opengraphfile: edge_code files can only be opened at the start\n");
*codetype = UNKNOWN_TYPE | HAS_HEADER;
FUNLOCKFILE(f);
fclose(f);
return NULL;
}
if (!assumefixed || (*codetype&SPARSE6) || firstc == ':')
{
l = 1;
while ((c = GETC(f)) != EOF)
{
if (c == '\n')
{
++l;
if (l == position) break;
}
}
if (l == position) return f;
fprintf(stderr,
">E opengraphfile: can't find line %ld in %s\n",position,
filename == NULL ? "stdin" : filename);
return NULL;
}
else
{
pos1 = FTELL_VER(f);
if (pos1 < 0)
{
fprintf(stderr,">E opengraphfile: error on first ftell\n");
return NULL;
}
for (i = 1; (c = GETC(f)) != EOF && c != '\n'; ++i) {}
ogf_linelen = i;
if (c == EOF)
{
fprintf(stderr,
">E opengraphfile: required record no present\n");
FUNLOCKFILE(f);
return NULL;
}
pos2 = FTELL_VER(f);
if (pos2 < 0)
{
fprintf(stderr,">E opengraphfile: error on second ftell\n");
return NULL;
}
pos = pos1 + (position-1)*(pos2-pos1);
if (FSEEK_VER(f,pos,SEEK_SET) < 0)
{
fprintf(stderr,">E opengraphfile: seek failed\n");
return NULL;
}
}
FUNLOCKFILE(f);
return f;
}
/*********************************************************************/
void
writeline(FILE *f, char *s)
/* write a line with error checking */
/* \n is not appended automatically */
{
size_t slen;
slen = strlen(s);
if (fwrite(s,1,slen,f) != slen || ferror(f))
gt_abort(">E writeline : error on writing\n");
}
/*********************************************************************/
/* This function used to be called getline(), but this was changed due
to too much confusion with the GNU function of that name.
*/
char*
gtools_getline(FILE *f) /* read a line with error checking */
/* includes \n (if present) and \0. Immediate EOF causes NULL return. */
{
DYNALLSTAT(char,s,s_sz);
int c;
long i;
DYNALLOC1(char,s,s_sz,5000,"gtools_getline");
FLOCKFILE(f);
i = 0;
while ((c = GETC(f)) != EOF && c != '\n')
{
if (i == s_sz-3)
DYNREALLOC(char,s,s_sz,3*(s_sz/2)+10000,"gtools_getline");
s[i++] = (char)c;
}
FUNLOCKFILE(f);
if (i == 0 && c == EOF) return NULL;
if (c == '\n') s[i++] = '\n';
s[i] = '\0';
return s;
}
/****************************************************************************/
char*
getecline(FILE *f) /* read an edge_code line */
/* No trailing \n or \0 is added. Immediate EOF causes NULL return. */
{
size_t headsize,bodysize;
int sizesize,edgesize;
int c1,c,i;
DYNALLSTAT(unsigned char,s,s_sz);
FLOCKFILE(f);
if ((c1 = GETC(f)) == EOF) return NULL;
if (c1 > 0)
{
bodysize = c1;
edgesize = 1;
headsize = 1;
}
else
{
if ((c = GETC(f)) == EOF)
gt_abort(">E Incomplete edge_code line\n");
else
{
sizesize = c >> 4;
edgesize = c & 0xF;
bodysize = 0;
for (i = 0; i < sizesize; ++i)
{
if ((c = GETC(f)) == EOF)
gt_abort(">E Incomplete edge_code line\n");
else
bodysize = (bodysize << 8) + c;
}
headsize = 2 + sizesize;
}
}
DYNALLOC1(unsigned char,s,s_sz,headsize+bodysize,"getecline");
s[0] = (unsigned char)c1;
if (c1 == 0)
{
s[1] = (char)((sizesize << 4) + edgesize);
for (i = 0; i < sizesize; ++i)
s[headsize-1-i] = (bodysize >> 8*i) & 0xFF;
}
if (bodysize > 0 && fread(s+headsize,bodysize,1,f) != bodysize)
gt_abort(">E Incomplete edge_code line\n");
FUNLOCKFILE(f);
return (char*)s;
}
int
graphsize(char *s)
/* Get size of graph out of graph6, digraph6 or sparse6 string. */
{
char *p;
int n;
if (s[0] == ':' || s[0] == '&') p = s+1;
else p = s;
n = *p++ - BIAS6;
if (n > SMALLN)
{
n = *p++ - BIAS6;
if (n > SMALLN)
{
n = *p++ - BIAS6;
n = (n << 6) | (*p++ - BIAS6);
n = (n << 6) | (*p++ - BIAS6);
n = (n << 6) | (*p++ - BIAS6);
n = (n << 6) | (*p++ - BIAS6);
n = (n << 6) | (*p++ - BIAS6);
}
else
{
n = (n << 6) | (*p++ - BIAS6);
n = (n << 6) | (*p++ - BIAS6);
}
}
return n;
}
/****************************************************************************/
void
encodegraphsize(int n, char **pp)
/* Encode the size n in a string starting at **p, and reset **p
to point to the character after the size */
{
char *p;
p = *pp;
if (n <= SMALLN)
*p++ = (char)(BIAS6 + n);
else if (n <= SMALLISHN)
{
*p++ = MAXBYTE;
*p++ = (char)(BIAS6 + (n >> 12));
*p++ = (char)(BIAS6 + ((n >> 6) & C6MASK));
*p++ = (char)(BIAS6 + (n & C6MASK));
}
else
{
*p++ = MAXBYTE;
*p++ = MAXBYTE;
*p++ = (char)(BIAS6 + (n >> 30));
*p++ = (char)(BIAS6 + ((n >> 24) & C6MASK));
*p++ = (char)(BIAS6 + ((n >> 18) & C6MASK));
*p++ = (char)(BIAS6 + ((n >> 12) & C6MASK));
*p++ = (char)(BIAS6 + ((n >> 6) & C6MASK));
*p++ = (char)(BIAS6 + (n & C6MASK));
}
*pp = p;
}
/****************************************************************************/
void
stringcounts(char *s, int *pn, size_t *pe)
/* Determine number of edges of graph6, digraph6 or sparse6 string */
{
char *p;
int i,j,k,x,nb,v,n,need;
size_t count;
boolean done;
n = graphsize(s);
*pn = n;
p = s + (s[0] == ':' || s[0] == '&') + SIZELEN(n);
if (s[0] == ':') /* sparse6 */
{
count = 0;
for (i = n-1, nb = 0; i > 0 ; i >>= 1, ++nb) {}
k = 0;
v = 0;
done = FALSE;
while (!done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if ((x & B(k))) ++v;
--k;
need = nb;
j = 0;
while (need > 0 && !done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if (need >= k)
{
j = (j << k) | (x & M(k));
need -= k; k = 0;
}
else
{
k -= need;
j = (j << need) | ((x >> k) & M(need));
need = 0;
}
}
if (done) continue;
if (j > v)
v = j;
else if (v < n)
++count;
}
}
else /* graph6 or digraph6 */
{
count = 0;
for (; *p != '\n' && *p != '\0'; ++p)
count += bytecount[*p - BIAS6];
}
*pe = count;
}
/****************************************************************************/
void
stringtograph(char *s, graph *g, int m)
/* Convert string (graph6, digraph6 or sparse6 format) to graph. */
/* Assumes g is big enough to hold it. */
{
char *p;
int n,i,j,k,v,x,nb,need;
size_t ii;
set *gi,*gj;
boolean done;
n = graphsize(s);
if (n == 0) return;
p = s + (s[0] == ':' || s[0] == '&') + SIZELEN(n);
if (TIMESWORDSIZE(m) < n)
gt_abort(">E stringtograph: impossible m value\n");
for (ii = m*(size_t)n; --ii > 0;) g[ii] = 0;
g[0] = 0;
if (s[0] != ':' && s[0] != '&') /* graph6 format */
{
k = 1;
for (j = 1; j < n; ++j)
{
gj = GRAPHROW(g,j,m);
for (i = 0; i < j; ++i)
{
if (--k == 0)
{
k = 6;
x = *(p++) - BIAS6;
}
if ((x & TOPBIT6))
{
gi = GRAPHROW(g,i,m);
ADDELEMENT(gi,j);
ADDELEMENT(gj,i);
}
x <<= 1;
}
}
}
else if (s[0] == '&')
{
k = 1;
for (i = 0; i < n; ++i)
{
gi = GRAPHROW(g,i,m);
for (j = 0; j < n; ++j)
{
if (--k == 0)
{
k = 6;
x = *(p++) - BIAS6;
}
if ((x & TOPBIT6))
{
ADDELEMENT(gi,j);
}
x <<= 1;
}
}
}
else /* sparse6 format */
{
for (i = n-1, nb = 0; i > 0 ; i >>= 1, ++nb) {}
k = 0;
v = 0;
done = FALSE;
while (!done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if ((x & B(k))) ++v;
--k;
need = nb;
j = 0;
while (need > 0 && !done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if (need >= k)
{
j = (j << k) | (x & M(k));
need -= k; k = 0;
}
else
{
k -= need;
j = (j << need) | ((x >> k) & M(need));
need = 0;
}
}
if (done) continue;
if (j > v)
v = j;
else if (v < n)
{
ADDELEMENT(GRAPHROW(g,v,m),j);
ADDELEMENT(GRAPHROW(g,j,m),v);
}
}
}
}
/****************************************************************************/
void
stringtograph_inc(char *s, graph *g, int m,
graph *prevg, int prevn)
/* Convert string (graph6, digraph6 or sparse6 format) to graph,
allowing incremental sparse6 format with a prior graph assumed
to have matching m,n values.
If prevg != NULL and type is is6, use prevg as prior graph.
Assumes g is big enough to hold it.
*digraph is set according to the graph type.
*/
{
char *p;
int n,i,j,k,v,x,nb,need;
size_t ii;
set *gi,*gj;
boolean done;
if (s[0] == ';' && !prevg)
gt_abort(">E stringtograph_inc missing prior graph\n");
if (s[0] == ';')
{
n = prevn;
if (n == 0) return;
p = s + 1;
for (ii = m*(size_t)n; --ii > 0;) g[ii] = prevg[ii];
g[0] = prevg[0];
}
else
{
n = graphsize(s);
if (n == 0) return;
p = s + (s[0] == ':' || s[0] == '&') + SIZELEN(n);
for (ii = m*(size_t)n; --ii > 0;) g[ii] = 0;
g[0] = 0;
}
if (TIMESWORDSIZE(m) < n)
gt_abort(">E stringtograph_inc: impossible m value\n");
if (s[0] != ':' && s[0] != ';' && s[0] != '&') /* graph6 format */
{
k = 1;
for (j = 1; j < n; ++j)
{
gj = GRAPHROW(g,j,m);
for (i = 0; i < j; ++i)
{
if (--k == 0)
{
k = 6;
x = *(p++) - BIAS6;
}
if ((x & TOPBIT6))
{
gi = GRAPHROW(g,i,m);
FLIPELEMENT(gi,j);
if (i != j) FLIPELEMENT(gj,i);
}
x <<= 1;
}
}
}
else if (s[0] == '&') /* digraph6 format */
{
k = 1;
for (j = 0; j < n; ++j)
{
gj = GRAPHROW(g,j,m);
for (i = 0; i < n; ++i)
{
if (--k == 0)
{
k = 6;
x = *(p++) - BIAS6;
}
if ((x & TOPBIT6))
{
FLIPELEMENT(gj,i);
}
x <<= 1;
}
}
}
else /* sparse6 format */
{
for (i = n-1, nb = 0; i != 0 ; i >>= 1, ++nb) {}
k = 0;
v = 0;
done = FALSE;
while (!done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if ((x & B(k))) ++v;
--k;
need = nb;
j = 0;
while (need > 0 && !done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if (need >= k)
{
j = (j << k) | (x & M(k));
need -= k; k = 0;
}
else
{
k -= need;
j = (j << need) | ((x >> k) & M(need));
need = 0;
}
}
if (done) continue;
if (j > v)
v = j;
else if (v < n)
{
FLIPELEMENT(GRAPHROW(g,v,m),j);
if (j != v) FLIPELEMENT(GRAPHROW(g,j,m),v);
}
}
}
}
/***********************************************************************/
graph* /* read graph into nauty format */
readgg(FILE *f, graph *g, int reqm, int *pm, int *pn, boolean *digraph)
/* graph6, digraph6 and sparse6 formats are supported
f = an open file
g = place to put the answer (NULL for dynamic allocation)
reqm = the requested value of m (0 => compute from n)
*pm = the actual value of m
*pn = the value of n
*digraph = whether the input is a digraph
*/
{
char *s,*p;
int m,n;
if ((readg_line = gtools_getline(f)) == NULL) return NULL;
s = readg_line;
if (s[0] == ':')
{
readg_code = SPARSE6;
*digraph = FALSE;
p = s + 1;
}
else if (s[0] == '&')
{
readg_code = DIGRAPH6;
*digraph = TRUE;
p = s + 1;
}
else
{
readg_code = GRAPH6;
*digraph = FALSE;
p = s;
}
while (*p >= BIAS6 && *p <= MAXBYTE)
++p;
if (*p == '\0')
gt_abort(">E readgg: missing newline\n");
else if (*p != '\n')
gt_abort(">E readgg: illegal character\n");
n = graphsize(s);
if (readg_code == GRAPH6 && p - s != G6LEN(n))
gt_abort(">E readgg: truncated graph6 line\n");
if (readg_code == DIGRAPH6 && p - s != D6LEN(n))
gt_abort(">E readgg: truncated digraph6 line\n");
if (reqm > 0 && TIMESWORDSIZE(reqm) < n)
gt_abort(">E readgg: reqm too small\n");
else if (reqm > 0)
m = reqm;
else
m = (n + WORDSIZE - 1) / WORDSIZE;
if (g == NULL)
{
if ((g = (graph*)ALLOCS(n,m*sizeof(graph))) == NULL)
gt_abort(">E readgg: malloc failed\n");
}
*pn = n;
*pm = m;
stringtograph(s,g,m);
return g;
}
/***********************************************************************/
graph* /* read undirected graph into nauty format */
readg(FILE *f, graph *g, int reqm, int *pm, int *pn)
/* graph6 and sparse6 formats are supported
f = an open file
g = place to put the answer (NULL for dynamic allocation)
reqm = the requested value of m (0 => compute from n)
*pm = the actual value of m
*pn = the value of n
Only allows undirected graphs.
*/
{
boolean digraph;
graph *gg;
gg = readgg(f,g,reqm,pm,pn,&digraph);
if (!gg) return NULL;
if (digraph)
gt_abort(">E readg() doesn't all digraphs; use readgg()\n");
return gg;
}
/***********************************************************************/
int
checkgline(char *s)
/* Check if s[0..] appears to be a graph input line. A complete check
is not performed. Note that graph input lines must end with \n.
The value returned is 0 if no errors are found, otherwise:
1 = missing newline
2 = illegal character
3 = graph6 or digraph6 line with wrong length
*/
{
char *p;
int n,t;
if (s[0] == ':' || s[0] == ';')
{
t = SPARSE6;
p = s + 1;
}
else if (s[0] == '&')
{
t = DIGRAPH6;
p = s + 1;
}
else
{
t = GRAPH6;
p = s;
}
while (*p >= BIAS6 && *p <= MAXBYTE)
++p;
if (*p == '\0')
return 1;
else if (*p != '\n')
return 2;
if (t == GRAPH6)
{
n = graphsize(s);
if (p - s != G6LEN(n)) return 3;
}
if (t == DIGRAPH6)
{
n = graphsize(s);
if (p - s != D6LEN(n)) return 3;
}
return 0;
}
/***********************************************************************/
graph* /* read graph into nauty format */
readgg_inc(FILE *f, graph *g, int reqm, int *pm, int *pn,
graph *prevg, int prevm, int prevn, boolean *digraph)
/* graph6, digraph6 and sparse6 formats are supported
f = an open file
g = place to put the answer (NULL for dynamic allocation)
reqm = the requested value of m (0 => compute from n)
This is ignored for an incremental input.
*pm = the actual value of m
*pn = the value of n
*digraph = whether the input is a digraph
If prevg!=NULL, it is a prior graph for use in case the next
input is a sparse6 increment.
*/
{
char *s,*p;
int m,n;
if ((readg_line = gtools_getline(f)) == NULL) return NULL;
s = readg_line;
if (s[0] == ':')
{
readg_code = SPARSE6;
*digraph = FALSE;
p = s + 1;
}
else if (s[0] == ';')
{
readg_code = INCSPARSE6;
*digraph = FALSE;
p = s + 1;
}
else if (s[0] == '&')
{
readg_code = DIGRAPH6;
*digraph = TRUE;
p = s + 1;
}
else
{
readg_code = GRAPH6;
*digraph = FALSE;
p = s;
}
while (*p >= BIAS6 && *p <= MAXBYTE)
++p;
if (*p == '\0')
gt_abort(">E readg_inc: missing newline\n");
else if (*p != '\n')
gt_abort(">E readg_inc: illegal character\n");
if (readg_code == INCSPARSE6)
{
if (prevg == NULL) gt_abort(">E readg_inc: missing prior\n");
n = prevn;
m = prevm;
}
else
{
n = graphsize(s);
if (readg_code == GRAPH6 && p - s != G6LEN(n))
gt_abort(">E readg_inc: truncated graph6 line\n");
if (readg_code == DIGRAPH6 && p - s != D6LEN(n))
gt_abort(">E readg_inc: truncated digraph6 line\n");
if (reqm > 0 && TIMESWORDSIZE(reqm) < n)
gt_abort(">E readg_inc: reqm too small\n");
else if (reqm > 0)
m = reqm;
else
m = SETWORDSNEEDED(n);
}
if (g == NULL)
{
if ((g = (graph*)ALLOCS(n,m*sizeof(graph))) == NULL)
gt_abort(">E readg_inc: malloc failed\n");
}
*pn = n;
*pm = m;
stringtograph_inc(s,g,m,prevg,prevn);
return g;
}
/***********************************************************************/
graph* /* read undirected graph into nauty format */
readg_inc(FILE *f, graph *g, int reqm, int *pm, int *pn,
graph *prevg, int prevm, int prevn)
/* graph6 and sparse6 formats are supported
f = an open file
g = place to put the answer (NULL for dynamic allocation)
reqm = the requested value of m (0 => compute from n)
This is ignored for an incremental input.
*pm = the actual value of m
*pn = the value of n
*digraph = whether the input is a digraph
If prevg!=NULL, it is a prior graph for use in case the next
input is a sparse6 increment.
*/
{
boolean digraph;
graph *gg;
gg = readgg_inc(f,g,reqm,pm,pn,prevg,prevm,prevn,&digraph);
if (!gg) return NULL;
if (digraph)
gt_abort(">E readg_inc() doesn't all digraphs; use readgg_inc()\n");
return gg;
}
/****************************************************************************/
void
stringtosparsegraph(char *s, sparsegraph *sg, int *nloops)
/* Convert string (graph6, digraph6 or sparse6 format)
* to sparse graph.
* Assumes sg exists and is initialised
* Also returns the number of loops */
{
char *p,*q;
int n,nde,i,j,k,vv,x,nb,need;
int *d,*e;
size_t *v;
int loops;
boolean done;
n = graphsize(s);
q = s + (s[0] == ':' || s[0] == '&') + SIZELEN(n);
sg->nv = n;
DYNALLOC1(size_t,sg->v,sg->vlen,n,"stringtosparsegraph");
DYNALLOC1(int,sg->d,sg->dlen,n,"stringtosparsegraph");
v = sg->v;
d = sg->d;
for (i = 0; i < n; ++i) d[i] = 0;
if (s[0] != ':' && s[0] != '&') /* graph6 format */
{
p = q;
k = 1;
for (j = 1; j < n; ++j)
{
for (i = 0; i < j; ++i)
{
if (--k == 0)
{
k = 6;
x = *(p++) - BIAS6;
}
if ((x & TOPBIT6))
{
d[i]++;
d[j]++;
}
x <<= 1;
}
}
nde = 0;
for (i = 0; i < n; ++i)
{
v[i] = nde; nde += d[i]; d[i] = 0;
}
sg->nde = nde;
DYNALLOC1(int,sg->e,sg->elen,nde,"stringtosparsegraph");
e = sg->e;
p = q;
k = 1;
for (j = 1; j < n; ++j)
{
for (i = 0; i < j; ++i)
{
if (--k == 0)
{
k = 6;
x = *(p++) - BIAS6;
}
if ((x & TOPBIT6))
{
e[v[i]+d[i]++] = j;
e[v[j]+d[j]++] = i;
}
x <<= 1;
}
}
*nloops = 0;
}
else if (s[0] == '&') /* digraph6 */
{
p = q;
k = 1;
for (j = 0; j < n; ++j)
{
for (i = 0; i < n; ++i)
{
if (--k == 0)
{
k = 6;
x = *(p++) - BIAS6;
}
if ((x & TOPBIT6))
d[j]++;
x <<= 1;
}
}
nde = 0;
for (i = 0; i < n; ++i)
{
v[i] = nde; nde += d[i]; d[i] = 0;
}
sg->nde = nde;
DYNALLOC1(int,sg->e,sg->elen,nde,"stringtosparsegraph");
e = sg->e;
p = q;
k = 1;
*nloops = 0;
for (j = 0; j < n; ++j)
{
for (i = 0; i < n; ++i)
{
if (--k == 0)
{
k = 6;
x = *(p++) - BIAS6;
}
if ((x & TOPBIT6))
{
e[v[j]+d[j]++] = i;
if (i == j) ++*nloops;
}
x <<= 1;
}
}
}
else /* sparse6 format */
{
for (i = n-1, nb = 0; i > 0 ; i >>= 1, ++nb) {}
p = q;
k = 0;
vv = 0;
done = FALSE;
loops = 0;
while (!done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if ((x & B(k))) ++vv;
--k;
need = nb;
j = 0;
while (need > 0 && !done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if (need >= k)
{
j = (j << k) | (x & M(k));
need -= k; k = 0;
}
else
{
k -= need;
j = (j << need) | ((x >> k) & M(need));
need = 0;
}
}
if (done) continue;
if (j > vv)
vv = j;
else if (vv < n)
{
d[vv]++;
if (vv != j) d[j]++;
else ++loops;
}
}
nde = 0;
for (i = 0; i < n; ++i)
{
v[i] = nde; nde += d[i]; d[i] = 0;
}
sg->nde = nde;
DYNALLOC1(int,sg->e,sg->elen,nde,"stringtosparsegraph");
e = sg->e;
p = q;
k = 0;
vv = 0;
done = FALSE;
while (!done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if ((x & B(k))) ++vv;
--k;
need = nb;
j = 0;
while (need > 0 && !done)
{
if (k == 0)
{
x = *(p++);
if (x == '\n' || x == '\0')
{
done = TRUE; continue;
}
else
{
x -= BIAS6; k = 6;
}
}
if (need >= k)
{
j = (j << k) | (x & M(k));
need -= k; k = 0;
}
else
{
k -= need;
j = (j << need) | ((x >> k) & M(need));
need = 0;
}
}
if (done) continue;
if (j > vv)
vv = j;
else if (vv < n)
{
e[v[vv]+d[vv]++] = j;
if (vv != j) e[v[j]+d[j]++] = vv;
}
}
*nloops = loops;
}
}
/***********************************************************************/
sparsegraph* /* read graph into sparsegraph format */
read_sgg_loops(FILE *f, sparsegraph *sg, int *nloops, boolean *digraph)
/* graph6, digraph6 and sparse6 formats are supported
* f = an open file
* sg = place to put the answer (NULL for dynamic allocation)
* - must be initialised if not NULL
* nloops := number of loops (each loop in a sparse6 string
* gives one loop in the sparse representation)
*/
{
char *s,*p;
int n,loops;
if ((readg_line = gtools_getline(f)) == NULL) return NULL;
s = readg_line;
if (s[0] == ':')
{
readg_code = SPARSE6;
*digraph = FALSE;
p = s + 1;
}
else if (s[0] == '&')
{
readg_code = DIGRAPH6;
*digraph = TRUE;
p = s + 1;
}
else
{
readg_code = GRAPH6;
*digraph = FALSE;
p = s;
}
while (*p >= BIAS6 && *p <= MAXBYTE)
++p;
if (*p == '\0')
gt_abort(">E read_sg: missing newline\n");
else if (*p != '\n')
gt_abort(">E read_sg: illegal character\n");
n = graphsize(s);
if (readg_code == GRAPH6 && p - s != G6LEN(n))
gt_abort(">E read_sg: truncated graph6 line\n");
if (readg_code == DIGRAPH6 && p - s != D6LEN(n))
gt_abort(">E read_sg: truncated digraph6 line\n");
if (sg == NULL)
{
if ((sg = (sparsegraph*)ALLOCS(1,sizeof(sparsegraph))) == NULL)
gt_abort(">E read_sg: malloc failed\n");
SG_INIT(*sg);
}
stringtosparsegraph(s,sg,&loops);
*nloops = loops;
return sg;
}
/***********************************************************************/
sparsegraph* /* read undirected graph into sparsegraph format */
read_sg_loops(FILE *f, sparsegraph *sg, int *nloops)
/* graph6 and sparse6 formats are supported
* f = an open file
* sg = place to put the answer (NULL for dynamic allocation)
* - must be initialised if not NULL
* nloops := number of loops (each loop in a sparse6 string
* gives one loop in the sparse representation)
* digraph = whether input line was a digraph
*/
{
sparsegraph *sgg;
boolean digraph;
sgg = read_sgg_loops(f,sg,nloops,&digraph);
if (!sgg) return NULL;
if (digraph) gt_abort(">E read_sg_loops() can't handle digraphs,"
" use read_sgg_loops()\n");
return sgg;
}
/***********************************************************************/
sparsegraph* /* read graph into sparsegraph format */
read_sg(FILE *f, sparsegraph *sg)
/* graph6 and sparse6 formats are supported
* *f = an open file
* *sg = place to put the answer (NULL for dynamic allocation)
* - must be initialised if not NULL
*/
{
int loops;
sparsegraph *sgg;
boolean digraph;
sgg = read_sgg_loops(f,sg,&loops,&digraph);
if (!sgg) return NULL;
if (digraph) gt_abort(">E read_sg() can't handle digraphs,"
" use read_sgg_loops()\n");
return sgg;
}
/****************************************************************************/
DYNALLSTAT(char,gcode,gcode_sz); /* Used by ntog6, ntos6, ntod6 and sgtos6 */
TLS_ATTR size_t s6len;
TLS_ATTR int readg_code;
TLS_ATTR char *readg_line;
/****************************************************************************/
char*
ntod6(graph *g, int m, int n)
/* convert nauty graph to digraph6 string, including \n and \0 */
{
int i,j,k;
char *p,x;
set *gj;
size_t ii;
ii = D6LEN(n)+3;
DYNALLOC1(char,gcode,gcode_sz,ii,"ntod6");
p = gcode;
*p++ = '&';
encodegraphsize(n,&p);
k = 6;
x = 0;
for (j = 0; j < n; ++j)
{
gj = GRAPHROW(g,j,m);
for (i = 0; i < n; ++i)
{
x <<= 1;
if (ISELEMENT(gj,i)) x |= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
}
if (k != 6) *p++ = (char)(BIAS6 + (x << k));
*p++ = '\n';
*p = '\0';
return gcode;
}
/****************************************************************************/
char*
ntog6(graph *g, int m, int n)
/* convert nauty graph to graph6 string, including \n and \0 */
{
int i,j,k;
char *p,x;
set *gj;
size_t ii;
ii = G6LEN(n)+3;
DYNALLOC1(char,gcode,gcode_sz,ii,"ntog6");
p = gcode;
encodegraphsize(n,&p);
k = 6;
x = 0;
for (j = 1; j < n; ++j)
{
gj = GRAPHROW(g,j,m);
for (i = 0; i < j; ++i)
{
x <<= 1;
if (ISELEMENT(gj,i)) x |= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
}
if (k != 6) *p++ = (char)(BIAS6 + (x << k));
*p++ = '\n';
*p = '\0';
return gcode;
}
/****************************************************************************/
char*
ntos6(graph *g, int m, int n)
/* convert nauty graph to sparse6 string, including \n and \0 */
{
int i,j,k;
char *p,x;
set *gj;
size_t ii;
int r,rr,topbit,nb,lastj;
char *plim;
DYNALLOC1(char,gcode,gcode_sz,5000,"ntos6");
plim = gcode + gcode_sz - 20;
gcode[0] = ':';
p = gcode+1;
encodegraphsize(n,&p);
for (i = n-1, nb = 0; i > 0 ; i >>= 1, ++nb)
{}
topbit = 1 << (nb-1);
k = 6;
x = 0;
lastj = 0;
for (j = 0; j < n; ++j)
{
gj = GRAPHROW(g,j,m);
for (i = 0; i <= j; ++i)
{
if (ISELEMENT(gj,i))
{
if (p >= plim)
{
ii = p - gcode;
DYNREALLOC(char,gcode,gcode_sz,
3*(gcode_sz/2)+10000,"ntos6");
p = gcode + ii;
plim = gcode + gcode_sz - 20;
}
if (j == lastj)
{
x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
else
{
x = (x << 1) | (char)1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
if (j > lastj+1)
{
for (r = 0, rr = j; r < nb; ++r, rr <<= 1)
{
if ((rr & topbit)) x = (x << 1) | (char)1;
else x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
lastj = j;
}
for (r = 0, rr = i; r < nb; ++r, rr <<= 1)
{
if ((rr & topbit)) x = (x << 1) | (char)1;
else x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
}
}
}
if (k != 6)
{
if (k >= nb+1 && lastj == n-2 && n == (1<<nb))
*p++ = (char)(BIAS6 + ((x << k) | ((1 << (k-1)) - 1)));
else
*p++ = (char)(BIAS6 + ((x << k) | ((1 << k) - 1)));
}
*p++ = '\n';
*p = '\0';
s6len = p - gcode;
return gcode;
}
/****************************************************************************/
char*
ntois6(graph *g, graph *prevg, int m, int n)
/* convert nauty graph to incremental sparse6 string, including \n and \0.
prevg == NULL implies there is no prior graph */
{
int i,j,k;
char *p,x;
set *gj,*pgj;
setword gdiff;
size_t ii;
int r,rr,topbit,nb,lastj,iw,nwords;
char *plim;
if (!prevg) return ntos6(g,m,n);
DYNALLOC1(char,gcode,gcode_sz,5000,"ntois6");
plim = gcode + gcode_sz - 20;
gcode[0] = ';';
p = gcode+1;
for (i = n-1, nb = 0; i > 0 ; i >>= 1, ++nb)
{}
topbit = 1 << (nb-1);
k = 6;
x = 0;
lastj = 0;
for (j = 0; j < n; ++j)
{
gj = GRAPHROW(g,j,m);
pgj = GRAPHROW(prevg,j,m);
nwords = SETWORDSNEEDED(j+1);
for (iw = 0; iw < nwords; ++iw)
{
gdiff = gj[iw] ^ pgj[iw];
if (TIMESWORDSIZE(iw+1) > j+1) gdiff &= ALLMASK(SETBT(j+1));
while (gdiff)
{
TAKEBIT(i,gdiff);
i += TIMESWORDSIZE(iw);
if (p >= plim)
{
ii = p - gcode;
DYNREALLOC(char,gcode,gcode_sz,
3*(gcode_sz/2)+10000,"ntois6");
p = gcode + ii;
plim = gcode + gcode_sz - 20;
}
if (j == lastj)
{
x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
else
{
x = (x << 1) | (char)1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
if (j > lastj+1)
{
for (r = 0, rr = j; r < nb; ++r, rr <<= 1)
{
if ((rr & topbit)) x = (x << 1) | (char)1;
else x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
lastj = j;
}
for (r = 0, rr = i; r < nb; ++r, rr <<= 1)
{
if ((rr & topbit)) x = (x << 1) | (char)1;
else x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
}
}
}
if (k != 6)
{
if (k >= nb+1 && lastj == n-2 && n == (1<<nb))
*p++ = (char)(BIAS6 + ((x << k) | ((1 << (k-1)) - 1)));
else
*p++ = (char)(BIAS6 + ((x << k) | ((1 << k) - 1)));
}
*p++ = '\n';
*p = '\0';
s6len = p - gcode;
return gcode;
}
/*************************************************************************/
char*
sgtos6(sparsegraph *sg)
/* Convert undirected sparse graph to sparse6 string including '\n'.
It is null-terminated and its address (static memory) is returned.
The length, not including the null, is put in s6len. */
{
int *d,*e;
int i,j,n;
char *p,x,*plim;
int nb,topbit;
int dj,k,lastj;
int r,rr;
size_t ii,*v,vj,l;
SG_VDE(sg,v,d,e);
n = sg->nv;
for (i = n-1, nb = 0; i > 0 ; i >>= 1, ++nb) {}
ii = (size_t)(nb+1)*(n/6+sg->nde/3);
DYNALLOC1(char,gcode,gcode_sz,ii+1000,"sgtos6");
plim = gcode + gcode_sz - 20;
p = gcode;
*p++ = ':';
encodegraphsize(n,&p);
topbit = 1 << (nb-1);
k = 6;
x = 0;
lastj = 0;
for (j = 0; j < n; ++j)
{
vj = v[j];
dj = d[j];
for (l = 0; l < dj; ++l)
{
i = e[vj+l];
if (i <= j)
{
if (p >= plim)
{
ii = p - gcode;
DYNREALLOC(char,
gcode,gcode_sz,5*(gcode_sz/4)+1000,"sgtos6");
p = gcode + ii;
plim = gcode + gcode_sz - 20;
}
if (j == lastj)
{
x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
else
{
x = (x << 1) | (char)1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
if (j > lastj+1)
{
for (r = 0, rr = j; r < nb; ++r, rr <<= 1)
{
if ((rr & topbit)) x = (x << 1) | (char)1;
else x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
lastj = j;
}
for (r = 0, rr = i; r < nb; ++r, rr <<= 1)
{
if ((rr & topbit)) x = (x << 1) | (char)1;
else x <<= 1;
if (--k == 0)
{
*p++ = (char)(BIAS6 + x);
k = 6;
x = 0;
}
}
}
}
}
if (k != 6)
{
if (k >= nb+1 && lastj == n-2 && n == (1<<nb))
*p++ = (char)(BIAS6 + ((x << k) | ((1 << (k-1)) - 1)));
else
*p++ = (char)(BIAS6 + ((x << k) | ((1 << k) - 1)));
}
*p++ = '\n';
*p = '\0';
s6len = p - gcode;
return gcode;
}
/*************************************************************************/
char*
sgtog6(sparsegraph *sg)
/* Convert undirected sparse graph to graph6 string including '\n','\0'.
It is null-terminated and its address (static memory) is returned. */
{
int *d,*e,*ei;
int i,j,n;
char *p;
size_t ii,*v,bodylen,org;
static char g6bit[] = {32,16,8,4,2,1};
SG_VDE(sg,v,d,e);
n = sg->nv;
ii = G6LEN(n)+3;
DYNALLOC1(char,gcode,gcode_sz,ii,"sgtog6");
p = gcode;
encodegraphsize(n,&p);
bodylen = G6BODYLEN(n);
for (ii = 0; ii < bodylen; ++ii) p[ii] = 0;
p[bodylen] = '\n';
p[bodylen+1] = '\0';
for (i = 0, org = 0; i < n; org += i, ++i)
{
ei = e + v[i];
for (j = 0; j < d[i]; ++j)
if (ei[j] < i)
{
ii = ei[j] + org;
p[ii/6] |= g6bit[ii%6];
}
}
for (ii = 0; ii < bodylen; ++ii) p[ii] += BIAS6;
return gcode;
}
/*************************************************************************/
char*
sgtod6(sparsegraph *sg)
/* Convert undirected sparse graph to digraph6 string including '\n','\0'.
It is null-terminated and its address (static memory) is returned. */
{
int *d,*e,*ei;
int i,j,n;
char *p;
size_t ii,*v,bodylen,org;
static char g6bit[] = {32,16,8,4,2,1};
SG_VDE(sg,v,d,e);
n = sg->nv;
ii = D6LEN(n)+3;
DYNALLOC1(char,gcode,gcode_sz,ii,"sgtog6");
p = gcode;
*p++ = '&';
encodegraphsize(n,&p);
bodylen = D6BODYLEN(n);
for (ii = 0; ii < bodylen; ++ii) p[ii] = 0;
p[bodylen] = '\n';
p[bodylen+1] = '\0';
for (i = 0, org = 0; i < n; org += n, ++i)
{
ei = e + v[i];
for (j = 0; j < d[i]; ++j)
{
ii = ei[j] + org;
p[ii/6] |= g6bit[ii%6];
}
}
for (ii = 0; ii < bodylen; ++ii) p[ii] += BIAS6;
return gcode;
}
/**************************************************************************/
void
writeg6(FILE *f, graph *g, int m, int n)
/* write graph to file in graph6 format */
{
writeline(f,ntog6(g,m,n));
}
/**************************************************************************/
void
writed6(FILE *f, graph *g, int m, int n)
/* write graph to file in digraph6 format */
{
writeline(f,ntod6(g,m,n));
}
/**************************************************************************/
void
writes6(FILE *f, graph *g, int m, int n)
/* write graph to file in sparse6 format */
{
char *s;
s = ntos6(g,m,n);
if (fwrite(s,1,s6len,f) != s6len || ferror(f))
gt_abort(">E writes6 : error on writing\n");
}
/**************************************************************************/
void
writeis6(FILE *f, graph *g, graph *prevg, int m, int n)
/* write graph to file in incremental sparse6 format
prevg can be NULL if there is no previous graph */
{
char *s;
s = ntois6(g,prevg,m,n);
if (fwrite(s,1,s6len,f) != s6len || ferror(f))
gt_abort(">E writeis6 : error on writing\n");
}
/**************************************************************************/
void
writeg6_sg(FILE *f, sparsegraph *g)
/* write undirected sparse graph to file in sparse6 format */
{
writeline(f,sgtog6(g));
}
/**************************************************************************/
void
writed6_sg(FILE *f, sparsegraph *g)
/* write undirected sparse graph to file in sparse6 format */
{
writeline(f,sgtod6(g));
}
/**************************************************************************/
void
writes6_sg(FILE *f, sparsegraph *g)
/* write undirected sparse graph to file in sparse6 format */
{
char *s;
s = sgtos6(g);
if (fwrite(s,1,s6len,f) != s6len || ferror(f))
gt_abort(">E writes6 : error on writing\n");
}
/**************************************************************************/
DYNALLSTAT(unsigned char,buff,buff_sz);
void
writepc_sg(FILE *f, sparsegraph *sg)
/* write a sparse graph in planar_code format
*f = an open file
*sg = the graph to write
*/
{
int bytes;
size_t i,j,len,k,*v,vi;
unsigned int w;
int n,*d,*e,di;
#define BEPUT1(x) buff[j++]=(unsigned char)(x);
#define BEPUT2(x) w=(x); buff[j++]=(unsigned char)((w>>8)&0xFF); \
buff[j++]=(unsigned char)(w&0xff);
#define BEPUT4(x) w=(x); buff[j++]=(unsigned char)((w>>24)&0xFF); \
buff[j++]=(unsigned char)((w>>16)&0xff); \
buff[j++]=(unsigned char)((w>>8)&0xFF); \
buff[j++]=(unsigned char)(w&0xff);
n = sg->nv;
SG_VDE(sg,v,d,e);
if (n <= 255) bytes = 1;
else if (n <= 65535) bytes = 2;
else bytes = 4;
len = bytes * (1 + n + (size_t)(sg->nde));
if (bytes == 2) len += 1;
else if (bytes == 4) len += 3;
DYNALLOC1(unsigned char,buff,buff_sz,len,"writepc_sg");
if (bytes == 1)
{
j = 0;
BEPUT1(n);
for (i = 0; i < n; ++i)
{
vi = v[i];
di = d[i];
for (k = 0; k < di; ++k) { BEPUT1(e[vi+k]+1); }
BEPUT1(0);
}
}
else if (bytes == 2)
{
j = 0;
BEPUT1(n);
BEPUT2(n);
for (i = 0; i < n; ++i)
{
vi = v[i];
di = d[i];
for (k = 0; k < di; ++k) { BEPUT2(e[vi+k]+1); }
BEPUT2(0);
}
}
else /* bytes==4 */
{
j = 0;
BEPUT1(n);
BEPUT2(n);
BEPUT4(n);
for (i = 0; i < n; ++i)
{
vi = v[i];
di = d[i];
for (k = 0; k < di; ++k) { BEPUT4(e[vi+k]+1); }
BEPUT4(0);
}
}
if (fwrite((void*)buff,1,j,f) != j)
gt_abort(">E writepc_sg : error on writing\n");
}
/**************************************************************************/
sparsegraph*
readpc_sg(FILE *f,sparsegraph *sg)
/* read a planar_code graph into sparse graph format
*f = an open file
*sg = place to put the answer (NULL for dynamic allocation)
- must be initialised if not NULL
*/
{
#define BEGET1(x) { x = GETC(f); }
#define BEGET2(x) { w1=GETC(f); w2=GETC(f); if (w2==EOF) x = EOF; else \
x = (w1<<8) | w2; }
#define BEGET4(x) { w1=GETC(f); w2=GETC(f); w3=GETC(f); w4=GETC(f); \
if (w4==EOF) x = EOF; \
else x = (w1<<24) | (w2<<16) | (w3<<8) | w4; }
int w1,w2,w3,w4;
int bytes,n;
int i,j,*d,*e,di;
size_t *v,vi;
BEGET1(n);
if (n == EOF || n < 0) return NULL;
else if (n > 0)
bytes = 1;
else
{
BEGET2(n);
if (n == EOF || n < 0)
gt_abort(">E readpc_sg : error 1 on reading\n");
else if (n > 0)
bytes = 2;
else
{
BEGET4(n);
if (n == EOF || n < 0)
gt_abort(">E readpc_sg : error 2 on reading\n");
else if (n > 0)
bytes = 4;
else
gt_abort(">E readpc_sg : error 3 on reading\n");
}
}
if (sg == NULL)
{
if ((sg = (sparsegraph*)ALLOCS(1,sizeof(sparsegraph))) == NULL)
gt_abort(">E readpc_sg: malloc failed\n");
SG_INIT(*sg);
}
SG_ALLOC(*sg,n,2*(size_t)n,"readpc_sg");
SG_VDE(sg,v,d,e);
vi = 0;
for (i = 0; i < n; ++i)
{
v[i] = vi;
di = 0;
do
{
if (bytes == 1) BEGET1(j)
else if (bytes == 2) BEGET2(j)
else BEGET4(j);
if (j == EOF) gt_abort(">E readpc_sg : error 4 on reading\n");
if (j > 0)
{
if (vi == sg->elen)
{
DYNREALLOC(int,sg->e,sg->elen,2*sg->elen,"readpc_sg");
e = sg->e;
}
e[vi++] = j-1;
++di;
}
else if (j == 0)
d[i] = di;
else
gt_abort(">E readpc_sg : error 5 on reading\n");
} while (j != 0);
}
sg->nv = n;
sg->nde = vi;
return sg;
}
/**************************************************************************/
sparsegraph*
readpcle_sg(FILE *f,sparsegraph *sg)
/* read a planar_code graph into sparse graph format
*f = an open file
*sg = place to put the answer (NULL for dynamic allocation)
- must be initialised if not NULL
*/
{
#define LEGET1(x) { x = GETC(f); }
#define LEGET2(x) { w2=GETC(f); w1=GETC(f); if (w1==EOF) x = EOF; else \
x = (w1<<8) | w2; }
#define LEGET4(x) { w4=GETC(f); w3=GETC(f); w2=GETC(f); w1=GETC(f); \
if (w1==EOF) x = EOF; \
else x = (w1<<24) | (w2<<16) | (w3<<8) | w4; }
int w1,w2,w3,w4;
int bytes,n;
int i,j,*d,*e,di;
size_t *v,vi;
LEGET1(n);
if (n == EOF || n < 0) return NULL;
else if (n > 0)
bytes = 1;
else
{
LEGET2(n);
if (n == EOF || n < 0)
gt_abort(">E readpcle_sg : error 1 on reading\n");
else if (n > 0)
bytes = 2;
else
{
LEGET4(n);
if (n == EOF || n < 0)
gt_abort(">E readpcle_sg : error 2 on reading\n");
else if (n > 0)
bytes = 4;
else
gt_abort(">E readpcle_sg : error 3 on reading\n");
}
}
if (sg == NULL)
{
if ((sg = (sparsegraph*)ALLOCS(1,sizeof(sparsegraph))) == NULL)
gt_abort(">E readpcle_sg: malloc failed\n");
SG_INIT(*sg);
}
SG_ALLOC(*sg,n,2*(size_t)n,"readpcle_sg");
SG_VDE(sg,v,d,e);
vi = 0;
for (i = 0; i < n; ++i)
{
v[i] = vi;
di = 0;
do
{
if (bytes == 1) LEGET1(j)
else if (bytes == 2) LEGET2(j)
else LEGET4(j);
if (j == EOF) gt_abort(">E readpcle_sg : error 4 on reading\n");
if (j > 0)
{
if (vi == sg->elen)
{
DYNREALLOC(int,sg->e,sg->elen,2*sg->elen,"readpcle_sg");
e = sg->e;
}
e[vi++] = j-1;
++di;
}
else if (j == 0)
d[i] = di;
else
gt_abort(">E readpcle_sg : error 5 on reading\n");
} while (j != 0);
}
sg->nv = n;
sg->nde = vi;
return sg;
}
/**************************************************************************/
void
writelast(FILE *f)
/* write last graph read by readg() assuming no intervening gtools_getline() */
{
writeline(f,readg_line);
}
/**************************************************************************/
int
longvalue(char **ps, long *l)
{
boolean neg,pos;
long sofar,last;
char *s;
s = *ps;
pos = neg = FALSE;
if (*s == '-')
{
neg = TRUE;
++s;
}
else if (*s == '+')
{
pos = TRUE;
++s;
}
if (*s < '0' || *s > '9')
{
*ps = s;
return (pos || neg) ? ARG_ILLEGAL : ARG_MISSING;
}
sofar = 0;
for (; *s >= '0' && *s <= '9'; ++s)
{
last = sofar;
sofar = sofar * 10 + (*s - '0');
if (sofar < last || sofar > MAXARG)
{
*ps = s;
return ARG_TOOBIG;
}
}
*ps = s;
*l = neg ? -sofar : sofar;
return ARG_OK;
}
/**************************************************************************/
int
doublevalue(char **ps, double *l)
{
boolean neg,pos;
double sofar,weight;
char *s;
s = *ps;
pos = neg = FALSE;
if (*s == '-')
{
neg = TRUE;
++s;
}
else if (*s == '+')
{
pos = TRUE;
++s;
}
if ((*s < '0' || *s > '9') && *s != '.')
{
*ps = s;
return (pos || neg) ? ARG_ILLEGAL : ARG_MISSING;
}
sofar = 0.0;
for (; *s >= '0' && *s <= '9'; ++s)
sofar = sofar * 10 + (*s - '0');
if (*s == '.')
{
weight = 1.0;
for (++s; *s >= '0' && *s <= '9'; ++s)
{
weight /= 10.0;
sofar += weight * (*s - '0');
}
}
*ps = s;
*l = neg ? -sofar : sofar;
return ARG_OK;
}
/*************************************************************************/
void
arg_long(char **ps, long *val, char *id)
{
int code;
code = longvalue(ps,val);
if (code == ARG_MISSING || code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: missing argument value\n",id);
gt_abort(NULL);
}
else if (code == ARG_TOOBIG)
{
fprintf(stderr,">E %s: argument value too large\n",id);
gt_abort(NULL);
}
}
/*************************************************************************/
void
arg_int(char **ps, int *val, char *id)
{
int code;
long longval;
code = longvalue(ps,&longval);
*val = longval;
if (code == ARG_MISSING || code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: missing argument value\n",id);
gt_abort(NULL);
}
else if (code == ARG_TOOBIG || *val != longval)
{
fprintf(stderr,">E %s: argument value too large\n",id);
gt_abort(NULL);
}
}
/*************************************************************************/
void
arg_double(char **ps, double *val, char *id)
{
int code;
code = doublevalue(ps,val);
if (code == ARG_MISSING || code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: missing argument value\n",id);
gt_abort(NULL);
}
}
/************************************************************************/
boolean
strhaschar(char *s, int c)
/* Check if s contains c. Saves the bother of figuring out whether
strchr() is available, or index() or whatever. */
{
int i;
for (i = 0; s[i] != '\0'; ++i)
if (s[i] == c) return TRUE;
return FALSE;
}
/************************************************************************/
void
arg_range(char **ps, char *sep, long *val1, long *val2, char *id)
{
int code;
char *s;
s = *ps;
code = longvalue(&s,val1);
if (code != ARG_MISSING)
{
if (code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: bad range\n",id);
gt_abort(NULL);
}
else if (code == ARG_TOOBIG)
{
fprintf(stderr,">E %s: value too big\n",id);
gt_abort(NULL);
}
}
else if (*s == '\0' || !strhaschar(sep,*s))
{
fprintf(stderr,">E %s: missing value\n",id);
gt_abort(NULL);
}
else
*val1 = -NOLIMIT;
if (*s != '\0' && strhaschar(sep,*s))
{
++s;
code = longvalue(&s,val2);
if (code == ARG_MISSING)
*val2 = NOLIMIT;
else if (code == ARG_TOOBIG)
{
fprintf(stderr,">E %s: value too big\n",id);
gt_abort(NULL);
}
else if (code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: illegal range\n",id);
gt_abort(NULL);
}
}
else
*val2 = *val1;
*ps = s;
}
/************************************************************************/
void
arg_sequence(char **ps, char *sep,
long *val, int maxvals, int *numvals, char *id)
{
int code,ival;
char *s;
s = *ps;
for (ival = 0; ival < maxvals; ++ival)
{
code = longvalue(&s,&val[ival]);
if (code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: illegal value\n",id);
gt_abort(NULL);
}
else if (code == ARG_TOOBIG)
{
fprintf(stderr,">E %s: value too big\n",id);
gt_abort(NULL);
}
else if (code == ARG_MISSING)
{
fprintf(stderr,">E %s: value missing\n",id);
gt_abort(NULL);
}
if (*s == '\0' || !strhaschar(sep,*s))
{
*numvals = ival+1;
*ps = s;
return;
}
++s;
}
fprintf(stderr,">E %s: too many values\n",id);
gt_abort(NULL);
}
/************************************************************************/
void
arg_sequence_min(char **ps, char *sep,
long *val, int minvals, int maxvals, int *numvals, char *id)
{
int code,ival;
char *s;
s = *ps;
for (ival = 0; ival < maxvals; ++ival)
{
code = longvalue(&s,&val[ival]);
if (code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: illegal value\n",id);
gt_abort(NULL);
}
else if (code == ARG_TOOBIG)
{
fprintf(stderr,">E %s: value too big\n",id);
gt_abort(NULL);
}
else if (code == ARG_MISSING)
{
fprintf(stderr,">E %s: value missing\n",id);
gt_abort(NULL);
}
if (*s == '\0' || !strhaschar(sep,*s))
{
*numvals = ival+1;
*ps = s;
if (*numvals < minvals)
{
fprintf(stderr,">E %s: too few values\n",id);
gt_abort(NULL);
}
return;
}
++s;
}
fprintf(stderr,">E %s: too many values\n",id);
gt_abort(NULL);
}
/************************************************************************/
void
arg_doublerange(char **ps, char *sep, double *val1, double *val2, char *id)
{
int code;
char *s;
s = *ps;
code = doublevalue(&s,val1);
if (code != ARG_MISSING)
{
if (code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: bad range\n",id);
gt_abort(NULL);
}
}
else if (*s == '\0' || !strhaschar(sep,*s))
{
fprintf(stderr,">E %s: missing value\n",id);
gt_abort(NULL);
}
else
*val1 = -NOLIMIT;
if (*s != '\0' && strhaschar(sep,*s))
{
++s;
code = doublevalue(&s,val2);
if (code == ARG_MISSING)
*val2 = NOLIMIT;
else if (code == ARG_ILLEGAL)
{
fprintf(stderr,">E %s: illegal range\n",id);
gt_abort(NULL);
}
}
else
*val2 = *val1;
*ps = s;
}
/***********************************************************************/
void
writerange(FILE *f, int c, long lo, long hi) /* Write a range. */
{
if (c != '\0') fprintf(f,"%c",c);
if (lo != -NOLIMIT) fprintf(f,"%ld",lo);
if (lo != hi)
{
fprintf(stderr,":");
if (hi != NOLIMIT) fprintf(f,"%ld",hi);
}
}
/************************************************************************/
void
gt_abort(const char *msg) /* Write message and halt. */
{
if (msg) fprintf(stderr,"%s",msg);
ABORT(">E gtools");
}
/************************************************************************/
char*
stringcopy(char *s) /* duplicate string */
{
char *scopy;
size_t i,len;
for (len = 0; s[len] != '\0'; ++len)
{}
if ((scopy = (char*)ALLOCS(len+1,1)) == NULL)
gt_abort(">E stringcopy: malloc failed\n");
for (i = 0; i <= len; ++i)
scopy[i] = s[i];
return scopy;
}
/*****************************************************************************
* *
* gtools_check() checks that this file is compiled compatibly with the *
* given parameters. If not, call exit(1). *
* *
*****************************************************************************/
void
gtools_check(int wordsize, int m, int n, int version)
{
if (wordsize != WORDSIZE)
{
fprintf(ERRFILE,"Error: WORDSIZE mismatch in gtools.c\n");
exit(1);
}
#if MAXN
if (m > MAXM)
{
fprintf(ERRFILE,"Error: MAXM inadequate in gtools.c\n");
exit(1);
}
if (n > MAXN)
{
fprintf(ERRFILE,"Error: MAXN inadequate in gtools.c\n");
exit(1);
}
#endif
if (version < NAUTYREQUIRED)
{
fprintf(ERRFILE,"Error: gtools.c version mismatch\n");
exit(1);
}
}

File Metadata

Mime Type
text/x-c
Expires
Tue, Oct 27, 3:30 PM (23 h, 51 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
406507
Default Alt Text
gtools.c (68 KB)

Event Timeline