1 /* vcolg.c version 2.0; B D McKay, May 11, 2017 */
2
3 #define USAGE \
4 "vcolg [-q] [-u|-T] [-e#|-e#:#] [-m#] [-f#] [infile [outfile]]"
5
6 #define HELPTEXT \
7 " Read graphs or digraphs and colour their vertices in\n\
8 in all possible ways with colours 0,1,2,... .\n\
9 Isomorphic graphs derived from the same input are suppressed.\n\
10 If the input graphs are non-isomorphic then the output graphs are also.\n\
11 \n\
12 -e# | -e#:# specify a value or range of the total value of the colours\n\
13 -m# number of available colours (default 2)\n\
14 -f# Use the group that fixes the first # vertices setwise\n\
15 -T use a simple text output format (nv ne {col} {v1 v2})\n\
16 -u no output, just count them\n\
17 -q suppress auxiliary information\n"
18
19 /*************************************************************************/
20
21 #include "gtools.h"
22 #include "naugroup.h"
23 #include "nautinv.h"
24
25 nauty_counter vc_nin,vc_nout;
26 FILE *outfile;
27
28 #define MAXNV 128
29
30 static int col[MAXNV];
31 static boolean first;
32 static int lastreject[MAXNV];
33 static boolean lastrejok;
34 static unsigned long groupsize;
35 static unsigned long newgroupsize;
36 static boolean Tswitch;
37
38 static int fail_level;
39
40 #define GROUPTEST_NOT
41 #ifdef GROUPTEST
42 static long long totallab;
43 #endif
44
45 /* If OUTPROC is defined at compile time, and -u is not used, the
46 * procedure OUTPROC is called for each graph. This must be linked
47 * by the compiler. The arguments are
48 * f = open output file
49 * g = the input graph
50 * col[0..n-1] = the colours
51 * m,n = usual nauty meanings
52 */
53
54 /* SUMMARY feature
55 *
56 * If SUMMARY is defined, it must expand as the name of a procedure
57 * with prototype void SUMMARY(void). It is called at the end before
58 * the normal summary (which can be suppressed with -q). The numbers of
59 * graphs read and coloured graphs produced are available in the global
60 * variables vc_nin and vc_nout (type nauty_counter).
61 */
62
63 #ifdef OUTPROC
64 extern void OUTPROC(FILE*,graph*,int*,int,int);
65 #endif
66
67 #ifdef SUMMARY
68 extern void SUMMARY(void);
69 #endif
70
71 /**************************************************************************/
72
73 static void
writeautom(int * p,int n)74 writeautom(int *p, int n)
75 /* Called by allgroup. */
76 {
77 int i;
78
79 for (i = 0; i < n; ++i) printf(" %2d",p[i]);
80 printf("\n");
81 }
82
83 /**************************************************************************/
84
85 static int
ismax(int * p,int n)86 ismax(int *p, int n)
87 /* test if col^p <= col */
88 {
89 int i,k;
90 int fail;
91
92 fail = 0;
93 for (i = 0; i < n; ++i)
94 {
95 k = p[i];
96 if (k > fail) fail = k;
97 if (col[k] > col[i])
98 {
99 fail_level = fail;
100 return FALSE;
101 }
102 else if (col[k] < col[i]) return TRUE;
103 }
104
105 ++newgroupsize;
106 return TRUE;
107 }
108
109 /**************************************************************************/
110
111 static void
testmax(int * p,int n,int * abort)112 testmax(int *p, int n, int *abort)
113 /* Called by allgroup2. */
114 {
115 int i;
116
117 if (first)
118 { /* only the identity */
119 first = FALSE;
120 return;
121 }
122
123 if (!ismax(p,n))
124 {
125 *abort = 1;
126 for (i = 0; i < n; ++i) lastreject[i] = p[i];
127 lastrejok = TRUE;
128 }
129 }
130
131 /**************************************************************************/
132
133 static int
trythisone(grouprec * group,graph * g,boolean digraph,int m,int n)134 trythisone(grouprec *group, graph *g, boolean digraph, int m, int n)
135 /* Try one solution, accept if maximal. */
136 /* Return value is level to return to. */
137 {
138 int i,j;
139 boolean accept;
140 graph *gi;
141 size_t ne;
142
143 newgroupsize = 1;
144
145 if (!group || groupsize == 1)
146 accept = TRUE;
147 else if (lastrejok && !ismax(lastreject,n))
148 accept = FALSE;
149 else if (lastrejok && groupsize == 2)
150 accept = TRUE;
151 else
152 {
153 newgroupsize = 1;
154 first = TRUE;
155
156 if (allgroup2(group,testmax) == 0)
157 accept = TRUE;
158 else
159 accept = FALSE;
160 }
161
162 if (accept)
163 {
164 #ifdef GROUPTEST
165 if (groupsize % newgroupsize != 0)
166 gt_abort("group size error\n");
167 totallab += groupsize/newgroupsize;
168 #endif
169
170 ++vc_nout;
171
172 if (outfile)
173 {
174 #ifdef OUTPROC
175 OUTPROC(outfile,g,col,m,n);
176 #else
177 ne = 0;
178 for (gi = g + m*(size_t)n; --gi >= g; )
179 ne += POPCOUNT(*gi);
180 if (!digraph)
181 {
182 for (i = 0, gi = g; i < n; ++i, gi += m)
183 if (ISELEMENT(gi,i)) ++ne;
184 ne /= 2;
185 }
186 fprintf(outfile,"%d %lu",n,(unsigned long)ne);
187
188 for (i = 0; i < n; ++i) fprintf(outfile," %d",col[i]);
189 fprintf(outfile," ");
190 for (i = 0, gi = g; i < n; ++i, gi += m)
191 {
192 for (j = (digraph?-1:i-1); (j = nextelement(gi,m,j)) >= 0; )
193 fprintf(outfile," %d %d",i,j);
194 }
195 fprintf(outfile,"\n");
196 #endif
197 }
198 return n-1;
199 }
200 else
201 return fail_level-1;
202 }
203
204 /**************************************************************************/
205
206 static int
scan(int level,graph * g,boolean digraph,int * prev,long minedges,long maxedges,long sofar,long numcols,grouprec * group,int m,int n)207 scan(int level, graph *g, boolean digraph, int *prev, long minedges, long maxedges,
208 long sofar, long numcols, grouprec *group, int m, int n)
209 /* Recursive scan for default case */
210 /* Returned value is level to return to. */
211 {
212 int left;
213 long min,max,k,ret;
214
215 if (level == n)
216 return trythisone(group,g,digraph,m,n);
217
218 left = n - level - 1;
219 min = minedges - sofar - numcols*left;
220 if (min < 0) min = 0;
221 max = maxedges - sofar;
222 if (max >= numcols) max = numcols - 1;
223 if (prev[level] >= 0 && col[prev[level]] < max)
224 max = col[prev[level]];
225
226 for (k = min; k <= max; ++k)
227 {
228 col[level] = k;
229 ret = scan(level+1,g,digraph,prev,minedges,maxedges,sofar+k,numcols,group,m,n);
230 if (ret < level) return ret;
231 }
232
233 return level-1;
234 }
235
236 /**************************************************************************/
237
238 static void
colourgraph(graph * g,int nfixed,long minedges,long maxedges,long numcols,int m,int n)239 colourgraph(graph *g, int nfixed, long minedges, long maxedges,
240 long numcols, int m, int n)
241 {
242 static DEFAULTOPTIONS_GRAPH(options);
243 statsblk stats;
244 setword workspace[MAXNV];
245 grouprec *group;
246 int i,j,k,nloops;
247 set *gi,*gj;
248 int lab[MAXNV],ptn[MAXNV],orbits[MAXNV];
249 boolean loop[MAXNV];
250 int prev[MAXNV]; /* If >= 0, earlier point that must have greater colour */
251 int weight[MAXNV];
252 int region,start,stop;
253
254 if (n > MAXNV) gt_abort(">E vcolg: MAXNV exceeded\n");
255 nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
256
257 nloops = 0;
258 for (i = 0, gi = g; i < n; ++i, gi += m)
259 if (ISELEMENT(gi,i))
260 {
261 DELELEMENT(gi,i);
262 loop[i] = TRUE;
263 ++nloops;
264 }
265 else
266 loop[i] = FALSE;
267
268 for (region = 0; region < 2; ++region)
269 {
270 if (region == 0)
271 {
272 if (nfixed == 0) continue;
273 start = 0;
274 stop = nfixed;
275 if (stop > n) stop = n;
276 }
277 else
278 {
279 if (nfixed >= n) continue;
280 start = nfixed;
281 stop = n;
282 }
283
284 for (i = start, gi = g + m*(size_t)start; i < stop; ++i, gi += m)
285 {
286 /* Find most recent equivalent j. */
287 for (j = i-1, gj = gi-m; j >= start; --j, gj -= m)
288 {
289 if (loop[j] != loop[i]) continue;
290 for (k = 0; k < m; ++k) if (gi[k] != gj[k]) break;
291 if (k < m)
292 {
293 FLIPELEMENT(gi,i); FLIPELEMENT(gj,j);
294 for (k = 0; k < m; ++k) if (gi[k] != gj[k]) break;
295 FLIPELEMENT(gi,i); FLIPELEMENT(gj,j);
296 }
297 if (k == m) break;
298 }
299 if (j >= start)
300 {
301 prev[i] = j;
302 weight[i] = weight[j] + 1;
303 }
304 else
305 {
306 prev[i] = -1;
307 weight[i] = 0;
308 }
309 }
310 }
311
312 if (n == 0)
313 {
314 scan(0,g,FALSE,prev,minedges,maxedges,0,numcols,FALSE,m,n);
315 return;
316 }
317
318 for (i = nfixed; i < n; ++i) weight[i] += nfixed;
319
320 if (maxedges == NOLIMIT || maxedges > n*numcols) maxedges = n*numcols;
321 if (n*numcols < minedges) return;
322
323 options.userautomproc = groupautomproc;
324 options.userlevelproc = grouplevelproc;
325 options.defaultptn = FALSE;
326 options.digraph = (nloops > 0);
327
328 setlabptn(weight,lab,ptn,n);
329
330 if (nloops > 0)
331 for (i = 0, gi = g; i < n; ++i, gi += m)
332 if (loop[i]) ADDELEMENT(gi,i);
333
334 nauty(g,lab,ptn,NULL,orbits,&options,&stats,workspace,MAXNV,m,n,NULL);
335
336 if (stats.grpsize2 == 0)
337 groupsize = stats.grpsize1 + 0.1;
338 else
339 groupsize = 0;
340
341 group = groupptr(FALSE);
342 makecosetreps(group);
343
344 if (stats.numorbits < n)
345 {
346 j = n;
347 for (i = 0; i < n; ++i)
348 if (orbits[i] < i && orbits[i] < j) j = orbits[i];
349
350 for (i = j + 1; i < n; ++i)
351 if (orbits[i] == j) prev[i] = j;
352 }
353
354 lastrejok = FALSE;
355 for (i = 0; i < n; ++i) col[i] = 0;
356
357 scan(0,g,FALSE,prev,minedges,maxedges,0,numcols,group,m,n);
358 }
359
360 /**************************************************************************/
361
362 static void
colourdigraph(graph * g,int nfixed,long minedges,long maxedges,long numcols,int m,int n)363 colourdigraph(graph *g, int nfixed, long minedges, long maxedges,
364 long numcols, int m, int n)
365 {
366 static DEFAULTOPTIONS_GRAPH(options);
367 statsblk stats;
368 setword workspace[MAXNV];
369 grouprec *group;
370 int i,j,k,nloops;
371 size_t ii;
372 set *gi,*gj,*gci,*gcj;
373 int lab[MAXNV],ptn[MAXNV],orbits[MAXNV];
374 boolean loop[MAXNV];
375 int prev[MAXNV]; /* If >= 0, earlier point that must have greater colour */
376 int weight[MAXNV];
377 int region,start,stop;
378 DYNALLSTAT(graph,gconv,gconv_sz);
379
380 if (n > MAXNV) gt_abort(">E vcolg: MAXNV exceeded\n");
381 nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
382
383 DYNALLOC2(graph,gconv,gconv_sz,n,m,"colourdigraph");
384
385 nloops = 0;
386 for (i = 0, gi = g; i < n; ++i, gi += m)
387 if (ISELEMENT(gi,i))
388 {
389 DELELEMENT(gi,i);
390 loop[i] = TRUE;
391 ++nloops;
392 }
393 else
394 loop[i] = FALSE;
395
396 for (ii = 0; ii < m*(size_t)n; ++ii) gconv[ii] = g[ii];
397 converse(gconv,m,n);
398
399 for (region = 0; region < 2; ++region)
400 {
401 if (region == 0)
402 {
403 if (nfixed == 0) continue;
404 start = 0;
405 stop = nfixed;
406 if (stop > n) stop = n;
407 }
408 else
409 {
410 if (nfixed >= n) continue;
411 start = nfixed;
412 stop = n;
413 }
414
415 for (i = start,
416 gi = g + m*(size_t)start, gci = gconv + m*(size_t)start;
417 i < stop; ++i, gi += m, gci += m)
418 {
419 /* Find most recent equivalent j. */
420 for (j = i-1, gj = gi-m, gcj = gci-m; j >= start;
421 --j, gj -= m, gcj -= m)
422 {
423 if (loop[j] != loop[i]
424 || ISELEMENT(gi,j) != ISELEMENT(gj,i)) continue;
425 for (k = 0; k < m; ++k)
426 if (gi[k] != gj[k] || gci[k] != gcj[k]) break;
427 if (k < m)
428 {
429 FLIPELEMENT(gi,i); FLIPELEMENT(gj,j);
430 FLIPELEMENT(gci,i); FLIPELEMENT(gcj,j);
431 for (k = 0; k < m; ++k)
432 if (gi[k] != gj[k] || gci[k] != gcj[k]) break;
433 FLIPELEMENT(gci,i); FLIPELEMENT(gcj,j);
434 FLIPELEMENT(gi,i); FLIPELEMENT(gj,j);
435 }
436 if (k == m) break;
437 }
438 if (j >= start)
439 {
440 prev[i] = j;
441 weight[i] = weight[j] + 1;
442 }
443 else
444 {
445 prev[i] = -1;
446 weight[i] = 0;
447 }
448 }
449 }
450
451 for (i = nfixed; i < n; ++i) weight[i] += nfixed;
452
453 if (maxedges == NOLIMIT || maxedges > n*numcols) maxedges = n*numcols;
454 if (n*numcols < minedges) return;
455
456 if (n == 0)
457 {
458 scan(0,g,TRUE,prev,minedges,maxedges,0,numcols,FALSE,m,n);
459 return;
460 }
461
462 options.userautomproc = groupautomproc;
463 options.userlevelproc = grouplevelproc;
464 options.defaultptn = FALSE;
465 options.digraph = TRUE;
466 options.invarproc = adjacencies;
467 options.maxinvarlevel = n;
468
469 setlabptn(weight,lab,ptn,n);
470
471 if (nloops > 0)
472 for (i = 0, gi = g; i < n; ++i, gi += m)
473 if (loop[i]) ADDELEMENT(gi,i);
474
475 nauty(g,lab,ptn,NULL,orbits,&options,&stats,workspace,MAXNV,m,n,NULL);
476
477 if (stats.grpsize2 == 0)
478 groupsize = stats.grpsize1 + 0.1;
479 else
480 groupsize = 0;
481
482 group = groupptr(FALSE);
483 makecosetreps(group);
484
485 if (stats.numorbits < n)
486 {
487 j = n;
488 for (i = 0; i < n; ++i)
489 if (orbits[i] < i && orbits[i] < j) j = orbits[i];
490
491 for (i = j + 1; i < n; ++i)
492 if (orbits[i] == j) prev[i] = j;
493 }
494
495 lastrejok = FALSE;
496 for (i = 0; i < n; ++i) col[i] = 0;
497
498 scan(0,g,TRUE,prev,minedges,maxedges,0,numcols,group,m,n);
499 }
500
501 /**************************************************************************/
502
503 int
main(int argc,char * argv[])504 main(int argc, char *argv[])
505 {
506 graph *g;
507 int m,n,codetype;
508 int argnum,j,nfixed;
509 char *arg,sw;
510 boolean badargs,digraph;
511 boolean fswitch,uswitch,eswitch,qswitch,mswitch;
512 long minedges,maxedges,numcols;
513 double t;
514 char *infilename,*outfilename;
515 FILE *infile;
516 char msg[201];
517 int msglen;
518
519 HELP; PUTVERSION;
520
521 nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);
522
523 fswitch = Tswitch = FALSE;
524 uswitch = eswitch = mswitch = qswitch = FALSE;
525 infilename = outfilename = NULL;
526
527 argnum = 0;
528 badargs = FALSE;
529 for (j = 1; !badargs && j < argc; ++j)
530 {
531 arg = argv[j];
532 if (arg[0] == '-' && arg[1] != '\0')
533 {
534 ++arg;
535 while (*arg != '\0')
536 {
537 sw = *arg++;
538 SWLONG('m',mswitch,numcols,"vcolg -m")
539 else SWBOOLEAN('q',qswitch)
540 else SWBOOLEAN('u',uswitch)
541 else SWBOOLEAN('T',Tswitch)
542 else SWINT('f',fswitch,nfixed,"vcolg -f")
543 else SWRANGE('e',":-",eswitch,minedges,maxedges,"vcolg -e")
544 else badargs = TRUE;
545 }
546 }
547 else
548 {
549 ++argnum;
550 if (argnum == 1) infilename = arg;
551 else if (argnum == 2) outfilename = arg;
552 else badargs = TRUE;
553 }
554 }
555
556 if (badargs || argnum > 2)
557 {
558 fprintf(stderr,">E Usage: %s\n",USAGE);
559 GETHELP;
560 exit(1);
561 }
562
563 if ((Tswitch!=0) + (uswitch!=0) >= 2)
564 gt_abort(">E vcolg: -T and -u are incompatible\n");
565
566 #ifndef OUTPROC
567 if (!Tswitch && !uswitch)
568 gt_abort(">E vcolg: must use -T or -u\n");
569 #endif
570
571 if (!mswitch) numcols = 2;
572 if (!eswitch)
573 {
574 minedges = 0;
575 maxedges = NOLIMIT;
576 }
577 if (!fswitch) nfixed = 0;
578
579 if (!qswitch)
580 {
581 msg[0] = '\0';
582 CATMSG0(">A vcolg");
583 if (eswitch || mswitch || uswitch || (fswitch && nfixed > 0)
584 || Tswitch)
585 CATMSG0(" -");
586 if (mswitch) CATMSG1("m%ld",numcols);
587 if (uswitch) CATMSG0("u");
588 if (Tswitch) CATMSG0("T");
589 if (fswitch) CATMSG1("f%d",nfixed);
590 if (eswitch) CATMSG2("e%ld:%ld",minedges,maxedges);
591 msglen = strlen(msg);
592 if (argnum > 0) msglen += strlen(infilename);
593 if (argnum > 1) msglen += strlen(outfilename);
594 if (msglen >= 196)
595 {
596 fputs(msg,stderr);
597 if (argnum > 0) fprintf(stderr," %s",infilename);
598 if (argnum > 1) fprintf(stderr," %s",outfilename);
599 fprintf(stderr,"\n");
600 }
601 else
602 {
603 if (argnum > 0) CATMSG1(" %s",infilename);
604 if (argnum > 1) CATMSG1(" %s",outfilename);
605 CATMSG0("\n");
606 fputs(msg,stderr);
607 }
608 fflush(stderr);
609 }
610
611 if (infilename && infilename[0] == '-') infilename = NULL;
612 infile = opengraphfile(infilename,&codetype,FALSE,1);
613 if (!infile) exit(1);
614 if (!infilename) infilename = "stdin";
615
616 if (uswitch)
617 outfile = NULL;
618 else
619 {
620 if (!outfilename || outfilename[0] == '-')
621 {
622 outfilename = "stdout";
623 outfile = stdout;
624 }
625 else if ((outfile = fopen(outfilename,"w")) == NULL)
626 {
627 fprintf(stderr,"Can't open output file %s\n",outfilename);
628 gt_abort(NULL);
629 }
630 }
631
632 vc_nin = vc_nout = 0;
633
634 t = CPUTIME;
635 while (TRUE)
636 {
637 if ((g = readgg(infile,NULL,0,&m,&n,&digraph)) == NULL) break;
638 ++vc_nin;
639
640 if (!digraph)
641 colourgraph(g,nfixed,minedges,maxedges,numcols,m,n);
642 else
643 colourdigraph(g,nfixed,minedges,maxedges,numcols,m,n);
644
645 if (!uswitch && ferror(outfile)) gt_abort(">E vcolg output error\n");
646 FREES(g);
647 }
648 t = CPUTIME - t;
649
650 #ifdef SUMMARY
651 SUMMARY();
652 #endif
653
654 if (!qswitch)
655 {
656 fprintf(stderr,">Z ");
657 PRINT_COUNTER(stderr,vc_nin);
658 fprintf(stderr," graphs read from %s",infilename);
659 fprintf(stderr,"; ");
660 PRINT_COUNTER(stderr,vc_nout);
661 if (!uswitch)
662 fprintf(stderr," coloured graphs written to %s",outfilename);
663 else
664 fprintf(stderr," coloured graphs generated");
665 fprintf(stderr,"; %.2f sec\n",t);
666 }
667
668 #ifdef GROUPTEST
669 fprintf(stderr,"Group test = %lld\n",totallab);
670 #endif
671
672 exit(0);
673 }
674