/* showg.c version 2.1; B D McKay, August 2017. Formerly called readg.c. This is a stand-alone edition of listg.c that does not need nauty or any other files. Use listg in preference if you have installed it. */ #define USAGE "showg [-p#:#l#o#Ftq] [-a|-A|-c|-d|-e] [infile [outfile]]" #define HELPTEXT \ " Write graphs in human-readable format.\n\ \n\ infile is the input file in graph6, sparse6 or digraph6 format\n\ This program does not support incremental sparse6 files; use listg.\n\ outfile is the output file\n\ Defaults are standard input and standard output.\n\ \n\ -p#, -p#:#, -p#-# : only display one graph or a sequence of\n\ graphs. The first graph is number 1. A second number\n\ which is empty or zero means infinity.\n\ \n\ -a : write the adjacency matrix\n\ -A : same as -a with a space between entries\n\ -d : write output to satisfy dreadnaut\n\ -c : write compact dreadnaut form with minimal line-breaks\n\ -e : write a list of edges, preceded by the order and the\n\ number of edges\n\ \n\ -o# : specify number of first vertex (default is 0)\n\ -t : write upper triangle only (affects -a, -A, -d and default)\n\ -F : write a form-feed after each graph except the last\n\ -l# : specify screen width limit (default 78, 0 means no limit)\n\ This is not currently implemented with -a or -A.\n\ -q : suppress auxiliary output\n\ \n\ -a, -A, -c, -d and -e are incompatible.\n" /* Version 1.1: Fixed sparse6 input for powers of 2. May 9, 1998. Version 1.3: Declared errno according to ISO C. August 22, 1998. Version 1.4: Change name of getline() so that broken compilers which define the GNU function without being asked don't cause a conflict. June 16, 2006. Version 1.5: Use function prototypes. Avoid errno. Sep 19, 2007. Version 1.6: Very minor tweaks. Hope you all have string.h. Sep 6, 2009. Version 1.7: Make it work for n=0. Sep 18, 2013. Version 2.0: Support digraph6 format. Version 2.1: Fix digraph6 format and remove limit of 200K or so vertices. */ /*************************************************************************/ #include #include /* gtools.h : General header for gtools programs. */ #ifndef MAXN #define MAXN 0 #endif #define BIAS6 63 #define MAXBYTE 126 #define SMALLN 62 #define SMALLISHN 258047 #define TOPBIT6 32 #define C6MASK 63 #define SIZELEN(n) ((n)<=SMALLN?1:((n)<=SMALLISHN?4:8)) /* length of size code in bytes */ #define G6BODYLEN(n) \ (((size_t)(n)/12)*((size_t)(n)-1) + (((size_t)(n)%12)*((size_t)(n)-1)+11)/12) #define G6LEN(n) (SIZELEN(n) + G6BODYLEN(n)) /* exact graph6 string length excluding \n\0 This twisted expression works up to n=227023 in 32-bit arithmetic and for larger n if size_t has 64 bits. */ #define D6BODYLEN(n) \ ((n)*(size_t)((n)/6) + (((n)*(size_t)((n)%6)+5)/6)) #define D6LEN(n) (1 + SIZELEN(n) + D6BODYLEN(n)) /* exact digraph6 string length excluding \n\0 This twisted expression works up to n=160529 in 32-bit arithmetic and for larger n if size_t has 64 bits. */ #define B(i) (1 << ((i)-1)) #define M(i) ((1 << (i))-1) /* Remove errno: too hard to get portable without configuration * #if defined(__unix) || defined(__unix__) || defined(unix) || \ defined(__ppc__) #include #else int errno = 0; #endif #define ABORT(msg) {if (errno != 0) perror(msg); exit(1);} */ /* extern long ftell(FILE*); Should be in stdio.h */ #define GRAPH6_HEADER ">>graph6<<" #define SPARSE6_HEADER ">>sparse6<<" #define DIGRAPH6_HEADER ">>sparse6<<" #define GRAPH6 1 #define SPARSE6 2 #define DIGRAPH6 4 #define UNKNOWN_TYPE 256 #define HAS_HEADER 512 #define ARG_OK 0 #define ARG_MISSING 1 #define ARG_TOOBIG 2 #define ARG_ILLEGAL 3 #define MAXARG 2000000000L #define NOLIMIT (MAXARG+1L) #define SWBOOLEAN(c,boool) if (sw==c) boool=TRUE; #define SWINT(c,boool,val,id) if (sw==c) \ {boool=TRUE;arg_int(&arg,&val,id);} #define SWRANGE(c,boool,val1,val2,id) if (sw==c) \ {boool=TRUE;arg_range(&arg,&val1,&val2,id);} #define FREES free #define ALLOCS calloc #define DYNALLSTAT(type,name,name_sz) static type *name; static size_t name_sz=0 #define DYNALLOC1(type,name,name_sz,sz,msg) \ if ((size_t)(sz) > name_sz) \ { if (name_sz) FREES(name); name_sz = (sz); \ if ((name=(type*)ALLOCS(sz,sizeof(type))) == NULL) alloc_error(msg);} #define DYNALLOC2(type,name,name_sz,sz1,sz2,msg) \ if ((size_t)(sz1)*(size_t)(sz2) > name_sz) \ { if (name_sz) FREES(name); name_sz = (size_t)(sz1)*(size_t)(sz2); \ if ((name=(type*)ALLOCS((sz1),(sz2)*sizeof(type))) == NULL) alloc_error(msg);} #define DYNFREE(name,name_sz) if (name_sz) {FREES(name); name_sz = 0;} #define DYNREALLOC(type,name,name_sz,sz,msg) \ {if ((size_t)(sz) > name_sz) \ { if ((name = (type*)realloc(name,(sz)*sizeof(type))) == NULL) \ alloc_error(msg); else name_sz = (sz);}} #define alloc_error gt_abort #ifdef __STDC__ #include #include #else #include extern char *calloc(); extern char *malloc(); extern char *realloc(); #endif #ifdef __alpha typedef unsigned int setword; #else typedef unsigned long setword; #endif typedef setword set; typedef setword graph; typedef int boolean; static setword bit[32]= {020000000000,010000000000,04000000000,02000000000, 01000000000,0400000000,0200000000,0100000000,040000000, 020000000,010000000,04000000,02000000,01000000,0400000, 0200000,0100000,040000,020000,010000,04000,02000,01000, 0400,0200,0100,040,020,010,04,02,01}; static int leftbit[] = {8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4, 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3, 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; static int labelorg = 0; #define WORDSIZE 32 #define FIRSTBIT(x) ((x) & 037777600000 ? ((x) & 037700000000 ? \ leftbit[((x)>>24) & 0377] : 8+leftbit[(x)>>16]) \ : ((x) & 0177400 ? 16+leftbit[(x)>>8] : 24+leftbit[x])) #define BITMASK(x) (017777777777 >> (x)) /* setword whose rightmost WORDSIZE-x-1 (numbered) bits are 1 and the rest 0 (0 <= x < WORDSIZE) */ #define TIMESWORDSIZE(w) ((w)<<5) #define SETWD(pos) ((pos)>>5) #define SETBT(pos) ((pos)&037) #define ISELEMENT(setadd,pos) (((setadd)[SETWD(pos)] & bit[SETBT(pos)]) != 0) #define ADDELEMENT(setadd,pos) ((setadd)[SETWD(pos)] |= bit[SETBT(pos)]) #define GRAPHROW(g,v,m) ((set*)(g) + (long)(v) * (long)(m)) #define FALSE 0 #define TRUE 1 /************************************************************************/ #ifndef SEEK_SET #define SEEK_SET 0 #define SEEK_CUR 1 #define SEEK_END 2 #endif #ifndef SEEK_CUR #define SEEK_CUR SEEK_CURRENT #endif static long ogf_linelen; /************************************************************************/ static void gt_abort(char *msg) /* Write message and halt. */ { if (msg) fprintf(stderr,"%s",msg); exit(1); } /***************************************************************************** * * * itos(i,s) converts the int i to a nul-terminated decimal character * * string s. The value returned is the number of characters excluding * * the nul. * * * * GLOBALS ACCESSED: NONE * * * *****************************************************************************/ static int itos(int i, char *s) { int digit,j,k; char c; int ans; if (i < 0) { k = 0; i = -i; j = 1; s[0] = '-'; } else { k = -1; j = 0; } do { digit = i % 10; i = i / 10; s[++k] = digit + '0'; } while (i); s[k+1] = '\0'; ans = k + 1; for (;j < k; ++j, --k) { c = s[j]; s[j] = s[k]; s[k] = c; } return(ans); } /***************************************************************************** * * * nextelement(set1,m,pos) = the position of the first element in set set1 * * which occupies a position greater than pos. If no such element exists, * * the value is -1. pos can have any value less than n, including negative * * values. * * * * GLOBALS ACCESSED: none * * * *****************************************************************************/ static int nextelement(set *set1, int m, int pos) { setword setwd; int w; if (pos < 0) { w = 0; setwd = set1[0]; } else { w = SETWD(pos); setwd = set1[w] & BITMASK(SETBT(pos)); } for (;;) { if (setwd != 0) return(TIMESWORDSIZE(w) + FIRSTBIT(setwd)); if (++w == m) return -1; setwd = set1[w]; } } /********************************************************************* 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) codetype = returns a code for the format. This is a combination of SPARSE6, GRAPH6, 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 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) If the file starts with ">", there must be a header, either GRAPH6_HEADER, SPARSE6_HEADER or DIGRAPH6_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. **********************************************************************/ static FILE* opengraphfile(char *filename, int *codetype, int assumefixed, long position) { FILE *f; int c,firstc; long i,l,pos,pos1,pos2; boolean bad_header; if (filename == NULL) f = stdin; else { f = fopen(filename,"r"); if (f == NULL) { fprintf(stderr,">E opengraphfile: can't open %s\n",filename); return NULL; } } firstc = c = getc(f); if (c == EOF) { *codetype = GRAPH6; 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'))) 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 == '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; } if (bad_header) { fprintf(stderr,">E opengraphfile: illegal header in %s\n", filename == NULL ? "stdin" : filename); *codetype = UNKNOWN_TYPE | HAS_HEADER; return NULL; } } if (position <= 1) return f; if (filename == NULL || !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(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"); return NULL; } pos2 = ftell(f); if (pos2 < 0) { fprintf(stderr,">E opengraphfile: error on second ftell\n"); return NULL; } pos = pos1 + (position-1)*(pos2-pos1); if (fseek(f,pos,SEEK_SET) < 0) { fprintf(stderr,">E opengraphfile: seek failed\n"); return NULL; } } return f; } /*********************************************************************/ static char* showg_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,500,"showg_getline"); i = 0; while ((c = getc(f)) != EOF && c != '\n') { if (i == s_sz-2) DYNREALLOC(char,s,s_sz,s_sz+1000,"showg_getline"); s[i++] = c; } if (i == 0 && c == EOF) return NULL; if (c == '\n') s[i++] = '\n'; s[i] = '\0'; return 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; } /****************************************************************************/ static 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); } } } } /***********************************************************************/ 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; int readg_code; if ((s = showg_getline(f)) == NULL) return NULL; if (s[0] == ':') { *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; } /**************************************************************************/ static 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; } /*************************************************************************/ static 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); } } /************************************************************************/ static void arg_range(char **ps, 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 != ':' && *s != '-') { fprintf(stderr,">E %s: missing value\n",id); gt_abort(NULL); } else *val1 = -NOLIMIT; if (*s == ':' || *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; } /************************************************************************/ #define LABELORG 0 /* number of first vertex (any integer >= 0) */ #define LINELEN 78 /* max characters per line (0 = no limit) */ static FILE *infile,*outfile; static long nin; /***************************************************************************** * * * putsetx(f,set1,curlenp,linelength,m,compress,start) writes the set * * set1 to file f using at most linelength characters per line (excluding * * '\n'). Set elements less than or equal to start are ignored. * * *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() * * * *****************************************************************************/ static void putsetx(FILE *f, set *set1, int *curlenp, int linelength, int m, boolean compress, int start) { int slen,j1,j2; char s[40]; boolean first; first = TRUE; j1 = start; 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 (*curlenp + slen + 1 >= linelength && linelength > 0) { fprintf(f,"\n "); *curlenp = 1; } if (first) { fprintf(f,"%s",s); *curlenp += slen; first = FALSE; } else { fprintf(f," %s",s); *curlenp += slen + 1; } j1 = j2; } } /***************************************************************************** * * * STOLEN FROM naututil.c * * putgraphx(f,g,linelength,m,n) writes a list of the edges of g to f * * using at most linelength characters per line (excluding '\n'). * * If triang, only write the upper triangle. * * labelorg is used. * * * *****************************************************************************/ static void putgraphx(FILE *f, graph *g, int linelength, boolean triang, 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; putsetx(f,pg,&curlen,linelength,m,FALSE,triang ? i-1 : -1); fprintf(f,";\n"); } } /***************************************************************************/ static void putedges(FILE *f, graph *g, int linelength, boolean digraph, int m, int n) /* Write list of edges, preceded by the numbers of vertices and edges. Use labelorg */ { int i,j,curlen,ne; char s[20]; set *pg; ne = 0; for (i = 0, pg = g; i < n; ++i, pg += m) { for (j = (digraph?-1:i-1); (j = nextelement(pg,m,j)) >= 0;) ++ne; } fprintf(f,"%d %d\n",n,ne); curlen = 0; for (i = 0, pg = g; i < n; ++i, pg += m) { for (j = (digraph ? -1 : i-1); (j = nextelement(pg,m,j)) >= 0;) { if (curlen > 0 && curlen > linelength - 10 && linelength > 0) { fprintf(f,"\n"); curlen = 0; } if (curlen > 0) { fprintf(f," "); curlen += 2; } curlen += itos(i+labelorg,s); fprintf(f,"%s",s); fprintf(f," "); curlen += 1 + itos(j+labelorg,s); fprintf(f,"%s",s); } } fprintf(f,"\n"); } /***************************************************************************/ static void putcgraph(FILE *f, graph *g, int linelength, boolean digraph, int m, int n) /* write compressed form, using labelorg */ { int i,curlen,j0; int semicolons; char s[20]; set *pg; curlen = itos(n,s)+2; fprintf(f,";n%s%s",s,(digraph?"dg":"g")); semicolons = 0; for (i = 0, pg = g; i < n; ++i, pg += m) { j0 = digraph ? -1: i-1; if (nextelement(pg,m,j0) >= 0) { while (semicolons > 0) { if (curlen >= linelength-1 && linelength > 0) { fprintf(f,"\n "); curlen = 1; } fprintf(f,";"); ++curlen; --semicolons; } putsetx(f,pg,&curlen,linelength,m,FALSE,j0); semicolons = 1; } else ++semicolons; } fprintf(f,".\n"); } /**************************************************************************/ static void putam(FILE *f, graph *g, int linelength, boolean space, boolean triang, int m, int n) /* write adjacency matrix */ { set *gi; int i,j; boolean first; for (i = 0, gi = (set*)g; i < n - (triang!=0); ++i, gi += m) { first = TRUE; for (j = triang ? i+1 : 0; j < n; ++j) { if (!first && space) putc(' ',f); else first = FALSE; if (ISELEMENT(gi,j)) putc('1',f); else putc('0',f); } putc('\n',f); } } /**************************************************************************/ /**************************************************************************/ int main(int argc, char *argv[]) { graph *g; int m,n,codetype; int argnum,j; char *arg,sw; boolean badargs,digraph; long maxin,pval1,pval2; boolean fswitch,pswitch,cswitch,dswitch; boolean aswitch,lswitch,oswitch,Fswitch; boolean Aswitch,eswitch,tswitch,qswitch; int linelength; char *infilename,*outfilename; if (argc > 1 && (strcmp(argv[1],"-help") == 0 || (strcmp(argv[1],"--help") == 0))) { printf("Usage: %s\n\n%s",USAGE,HELPTEXT); exit(0); } if (sizeof(setword) < 4) { fprintf(stderr,">E showg: setword too small\n"); fprintf(stderr," Please report this to bdm@cs.anu.edu.au\n"); exit(1); } fswitch = pswitch = cswitch = dswitch = FALSE; aswitch = lswitch = oswitch = Fswitch = FALSE; Aswitch = eswitch = tswitch = qswitch = FALSE; infilename = outfilename = NULL; linelength = LINELEN; labelorg = 0; argnum = 0; badargs = FALSE; for (j = 1; !badargs && j < argc; ++j) { arg = argv[j]; if (arg[0] == '-' && arg[1] != '\0') { ++arg; while (*arg != '\0') { sw = *arg++; SWBOOLEAN('a',aswitch) else SWBOOLEAN('A',Aswitch) else SWBOOLEAN('c',cswitch) else SWBOOLEAN('d',dswitch) else SWBOOLEAN('e',eswitch) else SWBOOLEAN('f',fswitch) else SWBOOLEAN('F',Fswitch) else SWBOOLEAN('t',tswitch) else SWBOOLEAN('q',qswitch) else SWRANGE('p',pswitch,pval1,pval2,"showg -p") else SWINT('l',lswitch,linelength,"showg -l") else SWINT('o',oswitch,labelorg,"listo -o") else badargs = TRUE; } } else { ++argnum; if (argnum == 1) infilename = arg; else if (argnum == 2) outfilename = arg; else badargs = TRUE; } } if (labelorg < 0) gt_abort(">E showg: negative origin forbidden.\n"); if ((aswitch!=0) + (Aswitch!=0) + (eswitch!=0) + (dswitch!=0) + (cswitch!=0) > 1) gt_abort(">E showg: -aAecd are incompatible\n"); if (badargs) { fprintf(stderr,">E Usage: %s\n",USAGE); fprintf(stderr,"Use showg -help to see a list of the options.\n"); exit(1); } if (!pswitch || pval1 < 1) pval1 = 1; if (infilename && infilename[0] == '-') infilename = NULL; infile = opengraphfile(infilename,&codetype,fswitch, pswitch ? pval1 : 1); if (!infile) exit(1); if (!infilename) infilename = "stdin"; if (!outfilename || outfilename[0] == '-') { outfilename = "stdout"; outfile = stdout; } else if ((outfile = fopen(outfilename,"w")) == NULL) { fprintf(stderr,"Can't open output file %s\n",outfilename); gt_abort(NULL); } nin = 0; if (!pswitch || pval2 == NOLIMIT) maxin = NOLIMIT; else if (pval1 < 1) maxin = pval2; else maxin = pval2 - pval1 + 1; while (nin < maxin || maxin == NOLIMIT) { if ((g = readgg(infile,NULL,0,&m,&n,&digraph)) == NULL) break; ++nin; if (Fswitch && nin > 1) fprintf(outfile,"\f"); if (cswitch) putcgraph(outfile,g,linelength,digraph,m,n); else if (dswitch) { if (qswitch) fprintf(outfile,"%d\n",n); else { fprintf(outfile,"\n!Graph %ld.\n",pval1+nin-1); fprintf(outfile,"n=%d $=%d g\n",n,labelorg); } putgraphx(outfile,g,linelength,tswitch,m,n); if (!qswitch) fprintf(outfile,"$$\n"); } else { if (qswitch) { if (!eswitch) fprintf(outfile,"%d\n",n); } else fprintf(outfile,"\nGraph %ld, order %d.\n", pval1+nin-1,n); if (aswitch|Aswitch) putam(outfile,g,linelength,Aswitch,tswitch,m,n); else if (eswitch) putedges(outfile,g,linelength,digraph,m,n); else putgraphx(outfile,g,linelength,tswitch,m,n); } FREES(g); } exit(0); }