1 /*****************************************************************************
2 * *
3 * This is the main file for dreadnaut() version 2.7, which is a test-bed *
4 * for nauty() version 2.7 and traces version 2.2. *
5 * *
6 * Subject to the copyright notice in the file COPYRIGHT. *
7 * *
8 * CHANGE HISTORY *
9 * 10-Nov-87 : final changes for version 1.2 *
10 * 5-Dec-87 - replaced all uses of fscanf() by appropriate uses *
11 * of the new procedures readinteger() and readstring() *
12 * - changed the '<' command slightly. If a file of the *
13 * given name cannot be openned, an attempt is made to *
14 * open a file with the same name extended by DEFEXT. *
15 * - improved error processing for 'n' command. *
16 * 28-Sep-88 : changes for version 1.4 : *
17 * - replaced incorrect %d by %ld in fprintf for ? command *
18 * 23-Mar-89 : changes for version 1.5 : *
19 * - added optional startup message *
20 * - enabled use of refine1 in 'i' command *
21 * - implemented $$ command *
22 * - replaced ALLOCS test by DYNALLOC test *
23 * - modified @ command and added # command *
24 * - declared local procedures static *
25 * 25-Mar-89 - implemented k command *
26 * 27-Mar-89 - implemented * and I commands *
27 * 29-Mar-89 - implemented K command *
28 * 2-Apr-89 - added reporting of vertex-invariant statistics *
29 * 2-Apr-89 - added ## command *
30 * 4-Apr-89 - added triples(), quadruples(), adjtriang() *
31 * - updated error reporting for nauty() *
32 * 5-Apr-89 - removed flushline() from g and e commands *
33 * - added T command *
34 * 6-Apr-89 - added cellquads() and distances() *
35 * 26-Apr-89 - modified ? command, added & and && commands *
36 * - added indsets(), cliques(), cellquins() *
37 * 18-Aug-89 - made g, lab, canong dynamically allocated always *
38 * 2-Mar-90 - added celltrips(), cellcliq(), cellind() *
39 * 13-Mar-90 - changed canong and savedg in output to h and h' *
40 * 19-Mar-90 - revised help() a little *
41 * 19-Apr-90 : changes for version 1.6 *
42 * - rewrote "*" command to avoid bug in Pyramid C compiler *
43 * 20-Apr-90 - rewrote above rewrite to avoid bug in SUN3 gcc *
44 * 23-Apr-90 - undid above rewrite and fixed *my* bug <blush> by *
45 * making NUMINVARS have type int. Sorry, gcc. *
46 * 10-Nov-90 - added calls to null routines (see comment on code) *
47 * 27-Aug-92 : renamed to version 1.7, no changes to this file *
48 * 5-Jun-93 : renamed to version 1.7+, no changes to this file *
49 * 18-Aug-93 : renamed to version 1.8, no changes to this file *
50 * 17-Sep-93 : changes for version 1.9 : *
51 * - added invariant adjacencies() *
52 * 7-Jun-96 : changes for version 2.0 : *
53 * - added invariants cellfano() and cellfano2() *
54 * - made y=10 the default *
55 * 11-Jul-96 - added dynamic allocation *
56 * - rewrote h command and added H command *
57 * - implemented M and R commands *
58 * 15-Aug-96 - changed z command to use sethash() *
59 * 30-Aug-96 - no need to declare seed; already in naututil.h *
60 * 12-Sep-96 - let i and I commands use userrefproc *
61 * 9-Dec-96 - made y=infinity the default *
62 * 6-Sep-97 - allocated arrays before accepting commands *
63 * 7-Sep-97 - make g,canong,savedg 1-d arrays even statically *
64 * 22-Sep-97 - undid error introduced on 7-Sep (worksize) *
65 * 9-Jan-00 - used *_check() instead of *_null() *
66 * 12-Feb-00 - minor code formatting *
67 * 17-Aug-00 - now use tc_level from DEFAULTOPTIONS *
68 * 16-Nov-00 - made changes listed in nauty.h *
69 * 22-Apr-01 - include nautyinv.h *
70 * - improve worksize processing for MAXN=0 *
71 * 5-May-01 - k=0 1 automatic for *, also K=3 or K=0 *
72 * 2-Jun-01 - added __ command for digraph converse *
73 * 18-Oct-01 - moved WORKSIZE to here *
74 * 21-Nov-01 - use NAUTYREQUIRED in *_check() calls *
75 * 1-Sep-02 - Undid the previous change *
76 * 17-Nov-03 - Changed INFINITY to NAUTY_INFINITY *
77 * 15-Nov-04 - Completed all prototypes *
78 * 23-Nov-06 - no usertcellproc() any more in version 2.4 *
79 * 10-Nov-09 - removed types shortish and permutation *
80 * 17-Nov-09 - added sparsegraphs, schreier, A and G commands *
81 * 19-Nov-09 - added F command, stub for Traces *
82 * 1-Dec-09 - added traces refinement, M also applies to i *
83 * 16-Dec-09 - added sr# command for random regular graphs *
84 * 19-Dec-09 - added s# command for the sparse case *
85 * - w command is in units of 2*m now *
86 * 19-May-10 - Incorporate traces canonical labelling *
87 * 7-Jun-10 - implement %, _ and __ commands for sparse format *
88 * 8-Jun-10 - add O and P commands, and sparse && command *
89 * 11-Jun-10 - revise command-line parameters *
90 * 14-Jun-10 - digraphs and invariants (top level only) in Traces *
91 * 26-Oct-10 - fix u command for sparse graphs; default G=10 *
92 * 14-Mar-11 - store partition with savedg *
93 * 21-Jul-11 - extend M command *
94 * 24-Oct-11 - add S and OO commands *
95 * 15-Jan-12 - use putorbitsplus() if USE_ANSICONTROLS *
96 * 20-Sep-12 - the first argument of ungetc is int, not char *
97 * 18-Jan-13 - add code for ^C catching in nauty *
98 * - add usercanonproc sample *
99 * - ->> means flush output file *
100 * 14-Nov-14 - fix numcells calculation in 'OO' command *
101 * 16-Mar-15 - add B command *
102 * 16-Dec-15 - add r& command *
103 * 22-Jan-16 - commands with short arguments must be all on one line *
104 * - most errors cause rest of input line to be skipped *
105 * 19-Feb-16 - make R command induce a partition if one is defined *
106 * *
107 *****************************************************************************/
108
109 #include "gtools.h" /* which includes nauty.h, which includes stdio.h */
110 #include "nautinv.h"
111 #include "schreier.h"
112 #include "traces.h"
113
114 #define USAGE "dreadnaut [-o options]"
115
116 #define HELPTEXT \
117 " Enter nauty+traces test program.\n\
118 \n\
119 -o options - set initial options. The parameter value is a string of\n\
120 dreadnaut commands from the following set:\n\
121 a,c,d,m,p,l,G,P,w,y,$,A,V,M\n\
122 The effect is the same as if these commands are entered\n\
123 at the beginning of the standard input.\n\
124 For help within dreadnaut, use the h command.\n"
125
126 #define PM(x) ((x) ? '+' : '-')
127 #define SS(n,sing,plur) (n),((n)==1?(sing):(plur))
128 #define WORKSIZE 60
129 #define FLUSHANDPROMPT do { flushline(INFILE); if (prompt) fprintf(PROMPTFILE,"> "); } while (0)
130
131 #define SORT_OF_SORT 2
132 #define SORT_NAME sort2ints
133 #define SORT_TYPE1 int
134 #define SORT_TYPE2 int
135 #include "sorttemplates.c" /* define sort2ints(a,b,n) */
136
137 #define INFILE fileptr[curfile]
138 #define SCHREIER_DEFAULT 10
139
140 static long seed;
141
142 #if !MAXN
143 DYNALLSTAT(graph,g,g_sz);
144 DYNALLSTAT(graph,canong,canong_sz);
145 DYNALLSTAT(graph,savedg,savedg_sz);
146 DYNALLSTAT(setword,workspace,workspace_sz);
147 DYNALLSTAT(int,lab,lab_sz);
148 DYNALLSTAT(int,ptn,ptn_sz);
149 DYNALLSTAT(int,orbits,orbits_sz);
150 DYNALLSTAT(int,templab,templab_sz);
151 DYNALLSTAT(int,tempptn,tempptn_sz);
152 DYNALLSTAT(int,perm,perm_sz);
153 DYNALLSTAT(int,savedlab,savedlab_sz);
154 DYNALLSTAT(int,savedptn,savedptn_sz);
155 DYNALLSTAT(set,tempactive,tempactive_sz);
156 DYNALLSTAT(set,active,active_sz);
157 #else
158 static graph g[MAXM*1L*MAXN];
159 static graph canong[MAXM*1L*MAXN];
160 static graph savedg[MAXM*1L*MAXN];
161 static setword workspace[MAXM*2L*WORKSIZE];
162 static int lab[MAXN];
163 static int ptn[MAXN];
164 static int orbits[MAXN];
165 static int savedlab[MAXN],savedptn[MAXN];
166 static int perm[MAXN];
167 static int templab[MAXN];
168 static int tempptn[MAXN];
169 static int tempactive[MAXM];
170 static set active[MAXM];
171 #endif
172
173 static sparsegraph g_sg;
174 static sparsegraph canong_sg;
175 static sparsegraph savedg_sg;
176
177 static DEFAULTOPTIONS_GRAPH(options);
178 static DEFAULTOPTIONS_SPARSEGRAPH(options_sg);
179 static statsblk stats;
180 static int curfile;
181 static FILE *fileptr[MAXIFILES];
182 static FILE *outfile;
183 static char def_ext[] = DEFEXT;
184 static boolean firstpath; /* used in usernode() */
185
186 DEFAULTOPTIONS_TRACES(traces_opts);
187 static TracesStats traces_stats;
188
189 #define TMP
190
191 #define DENSE_MODE 0
192 #define SPARSE_MODE 1
193 #define TRACES_MODE 2
194 #define SPARSEREP(mode) ((mode)==1||(mode)==2)
195 #define NOSPARSEYET(c) else if (SPARSEREP(mode)) { fprintf(ERRFILE,\
196 "command %s is not implemented in the sparse case\n",c); }
197 #define NODENSEYET else if (!SPARSEREP(mode)) { fprintf(ERRFILE,\
198 "command %c is not implemented in the dense case\n",c); }
199 #define NOTRACESYET if (mode==TRACES_MODE) { fprintf(ERRFILE,\
200 "command %c is not implemented for Traces\n",c); }
201
202 static int mode;
203
204 #define U_NODE 1 /* masks for u values */
205 #define U_AUTOM 2
206 #define U_LEVEL 4
207 #define U_TCELL 8 /* At version 2.4, usertcellproc() is gone */
208 #define U_REF 16
209 #define U_CANON 32
210
211 #ifndef NODEPROC
212 #define NODEPROC usernode
213 #else
214 extern void NODEPROC(graph*,int*,int*,int,int,int,int,int,int);
215 #endif
216
217 #ifndef AUTOMPROC
218 #define AUTOMPROC userautom
219 #else
220 extern void AUTOMPROC(int,int*,int*,int,int,int);
221 #endif
222
223 #ifndef LEVELPROC
224 #define LEVELPROC userlevel
225 #else
226 extern void LEVELPROC(int*,int*,int,int*,statsblk*,int,int,int,int,int,int);
227 #endif
228
229 #ifndef REFPROC
230 #define REFPROC NULL
231 #else
232 extern void REFPROC(graph*,int*,int*,int,int*,int*,set*,int*,int,int);
233 #endif
234
235 #ifndef CANONPROC
236 #define CANONPROC usercanon
237 #else
238 extern int CANONPROC(graph*,int*,graph*,unsigned long,int,int,int);
239 #endif
240
241 #ifndef INVARPROC
242 #define INVARPROC NULL
243 #define INVARPROCNAME "none"
244 #else
245 extern void INVARPROC(graph*,int*,int*,int,int,int,int*,int,boolean,int,int);
246 #define INVARPROCNAME "user-defined"
247 #endif
248
249 #ifndef INVARPROC_SG
250 #define INVARPROC_SG NULL
251 #define INVARPROCNAME_SG "none"
252 #else
253 extern void INVARPROC_SG(graph*,int*,int*,int,int,int,int*,int,boolean,int,int);
254 #define INVARPROCNAME_SG "user-defined"
255 #endif
256
257 static struct invarrec
258 {
259 void (*entrypoint)(graph*,int*,int*,int,int,int,int*,int,boolean,int,int);
260 char *name;
261 void (*entrypoint_sg)(graph*,int*,int*,int,int,int,int*,int,boolean,int,int);
262 char *name_sg;
263 } invarproc[]
264 = {{INVARPROC, INVARPROCNAME, INVARPROC_SG, INVARPROCNAME_SG},
265 {NULL, "none", NULL, "none"},
266 {twopaths, "twopaths", NULL, "unavailable"},
267 {adjtriang, "adjtriang", NULL, "unavailable"},
268 {triples, "triples", NULL, "unavailable"},
269 {quadruples, "quadruples", NULL, "unavailable"},
270 {celltrips, "celltrips", NULL, "unavailable"},
271 {cellquads, "cellquads", NULL, "unavailable"},
272 {cellquins, "cellquins", NULL, "unavailable"},
273 {distances, "distances", distances_sg, "distances_sg"},
274 {indsets, "indsets", NULL, "unavailable"},
275 {cliques, "cliques", NULL, "unavailable"},
276 {cellcliq, "cellcliq", NULL, "unavailable"},
277 {cellind, "cellind", NULL, "unavailable"},
278 {adjacencies, "adjacencies", adjacencies_sg, "adjacencies_sg"},
279 {cellfano, "cellfano", NULL, "unavailable"},
280 {cellfano2, "cellfano2", NULL, "unavailable"},
281 {refinvar, "refinvar", NULL, "unavailable"}
282 };
283 #define NUMINVARS ((int)(sizeof(invarproc)/sizeof(struct invarrec)))
284
285 static void help(FILE*, int);
286 static void userautom(int,int*,int*,int,int,int);
287 static void usernode(graph*,int*,int*,int,int,int,int,int,int);
288 static void userlevel(int*,int*,int,int*,statsblk*,int,int,int,int,int,int);
289 static int usercanon(graph*,int*,graph*,unsigned long,int,int,int);
290
291 static boolean options_writeautoms,options_writemarkers,
292 options_digraph,options_getcanon,options_linelength;
293 static int options_invarproc,options_mininvarlevel,options_maxinvarlevel,
294 options_invararg,options_tc_level,options_cartesian;
295 static int options_schreier,options_keepgroup,options_verbosity,
296 options_strategy;
297
298 #if USE_ANSICONTROLS && !DREADTEST
299 #define PUTORBITS putorbitsplus
300 #else
301 #define PUTORBITS putorbits
302 #endif
303
304 #ifdef EXTRADECLS
305 EXTRADECLS
306 #endif
307
308 #if !HAVE_SIGACTION
309 #undef ALLOW_INTERRUPT
310 #define ALLOW_INTERRUPT 0
311 #endif
312
313 #if ALLOW_INTERRUPT
314 /*****************************************************************************
315 * *
316 * Routines for catching SIGINT *
317 * *
318 *****************************************************************************/
319
320 void
sigintcatcher(int sig)321 sigintcatcher(int sig)
322 /* This is the routine called on SIGINT receipt. */
323 {
324 struct sigaction ss;
325
326 nauty_kill_request = 1;
327 ss.sa_handler = SIG_DFL;
328 sigemptyset(&ss.sa_mask);
329 ss.sa_flags = 0;
330 sigaction(SIGINT,&ss,0);
331 }
332
333 static void
setsigcatcher(void)334 setsigcatcher(void)
335 {
336 struct sigaction ss;
337
338 nauty_kill_request = 0;
339 ss.sa_handler = sigintcatcher;
340 sigemptyset(&ss.sa_mask);
341 ss.sa_flags = 0;
342 sigaction(SIGINT,&ss,0);
343 }
344
345 static void
unsetsigcatcher(void)346 unsetsigcatcher(void)
347 {
348 struct sigaction ss;
349
350 nauty_kill_request = 0;
351 ss.sa_handler = SIG_DFL;
352 sigemptyset(&ss.sa_mask);
353 ss.sa_flags = 0;
354 sigaction(SIGINT,&ss,0);
355 }
356 #else
357 static void
358 setsigcatcher(void)
359 {
360 }
361
362 static void
363 unsetsigcatcher(void)
364 {
365 }
366 #endif
367
368 /*****************************************************************************
369 * *
370 * This is a program which illustrates the use of nauty. *
371 * Commands are read from stdin, and may be separated by white space, *
372 * commas or not separated. Output is written to stdout. *
373 * For a short description, see the nauty User's Guide. *
374 * *
375 *****************************************************************************/
376
377 int
main(int argc,char * argv[])378 main(int argc, char *argv[])
379 {
380 int m,n,newm,newn;
381 boolean gvalid,ovalid,cvalid,pvalid,minus,prompt,doquot;
382 boolean gvalid_sg,cvalid_sg;
383 int i,j,k,worksize,numcells,savednc,refcode,umask,qinvar;
384 int oldorg,oldmode;
385 int maxsize,cell1,cell2;
386 boolean ranreg,same;
387 char *s1,*s2;
388 int c,d;
389 unsigned long uli;
390 size_t sli;
391 set *gp;
392 double timebefore,timeafter,mintime;
393 char filename[515];
394 int sgn,sgorg,nperm;
395 int multiplicity,actmult;
396 long zseed;
397 permnode *generators;
398 char *ap,*parameters;
399 boolean flushing;
400
401 HELP; PUTVERSION;
402
403 if (argc == 3 && strcmp(argv[1],"-o") == 0)
404 parameters = argv[2];
405 else if (argc != 1)
406 {
407 fprintf(ERRFILE,USAGE);
408 exit(1);
409 }
410 else
411 parameters = "";
412
413 mode = DENSE_MODE;
414 curfile = 0;
415 fileptr[curfile] = stdin;
416 #ifdef DREADTEST
417 prompt = FALSE;
418 #else
419 prompt = DOPROMPT(INFILE);
420 #endif
421 outfile = stdout;
422 options_writeautoms = options_writemarkers = TRUE;
423 options_digraph = FALSE;
424 options_getcanon = options.getcanon;
425 options_mininvarlevel = options.mininvarlevel;
426 options_maxinvarlevel = options.maxinvarlevel;
427 options_invararg = options.invararg;
428 options_invarproc = 1; /* index into invarproc[] */
429 options_tc_level = options.tc_level;
430 options_cartesian = options.cartesian;
431 options_linelength = options.linelength;
432 options_schreier = SCHREIER_DEFAULT;
433 options_keepgroup = FALSE;
434 generators = NULL;
435 options_verbosity = 1;
436 options_strategy = 0;
437
438 n = m = 1;
439 worksize = WORKSIZE;
440
441 #if !MAXN
442 n = WORDSIZE;
443 DYNALLOC2(graph,g,g_sz,n,m,"dreadnaut");
444 DYNALLOC1(int,lab,lab_sz,n,"dreadnaut");
445 DYNALLOC1(int,ptn,ptn_sz,n,"dreadnaut");
446 DYNALLOC1(int,orbits,orbits_sz,n,"dreadnaut");
447 DYNALLOC1(int,perm,perm_sz,n,"dreadnaut");
448 DYNALLOC1(set,active,active_sz,m,"dreadnaut");
449 n = 1;
450 #endif
451
452 #ifdef DREADTEST
453 seed = 1;
454 ran_init(seed);
455 #else
456 #ifdef INITSEED
457 INITSEED;
458 ran_init(seed);
459 #endif
460 #endif
461
462 umask = 0;
463 pvalid = FALSE;
464 ovalid = FALSE;
465 gvalid = gvalid_sg = FALSE; /* at most one valid */
466 cvalid = cvalid_sg = FALSE; /* at most one valid */
467 sgorg = labelorg = oldorg = 0;
468 sgn = 0;
469 multiplicity = 1;
470 mintime = 0.0;
471 flushing = FALSE;
472
473 #ifdef INITIALIZE
474 INITIALIZE;
475 #endif
476
477 if (prompt)
478 {
479 fprintf(PROMPTFILE,"Dreadnaut version %s.\n",NAUTYVERSION);
480 fprintf(PROMPTFILE,"> ");
481 }
482
483 nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);
484 nautinv_check(WORDSIZE,1,1,NAUTYVERSIONID);
485 nautil_check(WORDSIZE,1,1,NAUTYVERSIONID);
486 naututil_check(WORDSIZE,1,1,NAUTYVERSIONID);
487 nausparse_check(WORDSIZE,1,1,NAUTYVERSIONID);
488
489 SG_INIT(g_sg);
490 SG_INIT(canong_sg);
491 SG_INIT(savedg_sg);
492
493 minus = FALSE;
494 for (ap = parameters; *ap != '\0'; )
495 {
496 c = *ap++;
497
498 switch (c)
499 {
500 case ' ':
501 case '\t':
502 break;
503
504 case '-':
505 minus = TRUE;
506 break;
507
508 case '+':
509 minus = FALSE;
510 break;
511
512 case 'a':
513 options_writeautoms = !minus;
514 minus = FALSE;
515 break;
516
517 case 'c':
518 options_getcanon = !minus;
519 minus = FALSE;
520 break;
521
522 case 'm':
523 options_writemarkers = !minus;
524 minus = FALSE;
525 break;
526
527 case 'p':
528 options_cartesian = !minus;
529 minus = FALSE;
530 break;
531
532 case 'B':
533 flushing = !minus;
534 minus = FALSE;
535 break;
536
537 case 'd':
538 options_digraph = !minus;
539 minus = FALSE;
540 break;
541
542 case 'P':
543 options_keepgroup = !minus;
544 minus = FALSE;
545 break;
546
547 case 'w':
548 while (*ap == '=' || *ap == ' ') ++ap;
549 arg_int(&ap,&worksize,"w");
550 #if MAXN
551 if (worksize > 2*MAXM*WORKSIZE)
552 {
553 fprintf(ERRFILE,
554 "too big - setting worksize = %d\n",WORKSIZE);
555 worksize = WORKSIZE;
556 }
557 #endif
558 minus = FALSE;
559 break;
560
561 case 'V':
562 if (minus)
563 {
564 options_verbosity = 0;
565 minus = FALSE;
566 }
567 else
568 {
569 while (*ap == '=' || *ap == ' ') ++ap;
570 arg_int(&ap,&i,"V");
571 if (i < 0) fprintf(ERRFILE,"verbosity must be >= 0\n");
572 else options_verbosity = i;
573 }
574 break;
575
576
577 case 'S':
578 if (minus)
579 {
580 options_strategy = 0;
581 minus = FALSE;
582 }
583 else
584 {
585 while (*ap == '=' || *ap == ' ') ++ap;
586 arg_int(&ap,&i,"S");
587 /*
588 if (i < 0) fprintf(ERRFILE,"strategy must be >= 0\n");
589 else options_strategy = i;
590 */
591 if (i != 0) fprintf(ERRFILE,
592 "Only strategy 0 is supported in this version\n");
593 }
594 break;
595
596 case 'G':
597 if (minus)
598 {
599 options_schreier = 0;
600 minus = FALSE;
601 }
602 else
603 {
604 while (*ap == '=' || *ap == ' ') ++ap;
605 arg_int(&ap,&i,"G");
606 if (i < 0)
607 fprintf(ERRFILE,"schreierfails must be >= 0\n");
608 else
609 {
610 options_schreier = i;
611 if (i > 0) schreier_fails(i);
612 }
613 }
614 break;
615
616 case 'y':
617 while (*ap == '=' || *ap == ' ') ++ap;
618 arg_int(&ap,&options_tc_level,"y");
619 minus = FALSE;
620 break;
621
622 case '$':
623 while (*ap == '=' || *ap == ' ') ++ap;
624 arg_int(&ap,&labelorg,"$");
625 minus = FALSE;
626 break;
627
628 case 'M':
629 if (minus)
630 {
631 multiplicity = 1;
632 mintime = 0.0;
633 minus = FALSE;
634 }
635 else
636 {
637 actmult = 0;
638 while (*ap == '=' || *ap == ' ') ++ap;
639 arg_int(&ap,&multiplicity,"M");
640 if (*ap == '/')
641 {
642 ++ap;
643 arg_int(&ap,&actmult,"M/");
644 }
645 if (multiplicity < 0) multiplicity = 0;
646 if (actmult < 0) actmult = 0;
647 if (multiplicity == 0 && actmult == 0) multiplicity = 1;
648 mintime = (double)actmult;
649 }
650 break;
651
652 case 'l':
653 while (*ap == '=' || *ap == ' ') ++ap;
654 arg_int(&ap,&options_linelength,"l");
655 minus = FALSE;
656 break;
657
658 case 'A':
659 d = *ap++;
660 if (d == 'n' || d == 'N' || d == 'd' || d == 'D')
661 mode = DENSE_MODE;
662 else if (d == 's' || d == 'S') mode = SPARSE_MODE;
663 else if (d == 't' || d == 'T') mode = TRACES_MODE;
664 else
665 {
666 fprintf(ERRFILE,"Mode %c is unknown\n",(d?d:'0'));
667 break;
668 }
669 minus = FALSE;
670 break;
671
672 default:
673 fprintf(ERRFILE,"Illegal initialization command %c\n",c);
674 exit(1);
675 }
676 }
677
678 minus = FALSE;
679 while (curfile >= 0)
680 {
681 if ((c = getc(INFILE)) == EOF || c == '\004')
682 {
683 fclose(INFILE);
684 --curfile;
685 if (curfile >= 0) prompt = DOPROMPT(INFILE);
686 }
687 else switch (c)
688 {
689 case '\n': /* possibly issue prompt */
690 if (prompt) fprintf(PROMPTFILE,"> ");
691 minus = FALSE;
692 break;
693
694 case ' ': /* do nothing */
695 case '\t':
696 #ifndef NLMAP
697 case '\r':
698 #endif
699 case '\f':
700 break;
701
702 case '-': /* remember this for next time */
703 minus = TRUE;
704 break;
705
706 case '+': /* forget - */
707 case ',':
708 case ';':
709 minus = FALSE;
710 break;
711
712 case '<': /* new input file */
713 minus = FALSE;
714 if (curfile == MAXIFILES - 1)
715 {
716 fprintf(ERRFILE,"exceeded maximum input nesting of %d\n",
717 MAXIFILES);
718 FLUSHANDPROMPT;
719 break;
720 }
721 if (!readstring(INFILE,filename,513))
722 {
723 fprintf(ERRFILE,
724 "missing file name on '<' command : ignored\n");
725 break;
726 }
727 if ((fileptr[curfile+1] = fopen(filename,"r")) == NULL)
728 {
729 for (s1 = filename; *s1 != '\0'; ++s1) {}
730 for (s2 = def_ext; (*s1 = *s2) != '\0'; ++s1, ++s2) {}
731 fileptr[curfile+1] = fopen(filename,"r");
732 }
733 if (fileptr[curfile+1] != NULL)
734 {
735 ++curfile;
736 prompt = DOPROMPT(INFILE);
737 if (prompt)
738 fprintf(PROMPTFILE,"> ");
739 }
740 else
741 {
742 fprintf(ERRFILE,"can't open input file\n");
743 FLUSHANDPROMPT;
744 }
745 break;
746
747 case '>': /* new output file, or flush output file */
748 if ((d = getc(INFILE)) != '>') ungetc(d,INFILE);
749 if (minus)
750 {
751 minus = FALSE;
752 if (d == '>')
753 fflush(outfile);
754 else if (outfile != stdout)
755 {
756 fclose(outfile);
757 outfile = stdout;
758 }
759 }
760 else
761 {
762 if (!readstring(INFILE,filename,513))
763 {
764 fprintf(ERRFILE,
765 "improper file name, reverting to stdout\n");
766 outfile = stdout;
767 FLUSHANDPROMPT;
768 break;
769 }
770 OPENOUT(outfile,filename,d=='>');
771 if (outfile == NULL)
772 {
773 fprintf(ERRFILE,
774 "can't open output file, reverting to stdout\n");
775 outfile = stdout;
776 FLUSHANDPROMPT;
777 }
778 }
779 break;
780
781 case 'B':
782 flushing = !minus;
783 minus = FALSE;
784 break;
785
786 case '!': /* ignore rest of line */
787 do
788 c = getc(INFILE);
789 while (c != '\n' && c != EOF);
790 if (c == '\n') ungetc('\n',INFILE);
791 break;
792
793 case 'n': /* read n value */
794 minus = FALSE;
795 i = getint_sl(INFILE);
796 if (i <= 0 || (MAXN && i > MAXN)
797 || (!MAXN && i > NAUTY_INFINITY-2))
798 {
799 fprintf(ERRFILE,
800 " n can't be less than 1 or more than %d\n",
801 MAXN ? MAXN : NAUTY_INFINITY-2);
802 FLUSHANDPROMPT;
803 }
804 else
805 {
806 gvalid = FALSE;
807 cvalid = FALSE;
808 gvalid_sg = FALSE;
809 cvalid_sg = FALSE;
810 pvalid = FALSE;
811 ovalid = FALSE;
812 n = i;
813 m = SETWORDSNEEDED(n);
814 freeschreier(NULL,&generators);
815 #if !MAXN
816 DYNALLOC1(int,lab,lab_sz,n,"dreadnaut");
817 DYNALLOC1(int,ptn,ptn_sz,n,"dreadnaut");
818 DYNALLOC1(int,orbits,orbits_sz,n,"dreadnaut");
819 DYNALLOC1(int,perm,perm_sz,n,"dreadnaut");
820 DYNALLOC1(set,active,active_sz,m,"dreadnaut");
821 #endif
822 }
823 break;
824
825 case 'g': /* read graph */
826 minus = FALSE;
827 if (SPARSEREP(mode))
828 {
829 readgraph_sg(INFILE,&g_sg,options_digraph,prompt,
830 options_linelength,n);
831 gvalid_sg = TRUE;
832 cvalid_sg = FALSE;
833 }
834 else
835 {
836 #if !MAXN
837 DYNALLOC2(graph,g,g_sz,n,m,"dreadnaut");
838 #endif
839 readgraph(INFILE,g,options_digraph,prompt,FALSE,
840 options_linelength,m,n);
841 gvalid = TRUE;
842 cvalid = FALSE;
843 }
844 ovalid = FALSE;
845 break;
846
847 case 'e': /* edit graph */
848 minus = FALSE;
849 if (SPARSEREP(mode))
850 {
851 fprintf(ERRFILE,"e command only works in dense mode\n");
852 FLUSHANDPROMPT;
853 }
854 else
855 {
856 readgraph(INFILE,g,options_digraph,prompt,gvalid,
857 options_linelength,m,n);
858 gvalid = TRUE;
859 cvalid = FALSE;
860 ovalid = FALSE;
861 }
862 break;
863
864 case 'r': /* relabel graph and current partition */
865 minus = FALSE;
866 if ((d = getc(INFILE)) != '&') ungetc(d,INFILE);
867 if (gvalid_sg)
868 {
869 if (d == '&')
870 {
871 if (pvalid)
872 relabel_sg(&g_sg,lab,lab,&canong_sg);
873 }
874 else
875 {
876 readvperm(INFILE,perm,prompt,n,&nperm);
877 relabel_sg(&g_sg,(pvalid ? lab : NULL),perm,&canong_sg);
878 }
879 cvalid_sg = FALSE;
880 ovalid = FALSE;
881 }
882 else if (gvalid)
883 {
884 if (d == '&')
885 {
886 if (pvalid)
887 {
888 #if !MAXN
889 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
890 #endif
891 relabel(g,lab,lab,canong,m,n);
892 }
893 }
894 else
895 {
896 #if !MAXN
897 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
898 #endif
899 readvperm(INFILE,perm,prompt,n,&nperm);
900 relabel(g,(pvalid ? lab : NULL),perm,canong,m,n);
901 }
902 cvalid = FALSE;
903 ovalid = FALSE;
904 }
905 else
906 {
907 fprintf(ERRFILE,"g is not defined\n");
908 FLUSHANDPROMPT;
909 }
910 break;
911
912 case 'R': /* form subgraph */
913 if (gvalid)
914 {
915 #if !MAXN
916 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
917 #endif
918 readvperm(INFILE,perm,prompt,n,&nperm);
919 if ((minus && nperm == n) || (!minus && nperm == 0))
920 {
921 fprintf(ERRFILE,"can't form null graph\n");
922 FLUSHANDPROMPT;
923 }
924 else if (minus)
925 {
926 sublabel(g,perm+nperm,n-nperm,canong,m,n);
927 if (pvalid) numcells = subpartition(lab,ptn,n,perm+nperm,n-nperm);
928 n = n - nperm;
929 }
930 else
931 {
932 sublabel(g,perm,nperm,canong,m,n);
933 if (pvalid) numcells = subpartition(lab,ptn,n,perm,nperm);
934 n = nperm;
935 }
936 cvalid = FALSE;
937 ovalid = FALSE;
938 m = SETWORDSNEEDED(n);
939 }
940 else if (gvalid_sg)
941 {
942 readvperm(INFILE,perm,prompt,n,&nperm);
943 if ((minus && nperm == n) || (!minus && nperm == 0))
944 {
945 fprintf(ERRFILE,"can't form null graph\n");
946 FLUSHANDPROMPT;
947 }
948 else if (minus)
949 {
950 sublabel_sg(&g_sg,perm+nperm,n-nperm,&canong_sg);
951 if (pvalid) numcells = subpartition(lab,ptn,n,perm+nperm,n-nperm);
952 n = n - nperm;
953 }
954 else
955 {
956 sublabel_sg(&g_sg,perm,nperm,&canong_sg);
957 if (pvalid) numcells = subpartition(lab,ptn,n,perm,nperm);
958 n = nperm;
959 }
960 cvalid_sg = FALSE;
961 ovalid = FALSE;
962 m = SETWORDSNEEDED(n);
963 }
964 else
965 {
966 fprintf(ERRFILE,"g is not defined\n");
967 FLUSHANDPROMPT;
968 }
969 minus = FALSE;
970 break;
971
972 case '_': /* complement graph or converse digraph */
973 minus = FALSE;
974 if ((d = getc(INFILE)) != '_') ungetc(d,INFILE);
975
976 if (!gvalid && !gvalid_sg)
977 {
978 fprintf(ERRFILE,"g is not defined\n");
979 FLUSHANDPROMPT;
980 }
981 else if (gvalid)
982 {
983 if (d == '_') converse(g,m,n);
984 else complement(g,m,n);
985 cvalid = FALSE;
986 }
987 else
988 {
989 if (d == '_')
990 {
991 copy_sg(&g_sg,&canong_sg);
992 converse_sg(&canong_sg,&g_sg);
993 cvalid_sg = FALSE;
994 }
995 else
996 {
997 copy_sg(&g_sg,&canong_sg);
998 complement_sg(&canong_sg,&g_sg);
999 cvalid_sg = FALSE;
1000 }
1001 }
1002 break;
1003
1004 case '@': /* copy canong into savedg */
1005 minus = FALSE;
1006 if (cvalid)
1007 {
1008 #if !MAXN
1009 DYNALLOC2(graph,savedg,savedg_sz,n,m,"dreadnaut");
1010 DYNALLOC1(int,savedlab,savedlab_sz,n,"dreadnaut");
1011 DYNALLOC1(int,savedptn,savedptn_sz,n,"dreadnaut");
1012 #endif
1013 sgn = n;
1014 memcpy(savedg,canong,m*(size_t)n*sizeof(setword));
1015 for (i = n; --i >= 0;)
1016 {
1017 savedlab[i] = lab[i];
1018 savedptn[i] = ptn[i];
1019 }
1020 sgorg = labelorg;
1021 }
1022 else if (cvalid_sg)
1023 {
1024 #if !MAXN
1025 DYNALLOC1(int,savedlab,savedlab_sz,n,"dreadnaut");
1026 DYNALLOC1(int,savedptn,savedptn_sz,n,"dreadnaut");
1027 #endif
1028 sgn = n;
1029 copy_sg(&canong_sg,&savedg_sg);
1030 for (i = n; --i >= 0;)
1031 {
1032 savedlab[i] = lab[i];
1033 savedptn[i] = ptn[i];
1034 }
1035 sgorg = labelorg;
1036 }
1037 else
1038 {
1039 fprintf(ERRFILE,"h is not defined\n");
1040 FLUSHANDPROMPT;
1041 }
1042 break;
1043
1044 case '#': /* compare canong to savedg */
1045 if ((d = getc(INFILE)) != '#') ungetc(d,INFILE);
1046
1047 if (cvalid || cvalid_sg)
1048 {
1049 if (sgn > 0)
1050 {
1051 if (sgn != n)
1052 fprintf(outfile,
1053 "h and h' have different sizes.\n");
1054 else
1055 {
1056 if (cvalid)
1057 {
1058 for (sli = 0; sli < m*(size_t)n; ++sli)
1059 if (savedg[sli] != canong[sli]) break;
1060 same = (sli == m*(size_t)n);
1061 }
1062 else
1063 same = aresame_sg(&canong_sg,&savedg_sg);
1064
1065 if (!same)
1066 fprintf(outfile,"h and h' are different.\n");
1067 else
1068 {
1069 for (i = 0; i < n; ++i)
1070 if ((ptn[i] == 0) != (savedptn[i] == 0))
1071 break;
1072 if (i < n)
1073 fprintf(outfile,
1074 "h and h' are identical but have incompatible colourings.\n");
1075 else
1076 fprintf(outfile,
1077 "h and h' are identical.\n");
1078 if (d == '#')
1079 putmapping(outfile,savedlab,sgorg,
1080 lab,labelorg,options_linelength,n);
1081 }
1082 }
1083 }
1084 else
1085 {
1086 fprintf(ERRFILE,"h' is not defined\n");
1087 FLUSHANDPROMPT;
1088 }
1089 }
1090 else
1091 {
1092 fprintf(ERRFILE,"h is not defined\n");
1093 FLUSHANDPROMPT;
1094 }
1095 break;
1096
1097 case 'j': /* relabel graph randomly */
1098 minus = FALSE;
1099 if (gvalid)
1100 {
1101 ranperm(perm,n);
1102 #if !MAXN
1103 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
1104 #endif
1105 relabel(g,(pvalid?lab:NULL),perm,canong,m,n);
1106 cvalid = FALSE;
1107 ovalid = FALSE;
1108 freeschreier(NULL,&generators);
1109 }
1110 else if (gvalid_sg)
1111 {
1112 ranperm(perm,n);
1113 relabel_sg(&g_sg,(pvalid?lab:NULL),perm,&canong_sg);
1114 cvalid_sg = FALSE;
1115 ovalid = FALSE;
1116 freeschreier(NULL,&generators);
1117 }
1118 else
1119 {
1120 fprintf(ERRFILE,"g is not defined\n");
1121 FLUSHANDPROMPT;
1122 }
1123 break;
1124
1125 case 'v': /* write vertex degrees */
1126 minus = FALSE;
1127 if ((d = getc(INFILE)) != 'v') ungetc(d,INFILE);
1128
1129 if (gvalid)
1130 {
1131 if (d == 'v') putdegseq(outfile,g,options_linelength,m,n);
1132 else putdegs(outfile,g,options_linelength,m,n);
1133 }
1134 else if (gvalid_sg)
1135 {
1136 if (d == 'v') putdegseq_sg(outfile,&g_sg,options_linelength);
1137 else putdegs_sg(outfile,&g_sg,options_linelength);
1138 }
1139 else
1140 {
1141 fprintf(ERRFILE,"g is not defined\n");
1142 FLUSHANDPROMPT;
1143 }
1144 break;
1145
1146 case '%': /* do Mathon doubling operation */
1147 minus = FALSE;
1148 if (gvalid || gvalid_sg)
1149 {
1150 #if !MAXN
1151 if (2L * ((long)n + 1L) > NAUTY_INFINITY-2)
1152 {
1153 fprintf(ERRFILE,
1154 "n can't be more than %d\n",NAUTY_INFINITY-2);
1155 break;
1156 }
1157 #else
1158 if (2L * ((long)n + 1L) > MAXN)
1159 {
1160 fprintf(ERRFILE,"n can't be more than %d\n",MAXN);
1161 FLUSHANDPROMPT;
1162 break;
1163 }
1164 #endif
1165 newn = 2 * (n + 1);
1166 newm = SETWORDSNEEDED(newn);
1167 #if !MAXN
1168 DYNALLOC1(int,lab,lab_sz,newn,"dreadnaut");
1169 DYNALLOC1(int,ptn,ptn_sz,newn,"dreadnaut");
1170 DYNALLOC1(int,orbits,orbits_sz,newn,"dreadnaut");
1171 DYNALLOC1(int,perm,perm_sz,newn,"dreadnaut");
1172 DYNALLOC1(set,active,active_sz,newm,"dreadnaut");
1173 #endif
1174 ovalid = FALSE;
1175 pvalid = FALSE;
1176 freeschreier(NULL,&generators);
1177 }
1178 else
1179 {
1180 fprintf(ERRFILE,"g is not defined\n");
1181 FLUSHANDPROMPT;
1182 }
1183
1184 if (gvalid)
1185 {
1186 #if !MAXN
1187 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
1188 #endif
1189 memcpy(canong,g,m*(size_t)n*sizeof(setword));
1190
1191 #if !MAXN
1192 DYNALLOC2(graph,g,g_sz,newn,newm,"dreadnaut");
1193 #endif
1194 mathon(canong,m,n,g,newm,newn);
1195 m = newm;
1196 n = newn;
1197 cvalid = FALSE;
1198 }
1199 else if (gvalid_sg)
1200 {
1201 copy_sg(&g_sg,&canong_sg);
1202 mathon_sg(&canong_sg,&g_sg);
1203 m = newm;
1204 n = newn;
1205 cvalid_sg = FALSE;
1206 }
1207 break;
1208
1209 case 's': /* generate random graph */
1210 minus = FALSE;
1211 d = getc(INFILE);
1212 if (d == 'r')
1213 ranreg = TRUE;
1214 else
1215 {
1216 ranreg = FALSE;
1217 if (d != EOF) ungetc(d,INFILE);
1218 }
1219
1220 i = getint_sl(INFILE);
1221 if (ranreg)
1222 {
1223 if (i < 0) i = 3;
1224 if (i > MAXREG)
1225 {
1226 fprintf(ERRFILE,"sr is limited to degree %d\n",MAXREG);
1227 FLUSHANDPROMPT;
1228 break;
1229 }
1230 if (SPARSEREP(mode))
1231 {
1232 ranreg_sg(&g_sg,i,n);
1233 gvalid_sg = TRUE;
1234 cvalid = FALSE;
1235 ovalid = FALSE;
1236 freeschreier(NULL,&generators);
1237 }
1238 NODENSEYET
1239 }
1240 else
1241 {
1242 if (i <= 0) i = 2;
1243 if (!SPARSEREP(mode))
1244 {
1245 #if !MAXN
1246 DYNALLOC2(graph,g,g_sz,n,m,"dreadnaut");
1247 #endif
1248 rangraph(g,options_digraph,i,m,n);
1249 gvalid = TRUE;
1250 cvalid = FALSE;
1251 ovalid = FALSE;
1252 freeschreier(NULL,&generators);
1253 }
1254 else
1255 {
1256 rangraph2_sg(&g_sg,options_digraph,1,i,n);
1257 gvalid_sg = TRUE;
1258 cvalid = FALSE;
1259 ovalid = FALSE;
1260 freeschreier(NULL,&generators);
1261 }
1262 }
1263 break;
1264
1265 case 'q': /* quit */
1266 EXIT;
1267 break;
1268
1269 case '"': /* copy comment to output */
1270 minus = FALSE;
1271 copycomment(INFILE,outfile,'"');
1272 break;
1273
1274 case 'I': /* do refinement and invariants procedure */
1275 minus = FALSE;
1276 if (!gvalid && !gvalid_sg)
1277 {
1278 fprintf(ERRFILE,"g is not valid\n");
1279 FLUSHANDPROMPT;
1280 break;
1281 }
1282 if (!pvalid) unitptn(lab,ptn,&numcells,n);
1283 cellstarts(ptn,0,active,m,n);
1284 #ifdef CPUTIME
1285 timebefore = CPUTIME;
1286 #endif
1287 if (gvalid)
1288 {
1289 doref(g,lab,ptn,0,&numcells,&qinvar,perm,active,&refcode,
1290 options.userrefproc ? options.userrefproc :
1291 (m == 1 ? refine1 : refine),
1292 invarproc[options_invarproc].entrypoint,0,0,
1293 options_invararg,options_digraph,m,n);
1294 if (numcells > 1) pvalid = TRUE;
1295 }
1296 else if (gvalid_sg)
1297 {
1298 doref((graph*)&g_sg,lab,ptn,0,&numcells,&qinvar,perm,
1299 active,&refcode,
1300 options_sg.userrefproc ? options_sg.userrefproc :
1301 refine_sg,
1302 invarproc[options_invarproc].entrypoint_sg,0,0,
1303 options_invararg,options_digraph,m,n);
1304 if (numcells > 1) pvalid = TRUE;
1305 }
1306 else
1307 {
1308 fprintf(ERRFILE,"g is not valid\n");
1309 FLUSHANDPROMPT;
1310 break;
1311 }
1312 #ifdef CPUTIME
1313 timeafter = CPUTIME;
1314 #endif
1315 fprintf(outfile," %d cell%s; code = %x",
1316 SS(numcells,"","s"),refcode);
1317 if (mode == SPARSE_MODE)
1318 {
1319 if (invarproc[options_invarproc].entrypoint_sg)
1320 fprintf(outfile,
1321 " (%s %s)",invarproc[options_invarproc].name_sg,
1322 (qinvar == 2 ? "worked" : "failed"));
1323 }
1324 else if (mode == DENSE_MODE)
1325 {
1326 if (invarproc[options_invarproc].entrypoint)
1327 fprintf(outfile,
1328 " (%s %s)",invarproc[options_invarproc].name,
1329 (qinvar == 2 ? "worked" : "failed"));
1330 }
1331 #ifdef CPUTIME
1332 fprintf(outfile,"; cpu time = %.2f seconds\n",
1333 timeafter-timebefore);
1334 #else
1335 fprintf(outfile,"\n");
1336 #endif
1337 if (numcells > 1) pvalid = TRUE;
1338 break;
1339
1340 case 'i': /* do refinement */
1341 minus = FALSE;
1342 if (!gvalid && !gvalid_sg)
1343 {
1344 fprintf(ERRFILE,"g is not valid\n");
1345 FLUSHANDPROMPT;
1346 break;
1347 }
1348 if (!pvalid) unitptn(lab,ptn,&numcells,n);
1349 cellstarts(ptn,0,active,m,n);
1350
1351 if (multiplicity != 0 || mintime != 0.0)
1352 {
1353 savednc = numcells;
1354 #if !MAXN
1355 DYNALLOC1(int,tempptn,tempptn_sz,n,"dreadnaut");
1356 DYNALLOC1(int,templab,templab_sz,n,"dreadnaut");
1357 DYNALLOC1(set,tempactive,tempactive_sz,m,"dreadnaut");
1358 #endif
1359 memcpy(templab,lab,n*sizeof(int));
1360 memcpy(tempptn,ptn,n*sizeof(int));
1361 for (i = 0; i < m; ++i) tempactive[i] = active[i];
1362 }
1363
1364 #ifdef CPUTIME
1365 timebefore = CPUTIME;
1366 #endif
1367 actmult = 0;
1368 for (;;)
1369 {
1370 if (actmult > 0)
1371 {
1372 memcpy(lab,templab,n*sizeof(int));
1373 memcpy(ptn,tempptn,n*sizeof(int));
1374 for (i = 0; i < m; ++i) active[i] = tempactive[i];
1375 numcells = savednc;
1376 }
1377
1378 if (options.userrefproc)
1379 (*options.userrefproc)
1380 (g,lab,ptn,0,&numcells,perm,active,&refcode,m,n);
1381 else if (gvalid)
1382 {
1383 if (m == 1)
1384 refine1(g,lab,ptn,0,&numcells,perm,active,&refcode,m,n);
1385 else
1386 refine(g,lab,ptn,0,&numcells,perm,active,&refcode,m,n);
1387 }
1388 else if (mode == SPARSE_MODE)
1389 refine_sg((graph*)&g_sg,lab,ptn,0,&numcells,perm,active,
1390 &refcode,m,n);
1391 else /* traces mode */
1392 refine_tr(&g_sg,lab,ptn,&numcells,&refcode,&traces_opts);
1393
1394 ++actmult;
1395 if (multiplicity > 0 && actmult >= multiplicity) break;
1396 #ifdef CPUTIME
1397 if (mintime > 0.0 && (actmult < 20 || !(actmult&7))
1398 && CPUTIME >= timebefore+mintime)
1399 break;
1400 #endif
1401 }
1402 #ifdef CPUTIME
1403 timeafter = CPUTIME;
1404 #endif
1405 if (numcells > 1) pvalid = TRUE;
1406 fprintf(outfile," %d cell%s; code = %x",
1407 SS(numcells,"","s"),refcode);
1408 #ifdef CPUTIME
1409 fprintf(outfile,"; cpu time = %.7f seconds\n",
1410 (timeafter-timebefore)/actmult);
1411 #else
1412 fprintf(outfile,"\n");
1413 #endif
1414 break;
1415
1416 case 'x': /* execute nauty */
1417 minus = FALSE;
1418 if (mode == TRACES_MODE)
1419 {
1420 ovalid = FALSE;
1421 cvalid_sg = FALSE;
1422 if (!gvalid_sg)
1423 {
1424 fprintf(ERRFILE,"g is not defined\n");
1425 FLUSHANDPROMPT;
1426 break;
1427 }
1428
1429 traces_opts.getcanon = options_getcanon;
1430 traces_opts.writeautoms = options_writeautoms;
1431 traces_opts.cartesian = options_cartesian;
1432 traces_opts.linelength = options_linelength;
1433 traces_opts.digraph = options_digraph;
1434 traces_opts.outfile = outfile;
1435 traces_opts.verbosity = options_verbosity;
1436 traces_opts.strategy = options_strategy;
1437 if (options_keepgroup)
1438 traces_opts.generators = &generators;
1439 else
1440 traces_opts.generators = NULL;
1441
1442 #if !MAXN
1443 DYNALLOC1(int,tempptn,tempptn_sz,n,"dreadnaut");
1444 #endif
1445 if (!pvalid) unitptn(lab,ptn,&numcells,n);
1446 memcpy(tempptn,ptn,n*sizeof(int));
1447 savednc = numcells;
1448 if (options_invarproc != 1 && options_maxinvarlevel > 0)
1449 {
1450 if (options_maxinvarlevel > 1) fprintf(ERRFILE,
1451 "Warning: Traces only uses invariants at the top level\n");
1452 if (invarproc[options_invarproc].entrypoint_sg)
1453 {
1454 #ifdef CPUTIME
1455 timebefore = CPUTIME;
1456 #endif
1457 cellstarts(tempptn,0,active,m,n);
1458 doref((graph*)&g_sg,lab,tempptn,0,&savednc,&qinvar,perm,
1459 active,&refcode,
1460 options_sg.userrefproc ? options_sg.userrefproc :
1461 refine_sg,
1462 invarproc[options_invarproc].entrypoint_sg,0,0,
1463 options_invararg,options_digraph,m,n);
1464 fprintf(outfile,"Invariant %s %s; %d cell%s",
1465 invarproc[options_invarproc].name_sg,
1466 (qinvar == 2 ? "worked" : "failed"),
1467 SS(savednc,"","s"));
1468 #ifdef CPUTIME
1469 timeafter = CPUTIME;
1470 fprintf(outfile,"; cpu time = %.2f seconds\n",
1471 timeafter-timebefore);
1472 #else
1473 fprintf(outfile,"\n");
1474 #endif
1475 }
1476 }
1477
1478 #ifdef CPUTIME
1479 timebefore = CPUTIME;
1480 #endif
1481 actmult = 0;
1482 setsigcatcher();
1483 for (;;)
1484 {
1485 traces_opts.defaultptn = !pvalid;
1486 Traces(&g_sg,lab,tempptn,orbits,&traces_opts,&traces_stats,
1487 &canong_sg);
1488 if (traces_stats.errstatus) break;
1489 traces_opts.writeautoms = FALSE;
1490 traces_opts.verbosity = 0;
1491 ++actmult;
1492 if (multiplicity > 0 && actmult >= multiplicity) break;
1493 #ifdef CPUTIME
1494 if (mintime > 0.0 && (actmult < 20 || !(actmult&7))
1495 && CPUTIME >= timebefore+mintime)
1496 break;
1497 #endif
1498 }
1499 unsetsigcatcher();
1500 #ifdef CPUTIME
1501 timeafter = CPUTIME;
1502 #endif
1503 if (traces_stats.errstatus)
1504 {
1505 if (traces_stats.errstatus == NAUABORTED)
1506 fprintf(ERRFILE,"Traces aborted\n");
1507 else if (traces_stats.errstatus == NAUKILLED)
1508 fprintf(ERRFILE,"Traces interrupted\n");
1509 else
1510 fprintf(ERRFILE,
1511 "Traces returned error status %d [this can't happen]\n",
1512 traces_stats.errstatus);
1513 cvalid = cvalid_sg = ovalid = FALSE;
1514 }
1515 else
1516 {
1517 fprintf(outfile,"%d orbit%s",
1518 SS(traces_stats.numorbits,"","s"));
1519 fprintf(outfile,"; grpsize=");
1520 writegroupsize(outfile,
1521 traces_stats.grpsize1,traces_stats.grpsize2);
1522 fprintf(outfile,"; %d gen%s",
1523 SS(traces_stats.numgenerators,"","s"));
1524 fprintf(outfile,
1525 "; %lu node%s ", SS(traces_stats.numnodes,"","s"));
1526 if (traces_stats.interrupted)
1527 fprintf(outfile,
1528 "(%lu interrupted, ",traces_stats.interrupted);
1529 else
1530 fprintf(outfile,"(");
1531 fprintf(outfile,"%lu peak); maxlev=%d\n",
1532 traces_stats.peaknodes,traces_stats.treedepth);
1533 if (options_getcanon)
1534 fprintf(outfile,
1535 "canupdates=%d; ",traces_stats.canupdates);
1536 #ifdef CPUTIME
1537 fprintf(outfile,actmult == 1 ?
1538 "cpu time = %.2f seconds\n" :
1539 "cpu time = %.7f seconds\n",
1540 (timeafter-timebefore)/actmult);
1541 #else
1542 fprintf(outfile,"\n");
1543 #endif
1544 if (options_getcanon) cvalid_sg = TRUE;
1545 ovalid = TRUE;
1546 }
1547 }
1548 else
1549 {
1550 ovalid = FALSE;
1551 cvalid = cvalid_sg = FALSE;
1552 if (!gvalid && !gvalid_sg)
1553 {
1554 fprintf(ERRFILE,"g is not defined\n");
1555 FLUSHANDPROMPT;
1556 break;
1557 }
1558 if (mode == DENSE_MODE)
1559 {
1560 if (pvalid)
1561 {
1562 fprintf(outfile,"[fixing partition]\n");
1563 options.defaultptn = FALSE;
1564 }
1565 else
1566 options.defaultptn = TRUE;
1567
1568 options.outfile = outfile;
1569 options.digraph = options_digraph;
1570 options.cartesian = options_cartesian;
1571 options.schreier = (options_schreier > 0);
1572 options.getcanon = options_getcanon;
1573 options.tc_level = options_tc_level;
1574 options.linelength = options_linelength;
1575 options.invarproc
1576 = invarproc[options_invarproc].entrypoint;
1577 options.mininvarlevel = options_mininvarlevel;
1578 if (options.invarproc)
1579 options.maxinvarlevel = options_maxinvarlevel;
1580 else
1581 options.maxinvarlevel = 0;
1582 options.invararg = options_invararg;
1583 if (options_schreier > 0)
1584 schreier_fails(options_schreier);
1585
1586 if (umask & U_NODE) options.usernodeproc = NODEPROC;
1587 else options.usernodeproc = NULL;
1588 if (umask & U_AUTOM) options.userautomproc = AUTOMPROC;
1589 else options.userautomproc = NULL;
1590 if (umask & U_LEVEL) options.userlevelproc = LEVELPROC;
1591 else options.userlevelproc = NULL;
1592 if (umask & U_REF) options.userrefproc = REFPROC;
1593 else options.userrefproc = NULL;
1594 if (umask & U_CANON) options.usercanonproc = CANONPROC;
1595 else options.usercanonproc = NULL;
1596 #if !MAXN
1597 if (options_getcanon)
1598 DYNALLOC2(graph,canong,canong_sz,n,m,"dreadnaut");
1599 DYNALLOC1(setword,workspace,workspace_sz,2*m*worksize,
1600 "dreadnaut");
1601 #endif
1602 firstpath = TRUE;
1603 options.writeautoms = options_writeautoms;
1604 options.writemarkers = options_writemarkers;
1605 #ifdef CPUTIME
1606 timebefore = CPUTIME;
1607 #endif
1608 actmult = 0;
1609 setsigcatcher();
1610 for (;;)
1611 {
1612 nauty(g,lab,ptn,NULL,orbits,&options,&stats,workspace,
1613 2*m*worksize,m,n,canong);
1614 if (stats.errstatus) break;
1615 options.writeautoms = FALSE;
1616 options.writemarkers = FALSE;
1617 ++actmult;
1618 if (multiplicity > 0 && actmult >= multiplicity)
1619 break;
1620 #ifdef CPUTIME
1621 if (mintime > 0.0 && (actmult < 20 || !(actmult&7))
1622 && CPUTIME >= timebefore+mintime)
1623 break;
1624 #endif
1625 }
1626 unsetsigcatcher();
1627 #ifdef CPUTIME
1628 timeafter = CPUTIME;
1629 #endif
1630 }
1631 if (mode == SPARSE_MODE)
1632 {
1633 if (pvalid)
1634 {
1635 fprintf(outfile,"[fixing partition]\n");
1636 options_sg.defaultptn = FALSE;
1637 }
1638 else
1639 options_sg.defaultptn = TRUE;
1640
1641 options_sg.outfile = outfile;
1642 options_sg.digraph = options_digraph;
1643 options_sg.cartesian = options_cartesian;
1644 options_sg.schreier = (options_schreier > 0);
1645 options_sg.getcanon = options_getcanon;
1646 options_sg.linelength = options_linelength;
1647 options_sg.invarproc
1648 = invarproc[options_invarproc].entrypoint_sg;
1649 options_sg.mininvarlevel = options_mininvarlevel;
1650 if (options_sg.invarproc)
1651 options_sg.maxinvarlevel = options_maxinvarlevel;
1652 else
1653 options_sg.maxinvarlevel = 0;
1654 options_sg.invararg = options_invararg;
1655 options_sg.tc_level = options_tc_level;
1656 if (options_schreier > 0)
1657 schreier_fails(options_schreier);
1658
1659 if (umask & U_NODE) options_sg.usernodeproc = NODEPROC;
1660 else options_sg.usernodeproc = NULL;
1661 if (umask & U_AUTOM) options_sg.userautomproc = AUTOMPROC;
1662 else options_sg.userautomproc = NULL;
1663 if (umask & U_LEVEL) options_sg.userlevelproc = LEVELPROC;
1664 else options_sg.userlevelproc = NULL;
1665 if (umask & U_REF) options_sg.userrefproc = REFPROC;
1666 else options_sg.userrefproc = NULL;
1667 if (umask & U_CANON) options_sg.usercanonproc = CANONPROC;
1668 else options_sg.usercanonproc = NULL;
1669 #if !MAXN
1670 DYNALLOC1(setword,workspace,workspace_sz,2*m*worksize,
1671 "dreadnaut");
1672 #endif
1673
1674 firstpath = TRUE;
1675 options_sg.writeautoms = options_writeautoms;
1676 options_sg.writemarkers = options_writemarkers;
1677 #ifdef CPUTIME
1678 timebefore = CPUTIME;
1679 #endif
1680 actmult = 0;
1681 setsigcatcher();
1682 for (;;)
1683 {
1684 nauty((graph*)&g_sg,lab,ptn,NULL,orbits,&options_sg,
1685 &stats,workspace,2*m*worksize,m,n,(graph*)&canong_sg);
1686 if (stats.errstatus) break;
1687 options_sg.writeautoms = FALSE;
1688 options_sg.writemarkers = FALSE;
1689 ++actmult;
1690 if (multiplicity > 0 && actmult >= multiplicity)
1691 break;
1692 #ifdef CPUTIME
1693 if (mintime > 0.0 && (actmult < 20 || !(actmult&7))
1694 && CPUTIME >= timebefore+mintime)
1695 break;
1696 #endif
1697 }
1698 unsetsigcatcher();
1699 #ifdef CPUTIME
1700 timeafter = CPUTIME;
1701 #endif
1702 }
1703
1704 if (stats.errstatus)
1705 {
1706 if (stats.errstatus == NAUABORTED)
1707 fprintf(ERRFILE,"nauty aborted\n");
1708 else if (stats.errstatus == NAUKILLED)
1709 fprintf(ERRFILE,"nauty interrupted\n");
1710 else
1711 fprintf(ERRFILE,
1712 "nauty returned error status %d [this can't happen]\n",
1713 stats.errstatus);
1714 cvalid = cvalid_sg = ovalid = FALSE;
1715 }
1716 else
1717 {
1718 if (options_getcanon)
1719 {
1720 if (mode == DENSE_MODE) cvalid = TRUE;
1721 else cvalid_sg = TRUE;
1722 }
1723 ovalid = TRUE;
1724 fprintf(outfile,"%d orbit%s",SS(stats.numorbits,"","s"));
1725 fprintf(outfile,"; grpsize=");
1726 writegroupsize(outfile,stats.grpsize1,stats.grpsize2);
1727 fprintf(outfile,"; %d gen%s",
1728 SS(stats.numgenerators,"","s"));
1729 fprintf(outfile,"; %lu node%s",SS(stats.numnodes,"","s"));
1730 if (stats.numbadleaves)
1731 fprintf(outfile," (%lu bad lea%s)",
1732 SS(stats.numbadleaves,"f","ves"));
1733 fprintf(outfile,"; maxlev=%d\n", stats.maxlevel);
1734 /* fprintf(outfile,"tctotal=%lu",stats.tctotal); */
1735 if (options_getcanon)
1736 fprintf(outfile,"canupdates=%lu; ",stats.canupdates);
1737 #ifdef CPUTIME
1738 fprintf(outfile,actmult == 1 ?
1739 "cpu time = %.2f seconds\n" :
1740 "cpu time = %.7f seconds\n",
1741 (timeafter-timebefore)/actmult);
1742 #else
1743 fprintf(outfile,"\n");
1744 #endif
1745 if (mode == DENSE_MODE && options_maxinvarlevel != 0
1746 && invarproc[options_invarproc].entrypoint)
1747 {
1748 fprintf(outfile,"invarproc \"%s\" succeeded %lu/%lu",
1749 invarproc[options_invarproc].name,
1750 stats.invsuccesses,stats.invapplics);
1751 if (stats.invarsuclevel > 0)
1752 fprintf(outfile," beginning at level %d.\n",
1753 stats.invarsuclevel);
1754 else
1755 fprintf(outfile,".\n");
1756 }
1757 if (mode == SPARSE_MODE && options_maxinvarlevel != 0
1758 && invarproc[options_invarproc].entrypoint_sg)
1759 {
1760 fprintf(outfile,"invarproc \"%s\" succeeded %lu/%lu",
1761 invarproc[options_invarproc].name_sg,
1762 stats.invsuccesses,stats.invapplics);
1763 if (stats.invarsuclevel > 0)
1764 fprintf(outfile," beginning at level %d.\n",
1765 stats.invarsuclevel);
1766 else
1767 fprintf(outfile,".\n");
1768 }
1769 }
1770 }
1771 break;
1772
1773 case 'A': /* change mode, with possible conversion */
1774 minus = FALSE;
1775 oldmode = mode;
1776 d = getc(INFILE);
1777 if (d == 'n' || d == 'N' || d == 'd' || d == 'D') mode = DENSE_MODE;
1778 else if (d == 's' || d == 'S') mode = SPARSE_MODE;
1779 else if (d == 't' || d == 'T') mode = TRACES_MODE;
1780 else
1781 {
1782 fprintf(ERRFILE,"Mode %c is unknown\n",(d?d:'0'));
1783 FLUSHANDPROMPT;
1784 break;
1785 }
1786 if ((d = getc(INFILE)) != '+')
1787 {
1788 ungetc(d,INFILE);
1789 gvalid = gvalid_sg = FALSE;
1790 pvalid = ovalid = FALSE;
1791 }
1792 else
1793 {
1794 if (SPARSEREP(oldmode) && !SPARSEREP(mode) && gvalid_sg)
1795 {
1796 #if !MAXN
1797 DYNALLOC2(graph,g,g_sz,n,m,"dreadnaut");
1798 #endif
1799 sg_to_nauty(&g_sg,g,m,&m);
1800 gvalid_sg = FALSE;
1801 gvalid = TRUE;
1802 }
1803 if (!SPARSEREP(oldmode) && SPARSEREP(mode) && gvalid)
1804 {
1805 nauty_to_sg(g,&g_sg,m,n);
1806 gvalid = FALSE;
1807 gvalid_sg = TRUE;
1808 }
1809 }
1810 cvalid = cvalid_sg = FALSE;
1811 sgn = 0; /* invalidate saved graph */
1812 break;
1813
1814 case 'f': /* read initial partition */
1815
1816 if (minus)
1817 {
1818 pvalid = FALSE;
1819 minus = FALSE;
1820 }
1821 else
1822 {
1823 readptn(INFILE,lab,ptn,&numcells,prompt,n);
1824 pvalid = TRUE;
1825 freeschreier(NULL,&generators);
1826 }
1827 break;
1828
1829 case 'F': /* individualise one more vertex */
1830 if ((d = getc(INFILE)) != 'F') ungetc(d,INFILE);
1831 minus = FALSE;
1832 if (d != 'F')
1833 {
1834 i = getint_sl(INFILE);
1835 i -= labelorg;
1836 if (i < 0 || i >= n)
1837 {
1838 fprintf(ERRFILE,"F argument must be 0..n-1\n");
1839 FLUSHANDPROMPT;
1840 }
1841 else
1842 {
1843 if (!pvalid) unitptn(lab,ptn,&numcells,n);
1844 individualise(lab,ptn,0,i,&d,&numcells,n);
1845 pvalid = TRUE;
1846 }
1847 }
1848 else
1849 {
1850 if (!gvalid && !gvalid_sg)
1851 {
1852 fprintf(stderr,"g is not defined\n");
1853 FLUSHANDPROMPT;
1854 break;
1855 }
1856 if (!pvalid) unitptn(lab,ptn,&numcells,n);
1857
1858 if (!SPARSEREP(mode))
1859 i = targetcell(g,lab,ptn,0,1,options_digraph,-1,m,n);
1860 else if (mode == SPARSE_MODE)
1861 i = targetcell_sg((graph*)&g_sg,lab,ptn,0,1,
1862 options_digraph,-1,m,n);
1863 else /* Traces mode */
1864 {
1865 maxsize = 0;
1866 for (cell1 = 0; cell1 < n; cell1 = cell2 + 1)
1867 {
1868 for (cell2 = cell1; ptn[cell2] > 0; ++cell2) {}
1869 if (cell2-cell1+1 > maxsize)
1870 {
1871 i = cell1;
1872 maxsize = cell2 - cell1 + 1;
1873 }
1874 }
1875 }
1876
1877 if (ptn[i] > 0)
1878 {
1879 ptn[i] = 0;
1880 ++numcells;
1881 }
1882 pvalid = TRUE;
1883 }
1884 freeschreier(NULL,&generators);
1885 break;
1886
1887 case 't': /* type graph */
1888 minus = FALSE;
1889 if (gvalid)
1890 putgraph(outfile,g,options_linelength,m,n);
1891 else if (gvalid_sg)
1892 putgraph_sg(outfile,&g_sg,options_linelength);
1893 else
1894 {
1895 fprintf(ERRFILE,"g is not defined\n");
1896 FLUSHANDPROMPT;
1897 }
1898 break;
1899
1900 case 'T': /* type graph preceded by n, $ and g commands */
1901 minus = FALSE;
1902 if (gvalid)
1903 {
1904 fprintf(outfile,"n=%d $=%d g\n",n,labelorg);
1905 putgraph(outfile,g,options_linelength,m,n);
1906 fprintf(outfile,"$$\n");
1907 }
1908 else if (gvalid_sg)
1909 {
1910 fprintf(outfile,"n=%d $=%d g\n",n,labelorg);
1911 putgraph_sg(outfile,&g_sg,options_linelength);
1912 fprintf(outfile,"$$\n");
1913 }
1914 else
1915 {
1916 fprintf(ERRFILE,"g is not defined\n");
1917 FLUSHANDPROMPT;
1918 }
1919 break;
1920
1921 case 'u': /* call user procs */
1922 if (minus)
1923 {
1924 umask = 0;
1925 minus = FALSE;
1926 }
1927 else
1928 {
1929 umask = getint_sl(INFILE);
1930 if (umask < 0) umask = ~U_TCELL;
1931 }
1932 if (umask & U_TCELL)
1933 {
1934 fprintf(ERRFILE,"usertcellproc() is gone at version 2.4\n");
1935 umask &= ~U_TCELL;
1936 }
1937 break;
1938
1939 case 'o': /* type orbits */
1940 minus = FALSE;
1941 if (ovalid)
1942 PUTORBITS(outfile,orbits,options_linelength,n);
1943 else
1944 {
1945 fprintf(ERRFILE,"orbits are not defined\n");
1946 FLUSHANDPROMPT;
1947 }
1948 break;
1949
1950 case 'O': /* make orbits into a partition*/
1951 minus = FALSE;
1952 if ((d = getc(INFILE)) != 'O') ungetc(d,INFILE);
1953
1954 if (ovalid && d != 'O')
1955 {
1956 #if !MAXN
1957 DYNALLOC1(int,tempptn,tempptn_sz,n,"dreadnaut");
1958 #endif
1959 for (i = n; --i >= 0;) tempptn[i] = 0;
1960 for (i = n; --i >= 0;)
1961 if ((j = orbits[i]) < i)
1962 {
1963 tempptn[i] = tempptn[j];
1964 tempptn[j] = i;
1965 }
1966
1967 k = 0;
1968 numcells = 0;
1969 for (i = 0; i < n; ++i)
1970 {
1971 if (orbits[i] == i)
1972 {
1973 j = i;
1974 do
1975 {
1976 lab[k] = j;
1977 ptn[k] = 1;
1978 ++k;
1979 j = tempptn[j];
1980 } while (j > 0);
1981
1982 ptn[k-1] = 0;
1983 ++numcells;
1984 }
1985 }
1986 pvalid = TRUE;
1987 }
1988 else if (ovalid && d == 'O')
1989 {
1990 #if !MAXN
1991 DYNALLOC1(int,tempptn,tempptn_sz,n,"dreadnaut");
1992 DYNALLOC1(int,templab,templab_sz,n,"dreadnaut");
1993 #endif
1994 for (i = 0; i < n; ++i) tempptn[i] = 0;
1995 for (i = 0; i < n; ++i) ++tempptn[orbits[i]];
1996
1997 j = 0;
1998 for (i = 0; i < n; ++i)
1999 if (tempptn[i] > 0)
2000 {
2001 templab[j] = i;
2002 tempptn[j] = tempptn[i];
2003 ++j;
2004 }
2005 sort2ints(tempptn,templab,j);
2006
2007 k = 0;
2008 for (i = 0; i < j; ++i)
2009 {
2010 ptn[templab[i]] = k;
2011 k += tempptn[i];
2012 }
2013 for (i = 0; i < n; ++i) lab[ptn[orbits[i]]++] = i;
2014
2015 for (i = 0; i < n; ++i) ptn[i] = 1;
2016 k = 0;
2017 numcells = 0;
2018 for (i = 0; i < j; ++i)
2019 {
2020 k += tempptn[i];
2021 if (i == j-1 || tempptn[i] != tempptn[i+1])
2022 {
2023 ptn[k-1] = 0;
2024 ++numcells;
2025 }
2026 }
2027 pvalid = TRUE;
2028 }
2029 else
2030 {
2031 fprintf(ERRFILE,"orbits are not defined\n");
2032 FLUSHANDPROMPT;
2033 }
2034 break;
2035
2036 case 'b': /* type canonlab and canong */
2037 minus = FALSE;
2038 if (cvalid)
2039 putcanon(outfile,lab,canong,options_linelength,m,n);
2040 else if (cvalid_sg)
2041 {
2042 sortlists_sg(&canong_sg);
2043 putcanon_sg(outfile,lab,&canong_sg,options_linelength);
2044 }
2045 else
2046 {
2047 fprintf(ERRFILE,"h is not defined\n");
2048 FLUSHANDPROMPT;
2049 }
2050 break;
2051
2052 case 'z': /* type hashcode for canong */
2053 minus = FALSE;
2054 if (cvalid)
2055 {
2056 zseed = hashgraph(canong,m,n,2922320L);
2057 fprintf(outfile,"[N%07lx",zseed);
2058
2059 zseed = hashgraph(canong,m,n,19883109L);
2060 fprintf(outfile," %07lx",zseed);
2061
2062 zseed = hashgraph(canong,m,n,489317L);
2063 fprintf(outfile," %07lx]\n",zseed);
2064 }
2065 else if (cvalid_sg)
2066 {
2067 zseed = hashgraph_sg(&canong_sg,2922320L);
2068 fprintf(outfile,"[%c%07lx",
2069 mode==SPARSE_MODE?'S':'T',zseed);
2070
2071 zseed = hashgraph_sg(&canong_sg,19883109L);
2072 fprintf(outfile," %07lx",zseed);
2073
2074 zseed = hashgraph_sg(&canong_sg,489317L);
2075 fprintf(outfile," %07lx]\n",zseed);
2076 }
2077 else
2078 {
2079 fprintf(ERRFILE,"h is not defined\n");
2080 FLUSHANDPROMPT;
2081 }
2082 break;
2083
2084 case 'c': /* set getcanon option */
2085 options_getcanon = !minus;
2086 minus = FALSE;
2087 break;
2088
2089 case 'w': /* read size of workspace */
2090 minus = FALSE;
2091 worksize = getint_sl(INFILE);
2092 #if MAXN
2093 if (worksize > 2*MAXM*WORKSIZE)
2094 {
2095 fprintf(ERRFILE,
2096 "too big - setting worksize = %d\n",WORKSIZE);
2097 worksize = WORKSIZE;
2098 }
2099 #endif
2100 break;
2101
2102 case 'l': /* read linelength for output */
2103 options_linelength = getint_sl(INFILE);
2104 minus = FALSE;
2105 break;
2106
2107 case 'y': /* set tc_level field of options */
2108 options_tc_level = getint_sl(INFILE);
2109 minus = FALSE;
2110 break;
2111
2112 case 'M': /* set multiplicity */
2113 if (minus)
2114 {
2115 multiplicity = 1;
2116 mintime = 0.0;
2117 minus = FALSE;
2118 }
2119 else
2120 {
2121 multiplicity = getint_sl(INFILE);
2122 if (multiplicity < 0) multiplicity = 0;
2123 if ((d = getc(INFILE)) == '/')
2124 {
2125 actmult = getint_sl(INFILE);
2126 if (actmult < 0) actmult = 0;
2127 }
2128 else
2129 {
2130 ungetc(d,INFILE);
2131 actmult = 0;
2132 }
2133 if (multiplicity == 0 && actmult == 0) multiplicity = 1;
2134 mintime = (double)actmult;
2135 }
2136 break;
2137
2138 case 'k': /* set invarlev fields of options */
2139 options_mininvarlevel = getint_sl(INFILE);
2140 options_maxinvarlevel = getint_sl(INFILE);
2141 minus = FALSE;
2142 break;
2143
2144 case 'K': /* set invararg field of options */
2145 options_invararg = getint_sl(INFILE);
2146 minus = FALSE;
2147 break;
2148
2149 case '*': /* set invarproc field of options */
2150 minus = FALSE;
2151 d = getint_sl(INFILE);
2152 if (d >= -1 && d <= NUMINVARS-2)
2153 {
2154 options_invarproc = d+1;
2155 options_mininvarlevel = 0;
2156 options_maxinvarlevel = 1;
2157 if (options_invarproc >= 10 && options_invarproc <= 13)
2158 options.invararg = 3;
2159 else
2160 options.invararg = 0;
2161 }
2162 else
2163 {
2164 fprintf(ERRFILE,"no such vertex-invariant\n");
2165 FLUSHANDPROMPT;
2166 }
2167 break;
2168
2169 case 'a': /* set writeautoms option */
2170 options_writeautoms = !minus;
2171 minus = FALSE;
2172 break;
2173
2174 case 'm': /* set writemarkers option */
2175 options_writemarkers = !minus;
2176 minus = FALSE;
2177 break;
2178
2179 case 'V': /* set verbosity for Traces */
2180 if (minus)
2181 {
2182 options_verbosity = 0;
2183 minus = FALSE;
2184 }
2185 else
2186 {
2187 i = getint_sl(INFILE);
2188 if (i < 0)
2189 {
2190 fprintf(ERRFILE,"verbosity must be >= 0\n");
2191 FLUSHANDPROMPT;
2192 }
2193 else
2194 options_verbosity = i;
2195 }
2196 break;
2197
2198 case 'S': /* set strategy for Traces */
2199 if (minus)
2200 {
2201 options_strategy = 0;
2202 minus = FALSE;
2203 }
2204 else
2205 {
2206 i = getint_sl(INFILE);
2207 if (i != 0) fprintf(ERRFILE,
2208 "Only strategy 0 is supported in this version\n");
2209 /*
2210 if (i < 0)
2211 {
2212 fprintf(ERRFILE,"strategy must be >= 0\n");
2213 FLUSHANDPROMPT;
2214 }
2215 else
2216 options_strategy = i;
2217 */
2218 }
2219 break;
2220
2221 case 'G': /* set schreier option */
2222 if (minus)
2223 {
2224 options_schreier = 0;
2225 minus = FALSE;
2226 }
2227 else
2228 {
2229 i = getint_sl(INFILE);
2230 if (i < 0)
2231 {
2232 fprintf(ERRFILE,"schreierfails must be >= 0\n");
2233 FLUSHANDPROMPT;
2234 }
2235 else
2236 {
2237 options_schreier = i;
2238 if (i > 0) schreier_fails(i);
2239 }
2240 }
2241 break;
2242
2243 case 'p': /* set cartesian option */
2244 options_cartesian = !minus;
2245 minus = FALSE;
2246 break;
2247
2248 case 'd': /* set digraph option */
2249 if (options_digraph && minus) gvalid = gvalid_sg = FALSE;
2250 options_digraph = !minus;
2251 minus = FALSE;
2252 break;
2253
2254 case 'P': /* set keep-group option */
2255 if (minus && options_keepgroup)
2256 {
2257 options_keepgroup = FALSE;
2258 freeschreier(NULL,&generators);
2259 }
2260 else
2261 {
2262 if ((d = getc(INFILE)) != 'P') ungetc(d,INFILE);
2263 options_keepgroup = TRUE;
2264 if (d == 'P')
2265 {
2266 readvperm(INFILE,perm,prompt,n,&nperm);
2267 if (nperm != n)
2268 {
2269 fprintf(ERRFILE,"Incomplete permutation\n");
2270 FLUSHANDPROMPT;
2271 }
2272 else
2273 addpermutation(&generators,perm,n);
2274 }
2275 }
2276 minus = FALSE;
2277 break;
2278
2279 case '$': /* set label origin */
2280 if ((d = getc(INFILE)) == '$')
2281 labelorg = oldorg;
2282 else
2283 {
2284 ungetc(d,INFILE);
2285 oldorg = labelorg;
2286 i = getint_sl(INFILE);
2287 if (i < 0)
2288 {
2289 fprintf(ERRFILE,"labelorg must be >= 0\n");
2290 FLUSHANDPROMPT;
2291 }
2292 else
2293 labelorg = i;
2294 }
2295 break;
2296
2297 case '?': /* type options, etc. */
2298 minus = FALSE;
2299 fprintf(outfile,"Mode=%s ",
2300 (mode==DENSE_MODE?"dense":
2301 mode==SPARSE_MODE?"sparse":"Traces"));
2302 fprintf(outfile,"m=%d n=%d labelorg=%d",m,n,labelorg);
2303 if (!gvalid && !gvalid_sg)
2304 fprintf(outfile," g=undef");
2305 else if (gvalid)
2306 {
2307 uli = 0;
2308 for (i = 0, gp = g; i < n; ++i, gp += m) uli += setsize(gp,m);
2309 if (options_digraph) fprintf(outfile," arcs=%lu",uli);
2310 else fprintf(outfile," edges=%lu",uli/2);
2311 }
2312 else
2313 {
2314 uli = g_sg.nde;
2315 if (options_digraph) fprintf(outfile," arcs=%lu",uli);
2316 else fprintf(outfile," edges=%lu",uli/2);
2317 }
2318 fprintf(outfile," options=(%cc%ca%cm%cp%cd",
2319 PM(options_getcanon),PM(options_writeautoms),
2320 PM(options_writemarkers),PM(options_cartesian),
2321 PM(options_digraph));
2322 if (mode == TRACES_MODE)
2323 fprintf(outfile,"%cP",PM(options_keepgroup));
2324 if (umask & 31)
2325 fprintf(outfile," u=%d",umask&31);
2326 if (options_tc_level > 0)
2327 fprintf(outfile," y=%d",options_tc_level);
2328 if (options_mininvarlevel != 0 || options_maxinvarlevel != 0)
2329 fprintf(outfile," k=(%d,%d)",
2330 options_mininvarlevel,options_maxinvarlevel);
2331 if (options_invararg > 0)
2332 fprintf(outfile," K=%d",options_invararg);
2333 if (multiplicity != 1 || mintime != 0.0)
2334 fprintf(outfile," M=%d/%.0f",multiplicity,mintime);
2335 fprintf(outfile,")\n");
2336 fprintf(outfile,"linelen=%d worksize=%d input_depth=%d",
2337 options_linelength,worksize,curfile);
2338 if (options_schreier > 0)
2339 fprintf(outfile," G=%d",options_schreier);
2340 if (mode == TRACES_MODE)
2341 {
2342 if (options_verbosity != 1)
2343 fprintf(outfile," V=%d",options_verbosity);
2344 if (options_strategy != 0)
2345 fprintf(outfile," S=%d",options_strategy);
2346 }
2347 if (options_invarproc != 1)
2348 fprintf(outfile," invarproc=%s",
2349 (mode == DENSE_MODE ?
2350 invarproc[options_invarproc].name :
2351 invarproc[options_invarproc].name_sg));
2352 if (pvalid)
2353 fprintf(outfile,"; %d cell%s",SS(numcells,"","s"));
2354 else
2355 fprintf(outfile,"; 1 cell");
2356 fprintf(outfile,"\n");
2357 if (outfile != PROMPTFILE)
2358 {
2359 fprintf(outfile,"Mode=%s ",
2360 (mode==DENSE_MODE?"dense":
2361 mode==SPARSE_MODE?"sparse":"Traces"));
2362 fprintf(PROMPTFILE,"n=%d depth=%d labelorg=%d\n",
2363 n,curfile,labelorg);
2364 }
2365 break;
2366
2367 case '&': /* list the partition and possibly the quotient */
2368 if ((d = getc(INFILE)) == '&')
2369 doquot = TRUE;
2370 else
2371 {
2372 ungetc(d,INFILE);
2373 doquot = FALSE;
2374 }
2375 minus = FALSE;
2376 if (pvalid)
2377 putptn(outfile,lab,ptn,0,options_linelength,n);
2378 else
2379 fprintf(outfile,"unit partition\n");
2380 if (doquot)
2381 {
2382 if (!pvalid) unitptn(lab,ptn,&numcells,n);
2383 if (SPARSEREP(mode))
2384 putquotient_sg(outfile,&g_sg,lab,ptn,0,options_linelength);
2385 else
2386 putquotient(outfile,g,lab,ptn,0,options_linelength,m,n);
2387 }
2388 break;
2389
2390 case 'h': /* type help information */
2391 case 'H':
2392 minus = FALSE;
2393 help(PROMPTFILE,c == 'H');
2394 break;
2395
2396 default: /* illegal command */
2397 fprintf(ERRFILE,"'%c' is illegal - type 'h' for help\n",c);
2398 FLUSHANDPROMPT;
2399 break;
2400
2401 } /* end of switch */
2402
2403 if (flushing) fflush(outfile);
2404 }
2405
2406 exit(0);
2407 }
2408
2409 /*****************************************************************************
2410 * *
2411 * help(f,i) writes help information to file f (i = 0,1). *
2412 * *
2413 *****************************************************************************/
2414
2415 static void
help(FILE * f,int i)2416 help(FILE *f, int i)
2417 {
2418 #define H(ss) fprintf(f," %s\n",ss);
2419
2420 if (i == 0)
2421 {
2422 H("Modes: An = dense, As = sparse, At = Traces; extra + to convert graph")
2423 H("+- a : write automs v,vv : write degrees *=# : select invariant:")
2424 H(" b : write canong w=# : set worksize (units of 2m)")
2425 H("+- c : canonise x : run nauty -1 = user-defined")
2426 H("+- d : digraph or loops y=# : set tc_level 0 = none")
2427 H(" e : edit graph z : write hashcode 1 = twopaths")
2428 H("-f, f=#, f=[...] : set colours 2 = adjtriang(K=0,1)")
2429 H(" g : read graph $=# : set origin 3 = triples")
2430 H(" h,H : help $$ : restore origin 4 = quadruples")
2431 H(" i : refine ? : type options 5 = celltrips")
2432 H(" I : refine using invar _ : compl __ : conv 6 = cellquads")
2433 H(" j : relabel randomly % : Mathon doubling 7 = cellquins")
2434 H("k=# # : set invar levels & : type colouring 8 = distances(K)")
2435 H(" K=# : set invar param && : + quotient matrix 9 = indsets(K)")
2436 H(" l=# : set line length >ff : write to file 10 = cliques(K)")
2437 H("+- m : write markers >>ff : append to file 11 = cellcliq(K)")
2438 H(" n=# : set order ->/->> : close/flush output 12 = cellind(K)")
2439 H(" o : write orbits <ff : read from file 13 = adjacencies")
2440 H("+- p : set autom format @ : save canong 14 = cellfano")
2441 H(" q : quit # : canong = savedg? 15 = cellfano2")
2442 H(" r,R : relabel/subgraph ## : + write mapping 16 = refinvar")
2443 H(" s=# : random g (p=1/#) sr=# : random reg \"...\" : copy comment")
2444 H("-G,G=# : schreier param F=# : fix extra vertex FF: fix target vertex")
2445 H(" t,T : type graph ! : ignore line O : orbits->partition")
2446 H("+- P : keep group PP : add automorphism Type H for more..")
2447 }
2448
2449 if (i == 1)
2450 {
2451 H("Commands for g and e : ")
2452 H(" There is always a \"current vertex\" v, initially first vertex.")
2453 H(" # : add edge v-# ; : increment v (exit if over limit)")
2454 H(" -# : delete edge v-# #: : set v := #")
2455 H(" ? : list nbhs of v . : exit")
2456 H("Mode change: An = dense nauty, As = sparse nauty, At = Traces")
2457 H("Use An+, As+ or At+ to also convert graph between dense and sparse")
2458 H("Command line argument -o options allows a,c,d,m,p,l,G,P,w,y,$,A,V,M")
2459 H("Syntax for f : f=[2 3|4:9|10] (rest in extra cell at right)")
2460 H(" -f same as f=[], f=# same as f=[#]")
2461 H("Syntax for r : r 2:4 1 5; (rest appended in order)")
2462 H("r& relabels the graph and partition in order of the partition")
2463 H("Syntax for R : R 2:4 1 5; or -R 0 3 6:10;")
2464 H("Syntax for PP : PP 2:4 1 5 0; (must be complete)")
2465 H("Arguments for u : 1=node,2=autom,4=level,16=ref,32=canon (add them)")
2466 H("Accurate times: M=#/# set number of runs and minimum total cpu.")
2467 }
2468
2469 }
2470
2471 /*****************************************************************************
2472 * *
2473 * usernode(g,lab,ptn,level,numcells,tc,code,m,n) is a simple version of the *
2474 * procedure named by options.usernodeproc. *
2475 * *
2476 *****************************************************************************/
2477
2478 static void
usernode(graph * g,int * lab,int * ptn,int level,int numcells,int tc,int code,int m,int n)2479 usernode(graph *g, int *lab, int *ptn, int level, int numcells,
2480 int tc, int code, int m, int n)
2481 {
2482 int i;
2483
2484 for (i = 0; i < level; ++i) PUTC('.',outfile);
2485 if (numcells == n)
2486 fprintf(outfile,"(n/%d)\n",code);
2487 else if (tc < 0)
2488 fprintf(outfile,"(%d/%d)\n",numcells,code);
2489 else
2490 fprintf(outfile,"(%d/%d/%d)\n",numcells,code,tc);
2491 if (firstpath) putptn(outfile,lab,ptn,level,options_linelength,n);
2492 if (numcells == n) firstpath = FALSE;
2493 }
2494
2495 /*****************************************************************************
2496 * *
2497 * userautom(count,perm,orbits,numorbits,stabvertex,n) is a simple *
2498 * version of the procedure named by options.userautomproc. *
2499 * *
2500 *****************************************************************************/
2501
2502 static void
userautom(int count,int * perm,int * orbits,int numorbits,int stabvertex,int n)2503 userautom(int count, int *perm, int *orbits,
2504 int numorbits, int stabvertex, int n)
2505 {
2506 fprintf(outfile,
2507 "**userautomproc: count=%d stabvertex=%d numorbits=%d\n",
2508 count,stabvertex+labelorg,numorbits);
2509 PUTORBITS(outfile,orbits,options_linelength,n);
2510 }
2511
2512 /*****************************************************************************
2513 * *
2514 * userlevel(lab,ptn,level,orbits,stats,tv,index,tcellsize,numcells,cc,n) *
2515 * is a simple version of the procedure named by options.userlevelproc. *
2516 * *
2517 *****************************************************************************/
2518
2519 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)2520 userlevel(int *lab, int *ptn, int level, int *orbits, statsblk *stats,
2521 int tv, int index, int tcellsize, int numcells, int cc, int n)
2522 {
2523 fprintf(outfile,
2524 "**userlevelproc: level=%d tv=%d index=%d tcellsize=%d cc=%d\n",
2525 level,tv+labelorg,index,tcellsize,cc);
2526 fprintf(outfile," nodes=%lu cells=%d orbits=%d generators=%d\n",
2527 stats->numnodes,numcells,stats->numorbits,stats->numgenerators);
2528 }
2529
2530 /*****************************************************************************
2531 * *
2532 * usercanon(g,lab,canong,count,code,m,n) *
2533 * is a simple version of the procedure named by options.userlevelproc. *
2534 * *
2535 *****************************************************************************/
2536
2537 static int
usercanon(graph * g,int * lab,graph * canong,unsigned long count,int code,int m,int n)2538 usercanon(graph *g, int *lab, graph *canong, unsigned long count, int code,
2539 int m, int n)
2540 {
2541 fprintf(outfile,
2542 "**usercanonproc: count=%lu code=%d\n",count,code);
2543 return 0;
2544 }
2545