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