1 /* showg.c  version 1.2; B D McKay, Oct 2000.
2    Formerly called readg.c.
3 
4    This is a stand-alone edition of listg.c that does not
5    need nauty or any other files.  Use listg in preference
6    if you have installed it.  */
7 
8 #define USAGE "showg [-p#:#l#o#Ftq] [-a|-A|-c|-d|-e] [infile [outfile]]"
9 
10 #define HELPTEXT \
11 " Write graphs in human-readable format.\n\
12 \n\
13    infile is the input file in graph6 or sparse6 format\n\
14    outfile is the output file\n\
15    Defaults are standard input and standard output.\n\
16 \n\
17     -p#, -p#:#, -p#-# : only display one graph or a sequence of\n\
18           graphs.  The first graph is number 1.  A second number\n\
19           which is empty or zero means infinity.\n\
20 \n\
21     -a  : write the adjacency matrix\n\
22     -A  : same as -a with a space between entries\n\
23     -d  : write output to satisfy dreadnaut\n\
24     -c  : write compact dreadnaut form with minimal line-breaks\n\
25     -e  : write a list of edges, preceded by the order and the\n\
26           number of edges\n\
27 \n\
28     -o# : specify number of first vertex (default is 0)\n\
29     -t  : write upper triangle only (affects -a, -A, -d and default)\n\
30     -F  : write a form-feed after each graph except the last\n\
31     -l# : specify screen width limit (default 78, 0 means no limit)\n\
32           This is not currently implemented with -a or -A.\n\
33     -q  : suppress auxiliary output\n\
34 \n\
35     -a, -A, -c, -d and -e are incompatible.\n"
36 
37 /*
38  Version 1.1: Fixed sparse6 input for powers of 2.  May 9, 1998.
39  Version 1.3: Declared errno according to ISO C.  August 22, 1998.
40 */
41 
42 /*************************************************************************/
43 
44 #include <stdio.h>
45 
46 /* gtools.h : General header for gtools programs. */
47 
48 #ifndef MAXN
49 #define MAXN  0
50 #endif
51 #define G6LEN(n)  (((n)*((n)-1)/2+5)/6+(n<=SMALLN?1:4))
52 		/* Exact length of graph6 code except for \n\0 */
53 
54 #if defined(__unix) || defined(__unix__) || defined(unix) || \
55     defined(__ppc__)
56 #include <errno.h>
57 #else
58 int errno = 0;
59 #endif
60 #define ABORT(msg) {if (errno != 0) perror(msg); exit(1);}
61 
62 extern long ftell(FILE*);
63 
64 #define BIAS6 63
65 #define MAXBYTE 126
66 #define SMALLN 62
67 #define TOPBIT6 32
68 #define C6MASK 63
69 
70 #define GRAPH6_HEADER ">>graph6<<"
71 #define SPARSE6_HEADER ">>sparse6<<"
72 
73 #define GRAPH6         1
74 #define SPARSE6        2
75 #define UNKNOWN_TYPE 256
76 #define HAS_HEADER   512
77 
78 #define ARG_OK 0
79 #define ARG_MISSING 1
80 #define ARG_TOOBIG 2
81 #define ARG_ILLEGAL 3
82 
83 #define MAXARG 2000000000L
84 #define NOLIMIT (MAXARG+1L)
85 
86 #define SWBOOLEAN(c,bool) if (sw==c) bool=TRUE;
87 #define SWINT(c,bool,val,id) if (sw==c) \
88         {bool=TRUE;arg_int(&arg,&val,id);}
89 #define SWRANGE(c,bool,val1,val2,id) if (sw==c) \
90 	{bool=TRUE;arg_range(&arg,&val1,&val2,id);}
91 
92 #define FREES free
93 #define ALLOCS calloc
94 
95 #define DYNALLSTAT(type,name,name_sz) static type *name; static size_t name_sz=0
96 #define DYNALLOC1(type,name,name_sz,sz,msg) \
97  if ((size_t)(sz) > name_sz) \
98  { if (name_sz) FREES(name); name_sz = (sz); \
99  if ((name=(type*)ALLOCS(sz,sizeof(type))) == NULL) alloc_error(msg);}
100 #define DYNALLOC2(type,name,name_sz,sz1,sz2,msg) \
101  if ((size_t)(sz1)*(size_t)(sz2) > name_sz) \
102  { if (name_sz) FREES(name); name_sz = (size_t)(sz1)*(size_t)(sz2); \
103  if ((name=(type*)ALLOCS((sz1),(sz2)*sizeof(type))) == NULL) alloc_error(msg);}
104 #define DYNFREE(name,name_sz) if (name_sz) {FREES(name); name_sz = 0;}
105 #define DYNREALLOC(type,name,name_sz,sz,msg) \
106  {if ((size_t)(sz) > name_sz) \
107  { if ((name = (type*)realloc(name,(sz)*sizeof(type))) == NULL) \
108       alloc_error(msg); else name_sz = (sz);}}
109 
110 #define alloc_error gt_abort
111 
112 #ifdef __STDC__
113 #include <stddef.h>
114 #include <stdlib.h>
115 #else
116 #include <sys/types.h>
117 extern char *calloc();
118 extern char *malloc();
119 extern char *realloc();
120 #endif
121 
122 #ifdef __alpha
123 typedef unsigned int setword;
124 #else
125 typedef unsigned long setword;
126 #endif
127 typedef setword set;
128 typedef setword graph;
129 typedef int boolean;
130 
131 static setword bit[32]=
132   {020000000000,010000000000,04000000000,02000000000,
133    01000000000,0400000000,0200000000,0100000000,040000000,
134    020000000,010000000,04000000,02000000,01000000,0400000,
135    0200000,0100000,040000,020000,010000,04000,02000,01000,
136    0400,0200,0100,040,020,010,04,02,01};
137 static int leftbit[] =
138   {8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,
139    3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
140    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
141    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
142    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
143    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
144    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
145    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
146    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
147    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
148    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
149    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
150    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
151    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
152    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
153    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
154 static int labelorg = 0;
155 
156 #define WORDSIZE 32
157 #define FIRSTBIT(x) ((x) & 037777600000 ? ((x) & 037700000000 ? \
158                      leftbit[((x)>>24) & 0377] : 8+leftbit[(x)>>16]) \
159                     : ((x) & 0177400 ? 16+leftbit[(x)>>8] : 24+leftbit[x]))
160 #define BITMASK(x)  (017777777777 >> (x)) /* setword whose rightmost
161   WORDSIZE-x-1 (numbered) bits are 1 and the rest 0 (0 <= x < WORDSIZE) */
162 #define TIMESWORDSIZE(w) ((w)<<5)
163 #define SETWD(pos) ((pos)>>5)
164 #define SETBT(pos) ((pos)&037)
165 #define ISELEMENT(setadd,pos)  (((setadd)[SETWD(pos)] & bit[SETBT(pos)]) != 0)
166 #define ADDELEMENT(setadd,pos)  ((setadd)[SETWD(pos)] |= bit[SETBT(pos)])
167 #define GRAPHROW(g,v,m) ((set*)(g) + (long)(v) * (long)(m))
168 
169 #define FALSE 0
170 #define TRUE  1
171 
172 /************************************************************************/
173 
174 #ifndef SEEK_SET
175 #define SEEK_SET 0
176 #define SEEK_CUR 1
177 #define SEEK_END 2
178 #endif
179 
180 #ifndef SEEK_CUR
181 #define SEEK_CUR SEEK_CURRENT
182 #endif
183 
184 static long ogf_linelen;
185 
186 /************************************************************************/
187 
188 static void
gt_abort(msg)189 gt_abort(msg)     /* Write message and halt. */
190 char *msg;
191 {
192 	if (msg) fprintf(stderr,msg);
193 	ABORT(">E gtools");
194 }
195 
196 /*****************************************************************************
197 *                                                                            *
198 *  itos(i,s) converts the int i to a nul-terminated decimal character        *
199 *  string s.  The value returned is the number of characters excluding       *
200 *  the nul.                                                                  *
201 *                                                                            *
202 *  GLOBALS ACCESSED: NONE                                                    *
203 *                                                                            *
204 *****************************************************************************/
205 
206 static int
itos(i,s)207 itos(i,s)
208 register int i;
209 register char *s;
210 {
211         register int digit,j,k;
212         register char c;
213         int ans;
214 
215         if (i < 0)
216         {
217             k = 0;
218             i = -i;
219             j = 1;
220             s[0] = '-';
221         }
222         else
223         {
224             k = -1;
225             j = 0;
226         }
227 
228         do
229         {
230             digit = i % 10;
231             i = i / 10;
232             s[++k] = digit + '0';
233         }
234         while (i);
235 
236         s[k+1] = '\0';
237         ans = k + 1;
238 
239         for (;j < k; ++j, --k)
240         {
241             c = s[j];
242             s[j] = s[k];
243             s[k] = c;
244         }
245 
246         return(ans);
247 }
248 
249 /*****************************************************************************
250 *                                                                            *
251 *  nextelement(set1,m,pos) = the position of the first element in set set1   *
252 *  which occupies a position greater than pos.  If no such element exists,   *
253 *  the value is -1.  pos can have any value less than n, including negative  *
254 *  values.                                                                   *
255 *                                                                            *
256 *  GLOBALS ACCESSED: none                                                    *
257 *                                                                            *
258 *****************************************************************************/
259 
260 static int
nextelement(set1,m,pos)261 nextelement(set1,m,pos)
262 register set *set1;
263 int m,pos;
264 {
265         register setword setwd;
266         register int w;
267 
268         if (pos < 0)
269         {
270             w = 0;
271             setwd = set1[0];
272         }
273         else
274         {
275             w = SETWD(pos);
276             setwd = set1[w] & BITMASK(SETBT(pos));
277         }
278 
279         for (;;)
280         {
281             if (setwd != 0)
282                 return(TIMESWORDSIZE(w) + FIRSTBIT(setwd));
283             if (++w == m) return -1;
284             setwd = set1[w];
285         }
286 }
287 
288 /*********************************************************************
289 opengraphfile(filename,codetype,assumefixed,position)
290           opens and positions a file for reading graphs.
291 
292   filename = the name of the file to open
293 		(NULL means stdin, assumed already open)
294   codetype   = returns a code for the format.
295 		This is a combination of SPARSE6, GRAPH6,
296 		UNKNOWN_TYPE and HAS_HEADER.  If a header is
297 		present, that overrides the data.  If there is
298                 no header, the first graph is examined.
299   assumefixed = nonzero if files other than stdin should be assumed to
300 		be seekable and have equal record sizes.
301 		Ignored if there is a sparse6 header or the first
302 		graph has sparse6 format.
303   position = the number of the record to position to
304 		(the first is number 1; 0 and -NOLIMIT also mean
305                  to position at start)
306 
307   If the file starts with ">", there must be a header, either
308   GRAPH6_HEAD or SPARSE6_HEAD.  Otherwise opengraphfile() fails.
309 
310   The value returned is a file pointer or NULL.
311   If assumedfixed is not zero and position > 1, the global variable
312   ogf_linelen is set to the length (including \n) of the length of the
313   first record.
314 
315 **********************************************************************/
316 
317 static FILE*
opengraphfile(filename,codetype,assumefixed,position)318 opengraphfile(filename,codetype,assumefixed,position)
319 char *filename;
320 int *codetype,assumefixed;
321 long position;
322 {
323 	FILE *f;
324 	int c,firstc;
325 	long i,l,pos,pos1,pos2;
326 	boolean bad_header;
327 
328 	if (filename == NULL)
329 	    f = stdin;
330 	else
331 	{
332 	    f = fopen(filename,"r");
333 	    if (f == NULL)
334 	    {
335 		fprintf(stderr,">E opengraphfile: can't open %s\n",filename);
336 		return NULL;
337 	    }
338 	}
339 
340 	firstc = c = getc(f);
341 	if (c == EOF)
342 	{
343 	    *codetype = GRAPH6;
344 	    return f;
345 	}
346 
347 	if (c != '>')
348 	{
349 	    *codetype = firstc == ':' ? SPARSE6 : GRAPH6;
350 	    ungetc(c,f);
351 	}
352 	else
353 	{
354 	    bad_header = FALSE;
355 	    if ((c = getc(f)) == EOF || c != '>')
356 	        bad_header = TRUE;
357 	    if (!bad_header && ((c = getc(f)) == EOF || c != 'g' && c != 's'))
358 		bad_header = TRUE;
359 	    if (!bad_header && c == 'g')
360 	    {
361 		if ((c = getc(f)) == EOF || c != 'r' ||
362 		    (c = getc(f)) == EOF || c != 'a' ||
363 		    (c = getc(f)) == EOF || c != 'p' ||
364 		    (c = getc(f)) == EOF || c != 'h' ||
365 		    (c = getc(f)) == EOF || c != '6' ||
366 		    (c = getc(f)) == EOF || c != '<' ||
367 		    (c = getc(f)) == EOF || c != '<')
368 			bad_header = TRUE;
369 		else
370 		    *codetype = GRAPH6 | HAS_HEADER;
371 	    }
372 	    else if (!bad_header && c == 's')
373 	    {
374 		if ((c = getc(f)) == EOF || c != 'p' ||
375 		    (c = getc(f)) == EOF || c != 'a' ||
376 		    (c = getc(f)) == EOF || c != 'r' ||
377 		    (c = getc(f)) == EOF || c != 's' ||
378 		    (c = getc(f)) == EOF || c != 'e' ||
379 		    (c = getc(f)) == EOF || c != '6' ||
380 		    (c = getc(f)) == EOF || c != '<' ||
381 		    (c = getc(f)) == EOF || c != '<')
382 			bad_header = TRUE;
383 		else
384 		    *codetype = SPARSE6 | HAS_HEADER;
385 	    }
386 	    if (bad_header)
387 	    {
388 		fprintf(stderr,">E opengraphfile: illegal header in %s\n",
389 			filename == NULL ? "stdin" : filename);
390 		*codetype = UNKNOWN_TYPE | HAS_HEADER;
391 		return NULL;
392 	    }
393 	}
394 
395 	if (position <= 1) return f;
396 
397 	if (filename == NULL || !assumefixed || (*codetype&SPARSE6)
398 			     || firstc == ':')
399 	{
400 	    l = 1;
401 	    while ((c = getc(f)) != EOF)
402 	    {
403 	        if (c == '\n')
404 		{
405 		    ++l;
406 		    if (l == position) break;
407 		}
408 	    }
409 	    if (l == position) return f;
410 
411 	    fprintf(stderr,
412                ">E opengraphfile: can't find line %ld in %s\n",position,
413 		filename == NULL ? "stdin" : filename);
414 	    return NULL;
415 	}
416 	else
417 	{
418 	    pos1 = ftell(f);
419 	    if (pos1 < 0)
420 	    {
421 		fprintf(stderr,">E opengraphfile: error on first ftell\n");
422 		return NULL;
423 	    }
424 
425 	    for (i = 1; (c = getc(f)) != EOF && c != '\n'; ++i) {}
426 	    ogf_linelen = i;
427 
428 	    if (c == EOF)
429 	    {
430 		fprintf(stderr,
431 		        ">E opengraphfile: required record no present\n");
432 		return NULL;
433 	    }
434 
435 	    pos2 = ftell(f);
436 	    if (pos2 < 0)
437             {
438                 fprintf(stderr,">E opengraphfile: error on second ftell\n");
439                 return NULL;
440             }
441 
442 	    pos = pos1 + (position-1)*(pos2-pos1);
443 	    if (fseek(f,pos,SEEK_SET) < 0)
444 	    {
445 		fprintf(stderr,">E opengraphfile: seek failed\n");
446 		return NULL;
447 	    }
448 	}
449 
450 	return f;
451 }
452 
453 /*********************************************************************/
454 
455 static char*
getline(f)456 getline(f)     /* read a line with error checking */
457 FILE *f;       /* includes \n (if present) and \0.
458                   Immediate EOF causes NULL return. */
459 {
460 	DYNALLSTAT(char,s,s_sz);
461 	int c;
462 	long i;
463 
464 	DYNALLOC1(char,s,s_sz,500,"getline");
465 
466 	i = 0;
467 	while ((c = getc(f)) != EOF && c != '\n')
468 	{
469 	    if (i == s_sz-2) DYNREALLOC(char,s,s_sz,s_sz+1000,"getline");
470 	    s[i++] = c;
471 	}
472 
473 	if (i == 0 && c == EOF) return NULL;
474 
475 	if (c == '\n') s[i++] = '\n';
476 	s[i] = '\0';
477 	return s;
478 }
479 
480 /****************************************************************************/
481 
482 static int
graphsize(s)483 graphsize(s)
484 char *s;         /* Get size of graph out of graph6 or sparse6 string. */
485 {
486 	char *p;
487 	int n;
488 
489 	if (s[0] == ':') p = s+1;
490 	else             p = s;
491 	n = *p++ - BIAS6;
492 
493 	if (n > SMALLN)
494 	{
495 	    n = *p++ - BIAS6;
496 	    n = (n << 6) | (*p++ - BIAS6);
497 	    n = (n << 6) | (*p++ - BIAS6);
498         }
499 	return n;
500 }
501 
502 /****************************************************************************/
503 
504 static void
stringtograph(s,g,m)505 stringtograph(s,g,m)
506 char *s;          /* Convert string (graph6 or sparse6 format) to graph. */
507 graph *g;         /* Assumes g is big enough to hold it.                 */
508 int m;
509 {
510 	char *p;
511 	int n,i,j,k,v,x,nb;
512 	long ii;
513 	set *gi,*gj;
514 
515 	n = graphsize(s);
516 
517 	p = s + 1 + (s[0] == ':');
518 	if (n > SMALLN) p += 3;
519 
520 	if (TIMESWORDSIZE(m) < n)
521 	    gt_abort(">E stringtograph: impossible m value\n");
522 
523 	for (ii = (long)m*n; --ii >= 0;)
524 	    g[ii] = 0;
525 
526 	if (s[0] != ':')       /* graph6 format */
527 	{
528 	    k = 1;
529 	    for (j = 1; j < n; ++j)
530 	    {
531 	        gj = GRAPHROW(g,j,m);
532 
533 	        for (i = 0; i < j; ++i)
534 	        {
535 	            if (--k == 0)
536 	            {
537 		        k = 6;
538 		        x = *(p++) - BIAS6;
539 	            }
540 
541 	            if (x & TOPBIT6)
542 	            {
543 		        gi = GRAPHROW(g,i,m);
544 		        ADDELEMENT(gi,j);
545 		        ADDELEMENT(gj,i);
546 	            }
547 	            x <<= 1;
548 	        }
549 	    }
550 	}
551 	else    /* sparse6 format */
552 	{
553 	    for (i = n-1, nb = 0; i != 0 ; i >>= 1, ++nb)
554 	    {}
555 
556 	    k = 1;
557 	    v = 0;
558 	    for (;;)
559 	    {
560 		if (--k == 0)
561 		{
562 		    k = 6;
563 		    if (*p == '\n' || *p == '\0') break;
564 		    else x = *p - BIAS6;
565 		    ++p;
566 		}
567 		else
568 		    x <<= 1;
569 
570 		if (x & TOPBIT6) ++v;
571 		j = 0;
572 		for (i = 0; i < nb; ++i)
573 		{
574 		    if (--k == 0)
575 		    {
576 		 	k = 6;
577 			if (*p == '\n' || *p == '\0') break;
578 			else x = *p - BIAS6;
579 			++p;
580 		    }
581 		    else
582 			x <<= 1;
583 		    if (x & TOPBIT6) j = (j << 1) | 1;
584 		    else             j <<= 1;
585 	 	}
586 		if (i < nb) break;
587 		if (j > v)
588 		    v = j;
589 		else if (v < n)
590 		{
591 		    ADDELEMENT(GRAPHROW(g,v,m),j);
592 		    ADDELEMENT(GRAPHROW(g,j,m),v);
593 		}
594 	    }
595 	}
596 }
597 
598 /***********************************************************************/
599 
600 static graph*                 /* read graph into nauty format */
readg(f,g,reqm,pm,pn)601 readg(f,g,reqm,pm,pn)  /* graph6 and sparse6 formats are supported */
602 FILE *f;      /* an open file */
603 graph *g;     /* place to put the answer (NULL for dynamic allocation) */
604 int reqm;     /* the requested value of m (0 => compute from n) */
605 int *pm;      /* the actual value of m */
606 int *pn;      /* the value of n */
607 {
608 	char *s,*p,*readg_line;
609 	int m,n,readg_code;
610 
611 	if ((readg_line = getline(f)) == NULL) return NULL;
612 
613 	s = readg_line;
614 	if (s[0] == ':')
615 	{
616 	    readg_code = SPARSE6;
617 	    p = s + 1;
618 	}
619 	else
620 	{
621 	    readg_code = GRAPH6;
622             p = s;
623 	}
624 
625 	while (*p >= BIAS6 && *p <= MAXBYTE)
626 	    ++p;
627 	if (*p == '\0')
628 	    gt_abort(">E showg: missing newline\n");
629 	else if (*p != '\n')
630 	    gt_abort(">E showg: illegal character\n");
631 
632 	n = graphsize(s);
633 	if (readg_code == GRAPH6 && p - s != G6LEN(n))
634 	{
635 	    fprintf(stderr,"p-s=%d G6LEN(%d)=%d\n",(int)(p-s),n,G6LEN(n));
636 	    gt_abort(">E showg: truncated graph6 line\n");
637 	}
638 
639 	if (reqm > 0 && TIMESWORDSIZE(reqm) > n)
640 	    gt_abort(">E showg: reqm too small\n");
641 	else if (reqm > 0)
642 	    m = reqm;
643 	else
644 	    m = (n + WORDSIZE - 1) / WORDSIZE;
645 
646 	if (g == NULL)
647 	{
648 	    if ((g = (graph*)ALLOCS(n,m*sizeof(graph))) == NULL)
649 		gt_abort(">E showg: malloc failed\n");
650 	}
651 
652 	*pn = n;
653 	*pm = m;
654 
655 	stringtograph(s,g,m);
656 	return g;
657 }
658 
659 /**************************************************************************/
660 
661 static int
longvalue(ps,l)662 longvalue(ps,l)
663 char **ps;
664 long *l;
665 {
666 	boolean neg,pos;
667 	long sofar,last;
668 	char *s;
669 
670 	s = *ps;
671 	pos = neg = FALSE;
672 	if (*s == '-')
673 	{
674 	    neg = TRUE;
675 	    ++s;
676 	}
677 	else if (*s == '+')
678 	{
679 	    pos = TRUE;
680 	    ++s;
681 	}
682 
683 	if (*s < '0' || *s > '9')
684 	{
685 	    *ps = s;
686 	    return (pos || neg) ? ARG_ILLEGAL : ARG_MISSING;
687 	}
688 
689 	sofar = 0;
690 
691 	for (; *s >= '0' && *s <= '9'; ++s)
692 	{
693 	    last = sofar;
694 	    sofar = sofar * 10 + (*s - '0');
695 	    if (sofar < last || sofar > MAXARG)
696 	    {
697 		*ps = s;
698 		return ARG_TOOBIG;
699 	    }
700 	}
701 	*ps = s;
702 	*l = neg ? -sofar : sofar;
703 	return ARG_OK;
704 }
705 
706 /*************************************************************************/
707 
708 static void
arg_int(ps,val,id)709 arg_int(ps,val,id)
710 char **ps;
711 int *val;
712 char *id;
713 {
714 	int code;
715 	long longval;
716 
717 	code = longvalue(ps,&longval);
718 	*val = longval;
719 	if (code == ARG_MISSING || code == ARG_ILLEGAL)
720 	{
721 	    fprintf(stderr,">E %s: missing argument value\n",id);
722 	    gt_abort(NULL);
723 	}
724 	else if (code == ARG_TOOBIG || *val != longval)
725 	{
726 	    fprintf(stderr,">E %s: argument value too large\n",id);
727 	    gt_abort(NULL);
728 	}
729 }
730 
731 /************************************************************************/
732 
733 static void
arg_range(ps,val1,val2,id)734 arg_range(ps,val1,val2,id)
735 char **ps;
736 long *val1,*val2;
737 char *id;
738 {
739 	int code;
740 	char *s;
741 
742 	s = *ps;
743 	code = longvalue(&s,val1);
744 	if (code != ARG_MISSING)
745 	{
746 	    if (code == ARG_ILLEGAL)
747 	    {
748 		fprintf(stderr,">E %s: bad range\n",id);
749 		gt_abort(NULL);
750 	    }
751 	    else if (code == ARG_TOOBIG)
752 	    {
753 		fprintf(stderr,">E %s: value too big\n",id);
754 		gt_abort(NULL);
755 	    }
756 	}
757 	else if (*s != ':' && *s != '-')
758 	{
759 	    fprintf(stderr,">E %s: missing value\n",id);
760 	    gt_abort(NULL);
761 	}
762 	else
763 	    *val1 = -NOLIMIT;
764 
765 	if (*s == ':' || *s == '-')
766 	{
767 	    ++s;
768 	    code = longvalue(&s,val2);
769 	    if (code == ARG_MISSING)
770 		*val2 = NOLIMIT;
771 	    else if (code == ARG_TOOBIG)
772 	    {
773 		fprintf(stderr,">E %s: value too big\n",id);
774 		gt_abort(NULL);
775 	    }
776 	    else if (code == ARG_ILLEGAL)
777 	    {
778 		fprintf(stderr,">E %s: illegal range\n",id);
779 		gt_abort(NULL);
780 	    }
781 	}
782 	else
783 	    *val2 = *val1;
784 
785 	*ps = s;
786 }
787 
788 /************************************************************************/
789 
790 #define LABELORG 0   /* number of first vertex (any integer >= 0) */
791 #define LINELEN 78   /* max characters per line (0 = no limit) */
792 
793 static FILE *infile,*outfile;
794 static long nin;
795 extern int labelorg;
796 
797 /*****************************************************************************
798 *                                                                            *
799 *  putsetx(f,set1,curlenp,linelength,m,compress,start)   writes the set      *
800 *  set1 to file f using at most linelength characters per line (excluding    *
801 *  '\n').   Set elements less than or equal to start are ignored.            *
802 *  *curlenp is the number of characters on the line so far; it is updated.   *
803 *  A range j1,j1+1,...,j2 for j2-j1>=2 is written as "j1:j2" if compress     *
804 *  is nonzero (eg. TRUE); otherwise each element is written separately.      *
805 *  No final '\n' is written.  labelorg is used.                              *
806 *                                                                            *
807 *  FUNCTIONS CALLED: nextelement(),itos()                                    *
808 *                                                                            *
809 *****************************************************************************/
810 
811 void
putsetx(f,set1,curlenp,linelength,m,compress,start)812 putsetx(f,set1,curlenp,linelength,m,compress,start)
813 FILE *f;
814 set *set1;
815 int linelength,m,*curlenp;
816 boolean compress;
817 {
818         int slen,j1,j2;
819         char s[40];
820 	boolean first;
821 
822 	first = TRUE;
823         j1 = start;
824         while ((j1 = nextelement(set1,m,j1)) >= 0)
825         {
826             j2 = j1;
827             if (compress)
828             {
829                 while (nextelement(set1,m,j2) == j2 + 1)
830                     ++j2;
831                 if (j2 == j1+1)
832                     j2 = j1;
833             }
834             slen = itos(j1 + labelorg,s);
835             if (j2 >= j1 + 2)
836             {
837                 s[slen] = ':';
838                 slen += 1 + itos(j2 + labelorg,&s[slen+1]);
839             }
840 
841             if (*curlenp + slen + 1 >= linelength)
842             {
843                 fprintf(f,"\n ");
844                 *curlenp = 1;
845             }
846 	    if (first)
847 	    {
848                 fprintf(f,"%s",s);
849                 *curlenp += slen;
850 		first = FALSE;
851 	    }
852 	    else
853             {
854                 fprintf(f," %s",s);
855                 *curlenp += slen + 1;
856             }
857             j1 = j2;
858         }
859 }
860 
861 /*****************************************************************************
862 *                                                                            *
863 *  STOLEN FROM naututil.c                                                    *
864 *  putgraphx(f,g,linelength,m,n) writes a list of the edges of g to f        *
865 *  using at most linelength characters per line (excluding '\n').            *
866 *  If triang, only write the upper triangle.                                 *
867 *  labelorg is used.                                                         *
868 *                                                                            *
869 *****************************************************************************/
870 
871 void
putgraphx(f,g,linelength,triang,m,n)872 putgraphx(f,g,linelength,triang,m,n)
873 FILE *f;
874 graph *g;
875 int linelength,m,n;
876 boolean triang;
877 {
878         int i,curlen;
879         set *pg;
880 
881         for (i = 0, pg = g; i < n; ++i, pg += m)
882         {
883             fprintf(f,"%3d : ",i + labelorg);
884             curlen = 7;
885             putsetx(f,pg,&curlen,linelength,m,FALSE,triang ? i-1 : -1);
886             fprintf(f,";\n");
887         }
888 }
889 
890 /***************************************************************************/
891 
892 void
putedges(f,g,linelength,m,n)893 putedges(f,g,linelength,m,n)   /* write list of edges */
894 FILE *f;
895 graph *g;
896 int linelength,m,n;
897 {
898 	int i,j,curlen,ne;
899 	char s[20];
900 	set *pg;
901 
902 	ne = 0;
903         for (i = 0, pg = g; i < n; ++i, pg += m)
904 	{
905 	    for (j = i-1; (j = nextelement(pg,m,j)) >= 0;)
906 		++ne;
907 	}
908 
909 	fprintf(f,"%d %d\n",n,ne);
910 	curlen = 0;
911         for (i = 0, pg = g; i < n; ++i, pg += m)
912 	{
913 	    for (j = i-1; (j = nextelement(pg,m,j)) >= 0;)
914 	    {
915 		if (curlen > linelength - 10 && linelength > 0)
916 		{
917 		    fprintf(f,"\n");
918 		    curlen = 0;
919 		}
920 		if (curlen > 0)
921 		{
922 		    fprintf(f,"  ");
923 		    curlen += 2;
924 		}
925 		curlen += itos(i+labelorg,s);
926 		fprintf(f,s);
927 		fprintf(f," ");
928 		curlen += 1 + itos(j+labelorg,s);
929 		fprintf(f,s);
930 	    }
931 	}
932 	fprintf(f,"\n");
933 }
934 
935 /***************************************************************************/
936 
937 void
putcgraph(f,g,linelength,m,n)938 putcgraph(f,g,linelength,m,n)  /* write compressed form */
939 FILE *f;
940 graph *g;
941 int linelength,m,n;
942 {
943         int i,curlen;
944 	int semicolons;
945 	char s[20];
946         set *pg;
947 
948 	curlen = itos(n,s)+2;
949 	fprintf(f,";n%sg",s);
950 
951 	semicolons = 0;
952         for (i = 0, pg = g; i < n; ++i, pg += m)
953         {
954 	    if (nextelement(pg,m,i-1) >= 0)
955 	    {
956 		while (semicolons > 0)
957 		{
958 		    if (curlen >= linelength-1 && linelength > 0)
959 		    {
960 			fprintf(f,"\n ");
961 			curlen = 1;
962 		    }
963 		    fprintf(f,";");
964 		    ++curlen;
965 		    --semicolons;
966 		}
967                 putsetx(f,pg,&curlen,linelength,m,FALSE,i-1);
968                 semicolons = 1;
969 	    }
970 	    else
971 		++semicolons;
972         }
973 	fprintf(f,".\n");
974 }
975 
976 /**************************************************************************/
977 
978 static void
putam(f,g,linelength,space,triang,m,n)979 putam(f,g,linelength,space,triang,m,n)   /* write adjacency matrix */
980 FILE *f;
981 graph *g;
982 int linelength,m,n;
983 boolean space,triang;
984 {
985  	register set *gi;
986 	register int i,j;
987 	boolean first;
988 
989 	for (i = 0, gi = (set*)g; i < n - (triang!=0); ++i, gi += m)
990 	{
991 	    first = TRUE;
992 	    for (j = triang ? i+1 : 0; j < n; ++j)
993 	    {
994 		if (!first && space) putc(' ',f);
995 		else                 first = FALSE;
996 		if (ISELEMENT(gi,j)) putc('1',f);
997 		else                 putc('0',f);
998 	    }
999 	    putc('\n',f);
1000 	}
1001 }
1002 
1003 /**************************************************************************/
1004 /**************************************************************************/
1005 
main(argc,argv)1006 main(argc,argv)
1007 int argc;
1008 char *argv[];
1009 {
1010 	graph *g;
1011 	int m,n,codetype;
1012 	int argnum,j;
1013 	char *arg,sw;
1014 	boolean badargs;
1015 	long maxin,pval1,pval2;
1016 	boolean fswitch,pswitch,cswitch,dswitch;
1017 	boolean aswitch,lswitch,oswitch,Fswitch;
1018 	boolean Aswitch,eswitch,tswitch,qswitch;
1019 	int linelength;
1020 	char *infilename,*outfilename;
1021 
1022 	if (argc > 1 && strcmp(argv[1],"-help") == 0)
1023 	{
1024 	    printf("Usage: %s\n\n%s",USAGE,HELPTEXT);
1025 	    exit(0);
1026 	}
1027 
1028 	if (sizeof(setword) < 4)
1029 	{
1030 	    fprintf(stderr,">E showg: setword too small\n");
1031 	    fprintf(stderr,"   Please report this to bdm@cs.anu.edu.au\n");
1032 	    exit(1);
1033 	}
1034 
1035 	fswitch = pswitch = cswitch = dswitch = FALSE;
1036 	aswitch = lswitch = oswitch = Fswitch = FALSE;
1037 	Aswitch = eswitch = tswitch = qswitch = FALSE;
1038 	infilename = outfilename = NULL;
1039 	linelength = LINELEN;
1040 	labelorg = 0;
1041 
1042 	argnum = 0;
1043 	badargs = FALSE;
1044 	for (j = 1; !badargs && j < argc; ++j)
1045 	{
1046 	    arg = argv[j];
1047 	    if (arg[0] == '-' && arg[1] != '\0')
1048 	    {
1049 		++arg;
1050 		while (*arg != '\0')
1051 		{
1052 		    sw = *arg++;
1053 			 SWBOOLEAN('a',aswitch)
1054 		    else SWBOOLEAN('A',Aswitch)
1055 		    else SWBOOLEAN('c',cswitch)
1056 		    else SWBOOLEAN('d',dswitch)
1057 		    else SWBOOLEAN('e',eswitch)
1058 		    else SWBOOLEAN('f',fswitch)
1059 		    else SWBOOLEAN('F',Fswitch)
1060 		    else SWBOOLEAN('t',tswitch)
1061 		    else SWBOOLEAN('q',qswitch)
1062 		    else SWRANGE('p',pswitch,pval1,pval2,"showg -p")
1063 		    else SWINT('l',lswitch,linelength,"showg -l")
1064 		    else SWINT('o',oswitch,labelorg,"listo -o")
1065 		    else badargs = TRUE;
1066 		}
1067 	    }
1068 	    else
1069 	    {
1070 		++argnum;
1071 		if      (argnum == 1) infilename = arg;
1072 		else if (argnum == 2) outfilename = arg;
1073 		else                  badargs = TRUE;
1074 	    }
1075 	}
1076 
1077 	if (labelorg < 0) gt_abort(">E showg: negative origin forbidden.\n");
1078 
1079 	if ((aswitch!=0) + (Aswitch!=0) + (eswitch!=0)
1080 	    		 + (dswitch!=0) + (cswitch!=0) > 1)
1081 	    gt_abort(">E showg: -aAecd are incompatible\n");
1082 
1083 	if (badargs)
1084 	{
1085 	    fprintf(stderr,">E Usage: %s\n",USAGE);
1086 	    fprintf(stderr,"Use showg -help to see a list of the options.\n");
1087 	    exit(1);
1088 	}
1089 
1090 	if (!pswitch || pval1 < 1) pval1 = 1;
1091 
1092 	if (infilename && infilename[0] == '-') infilename = NULL;
1093 	infile = opengraphfile(infilename,&codetype,fswitch,
1094 			       pswitch ? pval1 : 1);
1095 	if (!infile) exit(1);
1096 	if (!infilename) infilename = "stdin";
1097 
1098 	if (!outfilename || outfilename[0] == '-')
1099 	{
1100 	    outfilename = "stdout";
1101 	    outfile = stdout;
1102 	}
1103 	else if ((outfile = fopen(outfilename,"w")) == NULL)
1104 	{
1105 	    fprintf(stderr,"Can't open output file %s\n",outfilename);
1106 	    gt_abort(NULL);
1107 	}
1108 
1109 	nin = 0;
1110 	if (!pswitch || pval2 == NOLIMIT)
1111 	    maxin = NOLIMIT;
1112 	else if (pval1 < 1) maxin = pval2;
1113 	else                maxin = pval2 - pval1 + 1;
1114 	while (nin < maxin || maxin == NOLIMIT)
1115 	{
1116 	    if ((g = readg(infile,NULL,0,&m,&n)) == NULL) break;
1117 	    ++nin;
1118 
1119 	    if (Fswitch && nin > 1) fprintf(outfile,"\f");
1120 
1121 	    if (cswitch)
1122 		putcgraph(outfile,g,linelength,m,n);
1123 	    else if (dswitch)
1124 	    {
1125 		if (qswitch)
1126 		    fprintf(outfile,"%d\n",n);
1127 		else
1128 		{
1129 		    fprintf(outfile,"\n!Graph %ld.\n",pval1+nin-1);
1130 		    fprintf(outfile,"n=%d $=%d g\n",n,labelorg);
1131 		}
1132 		putgraphx(outfile,g,linelength,tswitch,m,n);
1133 		if (!qswitch) fprintf(outfile,"$$\n");
1134 	    }
1135 	    else
1136             {
1137 		if (qswitch)
1138 		{
1139 		    if (!eswitch) fprintf(outfile,"%d\n",n);
1140 		}
1141                 else fprintf(outfile,"\nGraph %ld, order %d.\n",
1142 				     pval1+nin-1,n);
1143 	        if (aswitch|Aswitch)
1144 		    putam(outfile,g,linelength,Aswitch,tswitch,m,n);
1145 		else if (eswitch)
1146 		    putedges(outfile,g,linelength,m,n);
1147 	        else
1148 	            putgraphx(outfile,g,linelength,tswitch,m,n);
1149             }
1150 	    FREES(g);
1151 	}
1152 
1153 	exit(0);
1154 }
1155