/* 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. Version 4.4: Use fgets for gtools_getline() as it is faster except for very small graphs.
*/
/********************************************************************* 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. The most common example is that graph6 and digraph6 records have lengths that depend only on the number of vertices. 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 other than the header.
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' && c != 'd' && c != 'e')))
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;
} elseif (!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;
} elseif (!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;
} elseif (!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;
} elseif (!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; elseif (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; elseif (bl == 'l')
*codetype = PLANARCODELE | HAS_HEADER; else
*codetype = PLANARCODEBE | HAS_HEADER;
} elseif (c == '<')
{ if ((c = GETC(f)) == EOF || c != '<')
bad_header = TRUE; else
*codetype = PLANARCODE | HAS_HEADER;
} else
bad_header = TRUE;
}
}
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;
}
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;
size_t i;
boolean eof;
DYNALLOC1(char,s,s_sz,5000,"gtools_getline");
FLOCKFILE(f);
i = 0;
eof = FALSE; for (;;)
{ if (fgets(s+i,s_sz-i-4,f) == NULL)
{ if (feof(f)) eof = TRUE; else gt_abort(">E file error when reading\n");
} else
i += strlen(s+i);
if (eof || (i > 0 && s[i-1] == '\n')) break; if (i >= s_sz-5)
DYNREALLOC(char,s,s_sz,3*(s_sz/2)+10000,"gtools_getline");
}
FUNLOCKFILE(f);
if (i == 0 && eof) return NULL; if (i == 0 || (i > 0 && s[i-1] != '\n')) s[i++] = '\n';
s[i] = '\0';
return s;
}
#if 0 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);
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(unsignedchar,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;
}
}
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;
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; elseif (v < n)
++count;
}
} else/* graph6 or digraph6 */
{
count = 0; for (; *p != '\n' && *p != '\0'; ++p)
count += bytecount[*p - BIAS6];
}
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");
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;
}
}
} elseif (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; elseif (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] == ';')
{
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;
}
}
} elseif (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; elseif (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;
} elseif (s[0] == '&')
{
readg_code = DIGRAPH6;
*digraph = TRUE;
p = s + 1;
} else
{
readg_code = GRAPH6;
*digraph = FALSE;
p = s;
}
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"); elseif (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");
}
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 know 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;
} elseif (s[0] == '&')
{
t = DIGRAPH6;
p = s + 1;
} else
{
t = GRAPH6;
p = s;
}
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;
} elseif (s[0] == ';')
{
readg_code = INCSPARSE6;
*digraph = FALSE;
p = s + 1;
} elseif (s[0] == '&')
{
readg_code = DIGRAPH6;
*digraph = TRUE;
p = s + 1;
} else
{
readg_code = GRAPH6;
*digraph = FALSE;
p = s;
}
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"); elseif (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");
}
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;
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;
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;
} elseif (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;
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;
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;
} elseif (s[0] == '&')
{
readg_code = DIGRAPH6;
*digraph = TRUE;
p = s + 1;
} else
{
readg_code = GRAPH6;
*digraph = FALSE;
p = s;
}
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);
}
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;
}
}
}
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;
}
}
}
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;
}
}
}
}
}
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;
}
}
}
}
}
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) {}
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; staticchar 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];
}
}
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; staticchar 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];
}
}
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
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; unsignedint w; int n,*d,*e,di;
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; elseif (n > 0)
bytes = 1; else
{
BEGET2(n); if (n == EOF || n < 0)
gt_abort(">E readpc_sg : error 1 on reading\n"); elseif (n > 0)
bytes = 2; else
{
BEGET4(n); if (n == EOF || n < 0)
gt_abort(">E readpc_sg : error 2 on reading\n"); elseif (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);
}
vi = 0; for (i = 0; i < n; ++i)
{
v[i] = vi;
di = 0; do
{ if (bytes == 1) BEGET1(j) elseif (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;
} elseif (j == 0)
d[i] = di; else
gt_abort(">E readpc_sg : error 5 on reading\n");
} while (j != 0);
}
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; elseif (n > 0)
bytes = 1; else
{
LEGET2(n); if (n == EOF || n < 0)
gt_abort(">E readpcle_sg : error 1 on reading\n"); elseif (n > 0)
bytes = 2; else
{
LEGET4(n); if (n == EOF || n < 0)
gt_abort(">E readpcle_sg : error 2 on reading\n"); elseif (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);
}
vi = 0; for (i = 0; i < n; ++i)
{
v[i] = vi;
di = 0; do
{ if (bytes == 1) LEGET1(j) elseif (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;
} elseif (j == 0)
d[i] = di; else
gt_abort(">E readpcle_sg : error 5 on reading\n");
} while (j != 0);
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
