1 /* labelg.c version 2.0; B D McKay, Jun 2015 */ 2 3 #define USAGE "labelg [-q] [-sgz | -C#W#] [-fxxx] [-S|-t] \n\ 4 [-i# -I#:# -K#] [infile [outfile]]" 5 6 #define HELPTEXT \ 7 " Canonically label a file of graphs or digraphs.\n\ 8 \n\ 9 -s force output to sparse6 format\n\ 10 -g force output to graph6 format\n\ 11 -z force output to digraph6 format\n\ 12 If neither -s, -g or -z are given, the output format is\n\ 13 determined by the header or, if there is none, by the\n\ 14 format of the first input graph. As an exception, digraphs\n\ 15 are always written in digraph6 format.\n\ 16 -S Use sparse representation internally.\n\ 17 Note that this changes the canonical labelling.\n\ 18 Multiple edges are not supported. One loop per vertex is ok.\n\ 19 -t Use Traces.\n\ 20 Note that this changes the canonical labelling.\n\ 21 Multiple edges and loops are not supported, nor invariants.\n\ 22 \n\ 23 -C# Make an invariant in 0..#-1 and output the number of graphs\n\ 24 with each value of the invariant. Don't write graphs unless\n\ 25 -W too.\n\ 26 -W# (requires -C) Output the graphs with this invariant value,\n\ 27 in their original labelling. Don't write the table.\n\ 28 \n\ 29 The output file will have a header if and only if the input file does.\n\ 30 \n\ 31 -fxxx Specify a partition of the point set. xxx is any\n\ 32 string of ASCII characters except nul. This string is\n\ 33 considered extended to infinity on the right with the\n\ 34 character 'z'. One character is associated with each point,\n\ 35 in the order given. The labelling used obeys these rules:\n\ 36 (1) the new order of the points is such that the associated\n\ 37 characters are in ASCII ascending order\n\ 38 (2) if two graphs are labelled using the same string xxx,\n\ 39 the output graphs are identical iff there is an\n\ 40 associated-character-preserving isomorphism between them.\n\ 41 No option can be concatenated to the right of -f.\n\ 42 \n\ 43 -i# select an invariant (1 = twopaths, 2 = adjtriang(K), 3 = triples,\n\ 44 4 = quadruples, 5 = celltrips, 6 = cellquads, 7 = cellquins,\n\ 45 8 = distances(K), 9 = indsets(K), 10 = cliques(K), 11 = cellcliq(K),\n\ 46 12 = cellind(K), 13 = adjacencies, 14 = cellfano, 15 = cellfano2,\n\ 47 16 = refinvar(K))\n\ 48 -I#:# select mininvarlevel and maxinvarlevel (default 1:1)\n\ 49 -K# select invararg (default 3)\n\ 50 \n\ 51 -q suppress auxiliary information\n" 52 53 54 /*************************************************************************/ 55 56 #include "gtools.h" 57 #include "nautinv.h" 58 #include "gutils.h" 59 #include "traces.h" 60 61 static struct invarrec 62 { 63 void (*entrypoint)(graph*,int*,int*,int,int,int,int*, 64 int,boolean,int,int); 65 void (*entrypoint_sg)(graph*,int*,int*,int,int,int,int*, 66 int,boolean,int,int); 67 char *name; 68 } invarproc[] 69 = {{NULL, NULL, "none"}, 70 {twopaths, NULL, "twopaths"}, 71 {adjtriang, NULL, "adjtriang"}, 72 {triples, NULL, "triples"}, 73 {quadruples, NULL, "quadruples"}, 74 {celltrips, NULL, "celltrips"}, 75 {cellquads, NULL, "cellquads"}, 76 {cellquins, NULL, "cellquins"}, 77 {distances, distances_sg, "distances"}, 78 {indsets, NULL, "indsets"}, 79 {cliques, NULL, "cliques"}, 80 {cellcliq, NULL, "cellcliq"}, 81 {cellind, NULL, "cellind"}, 82 {adjacencies, adjacencies_sg, "adjacencies"}, 83 {cellfano, NULL, "cellfano"}, 84 {cellfano2, NULL, "cellfano2"}, 85 {refinvar, NULL, "refinvar"} 86 }; 87 88 #define NUMINVARS ((int)(sizeof(invarproc)/sizeof(struct invarrec))) 89 90 static nauty_counter orbtotal; 91 static double unorbtotal; 92 extern int gt_numorbits; 93 94 /**************************************************************************/ 95 96 int 97 main(int argc, char *argv[]) 98 { 99 graph *g; 100 sparsegraph sg,sh; 101 int m,n,codetype; 102 int argnum,j,outcode; 103 char *arg,sw,*fmt; 104 boolean badargs,digraph; 105 boolean sswitch,gswitch,qswitch,fswitch,Oswitch; 106 boolean iswitch,Iswitch,Kswitch,Mswitch,Sswitch; 107 boolean uswitch,tswitch,Cswitch,Wswitch,zswitch; 108 boolean dooutput; 109 int tabsize,outinvar; 110 int inv,mininvarlevel,maxinvarlevel,invararg; 111 long minil,maxil; 112 double t; 113 char *infilename,*outfilename; 114 FILE *infile,*outfile; 115 nauty_counter nin,nout; 116 int ii,secret,loops; 117 DEFAULTOPTIONS_TRACES(traces_opts); 118 TracesStats traces_stats; 119 #if MAXN 120 graph h[MAXN*MAXM]; 121 int lab[MAXN],ptn[MAXN],orbits[MAXN]; 122 #else 123 DYNALLSTAT(graph,h,h_sz); 124 DYNALLSTAT(int,lab,lab_sz); 125 DYNALLSTAT(int,ptn,ptn_sz); 126 DYNALLSTAT(int,orbits,orbits_sz); 127 #endif 128 DYNALLSTAT(nauty_counter,tab,tab_sz); 129 130 HELP; PUTVERSION; 131 132 nauty_check(WORDSIZE,1,1,NAUTYVERSIONID); 133 134 sswitch = gswitch = qswitch = FALSE; 135 fswitch = Oswitch = Mswitch = FALSE; 136 iswitch = Iswitch = Kswitch = FALSE; 137 uswitch = Sswitch = tswitch = FALSE; 138 zswitch = Cswitch = Wswitch = FALSE; 139 infilename = outfilename = NULL; 140 inv = 0; 141 142 argnum = 0; 143 badargs = FALSE; 144 for (j = 1; !badargs && j < argc; ++j) 145 { 146 arg = argv[j]; 147 if (arg[0] == '-' && arg[1] != '\0') 148 { 149 ++arg; 150 while (*arg != '\0') 151 { 152 sw = *arg++; 153 SWBOOLEAN('s',sswitch) 154 else SWBOOLEAN('g',gswitch) 155 else SWBOOLEAN('z',zswitch) 156 else SWBOOLEAN('u',uswitch) 157 else SWBOOLEAN('q',qswitch) 158 else SWBOOLEAN('O',Oswitch) 159 else SWBOOLEAN('S',Sswitch) 160 else SWBOOLEAN('t',tswitch) 161 else SWINT('C',Cswitch,tabsize,"labelg -C") 162 else SWINT('W',Wswitch,outinvar,"labelg -W") 163 else SWINT('i',iswitch,inv,"labelg -i") 164 else SWINT('K',Kswitch,invararg,"labelg -K") 165 else SWRANGE('k',":-",Iswitch,minil,maxil,"labelg -k") 166 else SWRANGE('I',":-",Iswitch,minil,maxil,"labelg -I") 167 else if (sw == 'f') 168 { 169 fswitch = TRUE; 170 fmt = arg; 171 break; 172 } 173 else SWINT('M',Mswitch,secret,"labelg -M") 174 else badargs = TRUE; 175 } 176 } 177 else 178 { 179 ++argnum; 180 if (argnum == 1) infilename = arg; 181 else if (argnum == 2) outfilename = arg; 182 else badargs = TRUE; 183 } 184 } 185 186 if ((sswitch!=0) + (zswitch!=0) + (gswitch!=0) + (uswitch!=0) > 1) 187 gt_abort(">E labelg: -szgu are incompatible\n"); 188 189 if (tswitch && (fswitch || Sswitch)) 190 gt_abort(">E labelg: -t is incompatible with -S and -f \n"); 191 192 if (iswitch && inv == 0) iswitch = FALSE; 193 194 if (!Sswitch && iswitch && (inv > NUMINVARS)) 195 gt_abort(">E labelg: -i value must be 0..16\n"); 196 if (tswitch && iswitch) 197 gt_abort(">E labelg: invariants are not available with -t\n"); 198 if (Wswitch && (sswitch || gswitch || zswitch || uswitch || !Cswitch)) 199 gt_abort(">E labelg: -W forbids -sgzu and requires -C\n"); 200 if (Cswitch && tabsize <= 0) 201 gt_abort(">E labelg: bad value for -C\n"); 202 if (Wswitch && (outinvar < 0 || outinvar >= tabsize)) 203 gt_abort(">E labelg: value of -W is not valid\n"); 204 if (Sswitch && iswitch && invarproc[inv].entrypoint_sg == NULL) 205 gt_abort( 206 ">E labelg: that invariant is not available in sparse mode\n"); 207 208 209 if (iswitch) 210 { 211 if (Iswitch) 212 { 213 mininvarlevel = minil; 214 maxinvarlevel = maxil; 215 } 216 else 217 mininvarlevel = maxinvarlevel = 1; 218 if (!Kswitch) invararg = 3; 219 } 220 221 if (!Mswitch) secret = 1; 222 223 if (badargs || argnum > 2) 224 { 225 fprintf(stderr,">E Usage: %s\n",USAGE); 226 GETHELP; 227 exit(1); 228 } 229 230 if (!qswitch) 231 { 232 fprintf(stderr,">A labelg"); 233 if (sswitch || gswitch || fswitch || iswitch || zswitch 234 || tswitch || Sswitch || Cswitch || Wswitch) 235 fprintf(stderr," -"); 236 if (sswitch) fprintf(stderr,"s"); 237 if (gswitch) fprintf(stderr,"g"); 238 if (zswitch) fprintf(stderr,"z"); 239 if (Sswitch) fprintf(stderr,"S"); 240 if (tswitch) fprintf(stderr,"t"); 241 if (Cswitch) fprintf(stderr,"C%d",tabsize); 242 if (Wswitch) fprintf(stderr,"W%d",outinvar); 243 if (iswitch) 244 fprintf(stderr,"i=%s[%d:%d,%d]",invarproc[inv].name, 245 mininvarlevel,maxinvarlevel,invararg); 246 if (fswitch) fprintf(stderr,"f%s",fmt); 247 if (argnum > 0) fprintf(stderr," %s",infilename); 248 if (argnum > 1) fprintf(stderr," %s",outfilename); 249 fprintf(stderr,"\n"); 250 fflush(stderr); 251 } 252 253 if (Cswitch & !Wswitch) 254 { 255 DYNALLOC1(nauty_counter,tab,tab_sz,tabsize,"table"); 256 for (j = 0; j < tabsize; ++j) tab[j] = 0; 257 } 258 259 if (infilename && infilename[0] == '-') infilename = NULL; 260 infile = opengraphfile(infilename,&codetype,FALSE,1); 261 262 if (!infile) exit(1); 263 if (!infilename) infilename = "stdin"; 264 265 if (!outfilename || outfilename[0] == '-') 266 { 267 outfilename = "stdout"; 268 outfile = stdout; 269 } 270 else if ((outfile = fopen(outfilename,"w")) == NULL) 271 { 272 fprintf(stderr,"Can't open output file %s\n",outfilename); 273 gt_abort(NULL); 274 } 275 276 if (uswitch) 277 outcode = 0; 278 else if (Cswitch && !Wswitch) 279 outcode = -1; 280 else if (Cswitch && Wswitch) 281 outcode = -2; 282 else if (gswitch) 283 outcode = GRAPH6; 284 else if (sswitch) 285 outcode = SPARSE6; 286 else if (zswitch) 287 outcode = DIGRAPH6; 288 else if ((codetype&DIGRAPH6)) 289 outcode = DIGRAPH6; 290 else if ((codetype&GRAPH6)) 291 outcode = GRAPH6; 292 else if ((codetype&SPARSE6)) 293 outcode = SPARSE6; 294 else 295 { 296 outcode = GRAPH6; 297 fprintf(stderr, 298 ">W labelg doesn't handle this graph format, writing graph6.\n"); 299 } 300 301 dooutput = (outcode == GRAPH6 || outcode == DIGRAPH6 || outcode == SPARSE6); 302 303 if (!fswitch) fmt = NULL; 304 305 if (!uswitch && (codetype&HAS_HEADER)) 306 { 307 if (outcode == SPARSE6) writeline(outfile,SPARSE6_HEADER); 308 else if (outcode == DIGRAPH6) writeline(outfile,DIGRAPH6_HEADER); 309 else writeline(outfile,GRAPH6_HEADER); 310 } 311 312 nin = nout = 0; 313 orbtotal = 0; 314 unorbtotal = 0.0; 315 t = CPUTIME; 316 if (Sswitch) 317 { 318 SG_INIT(sg); 319 SG_INIT(sh); 320 while (TRUE) 321 { 322 if (read_sgg_loops(infile,&sg,&loops,&digraph) == NULL) break; 323 ++nin; 324 n = sg.nv; 325 m = (n + WORDSIZE - 1) / WORDSIZE; 326 SG_ALLOC(sh,n,sg.nde,"labelg"); 327 for (ii = 0; ii < secret; ++ii) 328 fcanonise_inv_sg(&sg,m,n,&sh,fmt,invarproc[inv].entrypoint_sg, 329 mininvarlevel,maxinvarlevel,invararg,loops>0||digraph); 330 sortlists_sg(&sh); 331 if (n > 0) 332 { 333 orbtotal += gt_numorbits; 334 unorbtotal += 1.0 / gt_numorbits; 335 } 336 if (dooutput && (outcode == DIGRAPH6 || digraph)) writed6_sg(outfile,&sh); 337 else if (outcode == SPARSE6) writes6_sg(outfile,&sh); 338 else if (outcode == GRAPH6) writeg6_sg(outfile,&sh); 339 else if (outcode == -1) 340 ++tab[hashgraph_sg(&sh,137)%tabsize]; 341 else if (outcode == -2 && (hashgraph_sg(&sh,137)%tabsize) == outinvar) 342 { 343 writelast(outfile); 344 ++nout; 345 } 346 } 347 } 348 else if (tswitch) 349 { 350 SG_INIT(sg); 351 SG_INIT(sh); 352 traces_opts.getcanon = TRUE; 353 traces_opts.writeautoms = FALSE; 354 traces_opts.verbosity = 0; 355 traces_opts.outfile = stdout; 356 357 while (TRUE) 358 { 359 if (read_sgg_loops(infile,&sg,&loops,&digraph) == NULL) break; 360 if (loops > 0 || digraph) 361 gt_abort(">E Traces does not allow loops or directed edges\n"); 362 ++nin; 363 n = sg.nv; 364 DYNALLOC1(int,lab,lab_sz,n,"traces@labelg"); 365 DYNALLOC1(int,ptn,ptn_sz,n,"traces@labelg"); 366 DYNALLOC1(int,orbits,orbits_sz,n,"traces@labelg"); 367 SG_ALLOC(sh,n,sg.nde,"labelg"); 368 sh.nv = sg.nv; 369 sh.nde = sg.nde; 370 if (n > 0) 371 { 372 for (ii = 0; ii < n; ++ii) { lab[ii] = ii; ptn[ii] = 1; } 373 ptn[n-1] = 0; 374 for (ii = 0; ii < secret; ++ii) 375 Traces(&sg,lab,ptn,orbits,&traces_opts,&traces_stats,&sh); 376 sortlists_sg(&sh); 377 orbtotal += gt_numorbits; 378 unorbtotal += 1.0 / gt_numorbits; 379 } 380 if (outcode == SPARSE6) writes6_sg(outfile,&sh); 381 else if (outcode == GRAPH6) writeg6_sg(outfile,&sh); 382 else if (outcode == -1) 383 ++tab[hashgraph_sg(&sh,137)%tabsize]; 384 else if (outcode == -2 && (hashgraph_sg(&sh,137)%tabsize) == outinvar) 385 { 386 writelast(outfile); 387 ++nout; 388 } 389 SG_FREE(sh); 390 } 391 } 392 else 393 { 394 while (TRUE) 395 { 396 if ((g = readgg(infile,NULL,0,&m,&n,&digraph)) == NULL) break; 397 ++nin; 398 #if !MAXN 399 DYNALLOC2(graph,h,h_sz,n,m,"labelg"); 400 #endif 401 loops = loopcount(g,m,n); 402 for (ii = 0; ii < secret; ++ii) 403 fcanonise_inv(g,m,n,h,fmt,invarproc[inv].entrypoint, 404 mininvarlevel,maxinvarlevel,invararg,loops>0||digraph); 405 if (n > 0) 406 { 407 orbtotal += gt_numorbits; 408 unorbtotal += 1.0 / gt_numorbits; 409 } 410 if (dooutput && (outcode == DIGRAPH6 || digraph)) writed6(outfile,h,m,n); 411 else if (outcode == SPARSE6) writes6(outfile,h,m,n); 412 else if (outcode == GRAPH6) writeg6(outfile,h,m,n); 413 else if (outcode == -1) 414 ++tab[hashgraph(h,m,n,137)%tabsize]; 415 else if (outcode == -2 && (hashgraph(h,m,n,137)%tabsize) == outinvar) 416 { 417 writelast(outfile); 418 ++nout; 419 } 420 FREES(g); 421 } 422 } 423 t = CPUTIME - t; 424 425 if (Oswitch) 426 fprintf(stderr,">C orbit totals = " COUNTER_FMT " %15.8f\n", 427 orbtotal,unorbtotal); 428 if (!qswitch) 429 { 430 if (outcode == -1) 431 { 432 for (j = 0; j < tabsize; ++j) 433 fprintf(stderr,">C %5d " COUNTER_FMT "\n",j,tab[j]); 434 fprintf(stderr,">Z " COUNTER_FMT " total from %s in %3.2f sec.\n", 435 nin,infilename,t); 436 } 437 else if (outcode == -2) 438 { 439 fprintf(stderr, 440 ">Z " COUNTER_FMT " out of " COUNTER_FMT 441 " graphs copied from %s to %s in %3.2f sec.\n", 442 nout,nin,infilename,outfilename,t); 443 } 444 else 445 { 446 fprintf(stderr, 447 ">Z " COUNTER_FMT 448 " graphs labelled from %s to %s in %3.2f sec.\n", 449 nin,infilename,outfilename,t); 450 } 451 } 452 453 exit(0); 454 } 455