1 /* multig.c version 1.0; B D McKay, Oct 25, 2004 */
2
3 #define USAGE \
4 "multig [-q] [-u|-T|-G|-A|-B] [-e#|-e#:#] [-m#] [-f#] [infile [outfile]]"
5
6 #define HELPTEXT \
7 " Read undirected loop-free graphs and replace their edges with multiple\n\
8 edges in all possible ways (multiplicity at least 1).\n\
9 Isomorphic multigraphs 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 number of edges\n\
13 counting multiplicities\n\
14 -m# maximum edge multiplicity (minimum is 1)\n\
15 Either -e or -m with a finite maximum must be given\n\
16 -f# Use the group that fixes the first # vertices setwise\n\
17 -T use a simple text output format (nv ne {v1 v2 mult})\n\
18 -G like -T but includes group size as third item (if less than 10^10)\n\
19 The group size does not include exchange of isolated vertices.\n\
20 -A write as the upper triangle of an adjacency matrix, row by row,\n\
21 including the diagonal, and preceded by the number of vertices\n\
22 -B write as an integer matrix preceded by the number of rows and\n\
23 number of columns, where -f determines the number of rows\n\
24 -u no output, just count them\n\
25 -q suppress auxiliary information\n"
26
27 /*************************************************************************/
28
29 #include "gtools.h"
30 #include "naugroup.h"
31
32 typedef struct
33 {
34 long hi,lo;
35 } bigint;
36
37 #define ZEROBIG(big) big.hi = big.lo = 0L
38 #define ADDBIG(big,extra) if ((big.lo += (extra)) >= 1000000000L) \
39 { ++big.hi; big.lo -= 1000000000L;}
40 #define PRINTBIG(file,big) if (big.hi == 0) \
41 fprintf(file,"%ld",big.lo); else fprintf(file,"%ld%09ld",big.hi,big.lo)
42
43 static bigint nin,ngen,nout;
44 FILE *outfile;
45
46 #define MAXNV 128
47 #define MAXNE 1024
48 static int v0[MAXNE],v1[MAXNE];
49 static int edgeno[MAXNV][MAXNV];
50
51 #define MAXME ((MAXNE+WORDSIZE-1)/WORDSIZE)
52
53 static int ix[MAXNE],nix;
54 static boolean first;
55 static permutation lastreject[MAXNV];
56 static boolean lastrejok;
57 static int rejectlevel;
58 static unsigned long groupsize;
59 static unsigned long newgroupsize;
60 static boolean Gswitch,Tswitch,Aswitch,Bswitch;
61 static int Brows;
62
63 /* #define GROUPTEST */
64 #ifdef GROUPTEST
65 static long long totallab;
66 #endif
67
68 /**************************************************************************/
69
70 void
writeautom(permutation * p,int n)71 writeautom(permutation *p, int n)
72 /* Called by allgroup. */
73 {
74 int i;
75
76 for (i = 0; i < n; ++i) printf(" %2d",p[i]);
77 printf("\n");
78 }
79
80 /**************************************************************************/
81
82 static boolean
ismax(permutation * p,int n)83 ismax(permutation *p, int n)
84 /* test if x^p <= x */
85 {
86 int i,k;
87
88 for (i = 0; i < nix; ++i)
89 {
90 k = edgeno[p[v1[i]]][p[v0[i]]];
91
92 if (ix[k] > ix[i])
93 return FALSE;
94 else if (ix[k] < ix[i])
95 return TRUE;
96 }
97
98 ++newgroupsize;
99 return TRUE;
100 }
101
102 /**************************************************************************/
103
104 void
testmax(permutation * p,int n,int * abort)105 testmax(permutation *p, int n, int *abort)
106 /* Called by allgroup2. */
107 {
108 int i,j,k;
109
110 if (first)
111 { /* only the identity */
112 first = FALSE;
113 return;
114 }
115
116 if (!ismax(p,n))
117 {
118 *abort = 1;
119 for (i = 0; i < n; ++i) lastreject[i] = p[i];
120 lastrejok = TRUE;
121 }
122 }
123
124 /**************************************************************************/
125
126 void
printam(FILE * f,int n,int ne,int * ix)127 printam(FILE *f, int n, int ne, int *ix)
128 /* Write adjacency matrix formats */
129 {
130 int i,j,k;
131
132 if (Aswitch)
133 {
134 fprintf(f,"%d ",n);
135 for (i = 0; i < n; ++i)
136 for (j = i; j < n; ++j)
137 fprintf(f," %d",ix[edgeno[i][j]]);
138 fprintf(f,"\n");
139 }
140 else
141 {
142 if (Brows <= 0 || Brows > n)
143 {
144 fprintf(stderr,">E multig: impossible matrix size for output\n");
145 exit(1);
146 }
147 fprintf(f,"%d %d",Brows,n-Brows);
148
149 for (i = 0; i < Brows; ++i)
150 {
151 fprintf(f," ");
152 for (j = Brows; j < n; ++j)
153 fprintf(f," %d",ix[edgeno[i][j]]);
154 }
155 fprintf(f,"\n");
156 }
157 }
158
159 /**************************************************************************/
160
161 static void
trythisone(grouprec * group,int ne,int n)162 trythisone(grouprec *group, int ne, int n)
163 {
164 int i,k;
165 boolean accept;
166
167 ADDBIG(ngen,1);
168 nix = ne;
169 newgroupsize = 1;
170
171 if (!group || groupsize == 1)
172 accept = TRUE;
173 else if (lastrejok && !ismax(lastreject,n))
174 accept = FALSE;
175 else if (lastrejok && groupsize == 2)
176 accept = TRUE;
177 else
178 {
179 newgroupsize = 1;
180 first = TRUE;
181
182 if (allgroup2(group,testmax) == 0)
183 accept = TRUE;
184 else
185 accept = FALSE;
186 }
187
188 if (accept)
189 {
190
191 #ifdef GROUPTEST
192 if (groupsize % newgroupsize != 0)
193 gt_abort("group size error\n");
194 totallab += groupsize/newgroupsize;
195 #endif
196
197 ADDBIG(nout,1);
198
199 if (outfile)
200 {
201 if (Aswitch || Bswitch)
202 printam(outfile,n,ne,ix);
203
204 else
205 {
206 fprintf(outfile,"%d %ld",n,ne);
207 if (Gswitch) fprintf(outfile," %lu",newgroupsize);
208
209 for (i = 0; i < ne; ++i)
210 fprintf(outfile," %d %d %d",v0[i],v1[i],ix[i]);
211 fprintf(outfile,"\n");
212 }
213 }
214 return;
215 }
216 else
217 return;
218 }
219
220 /**************************************************************************/
221
222 static void
scan(int level,int ne,int minedges,int maxedges,int sofar,int maxmult,grouprec * group,int n)223 scan(int level, int ne, int minedges, int maxedges, int sofar,
224 int maxmult, grouprec *group, int n)
225 /* Main recursive scan; returns the level to return to. */
226 {
227 int k;
228 int min,max,left;
229
230 if (level == ne)
231 {
232 trythisone(group,ne,n);
233 return;
234 }
235
236 left = ne - level - 1;
237 min = minedges - sofar - maxmult*left;
238 if (min < 1) min = 1;
239 max = maxedges - sofar - left;
240 if (max > maxmult) max = maxmult;
241
242 for (k = min; k <= max; ++k)
243 {
244 ix[level] = k;
245 scan(level+1,ne,minedges,maxedges,sofar+k,maxmult,group,n);
246 }
247
248 return;
249 }
250
251 /**************************************************************************/
252
253 static void
multi(graph * g,int nfixed,long minedges,long maxedges,long maxmult,int m,int n)254 multi(graph *g, int nfixed, long minedges, long maxedges, long maxmult,
255 int m, int n)
256 {
257 static DEFAULTOPTIONS_GRAPH(options);
258 statsblk(stats);
259 setword workspace[100];
260 grouprec *group;
261 long ne;
262 int i,j,k,j0,j1,deg;
263 set *gi;
264 int lab[MAXNV],ptn[MAXNV],orbits[MAXNV];
265 set active[(MAXNV+WORDSIZE-1)/WORDSIZE];
266
267 nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
268
269 j0 = -1; /* last vertex with degree 0 */
270 j1 = n; /* first vertex with degree > 0 */
271
272 ne = 0;
273 for (i = 0, gi = g; i < n; ++i, gi += m)
274 {
275 deg = 0;
276 for (j = 0; j < m; ++j) deg += POPCOUNT(gi[j]);
277 if (deg == 0) lab[++j0] = i;
278 else lab[--j1] = i;
279 ne += deg;
280 }
281 ne /= 2;
282
283 if (ne == 0 && minedges <= 0)
284 {
285 trythisone(NULL,0,n);
286 return;
287 }
288
289 if (maxedges == NOLIMIT) maxedges = ne*maxmult;
290 if (maxmult == NOLIMIT) maxmult = maxedges - ne + 1;
291 if (maxedges < ne || ne*maxmult < minedges) return;
292
293 if (n > MAXNV || ne > MAXNE)
294 {
295 fprintf(stderr,">E multig: MAXNV or MAXNE exceeded\n");
296 exit(1);
297 }
298
299 for (i = 0; i < n; ++i) ptn[i] = 1;
300 ptn[n-1] = 0;
301 EMPTYSET(active,m);
302 if (j0 != n-1) ADDELEMENT(active,j0+1);
303
304 for (i = 0; i <= j0; ++i) ptn[i] = 0;
305
306 for (i = j0+1; i < n; ++i)
307 if (lab[i] < nfixed) break;
308
309 if (i != j0+1 && i != n)
310 {
311 ptn[i-1] = 0;
312 ADDELEMENT(active,i);
313 }
314
315 options.defaultptn = FALSE;
316 options.userautomproc = groupautomproc;
317 options.userlevelproc = grouplevelproc;
318
319 nauty(g,lab,ptn,active,orbits,&options,&stats,workspace,100,m,n,NULL);
320
321 if (stats.grpsize2 == 0)
322 groupsize = stats.grpsize1 + 0.1;
323 else
324 groupsize = 0;
325
326 group = groupptr(FALSE);
327 makecosetreps(group);
328
329 if (Aswitch || Bswitch)
330 for (i = 0; i < n; ++i)
331 for (j = 0; j < n; ++j)
332 edgeno[i][j] = -1;
333
334 k = 0;
335 for (i = 0, gi = g; i < n; ++i, gi += m)
336 {
337 for (j = i; (j = nextelement(gi,m,j)) >= 0; )
338 {
339 v0[k] = i;
340 v1[k] = j;
341 edgeno[i][j] = edgeno[j][i] = k;
342 ++k;
343 }
344 }
345
346 lastrejok = FALSE;
347
348 scan(0,ne,minedges,maxedges,0,maxmult,group,n);
349 }
350
351 /**************************************************************************/
352
main(int argc,char * argv[])353 main(int argc, char *argv[])
354 {
355 graph *g;
356 int m,n,codetype;
357 int argnum,j,outcode,nfixed;
358 char *arg,sw,*fmt;
359 boolean badargs;
360 boolean fswitch,uswitch,eswitch,qswitch,mswitch;
361 long minedges,maxedges,maxmult;
362 double t;
363 char *infilename,*outfilename;
364 FILE *infile;
365 #if MAXN
366 graph h[MAXN*MAXM];
367 #else
368 DYNALLSTAT(graph,h,h_sz);
369 #endif
370
371 HELP;
372
373 nauty_check(WORDSIZE,1,1,NAUTYVERSIONID);
374
375 fswitch = Tswitch = Gswitch = FALSE;
376 uswitch = eswitch = mswitch = qswitch = FALSE;
377 Aswitch = Bswitch = FALSE;
378 infilename = outfilename = NULL;
379
380 argnum = 0;
381 badargs = FALSE;
382 for (j = 1; !badargs && j < argc; ++j)
383 {
384 arg = argv[j];
385 if (arg[0] == '-' && arg[1] != '\0')
386 {
387 ++arg;
388 while (*arg != '\0')
389 {
390 sw = *arg++;
391 SWLONG('m',mswitch,maxmult,"multig -m")
392 else SWBOOLEAN('q',qswitch)
393 else SWBOOLEAN('u',uswitch)
394 else SWBOOLEAN('T',Tswitch)
395 else SWBOOLEAN('G',Gswitch)
396 else SWBOOLEAN('A',Aswitch)
397 else SWBOOLEAN('B',Bswitch)
398 else SWINT('f',fswitch,nfixed,"multig -f")
399 else SWRANGE('e',":-",eswitch,minedges,maxedges,"multig -e")
400 else badargs = TRUE;
401 }
402 }
403 else
404 {
405 ++argnum;
406 if (argnum == 1) infilename = arg;
407 else if (argnum == 2) outfilename = arg;
408 else badargs = TRUE;
409 }
410 }
411
412 if (badargs || argnum > 2)
413 {
414 fprintf(stderr,">E Usage: %s\n",USAGE);
415 GETHELP;
416 exit(1);
417 }
418
419 if ((Gswitch!=0) + (Tswitch!=0) + (uswitch!=0)
420 + (Aswitch!=0) + (Bswitch!=0) >= 2)
421 gt_abort(">E multig: -G, -T, -A, -B and -u are incompatible\n");
422
423 if (!Tswitch && !Gswitch && !Aswitch && !Bswitch && !uswitch)
424 gt_abort(">E multig: must use -A, -B, -T, -G or -u\n");
425
426 if (!eswitch)
427 {
428 minedges = 0;
429 maxedges = NOLIMIT;
430 }
431 if (!mswitch) maxmult = NOLIMIT;
432 if (!fswitch) nfixed = 0;
433
434 if (Bswitch && nfixed == 0)
435 gt_abort(">E multig: -B requires -f# with #>0\n");
436 if (fswitch) Brows = nfixed;
437
438 if (maxedges >= NOLIMIT && maxmult >= NOLIMIT)
439 gt_abort(">E multig: either -e or -m must impose a real limit\n");
440
441 if (!qswitch)
442 {
443 fprintf(stderr,">A multig");
444 if (eswitch || mswitch || uswitch || fswitch && nfixed > 0
445 || Tswitch || Gswitch || Aswitch || Bswitch)
446 fprintf(stderr," -");
447 if (mswitch) fprintf(stderr,"m%ld",maxmult);
448 if (uswitch) fprintf(stderr,"u");
449 if (Tswitch) fprintf(stderr,"T");
450 if (Tswitch) fprintf(stderr,"G");
451 if (Tswitch) fprintf(stderr,"A");
452 if (Tswitch) fprintf(stderr,"B");
453 if (fswitch) fprintf(stderr,"f%d",nfixed);
454 if (eswitch)
455 fprintf(stderr,"e%d:%d",minedges,maxedges);
456 if (argnum > 0) fprintf(stderr," %s",infilename);
457 if (argnum > 1) fprintf(stderr," %s",outfilename);
458 fprintf(stderr,"\n");
459 fflush(stderr);
460 }
461
462 if (infilename && infilename[0] == '-') infilename = NULL;
463 infile = opengraphfile(infilename,&codetype,FALSE,1);
464 if (!infile) exit(1);
465 if (!infilename) infilename = "stdin";
466
467 if (uswitch)
468 outfile = NULL;
469 else
470 {
471 if (!outfilename || outfilename[0] == '-')
472 {
473 outfilename = "stdout";
474 outfile = stdout;
475 }
476 else if ((outfile = fopen(outfilename,"w")) == NULL)
477 {
478 fprintf(stderr,"Can't open output file %s\n",outfilename);
479 gt_abort(NULL);
480 }
481 }
482
483 ZEROBIG(nin); ZEROBIG(ngen); ZEROBIG(nout);
484
485 t = CPUTIME;
486 while (TRUE)
487 {
488 if ((g = readg(infile,NULL,0,&m,&n)) == NULL) break;
489 ADDBIG(nin,1);
490 multi(g,nfixed,minedges,maxedges,maxmult,m,n);
491 FREES(g);
492 }
493 t = CPUTIME - t;
494
495 if (!qswitch)
496 {
497 fprintf(stderr,">Z ");
498 PRINTBIG(stderr,nin);
499 fprintf(stderr," graphs read from %s",infilename);
500 /* fprintf(stderr,"; ");
501 PRINTBIG(stderr,ngen);
502 fprintf(stderr,"; %lu multigraphs tested",ngen); */
503 fprintf(stderr,"; ");
504 PRINTBIG(stderr,nout);
505 if (!uswitch)
506 fprintf(stderr," multigraphs written to %s",outfilename);
507 else
508 fprintf(stderr," multigraphs generated");
509 fprintf(stderr,"; %.2f sec\n",t);
510 }
511
512 #ifdef GROUPTEST
513 fprintf(stderr,"Group test = %lld\n",totallab);
514 #endif
515
516 exit(0);
517 }
518