1 /*****************************************************************************
2 * *
3 * This is the main file for dreadnaut() version 2.2, which is a test-bed *
4 * for nauty() version 2.2. *
5 * *
6 * Copyright (1984-2004) Brendan McKay. All rights reserved. *
7 * Subject to the waivers and disclaimers in nauty.h. *
8 * *
9 * CHANGE HISTORY *
10 * 10-Nov-87 : final changes for version 1.2 *
11 * 5-Dec-87 - replaced all uses of fscanf() by appropriate uses *
12 * of the new procedures readinteger() and readstring() *
13 * - changed the '<' command slightly. If a file of the *
14 * given name cannot be openned, an attempt is made to *
15 * open a file with the same name extended by DEFEXT. *
16 * - improved error processing for 'n' command. *
17 * 28-Sep-88 : changes for version 1.4 : *
18 * - replaced incorrect %d by %ld in fprintf for ? command *
19 * 23-Mar-89 : changes for version 1.5 : *
20 * - added optional startup message *
21 * - enabled use of refine1 in 'i' command *
22 * - implemented $$ command *
23 * - replaced ALLOCS test by DYNALLOC test *
24 * - modified @ command and added # command *
25 * - declared local procedures static *
26 * 25-Mar-89 - implemented k command *
27 * 27-Mar-89 - implemented * and I commands *
28 * 29-Mar-89 - implemented K command *
29 * 2-Apr-89 - added reporting of vertex-invariant statistics *
30 * 2-Apr-89 - added ## command *
31 * 4-Apr-89 - added triples(), quadruples(), adjtriang() *
32 * - updated error reporting for nauty() *
33 * 5-Apr-89 - removed flushline() from g and e commands *
34 * - added T command *
35 * 6-Apr-89 - added cellquads() and distances() *
36 * 26-Apr-89 - modified ? command, added & and && commands *
37 * - added indsets(), cliques(), cellquins() *
38 * 18-Aug-89 - made g, lab, canong dynamically allocated always *
39 * 2-Mar-90 - added celltrips(), cellcliq(), cellind() *
40 * 13-Mar-90 - changed canong and savedg in output to h and h' *
41 * 19-Mar-90 - revised help() a little *
42 * 19-Apr-90 : changes for version 1.6 *
43 * - rewrote "*" command to avoid bug in Pyramid C compiler *
44 * 20-Apr-90 - rewrote above rewrite to avoid bug in SUN3 gcc *
45 * 23-Apr-90 - undid above rewrite and fixed *my* bug <blush> by *
46 * making NUMINVARS have type int. Sorry, gcc. *
47 * 10-Nov-90 - added calls to null routines (see comment on code) *
48 * 27-Aug-92 : renamed to version 1.7, no changes to this file *
49 * 5-Jun-93 : renamed to version 1.7+, no changes to this file *
50 * 18-Aug-93 : renamed to version 1.8, no changes to this file *
51 * 17-Sep-93 : changes for version 1.9 : *
52 * - added invariant adjacencies() *
53 * 7-Jun-96 : changes for version 2.0 : *
54 * - added invariants cellfano() and cellfano2() *
55 * - made y=10 the default *
56 * 11-Jul-96 - added dynamic allocation *
57 * - rewrote h command and added H command *
58 * - implemented M and R commands *
59 * 15-Aug-96 - changed z command to use sethash() *
60 * 30-Aug-96 - no need to declare seed; already in naututil.h *
61 * 12-Sep-96 - let i and I commands use userrefproc *
62 * 9-Dec-96 - made y=infinity the default *
63 * 6-Sep-97 - allocated arrays before accepting commands *
64 * 7-Sep-97 - make g,canong,savedg 1-d arrays even statically *
65 * 22-Sep-97 - undid error introduced on 7-Sep (worksize) *
66 * 9-Jan-00 - used *_check() instead of *_null() *
67 * 12-Feb-00 - minor code formatting *
68 * 17-Aug-00 - now use tc_level from DEFAULTOPTIONS *
69 * 16-Nov-00 - made changes listed in nauty.h *
70 * 22-Apr-01 - include nautyinv.h *
71 * - improve worksize processing for MAXN=0 *
72 * 5-May-01 - k=0 1 automatic for *, also K=3 or K=0 *
73 * 2-Jun-01 - added __ command for digraph converse *
74 * 18-Oct-01 - moved WORKSIZE to here *
75 * 21-Nov-01 - use NAUTYREQUIRED in *_check() calls *
76 * 1-Sep-02 - Undid the previous change *
77 * 17-Nov-03 - Changed INFINITY to NAUTY_INFINITY *
78 * 15-Nov-04 - Completed all prototypes *
79 * *
80 *****************************************************************************/
81
82 #include "naututil.h" /* which includes nauty.h, which includes stdio.h */
83 #include "nautinv.h" /* which includes nauty.h, which includes stdio.h */
84
85 #define PM(x) ((x) ? '+' : '-')
86 #define SS(n,sing,plur) (n),((n)==1?(sing):(plur))
87 #define WORKSIZE 60
88
89 #ifdef CPUDEFS
90 CPUDEFS /* data decls. for CPUTIME */
91 #endif
92
93 #define INFILE fileptr[curfile]
94 #define OUTFILE outfile
95
96 #if !MAXN
97 DYNALLSTAT(graph,g,g_sz);
98 DYNALLSTAT(graph,canong,canong_sz);
99 DYNALLSTAT(graph,savedg,savedg_sz);
100 DYNALLSTAT(setword,workspace,workspace_sz);
101 DYNALLSTAT(int,lab,lab_sz);
102 DYNALLSTAT(int,ptn,ptn_sz);
103 DYNALLSTAT(int,orbits,orbits_sz);
104 DYNALLSTAT(int,savedlab,savedlab_sz);
105 DYNALLSTAT(permutation,perm,perm_sz);
106 DYNALLSTAT(set,active,active_sz);
107 #else
108 static graph g[MAXM*1L*MAXN];
109 static graph canong[MAXM*1L*MAXN];
110 static graph savedg[MAXM*1L*MAXN];
111 static setword workspace[MAXM*2L*WORKSIZE];
112 static int lab[MAXN];
113 static int ptn[MAXN];
114 static int orbits[MAXN];
115 static int savedlab[MAXN];
116 static permutation perm[MAXN];
117 static set active[MAXM];
118 #endif
119
120 static DEFAULTOPTIONS_GRAPH(options);
121 static statsblk stats;
122 static int curfile;
123 static FILE *fileptr[MAXIFILES];
124 static FILE *outfile;
125 static char def_ext[] = DEFEXT;
126 static boolean firstpath; /* used in usernode() */
127
128 #define U_NODE 1 /* masks for u values */
129 #define U_AUTOM 2
130 #define U_LEVEL 4
131 #define U_TCELL 8
132 #define U_REF 16
133
134 #ifndef NODEPROC
135 #define NODEPROC usernode
136 #else
137 extern void NODEPROC(graph*,int*,int*,int,int,int,int,int,int);
138 #endif
139
140 #ifndef AUTOMPROC
141 #define AUTOMPROC userautom
142 #else
143 extern void AUTOMPROC(int,permutation*,int*,int,int,int);
144 #endif
145
146 #ifndef LEVELPROC
147 #define LEVELPROC userlevel
148 #else
149 extern void LEVELPROC(int*,int*,int,int*,statsblk*,int,int,int,int,int,int);
150 #endif
151
152 #ifndef TCELLPROC
153 #define TCELLPROC NULL
154 #else
155 extern void TCELLPROC(graph*,int*,int*,int,int,set*,int*,int*,int,int,
156 int(*)(graph*,int*,int*,int,int,int,int),int,int);
157 #endif
158
159 #ifndef REFPROC
160 #define REFPROC NULL
161 #else
162 extern void REFPROC(graph*,int*,int*,int,int*,permutation*,set*,int*,int,int);
163 #endif
164
165 #ifndef INVARPROC
166 #define INVARPROC NULL
167 #define INVARPROCNAME "none"
168 #else
169 extern void INVARPROC(graph*,int*,int*,int,int,int,permutation*,
170 int,boolean,int,int);
171 #define INVARPROCNAME "user-defined"
172 #endif
173
174 static struct invarrec
175 {
176 void (*entrypoint)(graph*,int*,int*,int,int,int,permutation*,
177 int,boolean,int,int);
178 char *name;
179 } invarproc[]
180 = {{INVARPROC, INVARPROCNAME},
181 {NULL, "none"},
182 {twopaths, "twopaths"},
183 {adjtriang, "adjtriang"},
184 {triples, "triples"},
185 {quadruples, "quadruples"},
186 {celltrips, "celltrips"},
187 {cellquads, "cellquads"},
188 {cellquins, "cellquins"},
189 {distances, "distances"},
190 {indsets, "indsets"},
191 {cliques, "cliques"},
192 {cellcliq, "cellcliq"},
193 {cellind, "cellind"},
194 {adjacencies, "adjacencies"},
195 {cellfano, "cellfano"},
196 {cellfano2, "cellfano2"}};
197 #define NUMINVARS ((int)(sizeof(invarproc)/sizeof(struct invarrec)))
198
199 static void help(FILE*, int);
200 static void userautom(int,permutation*,int*,int,int,int);
201 static void usernode(graph*,int*,int*,int,int,int,int,int,int);
202 static void userlevel(int*,int*,int,int*,statsblk*,int,int,int,int,int,int);
203
204 #ifdef EXTRADECLS
205 EXTRADECLS
206 #endif
207
208 /*****************************************************************************
209 * *
210 * This is a program which illustrates the use of nauty. *
211 * Commands are read from stdin, and may be separated by white space, *
212 * commas or not separated. Output is written to stdout. *
213 * For a short description, see the nauty User's Guide. *
214 * *
215 *****************************************************************************/
216
217 int
main(int argc,char * argv[])218 main(int argc, char *argv[])
219 {
220 int m,n,newm,newn;
221 boolean gvalid,ovalid,cvalid,pvalid,minus,prompt,doquot;
222 int i,worksize,numcells,refcode,umask,qinvar;
223 int oldorg;
224 char *s1,*s2,*invarprocname;
225 int c,d;
226 register long li;
227 set *gp;
228 double timebefore,timeafter;
229 char filename[200];
230 int sgn,sgorg,nperm;
231 int multiplicity;
232 boolean options_writeautoms,options_writemarkers;
233 long zseed;
234
235 curfile = 0;
236 fileptr[curfile] = stdin;
237 prompt = DOPROMPT(INFILE);
238 outfile = stdout;
239 options_writeautoms = options_writemarkers = TRUE;
240 n = m = 1;
241 worksize = 2*WORKSIZE;
242
243 #if !MAXN
244 n = WORDSIZE;
245 DYNALLOC2(graph,g,g_sz,n,m,"dreadnaut");
246 DYNALLOC1(int,lab,lab_sz,n,"dreadnaut");
247 DYNALLOC1(int,ptn,ptn_sz,n,"dreadnaut");
248 DYNALLOC1(setword,workspace,workspace_sz,
249 worksize,"dreadnaut");
250 DYNALLOC1(int,orbits,orbits_sz,n,"dreadnaut");
251 DYNALLOC1(permutation,perm,perm_sz,n,"dreadnaut");
252 DYNALLOC1(set,active,active_sz,m,"dreadnaut");
253 n = 1;
254 #endif
255
256 #ifdef INITSEED
257 INITSEED;
258 ran_init(seed);
259 #endif
260
261 umask = 0;
262 pvalid = FALSE;
263 gvalid = FALSE;
264 ovalid = FALSE;
265 cvalid = FALSE;
266 minus = FALSE;
267 labelorg = oldorg = 0;
268 multiplicity = 1;
269
270 #ifdef INITIALIZE
271 INITIALIZE;
272 #endif
273
274 invarprocname = "none";
275 if (prompt)
276 {
277 #ifdef BIGNAUTY
278 fprintf(PROMPTFILE,"Dreadnaut version %s [BIG].\n",NAUTYVERSION);
279 #else
280 fprintf(PROMPTFILE,"Dreadnaut version %s.\n",NAUTYVERSION);
281 #endif
282 fprintf(PROMPTFILE,"> ");
283 }
284
285 nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);
286 nautinv_check(WORDSIZE,1,1,NAUTYVERSIONID);
287 nautil_check(WORDSIZE,1,1,NAUTYVERSIONID);
288 naututil_check(WORDSIZE,1,1,NAUTYVERSIONID);
289
290 while (curfile >= 0)
291 if ((c = getc(INFILE)) == EOF || c == '\004')
292 {
293 fclose(INFILE);
294 --curfile;
295 if (curfile >= 0) prompt = DOPROMPT(INFILE);
296 }
297 else switch (c)
298 {
299 case '\n': /* possibly issue prompt */
300 if (prompt)
301 fprintf(PROMPTFILE,"> ");
302 minus = FALSE;
303 break;
304
305 case ' ': /* do nothing */
306 case '\t':
307 #ifndef NLMAP
308 case '\r':
309 #endif
310 case '\f':
311 break;
312
313 case '-': /* remember this for next time */
314 minus = TRUE;
315 break;
316
317 case '+': /* forget - */
318 case ',':
319 case ';':
320 minus = FALSE;
321 break;
322
323 case '<': /* new input file */
324 minus = FALSE;
325 if (curfile == MAXIFILES - 1)
326 fprintf(ERRFILE,"exceeded maximum input nesting of %d\n\n",
327 MAXIFILES);
328 if (!readstring(INFILE,filename,200))
329 {
330 fprintf(ERRFILE,
331 "missing file name on '>' command : ignored\n\n");
332 break;
333 }
334 if ((fileptr[curfile+1] = fopen(filename,"r")) == NULL)
335 {
336 for (s1 = filename; *s1 != '\0'; ++s1) {}
337 for (s2 = def_ext; (*s1 = *s2) != '\0'; ++s1, ++s2) {}
338 fileptr[curfile+1] = fopen(filename,"r");
339 }
340 if (fileptr[curfile+1] != NULL)
341 {
342 ++curfile;
343 prompt = DOPROMPT(INFILE);
344 if (prompt)
345 fprintf(PROMPTFILE,"> ");
346 }
347 else
348 fprintf(ERRFILE,"can't open input file\n\n");
349 break;
350
351 case '>': /* new output file */
352 if ((d = getc(INFILE)) != '>')
353 ungetc((char)d,INFILE);
354 if (minus)
355 {
356 minus = FALSE;
357 if (outfile != stdout)
358 {
359 fclose(outfile);
360 outfile = stdout;
361 }
362 }
363 else
364 {
365 if (!readstring(INFILE,filename,200))
366 {
367 fprintf(ERRFILE,
368 "improper file name, reverting to stdout\n\n");
369 outfile = stdout;
370 break;
371 }
372 OPENOUT(outfile,filename,d=='>');
373 if (outfile == NULL)
374 {
375 fprintf(ERRFILE,
376 "can't open output file, reverting to stdout\n\n");
377 outfile = stdout;
378 }
379 }
380 break;
381
382 case '!': /* ignore rest of line */
383 do
384 c = getc(INFILE);
385 while (c != '\n' && c != EOF);
386 if (c == '\n') ungetc('\n',INFILE);
387 break;
388
389 case 'n': /* read n value */
390 minus = FALSE;
391 i = getint(INFILE);
392 if (i <= 0 || (MAXN && i > MAXN)
393 || (!MAXN && i > NAUTY_INFINITY-2))
394 fprintf(ERRFILE,
395 " n can't be less than 1 or more than %d\n\n",
396 MAXN ? MAXN : NAUTY_INFINITY-2);
397 else
398 {
399 gvalid = FALSE;
400 ovalid = FALSE;
401 cvalid = FALSE;
402 pvalid = FALSE;
403 n = i;
404 m = (n + WORDSIZE - 1) / WORDSIZE;
405 #if !MAXN
406 worksize = 2 * m * WORKSIZE;
407 DYNALLOC2(graph,g,g_sz,n,m,"dreadnaut");
408 DYNALLOC1(int,lab,lab_sz,n,"dreadnaut");
409 DYNALLOC1(int,ptn,ptn_sz,n,"dreadnaut");
410 DYNALLOC1(setword,workspace,workspace_sz,
411 worksize,"dreadnaut");
412 DYNALLOC1(int,orbits,orbits_sz,n,"dreadnaut");
413 DYNALLOC1(permutation,perm,perm_sz,n,"dreadnaut");
414 DYNALLOC1(set,active,active_sz,m,"dreadnaut");
415 #endif
416 }
417 break;
418
419 case 'g': /* read graph */
420 minus = FALSE;
421 readgraph(INFILE,g,options.digraph,prompt,FALSE,
422 options.linelength,m,n);
423 gvalid = TRUE;
424 cvalid = FALSE;
425 ovalid = FALSE;
426 break;
427
428 case 'e': /* edit graph */
429 minus = FALSE;
430 readgraph(INFILE,g,options.digraph,prompt,gvalid,
431 options.linelength,m,n);
432 gvalid = TRUE;
433 cvalid = FALSE;
434 ovalid = FALSE;
435 break;
436
437 case 'r': /* relabel graph and current partition */
438 minus = FALSE;
439 if (gvalid)
440 {
441 #if !MAXN
442 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
443 #endif
444 readvperm(INFILE,perm,prompt,n,&nperm);
445 relabel(g,(pvalid ? lab : NULL),perm,canong,m,n);
446 cvalid = FALSE;
447 ovalid = FALSE;
448 }
449 else
450 fprintf(ERRFILE,"g is not defined\n\n");
451 break;
452
453 case 'R': /* form subgraph */
454 if (gvalid)
455 {
456 #if !MAXN
457 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
458 #endif
459 readvperm(INFILE,perm,prompt,n,&nperm);
460 if (minus && nperm == n || !minus && nperm == 0)
461 fprintf(ERRFILE,"can't form null graph\n\n");
462 else if (minus)
463 {
464 sublabel(g,perm+nperm,n-nperm,canong,m,n);
465 n = n - nperm;
466 }
467 else
468 {
469 sublabel(g,perm,nperm,canong,m,n);
470 n = nperm;
471 }
472 cvalid = FALSE;
473 pvalid = FALSE;
474 ovalid = FALSE;
475 m = (n + WORDSIZE - 1) / WORDSIZE;
476 }
477 else
478 fprintf(ERRFILE,"g is not defined\n\n");
479 minus = FALSE;
480 break;
481
482 case '_': /* complement graph or converse digraph */
483 minus = FALSE;
484 if ((d = getc(INFILE)) != '_') ungetc((char)d,INFILE);
485
486 if (gvalid)
487 {
488 if (d == '_') converse(g,m,n);
489 else complement(g,m,n);
490 cvalid = FALSE;
491 ovalid = FALSE;
492 }
493 else
494 fprintf(ERRFILE,"g is not defined\n\n");
495 break;
496
497 case '@': /* copy canong into savedg */
498 minus = FALSE;
499 if (cvalid)
500 {
501 #if !MAXN
502 DYNALLOC2(graph,savedg,savedg_sz,n,m,"dreadnaut");
503 DYNALLOC1(int,savedlab,savedlab_sz,n,"dreadnaut");
504 #endif
505 sgn = n;
506 for (li = (long)n * (long)m; --li >= 0;)
507 savedg[li] = canong[li];
508 for (i = n; --i >= 0;) savedlab[i] = lab[i];
509 sgorg = labelorg;
510 }
511 else
512 fprintf(ERRFILE,"h is not defined\n\n");
513 break;
514
515 case '#': /* compare canong to savedg */
516 if ((d = getc(INFILE)) != '#') ungetc((char)d,INFILE);
517
518 if (cvalid)
519 {
520 if (sgn > 0)
521 {
522 if (sgn != n)
523 fprintf(OUTFILE,
524 "h and h' have different sizes.\n");
525 else
526 {
527 for (li = (long)n * (long)m; --li >= 0;)
528 if (savedg[li] != canong[li]) break;
529 if (li >= 0)
530 fprintf(OUTFILE,"h and h' are different.\n");
531 else
532 {
533 fprintf(OUTFILE,
534 "h and h' are identical.\n");
535 if (d == '#')
536 putmapping(OUTFILE,savedlab,sgorg,
537 lab,labelorg,options.linelength,n);
538 }
539 }
540 }
541 else
542 fprintf(ERRFILE,"h' is not defined\n\n");
543 }
544 else
545 fprintf(ERRFILE,"h is not defined\n\n");
546 break;
547
548 case 'j': /* relabel graph randomly */
549 minus = FALSE;
550 if (gvalid)
551 {
552 #if !MAXN
553 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
554 #endif
555 ranperm(perm,n);
556 relabel(g,(pvalid ? lab : NULL),perm,canong,m,n);
557 cvalid = FALSE;
558 ovalid = FALSE;
559 }
560 else
561 fprintf(ERRFILE,"g is not defined\n\n");
562 break;
563
564 case 'v': /* write vertex degrees */
565 minus = FALSE;
566 if (gvalid)
567 putdegs(OUTFILE,g,options.linelength,m,n);
568 else
569 fprintf(ERRFILE,"g is not defined\n\n");
570 break;
571
572 case '%': /* do Mathon doubling operation */
573 minus = FALSE;
574 if (gvalid)
575 {
576 #if !MAXN
577 if (2L * ((long)n + 1L) > NAUTY_INFINITY-2)
578 {
579 fprintf(ERRFILE,
580 "n can't be more than %d\n\n",NAUTY_INFINITY-2);
581 break;
582 }
583 #else
584 if (2L * ((long)n + 1L) > MAXN)
585 {
586 fprintf(ERRFILE,"n can't be more than %d\n\n",MAXN);
587 break;
588 }
589 #endif
590 newn = 2 * (n + 1);
591 newm = (newn + WORDSIZE - 1) / WORDSIZE;
592 #if !MAXN
593 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
594 #endif
595
596 for (li = (long)n * (long)m; --li >= 0;)
597 canong[li] = g[li];
598
599 #if !MAXN
600 DYNALLOC2(graph,g,g_sz,newn,newm,"dreadnaut");
601 DYNALLOC1(int,lab,lab_sz,newn,"dreadnaut");
602 DYNALLOC1(int,ptn,ptn_sz,newn,"dreadnaut");
603 worksize = 2*WORKSIZE*newm;
604 DYNALLOC1(setword,workspace,workspace_sz,
605 worksize,"dreadnaut");
606 DYNALLOC1(int,orbits,orbits_sz,newn,"dreadnaut");
607 DYNALLOC1(permutation,perm,perm_sz,newn,"dreadnaut");
608 DYNALLOC1(set,active,active_sz,newm,"dreadnaut");
609 #endif
610 mathon(canong,m,n,g,newm,newn);
611 m = newm;
612 n = newn;
613 cvalid = FALSE;
614 ovalid = FALSE;
615 pvalid = FALSE;
616 }
617 else
618 fprintf(ERRFILE,"g is not defined\n\n");
619 break;
620
621 case 's': /* generate random graph */
622 minus = FALSE;
623 i = getint(INFILE);
624 if (i <= 0) i = 2;
625 rangraph(g,options.digraph,i,m,n);
626 gvalid = TRUE;
627 cvalid = FALSE;
628 ovalid = FALSE;
629 break;
630
631 case 'q': /* quit */
632 EXIT;
633 break;
634
635 case '"': /* copy comment to output */
636 minus = FALSE;
637 copycomment(INFILE,OUTFILE,'"');
638 break;
639
640 case 'I': /* do refinement and invariants procedure */
641 if (!pvalid)
642 unitptn(lab,ptn,&numcells,n);
643 cellstarts(ptn,0,active,m,n);
644 #ifdef CPUTIME
645 timebefore = CPUTIME;
646 #endif
647 doref(g,lab,ptn,0,&numcells,&qinvar,perm,active,&refcode,
648 options.userrefproc ? options.userrefproc :
649 (m == 1 ? refine1 : refine),
650 options.invarproc,0,0,
651 options.invararg,options.digraph,m,n);
652 #ifdef CPUTIME
653 timeafter = CPUTIME;
654 #endif
655 fprintf(OUTFILE," %d cell%s; code = %x",
656 SS(numcells,"","s"),refcode);
657 if (options.invarproc != NULL)
658 fprintf(OUTFILE," (%s %s)",invarprocname,
659 (qinvar == 2 ? "worked" : "failed"));
660 #ifdef CPUTIME
661 fprintf(OUTFILE,"; cpu time = %.2f seconds\n",
662 timeafter-timebefore);
663 #else
664 fprintf(OUTFILE,"\n");
665 #endif
666 if (numcells > 1) pvalid = TRUE;
667 break;
668
669 case 'i': /* do refinement */
670 if (!pvalid)
671 unitptn(lab,ptn,&numcells,n);
672 cellstarts(ptn,0,active,m,n);
673 if (options.userrefproc)
674 (*options.userrefproc)
675 (g,lab,ptn,0,&numcells,perm,active,&refcode,m,n);
676 else if (m == 1)
677 refine1(g,lab,ptn,0,&numcells,perm,active,&refcode,m,n);
678 else
679 refine(g,lab,ptn,0,&numcells,perm,active,&refcode,m,n);
680 fprintf(OUTFILE," %d cell%s; code = %x\n",
681 SS(numcells,"","s"),refcode);
682 if (numcells > 1) pvalid = TRUE;
683 break;
684
685 case 'x': /* execute nauty */
686 minus = FALSE;
687 ovalid = FALSE;
688 cvalid = FALSE;
689 if (!gvalid)
690 {
691 fprintf(ERRFILE,"g is not defined\n\n");
692 break;
693 }
694 if (pvalid)
695 {
696 fprintf(OUTFILE,"[fixing partition]\n");
697 options.defaultptn = FALSE;
698 }
699 else
700 options.defaultptn = TRUE;
701 options.outfile = outfile;
702
703 if (options.getcanon)
704 {
705 #if !MAXN
706 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
707 #endif
708 }
709
710 firstpath = TRUE;
711 options.writeautoms = options_writeautoms;
712 options.writemarkers = options_writemarkers;
713 #ifdef CPUTIME
714 timebefore = CPUTIME;
715 #endif
716 for (i = 0; i < multiplicity; ++i)
717 {
718 nauty(g,lab,ptn,NULL,orbits,&options,&stats,workspace,
719 worksize,m,n,canong);
720 options.writeautoms = FALSE;
721 options.writemarkers = FALSE;
722 }
723 #ifdef CPUTIME
724 timeafter = CPUTIME;
725 #endif
726 if (stats.errstatus != 0)
727 fprintf(ERRFILE,
728 "nauty returned error status %d [this can't happen]\n\n",
729 stats.errstatus);
730 else
731 {
732 if (options.getcanon) cvalid = TRUE;
733 ovalid = TRUE;
734 fprintf(OUTFILE,"%d orbit%s",SS(stats.numorbits,"","s"));
735 if (stats.grpsize2 == 0)
736 fprintf(OUTFILE,"; grpsize=%.0f",stats.grpsize1+0.1);
737 else
738 {
739 while (stats.grpsize1 >= 10.0)
740 {
741 stats.grpsize1 /= 10.0;
742 ++stats.grpsize2;
743 }
744 fprintf(OUTFILE,"; grpsize=%12.10fe%d",
745 stats.grpsize1,stats.grpsize2);
746 }
747 fprintf(OUTFILE,"; %d gen%s",
748 SS(stats.numgenerators,"","s"));
749 fprintf(OUTFILE,"; %ld node%s",SS(stats.numnodes,"","s"));
750 if (stats.numbadleaves)
751 fprintf(OUTFILE," (%ld bad lea%s)",
752 SS(stats.numbadleaves,"f","ves"));
753 fprintf(OUTFILE,"; maxlev=%d\n", stats.maxlevel);
754 fprintf(OUTFILE,"tctotal=%ld",stats.tctotal);
755 if (options.getcanon)
756 fprintf(OUTFILE,"; canupdates=%ld",stats.canupdates);
757 #ifdef CPUTIME
758 fprintf(OUTFILE,multiplicity == 1 ?
759 "; cpu time = %.2f seconds\n" :
760 "; cpu time = %.5f seconds\n",
761 (timeafter-timebefore)/multiplicity);
762 #else
763 fprintf(OUTFILE,"\n");
764 #endif
765 if (options.invarproc != NULL &&
766 options.maxinvarlevel != 0)
767 {
768 fprintf(OUTFILE,"invarproc \"%s\" succeeded %ld/%ld",
769 invarprocname,stats.invsuccesses,stats.invapplics);
770 if (stats.invarsuclevel > 0)
771 fprintf(OUTFILE," beginning at level %d.\n",
772 stats.invarsuclevel);
773 else
774 fprintf(OUTFILE,".\n");
775 }
776 }
777 break;
778
779 case 'f': /* read initial partition */
780 if (minus)
781 {
782 pvalid = FALSE;
783 minus = FALSE;
784 }
785 else
786 {
787 readptn(INFILE,lab,ptn,&numcells,prompt,n);
788 pvalid = TRUE;
789 }
790 break;
791
792 case 't': /* type graph */
793 minus = FALSE;
794 if (!gvalid)
795 fprintf(ERRFILE,"g is not defined\n\n");
796 else
797 putgraph(OUTFILE,g,options.linelength,m,n);
798 break;
799
800 case 'T': /* type graph preceded by n, $ and g commands */
801 minus = FALSE;
802 if (!gvalid)
803 fprintf(ERRFILE,"g is not defined\n\n");
804 else
805 {
806 fprintf(OUTFILE,"n=%d $=%d g\n",n,labelorg);
807 putgraph(OUTFILE,g,options.linelength,m,n);
808 fprintf(OUTFILE,"$$\n");
809 }
810 break;
811
812 case 'u': /* call user procs */
813 if (minus)
814 {
815 umask = 0;
816 minus = FALSE;
817 }
818 else
819 {
820 umask = getint(INFILE);
821 if (umask < 0)
822 umask = ~0;
823 }
824 if (umask & U_NODE) options.usernodeproc = NODEPROC;
825 else options.usernodeproc = NULL;
826 if (umask & U_AUTOM) options.userautomproc = AUTOMPROC;
827 else options.userautomproc = NULL;
828 if (umask & U_LEVEL) options.userlevelproc = LEVELPROC;
829 else options.userlevelproc = NULL;
830 if (umask & U_TCELL) options.usertcellproc = TCELLPROC;
831 else options.usertcellproc = NULL;
832 if (umask & U_REF) options.userrefproc = REFPROC;
833 else options.userrefproc = NULL;
834 break;
835
836 case 'o': /* type orbits */
837 minus = FALSE;
838 if (ovalid)
839 putorbits(OUTFILE,orbits,options.linelength,n);
840 else
841 fprintf(ERRFILE,"orbits are not defined\n\n");
842 break;
843
844 case 'b': /* type canonlab and canong */
845 minus = FALSE;
846 if (cvalid)
847 putcanon(OUTFILE,lab,canong,options.linelength,m,n);
848 else
849 fprintf(ERRFILE,"h is not defined\n\n");
850 break;
851
852 case 'z': /* type hashcode for canong */
853 minus = FALSE;
854 if (cvalid)
855 {
856 zseed = n;
857 for (i = 0, gp = canong; i < n; ++i, gp += m)
858 zseed = sethash(gp,n,zseed,321);
859 fprintf(OUTFILE,"[%7lx",zseed);
860
861 for (i = 0, gp = canong; i < n; ++i, gp += m)
862 zseed = sethash(gp,n,zseed,3109);
863 fprintf(OUTFILE," %7lx",zseed);
864
865 for (i = 0, gp = canong; i < n; ++i, gp += m)
866 zseed = sethash(gp,n,zseed,4317);
867 fprintf(OUTFILE," %7lx]\n",zseed);
868 }
869 else
870 fprintf(ERRFILE,"h is not defined\n\n");
871 break;
872
873 case 'c': /* set getcanon option */
874 options.getcanon = !minus;
875 minus = FALSE;
876 break;
877
878 case 'w': /* read size of workspace */
879 minus = FALSE;
880 worksize = getint(INFILE);
881 #if !MAXN
882 DYNALLOC1(setword,workspace,workspace_sz,worksize,"dreadnaut");
883 #else
884 if (worksize > 2*MAXM*WORKSIZE)
885 {
886 fprintf(ERRFILE,
887 "too big - setting worksize = %d\n\n", 2*MAXM*WORKSIZE);
888 worksize = 2*MAXM*WORKSIZE;
889 }
890 #endif
891 break;
892
893 case 'l': /* read linelength for output */
894 options.linelength = getint(INFILE);
895 minus = FALSE;
896 break;
897
898 case 'y': /* set tc_level field of options */
899 options.tc_level = getint(INFILE);
900 minus = FALSE;
901 break;
902
903 case 'M': /* set multiplicity */
904 multiplicity = getint(INFILE);
905 if (multiplicity <= 0) multiplicity = 1;
906 minus = FALSE;
907 break;
908
909 case 'k': /* set invarlev fields of options */
910 options.mininvarlevel = getint(INFILE);
911 options.maxinvarlevel = getint(INFILE);
912 minus = FALSE;
913 break;
914
915 case 'K': /* set invararg field of options */
916 options.invararg = getint(INFILE);
917 minus = FALSE;
918 break;
919
920 case '*': /* set invarproc field of options */
921 minus = FALSE;
922 d = getint(INFILE);
923 if (d >= -1 && d <= NUMINVARS-2)
924 {
925 options.invarproc = invarproc[d+1].entrypoint;
926 invarprocname = invarproc[d+1].name;
927 if (options.invarproc != NULL)
928 {
929 options.mininvarlevel = 0;
930 options.maxinvarlevel = 1;
931 if (options.invarproc == indsets ||
932 options.invarproc == cliques ||
933 options.invarproc == cellind ||
934 options.invarproc == cellcliq)
935 options.invararg = 3;
936 else
937 options.invararg = 0;
938 }
939 }
940 else
941 fprintf(ERRFILE,"no such vertex-invariant\n\n");
942 break;
943
944 case 'a': /* set writeautoms option */
945 options_writeautoms = !minus;
946 minus = FALSE;
947 break;
948
949 case 'm': /* set writemarkers option */
950 options_writemarkers = !minus;
951 minus = FALSE;
952 break;
953
954 case 'p': /* set cartesian option */
955 options.cartesian = !minus;
956 minus = FALSE;
957 break;
958
959 case 'd': /* set digraph option */
960 if (options.digraph && minus)
961 gvalid = FALSE;
962 options.digraph = !minus;
963 minus = FALSE;
964 break;
965
966 case '$': /* set label origin */
967 if ((d = getc(INFILE)) == '$')
968 labelorg = oldorg;
969 else
970 {
971 ungetc((char)d,INFILE);
972 oldorg = labelorg;
973 i = getint(INFILE);
974 if (i < 0)
975 fprintf(ERRFILE,"labelorg must be >= 0\n\n");
976 else
977 labelorg = i;
978 }
979 break;
980
981 case '?': /* type options, etc. */
982 minus = FALSE;
983 fprintf(OUTFILE,"m=%d n=%d labelorg=%d",m,n,labelorg);
984 if (!gvalid)
985 fprintf(OUTFILE," g=undef");
986 else
987 {
988 li = 0;
989 for (i = 0, gp = g; i < n; ++i, gp += m)
990 li += setsize(gp,m);
991 if (options.digraph)
992 fprintf(OUTFILE," arcs=%ld",li);
993 else
994 fprintf(OUTFILE," edges=%ld",li/2);
995 }
996 fprintf(OUTFILE," options=(%cc%ca%cm%cp%cd",
997 PM(options.getcanon),PM(options_writeautoms),
998 PM(options_writemarkers),PM(options.cartesian),
999 PM(options.digraph));
1000 if (umask & 31)
1001 fprintf(OUTFILE," u=%d",umask&31);
1002 if (options.tc_level > 0)
1003 fprintf(OUTFILE," y=%d",options.tc_level);
1004 if (options.mininvarlevel != 0 || options.maxinvarlevel != 0)
1005 fprintf(OUTFILE," k=(%d,%d)",
1006 options.mininvarlevel,options.maxinvarlevel);
1007 if (options.invararg > 0)
1008 fprintf(OUTFILE," K=%d",options.invararg);
1009 if (multiplicity > 1) fprintf(OUTFILE," M=%d",multiplicity);
1010 fprintf(OUTFILE,")\n");
1011 fprintf(OUTFILE,"linelen=%d worksize=%d input_depth=%d",
1012 options.linelength,worksize,curfile);
1013 if (options.invarproc != NULL)
1014 fprintf(OUTFILE," invarproc=%s",invarprocname);
1015 if (pvalid)
1016 fprintf(OUTFILE,"; %d cell%s",SS(numcells,"","s"));
1017 else
1018 fprintf(OUTFILE,"; 1 cell");
1019 fprintf(OUTFILE,"\n");
1020 if (OUTFILE != PROMPTFILE)
1021 fprintf(PROMPTFILE,"m=%d n=%d depth=%d labelorg=%d\n",
1022 m,n,curfile,labelorg);
1023 break;
1024
1025 case '&': /* list the partition and possibly the quotient */
1026 if ((d = getc(INFILE)) == '&')
1027 doquot = TRUE;
1028 else
1029 {
1030 ungetc((char)d,INFILE);
1031 doquot = FALSE;
1032 }
1033 minus = FALSE;
1034 if (pvalid)
1035 putptn(OUTFILE,lab,ptn,0,options.linelength,n);
1036 else
1037 fprintf(OUTFILE,"unit partition\n");
1038 if (doquot)
1039 {
1040 if (!pvalid) unitptn(lab,ptn,&numcells,n);
1041 putquotient(OUTFILE,g,lab,ptn,0,options.linelength,m,n);
1042 }
1043 break;
1044
1045 case 'h': /* type help information */
1046 case 'H':
1047 minus = FALSE;
1048 help(PROMPTFILE,c == 'H');
1049 break;
1050
1051 default: /* illegal command */
1052 fprintf(ERRFILE,"'%c' is illegal - type 'h' for help\n\n",c);
1053 flushline(INFILE);
1054 if (prompt) fprintf(PROMPTFILE,"> ");
1055 break;
1056
1057 } /* end of switch */
1058
1059 exit(0);
1060 }
1061
1062 /*****************************************************************************
1063 * *
1064 * help(f,i) writes help information to file f (i = 0,1). *
1065 * *
1066 *****************************************************************************/
1067
1068 static void
help(FILE * f,int i)1069 help(FILE *f, int i)
1070 {
1071 #define H(ss) fprintf(f," %s\n",ss);
1072
1073 if (i == 0)
1074 {
1075 H("+- a : write automs v : write degrees *=# : select invariant:")
1076 H(" b : write canong w=# : set worksize")
1077 H("+- c : canonise x : run nauty -1 = user-defined")
1078 H("+- d : digraph or loops y=# : set tc_level 0 = none")
1079 H(" e : edit graph z : write hashcode 1 = twopaths")
1080 H("-f, f=#, f=[...] : set colours 2 = adjtriang(K=0,1)")
1081 H(" g : read graph $=# : set origin 3 = triples")
1082 H(" h,H : help $$ : restore origin 4 = quadruples")
1083 H(" i : refine ? : type options 5 = celltrips")
1084 H(" I : refine using invar _ : compl __ : conv 6 = cellquads")
1085 H(" j : relabel randomly % : Mathon doubling 7 = cellquins")
1086 H("k=# # : set invar levels & : type colouring 8 = distances(K)")
1087 H(" K=# : set invar param && : + quotient matrix 9 = indsets(K)")
1088 H(" l=# : set line length >ff : write to file 10 = cliques(K)")
1089 H("+- m : write markers >>ff : append to file 11 = cellcliq(K)")
1090 H(" n=# : set order -> : revert to stdout 12 = cellind(K)")
1091 H(" o : write orbits <ff : read from file 13 = adjacencies")
1092 H("+- p : set autom format @ : save canong 14 = cellfano")
1093 H(" q : quit # : canong = savedg? 15 = cellfano2")
1094 H(" r,R : relabel/subgraph ## : + write mapping")
1095 H(" s=# : random g (p=1/#) \"...\" : copy comment")
1096 H(" t,T : type graph ! : ignore line Type H for more..")
1097 }
1098
1099 if (i == 1)
1100 {
1101 H("Commands for g and e : ")
1102 H(" There is always a \"current vertex\" v, initially first vertex.")
1103 H(" # : add edge v=# ; : increment v (exit if over limit)")
1104 H(" -# : delete edge v=# #: : set v := #")
1105 H(" ? : list nbhs of v . : exit")
1106 H("Syntax for f : f=[2 3|4:9|10] (rest in extra cell at right)")
1107 H(" -f same as f=[], f=# same as f=[#]")
1108 H("Syntax for r : r 2:4 1 5; (rest appended in order)")
1109 H("Syntax for R : R 2:4 1 5; or -R 0 3 6:10;")
1110 H("Arguments for u : 1=node,2=autom,4=level,8=tcell,16=ref (add them)")
1111 H("Accurate times for easy graphs: M=# selects number of times to run.")
1112 }
1113
1114 }
1115
1116 /*****************************************************************************
1117 * *
1118 * usernode(g,lab,ptn,level,numcells,tc,code,m,n) is a simple version of the *
1119 * procedure named by options.usernodeproc. *
1120 * *
1121 *****************************************************************************/
1122
1123 static void
usernode(graph * g,int * lab,int * ptn,int level,int numcells,int tc,int code,int m,int n)1124 usernode(graph *g, int *lab, int *ptn, int level, int numcells,
1125 int tc, int code, int m, int n)
1126 {
1127 register int i;
1128
1129 for (i = 0; i < level; ++i) PUTC('.',OUTFILE);
1130 if (numcells == n)
1131 fprintf(OUTFILE,"(n/%d)\n",code);
1132 else if (tc < 0)
1133 fprintf(OUTFILE,"(%d/%d)\n",numcells,code);
1134 else
1135 fprintf(OUTFILE,"(%d/%d/%d)\n",numcells,code,tc);
1136 if (firstpath) putptn(OUTFILE,lab,ptn,level,options.linelength,n);
1137 if (numcells == n) firstpath = FALSE;
1138 }
1139
1140 /*****************************************************************************
1141 * *
1142 * userautom(count,perm,orbits,numorbits,stabvertex,n) is a simple *
1143 * version of the procedure named by options.userautomproc. *
1144 * *
1145 *****************************************************************************/
1146
1147 static void
userautom(int count,permutation * perm,int * orbits,int numorbits,int stabvertex,int n)1148 userautom(int count, permutation *perm, int *orbits,
1149 int numorbits, int stabvertex, int n)
1150 {
1151 fprintf(OUTFILE,
1152 "**userautomproc: count=%d stabvertex=%d numorbits=%d\n",
1153 count,stabvertex+labelorg,numorbits);
1154 putorbits(OUTFILE,orbits,options.linelength,n);
1155 }
1156
1157 /*****************************************************************************
1158 * *
1159 * userlevel(lab,ptn,level,orbits,stats,tv,index,tcellsize,numcells,cc,n) *
1160 * is a simple version of the procedure named by options.userlevelproc. *
1161 * *
1162 *****************************************************************************/
1163
1164 static void
userlevel(int * lab,int * ptn,int level,int * orbits,statsblk * stats,int tv,int index,int tcellsize,int numcells,int cc,int n)1165 userlevel(int *lab, int *ptn, int level, int *orbits, statsblk *stats,
1166 int tv, int index, int tcellsize, int numcells, int cc, int n)
1167 {
1168 fprintf(OUTFILE,
1169 "**userlevelproc: level=%d tv=%d index=%d tcellsize=%d cc=%d\n",
1170 level,tv+labelorg,index,tcellsize,cc);
1171 fprintf(OUTFILE," nodes=%ld cells=%d orbits=%d generators=%d\n",
1172 stats->numnodes,numcells,stats->numorbits,stats->numgenerators);
1173 }
1174