1 /* genrang.c version 2.3; B D McKay, July 13, 2017 */
2 /* TODO: Check allocs for no edges */
3
4 #define USAGE \
5 "genrang [-P#|-P#/#|-e#|-r#|-R#|-d#] [-l#] [-m#] [-t] [-T] [-a] \n" \
6 " [-s|-g|-z] [-S#] [-q] n|n1,n2 num [outfile]"
7
8 #define HELPTEXT \
9 " Generate random graphs.\n\
10 n : number of vertices\n\
11 n1,n2 : number of vertices (bipartite graph)\n\
12 num : number of graphs\n\
13 \n\
14 A bipartite variant is only available if specified below.\n\
15 \n\
16 -s : Write in sparse6 format (default)\n\
17 -g : Write in graph6 format\n\
18 -z : Make random digraphs and write in digraph6 format\n\
19 -P#/# : Give edge probability; -P# means -P1/#.\n\
20 Bipartite version available.\n\
21 -e# : Give the number of edges\n\
22 Bipartite version available.\n\
23 -r# : Make regular of specified degree\n\
24 -d# : Make regular of specified degree (pseudorandom)\n\
25 Bipartite version: this is the degree on the first side\n\
26 -R# : Make regular of specified degree but output\n\
27 as vertex count, edge count, then list of edges\n\
28 -l# : Maximum loop multiplicity (default 0)\n\
29 -m# : Maximum multiplicity of non-loop edge (default and minimum 1)\n\
30 -t : Make a random spanning tree of a complete graph\n\
31 or complete bipartite graph\n\
32 -T : Make a random tournament (implies -z)\n\
33 -a : Make invariant under a random permutation\n\
34 -S# : Specify random generator seed (default nondeterministic)\n\
35 -q : suppress auxiliary output\n"
36
37 #define MAXLREG 88 /* Max value for -r or -R switch (multigraphs) */
38 /* This is also the limit for -r if MAXN > 0. */
39 /* The limit for simple graphs is in naututil-h.in */
40
41 /*************************************************************************
42
43 Oct 27, 2004 : corrected handling of -P values
44 **************************************************************************/
45
46 #include "gtools.h"
47
48 static long seed;
49
50 /*************************************************************************/
51
52 static void
perminvar(graph * g,int * perm,int m,int n)53 perminvar(graph *g, int *perm, int m, int n)
54 /* Add to g the least number of edges needed to make perm
55 an automorphism. */
56 {
57 int i,j,ii,jj;
58 set *gi,*gpi;
59
60 for (i = 0, gi = (set*)g; i < n; ++i, gi += m)
61 {
62 gpi = g + m * 1L * perm[i];
63 for (j = -1; (j = nextelement(gi,m,j)) >= 0; )
64 if (!ISELEMENT(gpi,perm[j]))
65 {
66 ii = perm[i];
67 jj = perm[j];
68 while (ii != i || jj != j)
69 {
70 ADDELEMENT(g+m*1L*ii,jj);
71 ii = perm[ii];
72 jj = perm[jj];
73 }
74 }
75 }
76 }
77
78 /**************************************************************************/
79
80 static void
gcomplement(graph * g,boolean loopstoo,int m,int n)81 gcomplement(graph *g, boolean loopstoo, int m, int n)
82 /* Replace g by its complement */
83 {
84 int i,j;
85 graph *gp;
86 #if MAXN
87 set mask[MAXM];
88 #else
89 DYNALLSTAT(set,mask,mask_sz);
90 DYNALLOC1(set,mask,mask_sz,m,"complement");
91 #endif
92
93 EMPTYSET(mask,m);
94 for (i = 0; i < n; ++i) ADDELEMENT(mask,i);
95
96 if (loopstoo)
97 {
98 for (i = 0, gp = g; i < n; ++i, gp += m)
99 {
100 for (j = 0; j < m; ++j) gp[j] ^= mask[j];
101 }
102 }
103 else
104 {
105 for (i = 0, gp = g; i < n; ++i, gp += m)
106 {
107 DELELEMENT(mask,i);
108 for (j = 0; j < m; ++j) gp[j] ^= mask[j];
109 ADDELEMENT(mask,i);
110 }
111 }
112 }
113
114 /**************************************************************************/
115
116 static void
gcomplement_bip(graph * g,int m,int n1,int n2)117 gcomplement_bip(graph *g, int m, int n1, int n2)
118 /* Replace g by its bipartite complement */
119 {
120 int i,j,n;
121 graph *gp;
122 #if MAXN
123 set mask[MAXM];
124 #else
125 DYNALLSTAT(set,mask,mask_sz);
126 DYNALLOC1(set,mask,mask_sz,m,"complement");
127 #endif
128
129 n = n1 + n2;
130
131 EMPTYSET(mask,m);
132 for (i = n1; i < n; ++i) ADDELEMENT(mask,i);
133
134 for (i = 0, gp = g; i < n1; ++i, gp += m)
135 for (j = 0; j < m; ++j) gp[j] ^= mask[j];
136
137 EMPTYSET(mask,m);
138 for (i = 0; i < n1; ++i) ADDELEMENT(mask,i);
139
140 for (i = n1, gp = GRAPHROW(g,n1,m); i < n; ++i, gp += m)
141 for (j = 0; j < m; ++j) gp[j] ^= mask[j];
142 }
143
144 /**************************************************************************/
145
146 static void
ranedges(long e,boolean loopsok,graph * g,int m,int n)147 ranedges(long e, boolean loopsok, graph *g, int m, int n)
148 /* Random graph with n vertices and e edges */
149 {
150 unsigned long ln,li,nc2,ned,sofar;
151 set *gi,*gj;
152 int i,j;
153
154 ln = n;
155 nc2 = (ln&1) ? ln*((ln-1)/2) : (ln/2)*(ln-1);
156 if (loopsok) nc2 += ln;
157
158 if (e + e > nc2) ned = nc2 - e;
159 else ned = e;
160 sofar = 0;
161
162 for (li = m*ln; --li != 0;) g[li] = 0;
163 g[0] = 0;
164
165 while (sofar < ned)
166 {
167 i = KRAN(n);
168 if (loopsok) j = KRAN(n);
169 else do { j = KRAN(n); } while (i == j);
170 gi = GRAPHROW(g,i,m);
171 if (!ISELEMENT(gi,j))
172 {
173 ADDELEMENT(gi,j);
174 gj = GRAPHROW(g,j,m);
175 ADDELEMENT(gj,i);
176 ++sofar;
177 }
178 }
179
180 if (ned != e) gcomplement(g,loopsok,m,n);
181 }
182
183 /**************************************************************************/
184
185 static void
ranedges_bip(long e,graph * g,int m,int n1,int n2)186 ranedges_bip(long e, graph *g, int m, int n1, int n2)
187 /* Random bipartite graph with n1+n2 vertices and e edges */
188 {
189 size_t li,nc2,ned,sofar;
190 set *gi,*gj;
191 int i,j,n;
192
193 n = n1 + n2;
194 nc2 = (size_t)n1*n2;
195
196 if (e + e > nc2) ned = nc2 - e;
197 else ned = e;
198 sofar = 0;
199
200 for (li = m*(size_t)n; --li != 0;) g[li] = 0;
201 g[0] = 0;
202
203 while (sofar < ned)
204 {
205 i = KRAN(n1);
206 j = n1 + KRAN(n2);
207 gi = GRAPHROW(g,i,m);
208 if (!ISELEMENT(gi,j))
209 {
210 ADDELEMENT(gi,j);
211 gj = GRAPHROW(g,j,m);
212 ADDELEMENT(gj,i);
213 ++sofar;
214 }
215 }
216
217 if (ned != e) gcomplement_bip(g,m,n1,n2);
218 }
219
220 /**************************************************************************/
221
222 static void
grandtourn(graph * g,int m,int n)223 grandtourn(graph *g, int m, int n)
224 /* Random tournament */
225 {
226 int i,j;
227 long li;
228 set *row,*col;
229
230 for (li = (long)m * (long)n; --li >= 0;) g[li] = 0;
231
232 for (i = 0, row = g; i < n; ++i, row += m)
233 {
234 for (j = i+1, col = GRAPHROW(g,i+1,m); j < n; ++j, col += m)
235 if (KRAN(2) < 1) ADDELEMENT(row,j);
236 else ADDELEMENT(col,i);
237 }
238 }
239
240 /**************************************************************************/
241
242 static void
grandtourn_bip(graph * g,int m,int n1,int n2)243 grandtourn_bip(graph *g, int m, int n1, int n2)
244 /* Random bipartite tournament */
245 {
246 int i,j,n;
247 long li;
248 set *row,*col;
249
250 n = n1 + n2;
251 for (li = (long)m * (long)n; --li >= 0;) g[li] = 0;
252
253 for (i = 0, row = g; i < n1; ++i, row += m)
254 {
255 for (j = n1, col = GRAPHROW(g,n1,m); j < n; ++j, col += m)
256 if (KRAN(2) < 1) ADDELEMENT(row,j);
257 else ADDELEMENT(col,i);
258 }
259 }
260
261 /**************************************************************************/
262
263 static void
grandgraph(graph * g,boolean digraph,boolean loopsok,int p1,int p2,int m,int n)264 grandgraph(graph *g, boolean digraph, boolean loopsok,
265 int p1, int p2, int m, int n)
266 /* Random graph with probability p1/p2 */
267 {
268 int i,j;
269 long li;
270 set *row,*col;
271
272 for (li = (long)m * (long)n; --li >= 0;) g[li] = 0;
273
274 for (i = 0, row = g; i < n; ++i, row += m)
275 if (digraph)
276 {
277 for (j = 0; j < n; ++j)
278 if (KRAN(p2) < p1) ADDELEMENT(row,j);
279 if (!loopsok) DELELEMENT(row,i);
280 }
281 else
282 {
283 for (j = i + (!loopsok), col = GRAPHROW(g,j,m);
284 j < n; ++j, col += m)
285 if (KRAN(p2) < p1)
286 {
287 ADDELEMENT(row,j);
288 ADDELEMENT(col,i);
289 }
290 }
291 }
292
293 /**************************************************************************/
294
295 static void
grandgraph_bip(graph * g,boolean digraph,int p1,int p2,int m,int n1,int n2)296 grandgraph_bip(graph *g, boolean digraph,
297 int p1, int p2, int m, int n1, int n2)
298 /* Random bipartite graph with probability p1/p2 */
299 {
300 int i,j,n;
301 long li;
302 set *row,*col;
303
304 n = n1 + n2;
305
306 for (li = (long)m * (long)n; --li >= 0;) g[li] = 0;
307
308 for (i = 0, row = g; i < n1; ++i, row += m)
309 if (digraph)
310 {
311 for (j = n1; j < n; ++j)
312 if (KRAN(p2) < p1) ADDELEMENT(row,j);
313 }
314 else
315 {
316 for (j = n1, col = GRAPHROW(g,j,m);
317 j < n; ++j, col += m)
318 if (KRAN(p2) < p1)
319 {
320 ADDELEMENT(row,j);
321 ADDELEMENT(col,i);
322 }
323 }
324 }
325
326 /**************************************************************************/
327
328 static void
ranarcs(long e,boolean loopsok,graph * g,int m,int n)329 ranarcs(long e, boolean loopsok, graph *g, int m, int n)
330 /* Random digraph graph with n vertices and e edges */
331 {
332 unsigned long ln,li,nn,ned,sofar;
333 set *gi;
334 int i,j;
335
336 ln = n;
337 nn = (loopsok ? n*n : n*(n-1));
338
339 if (e + e > nn) ned = nn - e;
340 else ned = e;
341 sofar = 0;
342
343 for (li = m*ln; --li != 0;) g[li] = 0;
344 g[0] = 0;
345
346 while (sofar < ned)
347 {
348 i = KRAN(n);
349 if (loopsok) j = KRAN(n);
350 else do { j = KRAN(n); } while (i == j);
351 gi = GRAPHROW(g,i,m);
352 if (!ISELEMENT(gi,j))
353 {
354 ADDELEMENT(gi,j);
355 ++sofar;
356 }
357 }
358
359 if (ned != e) gcomplement(g,loopsok,m,n);
360 }
361
362 /**************************************************************************/
363
364 static void
makeranreg(int * cub,int degree,int multmax,int loopmax,int n)365 makeranreg(int *cub, int degree, int multmax, int loopmax, int n)
366 /* Make a random regular graph in cub[]. Each consecutive degree
367 entries of cub[] is set to the neighbours of one vertex.
368 The length of cub had better be at least degree*n */
369 {
370 long i,j,k,v,w,nn,mult;
371 boolean ok;
372 #if MAXN
373 int deg[MAXN],p[MAXLREG*MAXN];
374 #else
375 DYNALLSTAT(int,deg,deg_sz);
376 DYNALLSTAT(int,p,p_sz);
377 DYNALLSTAT(int,loops,loops_sz);
378
379 DYNALLOC1(int,deg,deg_sz,n,"genrang");
380 DYNALLOC2(int,p,p_sz,degree,n,"genrang");
381 DYNALLOC1(int,loops,loops_sz,n,"genrang");
382 #endif
383
384 nn = n;
385
386 for (i = j = 0; i < nn; ++i)
387 for (k = 0; k < degree; ++k)
388 p[j++] = i;
389
390 do
391 {
392 ok = TRUE;
393
394 for (j = degree*nn-1; j >= 1; j -= 2)
395 {
396 i = KRAN(j);
397 k = p[j-1];
398 p[j-1] = p[i];
399 p[i] = k;
400 }
401 for (i = 0; i < nn; ++i) deg[i] = loops[i] = 0;
402
403 for (j = degree*nn-1; j >= 1;)
404 {
405 v = p[j--];
406 w = p[j--];
407 if (v == w && ++loops[v] > loopmax)
408 {
409 ok = FALSE;
410 break;
411 }
412 if (v != w && multmax < degree)
413 {
414 mult = 0;
415 for (i = deg[w]; --i >= 0;)
416 if (cub[degree*w+i] == v && ++mult >= multmax) break;
417 if (i >= 0)
418 {
419 ok = FALSE;
420 break;
421 }
422 }
423 cub[degree*w+deg[w]++] = v;
424 cub[degree*v+deg[v]++] = w;
425 }
426 }
427 while (!ok);
428 }
429
430 /**************************************************************************/
431
432 static void
rundmodel(int * cub,int degree,int n)433 rundmodel(int *cub, int degree, int n)
434 /* Make a random-ish regular graph in cub[] using the d-model.
435 Each consecutive degree entries of cub[] is set to the neighbours
436 of one vertex. The length of cub had better be at least degree*n */
437 {
438 long iters,fails;
439 size_t i,j,navail;
440 int *cubi,*cubj,vi,vj,k;
441 boolean ok;
442 #if MAXN
443 int deg[MAXN],avail[MAXN*MAXLREG];
444 #else
445 DYNALLSTAT(int,deg,deg_sz);
446 DYNALLSTAT(int,avail,avail_sz);
447
448 DYNALLOC1(int,deg,deg_sz,n,"genrang");
449 DYNALLOC2(int,avail,avail_sz,n,degree,"genrang");
450 #endif
451
452 iters = 0;
453 do
454 {
455 ok = TRUE;
456 ++iters;
457
458 k = 0;
459 for (i = 0; i < n; ++i)
460 {
461 deg[i] = 0;
462 for (j = 0; j < degree; ++j) avail[k++] = i;
463 }
464 navail = n*degree;
465
466 while (navail >= 2 && ok)
467 {
468 for (fails = 100 + navail; --fails >= 0;)
469 {
470 i = KRAN(navail);
471 do { j = KRAN(navail); } while (j == i);
472 vi = avail[i];
473 vj = avail[j];
474 if (vi == vj) continue;
475 cubi = cub + vi*degree;
476 cubj = cub + vj*degree;
477 for (k = deg[vi]; --k >= 0; ) if (cubi[k] == vj) break;
478 if (k < 0) break;
479 }
480
481 if (fails >= 0)
482 {
483 cubi[deg[vi]++] = vj;
484 cubj[deg[vj]++] = vi;
485
486 avail[i] = avail[navail-1];
487 --navail;
488 if (avail[i] == vj) j = i;
489
490 avail[j] = avail[navail-1];
491 --navail;
492 }
493 else
494 ok = FALSE;
495 }
496 if (navail > 0) ok = FALSE;
497 } while (!ok);
498
499 /* fprintf(stderr,">C %ld iters\n",iters); */
500 }
501
502 /**************************************************************************/
503
504 static void
ranregR(FILE * f,int degree,int multmax,int loopmax,int n)505 ranregR(FILE *f, int degree, int multmax, int loopmax, int n)
506 /* Make a random regular graph of order n and degree d and write
507 it in f, as number of vertices, number of edges, list of edges */
508 {
509 long i,j,k,l;
510 int loops;
511 #if MAXN
512 int cub[MAXLREG*MAXN];
513 #else
514 DYNALLSTAT(int,cub,cub_sz);
515 DYNALLOC2(int,cub,cub_sz,degree,n,"genrang");
516 #endif
517
518 makeranreg(cub,degree,multmax,loopmax,n);
519
520 fprintf(f,"%d %ld\n",n,n*(long)degree/2);
521 l = j = 0;
522 for (i = 0; i < n; ++i)
523 {
524 loops = 0;
525 for (k = 0; k < degree; ++k, ++j)
526 if (i < cub[j] || (i == cub[j] && (++loops & 1) == 0))
527 {
528 if (l > 0 && l % 5 == 0) fprintf(f,"\n");
529 fprintf(f," %ld %d",i,cub[j]);
530 ++l;
531 }
532 }
533 fprintf(f,"\n");
534 if (ferror(f)) gt_abort(">E genrang output error\n");
535 }
536
537 /**************************************************************************/
538
539 static void
ranreg(int degree,graph * g,int m,int n)540 ranreg(int degree, graph *g, int m, int n)
541 /* Make a random simple regular graph of order n and degree d and return
542 it in g. */
543 {
544 int i,j,k;
545 set *gi;
546 #if MAXN
547 int cub[MAXLREG*MAXN];
548 #else
549 DYNALLSTAT(int,cub,cub_sz);
550 DYNALLOC1(int,cub,cub_sz,degree*n,"genrang");
551 #endif
552
553 makeranreg(cub,degree,1,0,n);
554
555 j = 0;
556 for (i = 0, gi = (set*)g; i < n; ++i, gi += m)
557 {
558 EMPTYSET(gi,m);
559 for (k = 0; k < degree; ++k)
560 {
561 ADDELEMENT(gi,cub[j]);
562 j++;
563 }
564 }
565 }
566
567 /**************************************************************************/
568
569 static void
ranreglm_sg(int degree,sparsegraph * sg,int multmax,int loopmax,int n)570 ranreglm_sg(int degree, sparsegraph *sg, int multmax, int loopmax, int n)
571 /* Make a sparse random regular graph of order n and degree d
572 * and return it in sg. */
573 {
574 int i,j,k,deg,loops;
575 long nde,k0;
576 #if MAXN
577 int cub[MAXLREG*MAXN];
578 #else
579 DYNALLSTAT(int,cub,cub_sz);
580 DYNALLOC1(int,cub,cub_sz,degree*n,"genrang");
581 #endif
582
583 makeranreg(cub,degree,multmax,loopmax,n);
584
585 SG_ALLOC(*sg,n,degree*n,"genrang");
586
587 sg->nv = n;
588 j = nde = 0;
589 for (i = 0; i < n; ++i)
590 {
591 sg->v[i] = k0 = i*degree;
592 loops = deg = 0;
593 for (k = 0; k < degree; ++k, ++j)
594 {
595 if (cub[j] == i)
596 {
597 /* Loops are in cub twice but sg once */
598 ++loops;
599 if ((loops&1)) sg->e[k0+deg++] = i;
600 }
601 else
602 sg->e[k0+deg++] = cub[j];
603 }
604 sg->d[i] = deg;
605 nde += deg;
606 }
607 sg->nde = nde;
608 }
609
610 /**************************************************************************/
611
612 static void
dmodel_sg(int degree,sparsegraph * sg,int n)613 dmodel_sg(int degree, sparsegraph *sg, int n)
614 /* Make a sparse random-ish regular graph of order n and degree d
615 * and return it in sg. */
616 {
617 int i,j,k,deg,comdeg;
618 long k0,nde;
619 #if MAXN
620 int cub[MAXLREG*MAXN];
621 boolean adj[MAXN];
622 #else
623 DYNALLSTAT(int,cub,cub_sz);
624 DYNALLSTAT(boolean,adj,adj_sz);
625 #endif
626
627 SG_ALLOC(*sg,n,degree*n,"dmodel_sg");
628
629 if (degree <= n-degree-1)
630 {
631 #if !MAXN
632 DYNALLOC1(int,cub,cub_sz,degree*n,"dmodel_sg");
633 #endif
634 rundmodel(cub,degree,n);
635
636 sg->nv = n;
637 j = nde = 0;
638 for (i = 0; i < n; ++i)
639 {
640 sg->v[i] = k0 = i*(long)degree;
641 deg = 0;
642 for (k = 0; k < degree; ++k, ++j)
643 sg->e[k0+deg++] = cub[j];
644 sg->d[i] = deg;
645 nde += deg;
646 }
647 sg->nde = nde;
648 }
649 else
650 {
651 comdeg = n - degree - 1;
652 #if !MAXN
653 DYNALLOC1(int,cub,cub_sz,comdeg*n,"dmodel_sg");
654 DYNALLOC1(boolean,adj,adj_sz,n,"dmodel_sg");
655 #endif
656 rundmodel(cub,comdeg,n);
657
658 sg->nv = n;
659 j = nde = 0;
660 for (i = 0; i < n; ++i)
661 {
662 sg->v[i] = k0 = i*(long)degree;
663 deg = 0;
664 for (k = 0; k < n; ++k) adj[k] = TRUE;
665 adj[i] = FALSE;
666 for (k = 0; k < comdeg; ++k, ++j) adj[cub[j]] = FALSE;
667 for (k = 0; k < n; ++k)
668 if (adj[k]) sg->e[k0+deg++] = k;
669 sg->d[i] = deg;
670 nde += deg;
671 }
672 sg->nde = nde;
673 }
674 }
675
676 /**************************************************************************/
677
678 static void
rundmodel_bip(int * cub,int deg1,int deg2,int n1,int n2)679 rundmodel_bip(int *cub, int deg1, int deg2, int n1, int n2)
680 /* Make a random-ish semiregular bipartite graph in cub[] using the d-model.
681 Each consecutive deg1/deg2 entries of cub[] is set to the neighbours
682 of one vertex. The length of cub had better be deg1*n1 */
683 {
684 long iters,fails;
685 size_t i,j,k,navail,ne;
686 int *cubi,*cubj,vi,vj,n;
687 boolean ok;
688 #if MAXN
689 int deg[MAXN],avail[MAXN*MAXLREG];
690 #else
691 DYNALLSTAT(int,deg,deg_sz);
692 DYNALLSTAT(int,avail,avail_sz);
693
694 n = n1 + n2;
695 DYNALLOC1(int,deg,deg_sz,n,"genrang");
696 DYNALLOC2(int,avail,avail_sz,n,2*deg1,"genrang");
697 #endif
698
699 ne = n1*(size_t)deg1;
700
701 iters = 0;
702 do
703 {
704 ok = TRUE;
705 ++iters;
706
707 k = 0;
708 for (i = 0; i < n1; ++i)
709 {
710 deg[i] = 0;
711 for (j = 0; j < deg1; ++j) avail[k++] = i;
712 }
713 for (i = n1; i < n; ++i)
714 {
715 deg[i] = 0;
716 for (j = 0; j < deg2; ++j) avail[k++] = i;
717 }
718 navail = ne;
719
720 while (navail >= 1 && ok)
721 {
722 for (fails = 100 + navail; --fails >= 0;)
723 {
724 i = KRAN(navail);
725 j = ne + KRAN(navail);
726 vi = avail[i];
727 vj = avail[j];
728 cubi = cub + vi*deg1;
729 cubj = cub + ne + (vj-n1)*deg2;
730 for (k = 0; k < deg[vi]; ++k) if (cubi[k] == vj) break;
731 if (k == deg[vi]) break;
732 }
733
734 if (fails >= 0)
735 {
736 cubi[deg[vi]++] = vj;
737 cubj[deg[vj]++] = vi;
738
739 avail[i] = avail[navail-1];
740 avail[j] = avail[ne+navail-1];
741 --navail;
742 }
743 else
744 ok = FALSE;
745 }
746 if (navail > 0) ok = FALSE;
747 } while (!ok);
748
749 /* fprintf(stderr,">C %ld iters\n",iters); */
750 }
751
752 /**************************************************************************/
753
754 static void
dmodel_bip_sg(int deg1,sparsegraph * sg,int n1,int n2)755 dmodel_bip_sg(int deg1, sparsegraph *sg, int n1, int n2)
756 /* Make a sparse random-ish semiregular bipartite graph of order n1+n2
757 and degree deg1 on the left and return it in sg. */
758 {
759 int i,k,deg,comdeg1,comdeg2,n,deg2;
760 size_t j,k0,nde,ne,comne;
761 #if MAXN
762 int cub[MAXLREG*MAXN];
763 boolean adj[MAXN];
764 #else
765 DYNALLSTAT(int,cub,cub_sz);
766 DYNALLSTAT(boolean,adj,adj_sz);
767 #endif
768
769 n = n1 + n2;
770 ne = n1*(size_t)deg1;
771 deg2 = ne / n2;
772 if (deg2*(size_t)n2 != ne || deg1 > n2 || deg2 > n1)
773 gt_abort(">E genrang: impossible bipartite degrees\n");
774
775 SG_ALLOC(*sg,n,2*ne,"dmodel_bip_sg");
776
777 if (deg1 <= n2-deg1)
778 {
779 #if !MAXN
780 DYNALLOC1(int,cub,cub_sz,2*ne,"dmodel_bip_sg");
781 #endif
782 rundmodel_bip(cub,deg1,deg2,n1,n2);
783
784 sg->nv = n;
785 j = nde = 0;
786 for (i = 0; i < n1; ++i)
787 {
788 sg->v[i] = k0 = i*(size_t)deg1;
789 deg = 0;
790 for (k = 0; k < deg1; ++k, ++j)
791 sg->e[k0+deg++] = cub[j];
792 sg->d[i] = deg;
793 nde += deg;
794 }
795 for (i = n1; i < n; ++i)
796 {
797 sg->v[i] = k0 = ne + (i-n1)*(size_t)deg2;
798 deg = 0;
799 for (k = 0; k < deg2; ++k, ++j)
800 sg->e[k0+deg++] = cub[j];
801 sg->d[i] = deg;
802 nde += deg;
803 }
804 sg->nde = nde;
805 }
806 else
807 {
808 comdeg1 = n2 - deg1;
809 comdeg2 = n1 - deg2;
810 comne = n1*(size_t)comdeg1;
811 #if !MAXN
812 DYNALLOC1(int,cub,cub_sz,2*comne,"dmodel_bip_sg");
813 DYNALLOC1(boolean,adj,adj_sz,n,"dmodel_bip_sg");
814 #endif
815 rundmodel_bip(cub,comdeg1,comdeg2,n1,n2);
816
817 sg->nv = n;
818 j = nde = 0;
819 for (i = 0; i < n1; ++i)
820 {
821 sg->v[i] = k0 = i*(long)deg1;
822 deg = 0;
823 for (k = n1; k < n; ++k) adj[k] = TRUE;
824 for (k = 0; k < comdeg1; ++k, ++j) adj[cub[j]] = FALSE;
825 for (k = n1; k < n; ++k)
826 if (adj[k]) sg->e[k0+deg++] = k;
827 sg->d[i] = deg;
828 nde += deg;
829 }
830 for (i = n1; i < n; ++i)
831 {
832 sg->v[i] = k0 = ne + (i-n1)*(long)deg2;
833 deg = 0;
834 for (k = 0; k < n1; ++k) adj[k] = TRUE;
835 for (k = 0; k < comdeg2; ++k, ++j) adj[cub[j]] = FALSE;
836 for (k = 0; k < n1; ++k)
837 if (adj[k]) sg->e[k0+deg++] = k;
838 sg->d[i] = deg;
839 nde += deg;
840 }
841 sg->nde = nde;
842 }
843 }
844
845 /**************************************************************************/
846
847 static void
randomtree(sparsegraph * sg,int n)848 randomtree(sparsegraph *sg, int n)
849 /* Make a random tree with n vertices */
850 {
851 int i,v0,v1,ne,k;
852 #if MAXN
853 int ed[2*MAXN];
854 #else
855 DYNALLSTAT(int,ed,ed_sz);
856 DYNALLOC1(int,ed,ed_sz,2*n,"randomtree");
857 #endif
858
859 SG_ALLOC(*sg,n,2*(n-1),"randomtree");
860 sg->nv = n;
861 sg->nde = 2*(n-1);
862 sg->w = NULL;
863
864 for (i = 0; i < n; ++i) sg->d[i] = 0;
865
866 v0 = KRAN(n);
867 ne = k = 0;
868 while (ne < n-1)
869 {
870 do { v1 = KRAN(n); } while (v1 == v0);
871 if (sg->d[v1] == 0)
872 {
873 ed[k++] = v0;
874 ed[k++] = v1;
875 ++ne;
876 ++sg->d[v0];
877 ++sg->d[v1];
878 }
879 v0 = v1;
880 }
881
882 sg->v[0] = 0;
883 for (i = 1; i < n; ++i) sg->v[i] = sg->v[i-1] + sg->d[i-1];
884
885 for (i = 0; i < n; ++i) sg->d[i] = 0;
886
887 for (k = 0; k < 2*(n-1); )
888 {
889 v0 = ed[k++];
890 v1 = ed[k++];
891 sg->e[sg->v[v0]+(sg->d[v0])++] = v1;
892 sg->e[sg->v[v1]+(sg->d[v1])++] = v0;
893 }
894 }
895
896 /**************************************************************************/
897
898 static void
randombiptree(sparsegraph * sg,int n1,int n2)899 randombiptree(sparsegraph *sg, int n1, int n2)
900 /* Make a random subtree of K(n1,n2) */
901 {
902 int i,v0,v1,ne,k,n,cnt;
903 #if MAXN
904 int ed[2*MAXN];
905 #else
906 DYNALLSTAT(int,ed,ed_sz);
907 DYNALLOC1(int,ed,ed_sz,2*(n1+n2),"randombiptree");
908 #endif
909
910 n = n1 + n2;
911 if ((n1 == 0 || n2 == 0) && n > 1)
912 gt_abort(">E impossible bipartite tree\n");
913
914 SG_ALLOC(*sg,n,2*(n-1),"randomtree");
915 sg->nv = n;
916 sg->nde = 2*(n-1);
917 sg->w = NULL;
918
919 for (i = 0; i < n; ++i) sg->d[i] = 0;
920
921 v0 = KRAN(n1);
922 ne = k = cnt = 0;
923 while (ne < n-1)
924 {
925 if (cnt % 2 == 0) v1 = n1 + KRAN(n2);
926 else v1 = KRAN(n1);
927 ++cnt;
928 if (sg->d[v1] == 0)
929 {
930 ed[k++] = v0;
931 ed[k++] = v1;
932 ++ne;
933 ++sg->d[v0];
934 ++sg->d[v1];
935 }
936 v0 = v1;
937 }
938
939 sg->v[0] = 0;
940 for (i = 1; i < n; ++i) sg->v[i] = sg->v[i-1] + sg->d[i-1];
941
942 for (i = 0; i < n; ++i) sg->d[i] = 0;
943
944 for (k = 0; k < 2*(n-1); )
945 {
946 v0 = ed[k++];
947 v1 = ed[k++];
948 sg->e[sg->v[v0]+(sg->d[v0])++] = v1;
949 sg->e[sg->v[v1]+(sg->d[v1])++] = v0;
950 }
951 }
952
953 /**************************************************************************/
954 /**************************************************************************/
955
956 #define NOBIP if (bipartite) { fprintf(stderr, \
957 ">E genrang: This option is not available for bipartite graphs." \
958 " Feel free to request it.\n"); exit(1); }
959
960 int
main(int argc,char * argv[])961 main(int argc, char *argv[])
962 {
963 int m,n,n1,n2,codetype;
964 int argnum,j;
965 char *arg,sw;
966 boolean badargs;
967 boolean gswitch,sswitch,qswitch,Sswitch,Rswitch,lswitch,tswitch;
968 boolean aswitch,P1switch,P2switch,eswitch,rswitch,mswitch,dswitch;
969 boolean Tswitch;
970 long numgraphs,nout,P1value,P2value,evalue,rvalue;
971 nauty_counter ln,nc2;
972 int Svalue,loopmax,multmax;
973 static FILE *outfile;
974 char *outfilename;
975 sparsegraph sg;
976 boolean usesparse,digraph,bipartite;
977
978 #if MAXN
979 graph g[MAXM*1L*MAXN];
980 int perm[MAXN];
981 #else
982 DYNALLSTAT(graph,g,g_sz);
983 DYNALLSTAT(int,perm,perm_sz);
984 #endif
985
986 HELP; PUTVERSION;
987
988 gswitch = sswitch = qswitch = Sswitch = Rswitch = FALSE;
989 aswitch = P1switch = P2switch = eswitch = rswitch = FALSE;
990 digraph = dswitch = tswitch = lswitch = mswitch = FALSE;
991 Tswitch = FALSE;
992 outfilename = NULL;
993
994 argnum = 0;
995 badargs = FALSE;
996 for (j = 1; !badargs && j < argc; ++j)
997 {
998 arg = argv[j];
999 if (arg[0] == '-' && arg[1] != '\0')
1000 {
1001 ++arg;
1002 while (*arg != '\0')
1003 {
1004 sw = *arg++;
1005 SWBOOLEAN('g',gswitch)
1006 else SWBOOLEAN('s',sswitch)
1007 else SWBOOLEAN('z',digraph)
1008 else SWBOOLEAN('a',aswitch)
1009 else SWBOOLEAN('t',tswitch)
1010 else SWBOOLEAN('T',Tswitch)
1011 else SWBOOLEAN('q',qswitch)
1012 else SWLONG('P',P1switch,P1value,"genrang -P")
1013 else SWLONG('/',P2switch,P2value,"genrang -P")
1014 else SWLONG('e',eswitch,evalue,"genrang -e")
1015 else SWLONG('d',dswitch,rvalue,"genrang -d")
1016 else SWLONG('r',rswitch,rvalue,"genrang -r")
1017 else SWLONG('R',Rswitch,rvalue,"genrang -R")
1018 else SWINT('S',Sswitch,Svalue,"genrang -S")
1019 else SWINT('l',lswitch,loopmax,"genrang -l")
1020 else SWINT('m',mswitch,multmax,"genrang -m")
1021 else badargs = TRUE;
1022 }
1023 }
1024 else
1025 {
1026 ++argnum;
1027 if (argnum == 1)
1028 {
1029 if (sscanf(arg,"%d,%d",&n1,&n2) == 2)
1030 {
1031 bipartite = TRUE;
1032 if (n1 < 1 || n2 < 1) badargs = TRUE;
1033 n = n1 + n2;
1034 }
1035 else if (sscanf(arg,"%d",&n) == 1)
1036 {
1037 bipartite = FALSE;
1038 if (n < 1) badargs = TRUE;
1039 }
1040 else
1041 badargs = TRUE;
1042 }
1043 else if (argnum == 2)
1044 {
1045 if (sscanf(arg,"%ld",&numgraphs) != 1 || numgraphs < 1)
1046 badargs = TRUE;
1047 }
1048 else if (argnum == 3) outfilename = arg;
1049 else badargs = TRUE;
1050 }
1051 }
1052
1053 if (Tswitch) digraph = TRUE;
1054
1055 if ((gswitch!=0) + (sswitch!=0) + (digraph!=0) > 1)
1056 gt_abort(">E genrang: -gsz are incompatible\n");
1057
1058 if (gswitch) codetype = GRAPH6;
1059 else if (digraph) codetype = DIGRAPH6;
1060 else codetype = SPARSE6;
1061
1062 if (P1switch && !P2switch)
1063 {
1064 P2value = P1value;
1065 P1value = 1;
1066 }
1067 else if (P2switch && !P1switch)
1068 {
1069 P1value = 1;
1070 P1switch = TRUE;
1071 }
1072
1073 if (P1switch && (P1value < 0 || P2value <= 0 || P1value > P2value))
1074 gt_abort(">E genrang: bad value for -P switch\n");
1075
1076 if ((P1switch!=0) + (eswitch!=0) + (rswitch!=0) + (dswitch!=0)
1077 + (Tswitch!=0) + (Rswitch!=0) + (tswitch!=0) > 1)
1078 gt_abort(">E genrang: -PerRdtT are incompatible\n");
1079
1080 if ((sswitch!=0) + (gswitch!=0) + (Rswitch!=0) > 1) /* REVISE */
1081 gt_abort(">E genrang: -sgR are incompatible\n");
1082
1083 if ((aswitch!=0) + (Rswitch!=0) > 1)
1084 gt_abort(">E genrang: -aR are incompatible\n");
1085
1086 if (!lswitch) loopmax = 0;
1087 if (!mswitch) multmax = 1;
1088 if (digraph &&
1089 (Rswitch || multmax>1 || loopmax>1 || dswitch || tswitch))
1090 gt_abort(">E genrang: -z is only compatible with -T, -P, -e and -l1\n");
1091
1092 if (!digraph && (loopmax>1 || multmax>1)
1093 && !(Rswitch || (rswitch && !gswitch)))
1094 gt_abort(">E genrang: -l>1,-m>1 need -R or -r without -g\n");
1095
1096 if (multmax < 1 || loopmax < 0)
1097 gt_abort(">E genrang: bad value for -l or -m\n");
1098
1099 if (argnum < 2 || argnum > 3) badargs = TRUE;
1100
1101 if (badargs)
1102 {
1103 fprintf(stderr,">E Usage: %s\n",USAGE);
1104 GETHELP;
1105 exit(1);
1106 }
1107
1108 if (!Sswitch)
1109 {
1110 #ifdef INITSEED
1111 INITSEED;
1112 ran_init(seed);
1113 #endif
1114 }
1115 else
1116 ran_init(Svalue);
1117
1118 if (!outfilename || outfilename[0] == '-')
1119 {
1120 outfilename = "stdout";
1121 outfile = stdout;
1122 }
1123 else if ((outfile = fopen(outfilename,"w")) == NULL)
1124 {
1125 fprintf(stderr,"Can't open output file %s\n",outfilename);
1126 gt_abort(NULL);
1127 }
1128
1129 m = (n + WORDSIZE + 1) / WORDSIZE;
1130 usesparse = tswitch || dswitch ||
1131 (rswitch && !aswitch && codetype==SPARSE6);
1132 #if !MAXN
1133 if (!Rswitch && !usesparse)
1134 {
1135 DYNALLOC2(graph,g,g_sz,n,m,"genrang");
1136 if (aswitch) DYNALLOC1(int,perm,perm_sz,n,"genrang");
1137 }
1138 #endif
1139
1140 rswitch = rswitch || Rswitch || dswitch;
1141
1142 #if MAXN
1143 if (rswitch && rvalue > MAXLREG)
1144 {
1145 fprintf(stderr,
1146 ">E -r/-R is only implemented for degree <= %d\n",MAXLREG);
1147 exit(1);
1148 }
1149 #endif
1150
1151 ln = n;
1152 if (bipartite)
1153 nc2 = (unsigned long)n1*n2;
1154 else
1155 nc2 = ln*loopmax + (1+(digraph!=0))*ln*(ln-1)/2*multmax;
1156
1157 if (eswitch && evalue > nc2)
1158 {
1159 fprintf(stderr,
1160 ">E There are no graphs of order %d and %ld edges\n",
1161 n,evalue);
1162 exit(1);
1163 }
1164
1165 if (rswitch && !bipartite && (((n&1) != 0 && (rvalue&1) != 0)
1166 || rvalue > (n-1)*multmax+2*loopmax))
1167 {
1168 fprintf(stderr,
1169 ">E There are no such graphs of order %d and degree %ld\n",
1170 n,rvalue);
1171 exit(1);
1172 }
1173
1174 if (bipartite && dswitch && (n1 == 0 || n2 == 0 || rvalue > n2
1175 || (n1*(size_t)rvalue) % n2 != 0))
1176 {
1177 fprintf(stderr,
1178 ">E There are no bipartite graphs of order %d+%d and degree %ld\n",
1179 n1,n2,rvalue);
1180 exit(1);
1181 }
1182
1183 if (!P1switch)
1184 {
1185 P1value = 1;
1186 P2value = 2;
1187 }
1188
1189 SG_INIT(sg);
1190
1191 for (nout = 1; nout <= numgraphs; ++nout)
1192 {
1193 if (eswitch)
1194 {
1195 if (digraph)
1196 {
1197 NOBIP;
1198 ranarcs(evalue,loopmax>0,g,m,n);
1199 }
1200 else
1201 {
1202 if (bipartite)
1203 ranedges_bip(evalue,g,m,n1,n2);
1204 else
1205 ranedges(evalue,loopmax>0,g,m,n);
1206 }
1207 }
1208 else if (dswitch)
1209 {
1210 if (bipartite)
1211 dmodel_bip_sg(rvalue,&sg,n1,n2);
1212 else
1213 dmodel_sg(rvalue,&sg,n);
1214 }
1215 else if (Rswitch)
1216 {
1217 NOBIP;
1218 ranregR(outfile,rvalue,multmax,loopmax,n);
1219 }
1220 else if (rswitch && usesparse)
1221 {
1222 NOBIP;
1223 ranreglm_sg(rvalue,&sg,multmax,loopmax,n);
1224 }
1225 else if (rswitch && !usesparse)
1226 {
1227 NOBIP;
1228 ranreg(rvalue,g,m,n);
1229 }
1230 else if (tswitch)
1231 {
1232 if (bipartite)
1233 randombiptree(&sg,n1,n2);
1234 else
1235 randomtree(&sg,n);
1236 }
1237 else if (Tswitch)
1238 {
1239 if (bipartite)
1240 grandtourn_bip(g,m,n1,n2);
1241 else
1242 grandtourn(g,m,n);
1243 }
1244 else
1245 {
1246 if (bipartite)
1247 grandgraph_bip(g,digraph,P1value,P2value,m,n1,n2);
1248 else
1249 grandgraph(g,digraph,loopmax>0,P1value,P2value,m,n);
1250 }
1251
1252 if (Rswitch) continue;
1253
1254 if (aswitch && !usesparse)
1255 {
1256 ranperm(perm,n);
1257 perminvar(g,perm,m,n);
1258 }
1259 if (codetype == SPARSE6)
1260 {
1261 if (usesparse)
1262 {
1263 sortlists_sg(&sg);
1264 writes6_sg(outfile,&sg);
1265 }
1266 else
1267 writes6(outfile,g,m,n);
1268 }
1269 else if (codetype == DIGRAPH6)
1270 {
1271 if (usesparse)
1272 writed6_sg(outfile,&sg);
1273 else
1274 writed6(outfile,g,m,n);
1275 }
1276 else
1277 {
1278 if (usesparse)
1279 writeg6_sg(outfile,&sg);
1280 else
1281 writeg6(outfile,g,m,n);
1282 }
1283 }
1284
1285 exit(0);
1286 }
1287