1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "config.h"
15
16#include <stdio.h>
17#include <stdlib.h>
18#include <math.h>
19#include <time.h>
20#include <graph_generator.h>
21
22void makePath(int n, edgefn ef)
23{
24 int i;
25
26 if (n == 1) {
27 ef (1, 0);
28 return;
29 }
30 for (i = 2; i <= n; i++)
31 ef (i - 1, i);
32}
33
34void makeComplete(int n, edgefn ef)
35{
36 int i, j;
37
38 if (n == 1) {
39 ef (1, 0);
40 return;
41 }
42 for (i = 1; i < n; i++) {
43 for (j = i + 1; j <= n; j++) {
44 ef ( i, j);
45 }
46 }
47}
48
49void makeCircle(int n, edgefn ef)
50{
51 int i;
52
53 if (n < 3) {
54 fprintf(stderr, "Warning: degenerate circle of %d vertices\n", n);
55 makePath(n, ef);
56 return;
57 }
58
59 for (i = 1; i < n; i++)
60 ef ( i, i + 1);
61 ef (1, n);
62}
63
64void makeStar(int n, edgefn ef)
65{
66 int i;
67
68 if (n < 3) {
69 fprintf(stderr, "Warning: degenerate star of %d vertices\n", n);
70 makePath(n, ef);
71 return;
72 }
73
74 for (i = 2; i <= n; i++)
75 ef (1, i);
76}
77
78void makeWheel(int n, edgefn ef)
79{
80 int i;
81
82 if (n < 4) {
83 fprintf(stderr, "Warning: degenerate wheel of %d vertices\n", n);
84 makeComplete(n, ef);
85 return;
86 }
87
88 makeStar(n, ef);
89
90 for (i = 2; i < n; i++)
91 ef( i, i + 1);
92 ef (2, n);
93}
94
95void makeCompleteB(int dim1, int dim2, edgefn ef)
96{
97 int i, j;
98
99 for (i = 1; i <= dim1; i++) {
100 for (j = 1; j <= dim2; j++) {
101 ef ( i, dim1 + j);
102 }
103 }
104}
105
106void makeTorus(int dim1, int dim2, edgefn ef)
107{
108 int i, j, n = 0;
109
110 for (i = 1; i <= dim1; i++) {
111 for (j = 1; j < dim2; j++) {
112 ef( n + j, n + j + 1);
113 }
114 ef( n + 1, n + dim2);
115 n += dim2;
116 }
117
118 for (i = 1; i <= dim2; i++) {
119 for (j = 1; j < dim1; j++) {
120 ef( dim2 * (j - 1) + i, dim2 * j + i);
121 }
122 ef( i, dim2 * (dim1 - 1) + i);
123 }
124}
125
126void makeTwistedTorus(int dim1, int dim2, int t1, int t2, edgefn ef)
127{
128 int i, j, li, lj;
129
130 for (i = 0; i < dim1; i++) {
131 for (j = 0; j < dim2; j++) {
132 li = (i + t1) % dim1;
133 lj = (j + 1) % dim2;
134 ef (i+j*dim1+1, li+lj*dim1+1);
135
136 li = (i + 1) % dim1;
137 lj = (j + t2) % dim2;
138 ef(i+j*dim1+1, li+lj*dim1+1);
139 }
140 }
141}
142
143void makeCylinder(int dim1, int dim2, edgefn ef)
144{
145 int i, j, n = 0;
146
147 for (i = 1; i <= dim1; i++) {
148 for (j = 1; j < dim2; j++) {
149 ef( n + j, n + j + 1);
150 }
151 ef( n + 1, n + dim2);
152 n += dim2;
153 }
154
155 for (i = 1; i <= dim2; i++) {
156 for (j = 1; j < dim1; j++) {
157 ef( dim2 * (j - 1) + i, dim2 * j + i);
158 }
159 }
160}
161
162#define OUTE(h) if (tl < (hd=(h))) ef( tl, hd)
163
164void
165makeSquareGrid(int dim1, int dim2, int connect_corners, int partial, edgefn ef)
166{
167 int i, j, tl, hd;
168
169 for (i = 0; i < dim1; i++)
170 for (j = 0; j < dim2; j++) {
171 // write the neighbors of the node i*dim2+j+1
172 tl = i * dim2 + j + 1;
173 if (j > 0
174 && (!partial || j <= 2 * dim2 / 6 || j > 4 * dim2 / 6
175 || i <= 2 * dim1 / 6 || i > 4 * dim1 / 6)) {
176 OUTE(i * dim2 + j);
177 }
178 if (j < dim2 - 1
179 && (!partial || j < 2 * dim2 / 6 || j >= 4 * dim2 / 6
180 || i <= 2 * dim1 / 6 || i > 4 * dim1 / 6)) {
181 OUTE(i * dim2 + j + 2);
182 }
183 if (i > 0) {
184 OUTE((i - 1) * dim2 + j + 1);
185 }
186 if (i < dim1 - 1) {
187 OUTE((i + 1) * dim2 + j + 1);
188 }
189 if (connect_corners == 1) {
190 if (i == 0 && j == 0) { // upper left
191 OUTE((dim1 - 1) * dim2 + dim2);
192 } else if (i == (dim1 - 1) && j == 0) { // lower left
193 OUTE(dim2);
194 } else if (i == 0 && j == (dim2 - 1)) { // upper right
195 OUTE((dim1 - 1) * dim2 + 1);
196 } else if (i == (dim1 - 1) && j == (dim2 - 1)) { // lower right
197 OUTE(1);
198 }
199 } else if (connect_corners == 2) {
200 if (i == 0 && j == 0) { // upper left
201 OUTE(dim2);
202 } else if (i == (dim1 - 1) && j == 0) { // lower left
203 OUTE((dim1 - 1) * dim2 + dim2);
204 } else if (i == 0 && j == (dim2 - 1)) { // upper right
205 OUTE(1);
206 } else if (i == (dim1 - 1) && j == (dim2 - 1)) { // lower right
207 OUTE((dim1 - 1) * dim2 + 1);
208 }
209 }
210 }
211}
212
213static int
214ipow (int base, int power)
215{
216 int ip;
217 if (power == 0) return 1;
218 if (power == 1) return base;
219
220 ip = base;
221 power--;
222 while (power--) ip *= base;
223 return ip;
224}
225
226void makeTree(int depth, int nary, edgefn ef)
227{
228 unsigned int i, j;
229 unsigned int n = (ipow(nary,depth)-1)/(nary-1); /* no. of non-leaf nodes */
230 unsigned int idx = 2;
231
232 for (i = 1; i <= n; i++) {
233 for (j = 0; j < nary; j++) {
234 ef (i, idx++);
235 }
236 }
237}
238
239void makeBinaryTree(int depth, edgefn ef)
240{
241 unsigned int i;
242 unsigned int n = (1 << depth) - 1;
243
244 for (i = 1; i <= n; i++) {
245 ef( i, 2 * i);
246 ef( i, 2 * i + 1);
247 }
248}
249
250typedef struct {
251 int nedges;
252 int* edges;
253} vtx_data;
254
255static void
256constructSierpinski(int v1, int v2, int v3, int depth, vtx_data* graph)
257{
258 static int last_used_node_name = 3;
259 int v4, v5, v6;
260
261 int nedges;
262
263 if (depth > 0) {
264 v4 = ++last_used_node_name;
265 v5 = ++last_used_node_name;
266 v6 = ++last_used_node_name;
267 constructSierpinski(v1, v4, v5, depth - 1, graph);
268 constructSierpinski(v2, v5, v6, depth - 1, graph);
269 constructSierpinski(v3, v4, v6, depth - 1, graph);
270 return;
271 }
272 // depth==0, Construct graph:
273
274 nedges = graph[v1].nedges;
275 graph[v1].edges[nedges++] = v2;
276 graph[v1].edges[nedges++] = v3;
277 graph[v1].nedges = nedges;
278
279 nedges = graph[v2].nedges;
280 graph[v2].edges[nedges++] = v1;
281 graph[v2].edges[nedges++] = v3;
282 graph[v2].nedges = nedges;
283
284 nedges = graph[v3].nedges;
285 graph[v3].edges[nedges++] = v1;
286 graph[v3].edges[nedges++] = v2;
287 graph[v3].nedges = nedges;
288
289 return;
290
291}
292
293#define NEW(t) (t*)calloc((1),sizeof(t))
294#define N_NEW(n,t) (t*)calloc((n),sizeof(t))
295
296void makeSierpinski(int depth, edgefn ef)
297{
298 vtx_data* graph;
299 int* edges;
300 int n;
301 int nedges;
302 int i, j;
303
304 depth--;
305 n = 3 * (1 + ((int) (pow(3.0, (double) depth) + 0.5) - 1) / 2);
306
307 nedges = (int) (pow(3.0, depth + 1.0) + 0.5);
308
309 graph = N_NEW(n + 1, vtx_data);
310 edges = N_NEW(4 * n, int);
311
312 for (i = 1; i <= n; i++) {
313 graph[i].edges = edges;
314 edges += 4;
315 graph[i].nedges = 0;
316 }
317
318 constructSierpinski(1, 2, 3, depth, graph);
319
320 for (i = 1; i <= n; i++) {
321 int nghbr;
322 // write the neighbors of the node i
323 for (j = 0; j < graph[i].nedges; j++) {
324 nghbr = graph[i].edges[j];
325 if (i < nghbr) ef( i, nghbr);
326 }
327 }
328
329 free(graph[1].edges);
330 free(graph);
331}
332
333static void
334constructTetrix(int v1, int v2, int v3, int v4, int depth, vtx_data* graph)
335{
336 static int last_used_node_name = 4;
337 int v5, v6, v7, v8, v9, v10;
338
339 int nedges;
340
341 if (depth > 0) {
342 v5 = ++last_used_node_name;
343 v6 = ++last_used_node_name;
344 v7 = ++last_used_node_name;
345 v8 = ++last_used_node_name;
346 v9 = ++last_used_node_name;
347 v10 = ++last_used_node_name;
348 constructTetrix(v1, v5, v6, v8, depth - 1, graph);
349 constructTetrix(v2, v6, v7, v9, depth - 1, graph);
350 constructTetrix(v3, v5, v7, v10, depth - 1, graph);
351 constructTetrix(v4, v8, v9, v10, depth - 1, graph);
352 return;
353 }
354 // depth==0, Construct graph:
355 nedges = graph[v1].nedges;
356 graph[v1].edges[nedges++] = v2;
357 graph[v1].edges[nedges++] = v3;
358 graph[v1].edges[nedges++] = v4;
359 graph[v1].nedges = nedges;
360
361 nedges = graph[v2].nedges;
362 graph[v2].edges[nedges++] = v1;
363 graph[v2].edges[nedges++] = v3;
364 graph[v2].edges[nedges++] = v4;
365 graph[v2].nedges = nedges;
366
367 nedges = graph[v3].nedges;
368 graph[v3].edges[nedges++] = v1;
369 graph[v3].edges[nedges++] = v2;
370 graph[v3].edges[nedges++] = v4;
371 graph[v3].nedges = nedges;
372
373 nedges = graph[v4].nedges;
374 graph[v4].edges[nedges++] = v1;
375 graph[v4].edges[nedges++] = v2;
376 graph[v4].edges[nedges++] = v3;
377 graph[v4].nedges = nedges;
378
379 return;
380
381}
382
383void makeTetrix(int depth, edgefn ef)
384{
385 vtx_data* graph;
386 int* edges;
387 int n;
388 int nedges;
389 int i, j;
390
391 depth--;
392 n = 4 + 2 * (((int) (pow(4.0, (double) depth) + 0.5) - 1));
393
394 nedges = 6 * (int) (pow(4.0, depth) + 0.5);
395
396 graph = N_NEW(n + 1, vtx_data);
397 edges = N_NEW(6 * n, int);
398
399 for (i = 1; i <= n; i++) {
400 graph[i].edges = edges;
401 edges += 6;
402 graph[i].nedges = 0;
403 }
404
405 constructTetrix(1, 2, 3, 4, depth, graph);
406
407 for (i = 1; i <= n; i++) {
408 int nghbr;
409 // write the neighbors of the node i
410 for (j = 0; j < graph[i].nedges; j++) {
411 nghbr = graph[i].edges[j];
412 if (i < nghbr) ef( i, nghbr);
413 }
414 }
415
416 free(graph[1].edges);
417 free(graph);
418}
419
420void makeHypercube(int dim, edgefn ef)
421{
422 int i, j, n;
423 int neighbor;
424
425 n = 1 << dim;
426
427 for (i = 0; i < n; i++) {
428 for (j = 0; j < dim; j++) {
429 neighbor = (i ^ (1 << j)) + 1;
430 if (i < neighbor)
431 ef( i + 1, neighbor);
432 }
433 }
434}
435
436void makeTriMesh(int sz, edgefn ef)
437{
438 int i, j, idx;
439
440 if (sz == 1) {
441 ef (1, 0);
442 return;
443 }
444 ef(1,2);
445 ef(1,3);
446 idx = 2;
447 for (i=2; i < sz; i++) {
448 for (j=1; j <= i; j++) {
449 ef(idx,idx+i);
450 ef(idx,idx+i+1);
451 if (j < i)
452 ef(idx,idx+1);
453 idx++;
454 }
455 }
456 for (j=1; j < sz; j++) {
457 ef (idx,idx+1);
458 idx++;
459 }
460}
461
462void makeBall(int w, int h, edgefn ef)
463{
464 int i, cap;
465
466 makeCylinder (w, h, ef);
467
468 for (i = 1; i <= h; i++)
469 ef (0, i);
470
471 cap = w*h+1;
472 for (i = (w-1)*h+1; i <= w*h; i++)
473 ef (i, cap);
474
475}
476
477/* makeRandom:
478 * No. of nodes is largest 2^n - 1 less than or equal to h.
479 */
480void makeRandom(int h, int w, edgefn ef)
481{
482 int i, j, type, size, depth;
483
484 srand(time(0));
485 if (rand()%2==1)
486 type = 1;
487 else
488 type = 0;
489
490 size = depth = 0;
491 while (size <= h) {
492 size += ipow(2,depth);
493 depth++;
494 }
495 depth--;
496 if (size > h) {
497 size -= ipow(2,depth);
498 depth--;
499 }
500
501 if (type)
502 makeBinaryTree (depth, ef);
503 else
504 makePath (size, ef);
505
506 for (i=3; i<=size; i++) {
507 for (j=1; j<i-1; j++) {
508 int th = rand()%(size*size);
509 if (((th<=(w*w))&&((i<5)||((i>h-4)&&(j>h-4)))) || (th<=w))
510 ef(j,i);
511 }
512 }
513}
514
515void makeMobius(int w, int h, edgefn ef)
516{
517 int i, j;
518
519 if (h == 1) {
520 fprintf(stderr, "Warning: degenerate Moebius strip of %d vertices\n", w);
521 makePath(w, ef);
522 return;
523 }
524 if (w == 1) {
525 fprintf(stderr, "Warning: degenerate Moebius strip of %d vertices\n", h);
526 makePath(h, ef);
527 return;
528 }
529
530 for(i=0; i < w-1; i++) {
531 for(j = 1; j < h; j++){
532 ef(j + i*h, j + (i+1)*h);
533 ef(j + i*h, j+1 + i*h);
534 }
535 }
536
537 for(i = 1; i < h; i++){
538 ef (i + (w-1)*h, i+1 + (w-1)*h);
539 }
540 for(i=1; i < w; i++) {
541 ef(i*h , (i+1)*h);
542 ef(i*h, (w-i)*h+1);
543 }
544
545 ef(1,w*h);
546}
547
548typedef struct {
549 int j, d;
550} pair;
551
552typedef struct {
553 int top, root;
554 int* p;
555} tree_t;
556
557static tree_t*
558mkTree (int sz)
559{
560 tree_t* tp = NEW(tree_t);
561 tp->root = 0;
562 tp->top = 0;
563 tp->p = N_NEW(sz,int);
564 return tp;
565}
566
567static void
568freeTree (tree_t* tp)
569{
570 free (tp->p);
571 free (tp);
572}
573
574static void
575resetTree (tree_t* tp)
576{
577 tp->root = 0;
578 tp->top = 0;
579}
580
581static int
582treeRoot (tree_t* tp)
583{
584 return tp->root;
585}
586
587static int
588prevRoot (tree_t* tp)
589{
590 return tp->p[tp->root];
591}
592
593static int
594treeSize (tree_t* tp)
595{
596 return (tp->top - tp->root + 1);
597}
598
599static int
600treeTop (tree_t* tp)
601{
602 return (tp->top);
603}
604
605static void
606treePop (tree_t* tp)
607{
608 tp->root = prevRoot(tp);
609}
610
611static void
612addTree (tree_t* tp, int sz)
613{
614 tp->p[tp->top+1] = tp->root;
615 tp->root = tp->top+1;
616 tp->top += sz;
617 if (sz > 1) tp->p[tp->top] = tp->top-1;
618}
619
620static void
621treeDup (tree_t* tp, int J)
622{
623 int M = treeSize(tp);
624 int L = treeRoot(tp);
625 int LL = prevRoot(tp);
626 int i, LS = L + (J-1)*M - 1;
627 for (i = L; i <= LS; i++) {
628 if ((i-L)%M == 0) tp->p[i+M] = LL;
629 else tp->p[i+M] = tp->p[i] + M;
630 }
631 tp->top = LS + M;
632}
633
634/*****************/
635
636typedef struct {
637 int top;
638 pair* v;
639} stack;
640
641static stack*
642mkStack (int sz)
643{
644 stack* sp = NEW(stack);
645 sp->top = 0;
646 sp->v = N_NEW(sz,pair);
647 return sp;
648}
649
650static void
651freeStack (stack* sp)
652{
653 free (sp->v);
654 free (sp);
655}
656
657static void
658resetStack (stack* sp)
659{
660 sp->top = 0;
661}
662
663static void
664push(stack* sp, int j, int d)
665{
666 sp->top++;
667 sp->v[sp->top].j = j;
668 sp->v[sp->top].d = d;
669}
670
671static pair
672pop (stack* sp)
673{
674 sp->top--;
675 return sp->v[sp->top+1];
676}
677
678/*****************/
679
680static int*
681genCnt(int NN)
682{
683 int* T = N_NEW(NN+1,int);
684 int D, I, J, TD;
685 int SUM;
686 int NLAST = 1;
687 T[1] = 1;
688 while (NN > NLAST) {
689 SUM = 0;
690 for (D = 1; D <= NLAST; D++) {
691 I = NLAST+1;
692 TD = T[D]*D;
693 for (J = 1; J <= NLAST; J++) {
694 I = I-D;
695 if (I <= 0) break;
696 SUM += T[I]*TD;
697 }
698 }
699 NLAST++;
700 T[NLAST] = SUM/(NLAST-1);
701 }
702 return T;
703}
704
705static double
706drand(void)
707{
708 double d;
709 d = rand();
710 d = d / RAND_MAX;
711 return d;
712}
713
714static void
715genTree (int NN, int* T, stack* stack, tree_t* TREE)
716{
717 double v;
718 pair p;
719 int Z, D, N, J, TD, M, more;
720
721 N = NN;
722
723 while (1) {
724 while (N > 2) {
725 v = (N-1)*T[N];
726 Z = v*drand();
727 D = 0;
728 more = 1;
729 do {
730 D++;
731 TD = D*T[D];
732 M = N;
733 J = 0;
734 do {
735 J++;
736 M -= D;
737 if (M < 1) break;
738 Z -= T[M]*TD;
739 if (Z < 0) more = 0;
740 } while (Z >= 0);
741 } while (more);
742 push(stack, J, D);
743 N = M;
744 }
745 addTree (TREE, N);
746
747 while (1) {
748 p = pop(stack);
749 N = p.d;
750 if (N != 0) {
751 push(stack,p.j,0);
752 break;
753 }
754 J = p.j;
755 if (J > 1) treeDup (TREE, J);
756 if (treeTop(TREE) == NN) return;
757 treePop(TREE);
758 }
759 }
760
761}
762
763static void
764writeTree (tree_t* tp, edgefn ef)
765{
766 int i;
767 for (i = 2; i <= tp->top; i++)
768 ef (tp->p[i], i);
769}
770
771struct treegen_s {
772 int N;
773 int* T;
774 stack* sp;
775 tree_t* tp;
776};
777
778treegen_t*
779makeTreeGen (int N)
780{
781 treegen_t* tg = NEW(treegen_t);
782
783 tg->N = N;
784 tg->T = genCnt(N);
785 tg->sp = mkStack(N+1);
786 tg->tp = mkTree(N+1);
787 srand(time(0));
788
789 return tg;
790}
791
792void makeRandomTree (treegen_t* tg, edgefn ef)
793{
794 resetStack(tg->sp);
795 resetTree(tg->tp);
796 genTree (tg->N, tg->T, tg->sp, tg->tp);
797 writeTree (tg->tp, ef);
798}
799
800void
801freeTreeGen(treegen_t* tg)
802{
803 free (tg->T);
804 freeStack (tg->sp);
805 freeTree (tg->tp);
806 free (tg);
807}
808
809