Graphviz 13.0.0~dev.20250424.1043
Loading...
Searching...
No Matches
graph_generator.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include "config.h"
12#include <inttypes.h>
13#include <stdbool.h>
14#include <stdio.h>
15#include <stdint.h>
16#include <stdlib.h>
17#include <math.h>
18#include <graph_generator.h>
19#include <util/alloc.h>
20#include <util/exit.h>
21#include <util/list.h>
22#include <util/random.h>
23#include <util/overflow.h>
24
25void makePath(unsigned n, edgefn ef){
26 if (n == 1) {
27 ef (1, 0);
28 return;
29 }
30 for (unsigned i = 2; i <= n; i++)
31 ef (i - 1, i);
32}
33
34void makeComplete(unsigned n, edgefn ef) {
35 if (n == 1) {
36 ef (1, 0);
37 return;
38 }
39 for (unsigned i = 1; i < n; i++) {
40 for (unsigned j = i + 1; j <= n; j++) {
41 ef ( i, j);
42 }
43 }
44}
45
46void makeCircle(unsigned n, edgefn ef) {
47 if (n < 3) {
48 fprintf(stderr, "Warning: degenerate circle of %u vertices\n", n);
49 makePath(n, ef);
50 return;
51 }
52
53 for (unsigned i = 1; i < n; i++)
54 ef ( i, i + 1);
55 ef (1, n);
56}
57
58void makeStar(unsigned n, edgefn ef) {
59 if (n < 3) {
60 fprintf(stderr, "Warning: degenerate star of %u vertices\n", n);
61 makePath(n, ef);
62 return;
63 }
64
65 for (unsigned i = 2; i <= n; i++)
66 ef (1, i);
67}
68
69void makeWheel(unsigned n, edgefn ef) {
70 if (n < 4) {
71 fprintf(stderr, "Warning: degenerate wheel of %u vertices\n", n);
72 makeComplete(n, ef);
73 return;
74 }
75
76 makeStar(n, ef);
77
78 for (unsigned i = 2; i < n; i++)
79 ef( i, i + 1);
80 ef (2, n);
81}
82
83void makeCompleteB(unsigned dim1, unsigned dim2, edgefn ef) {
84 for (unsigned i = 1; i <= dim1; i++) {
85 for (unsigned j = 1; j <= dim2; j++) {
86 ef ( i, dim1 + j);
87 }
88 }
89}
90
91void makeTorus(unsigned dim1, unsigned dim2, edgefn ef) {
92 for (unsigned i = 1, n = 0; i <= dim1; i++) {
93 for (unsigned j = 1; j < dim2; j++) {
94 ef( n + j, n + j + 1);
95 }
96 ef( n + 1, n + dim2);
97 n += dim2;
98 }
99
100 for (unsigned i = 1; i <= dim2; i++) {
101 for (unsigned j = 1; j < dim1; j++) {
102 ef( dim2 * (j - 1) + i, dim2 * j + i);
103 }
104 ef( i, dim2 * (dim1 - 1) + i);
105 }
106}
107
108void makeTwistedTorus(unsigned dim1, unsigned dim2, unsigned t1, unsigned t2,
109 edgefn ef) {
110 for (unsigned i = 0; i < dim1; i++) {
111 for (unsigned j = 0; j < dim2; j++) {
112 unsigned li = (i + t1) % dim1;
113 unsigned lj = (j + 1) % dim2;
114 ef (i+j*dim1+1, li+lj*dim1+1);
115
116 li = (i + 1) % dim1;
117 lj = (j + t2) % dim2;
118 ef(i+j*dim1+1, li+lj*dim1+1);
119 }
120 }
121}
122
123void makeCylinder(unsigned dim1, unsigned dim2, edgefn ef) {
124 for (unsigned i = 1, n = 0; i <= dim1; i++) {
125 for (unsigned j = 1; j < dim2; j++) {
126 ef( n + j, n + j + 1);
127 }
128 ef( n + 1, n + dim2);
129 n += dim2;
130 }
131
132 for (unsigned i = 1; i <= dim2; i++) {
133 for (unsigned j = 1; j < dim1; j++) {
134 ef( dim2 * (j - 1) + i, dim2 * j + i);
135 }
136 }
137}
138
139#define OUTE(h) if (tl < (hd=(h))) ef( tl, hd)
140
141void makeSquareGrid(unsigned dim1, unsigned dim2, int connect_corners, int partial, edgefn ef)
142{
143 for (unsigned i = 0; i < dim1; i++)
144 for (unsigned j = 0; j < dim2; j++) {
145 // write the neighbors of the node i*dim2+j+1
146 const unsigned tl = i * dim2 + j + 1;
147 unsigned hd;
148 if (j + 1 < dim2
149 && (!partial || j < 2 * dim2 / 6 || j >= 4 * dim2 / 6
150 || i <= 2 * dim1 / 6 || i > 4 * dim1 / 6)) {
151 ef(tl, i * dim2 + j + 2);
152 }
153 if (i + 1 < dim1) {
154 ef(tl, (i + 1) * dim2 + j + 1);
155 }
156 if (connect_corners == 1) {
157 if (i == 0 && j == 0) { // upper left
158 OUTE((dim1 - 1) * dim2 + dim2);
159 } else if (i + 1 == dim1 && j == 0) { // lower left
160 OUTE(dim2);
161 } else if (i == 0 && j + 1 == dim2) { // upper right
162 OUTE((dim1 - 1) * dim2 + 1);
163 } else if (i + 1 == dim1 && j + 1 == dim2) { // lower right
164 OUTE(1);
165 }
166 } else if (connect_corners == 2) {
167 if (i == 0 && j == 0) { // upper left
168 OUTE(dim2);
169 } else if (i + 1 == dim1 && j == 0) { // lower left
170 OUTE((dim1 - 1) * dim2 + dim2);
171 } else if (i == 0 && j + 1 == dim2) { // upper right
172 OUTE(1);
173 } else if (i + 1 == dim1 && j + 1 == dim2) { // lower right
174 OUTE((dim1 - 1) * dim2 + 1);
175 }
176 }
177 }
178}
179
180void makeTree(unsigned depth, unsigned nary, edgefn ef) {
181 const double n = (pow(nary, depth) - 1) / (nary - 1); // no. of non-leaf nodes
182 unsigned idx = 2;
183
184 for (unsigned i = 1; i <= n; i++) {
185 for (unsigned j = 0; j < nary; j++) {
186 ef (i, idx++);
187 }
188 }
189}
190
191void makeBinaryTree(unsigned depth, edgefn ef) {
192 const unsigned n = (1u << depth) - 1;
193
194 for (unsigned i = 1; i <= n; i++) {
195 ef( i, 2 * i);
196 ef( i, 2 * i + 1);
197 }
198}
199
200typedef struct {
201 unsigned nedges;
202 unsigned *edges;
203} vtx_data;
204
205static void constructSierpinski(unsigned v1, unsigned v2, unsigned v3,
206 unsigned depth, vtx_data *graph) {
207 static unsigned last_used_node_name = 3;
208
209 if (depth > 0) {
210 const unsigned v4 = ++last_used_node_name;
211 const unsigned v5 = ++last_used_node_name;
212 const unsigned v6 = ++last_used_node_name;
213 constructSierpinski(v1, v4, v5, depth - 1, graph);
214 constructSierpinski(v2, v5, v6, depth - 1, graph);
215 constructSierpinski(v3, v4, v6, depth - 1, graph);
216 return;
217 }
218 // depth==0, Construct graph:
219
220 unsigned nedges = graph[v1].nedges;
221 graph[v1].edges[nedges++] = v2;
222 graph[v1].edges[nedges++] = v3;
223 graph[v1].nedges = nedges;
224
225 nedges = graph[v2].nedges;
226 graph[v2].edges[nedges++] = v1;
227 graph[v2].edges[nedges++] = v3;
228 graph[v2].nedges = nedges;
229
230 nedges = graph[v3].nedges;
231 graph[v3].edges[nedges++] = v1;
232 graph[v3].edges[nedges++] = v2;
233 graph[v3].nedges = nedges;
234}
235
236void makeSierpinski(unsigned depth, edgefn ef) {
238
239 depth--;
240 const unsigned n = 3 * (1 + ((unsigned)(pow(3.0, depth) + 0.5) - 1) / 2);
241
242 graph = gv_calloc(n + 1, sizeof(vtx_data));
243 unsigned *edges = gv_calloc(4 * n, sizeof(unsigned));
244
245 for (unsigned i = 1; i <= n; i++) {
246 graph[i].edges = edges;
247 edges += 4;
248 graph[i].nedges = 0;
249 }
250
251 constructSierpinski(1, 2, 3, depth, graph);
252
253 for (unsigned i = 1; i <= n; i++) {
254 // write the neighbors of the node i
255 for (unsigned j = 0; j < graph[i].nedges; j++) {
256 const unsigned nghbr = graph[i].edges[j];
257 if (i < nghbr) ef( i, nghbr);
258 }
259 }
260
261 free(graph[1].edges);
262 free(graph);
263}
264
265static void constructTetrix(unsigned v1, unsigned v2, unsigned v3, unsigned v4,
266 unsigned depth, vtx_data* graph) {
267 static unsigned last_used_node_name = 4;
268
269 if (depth > 0) {
270 const unsigned v5 = ++last_used_node_name;
271 const unsigned v6 = ++last_used_node_name;
272 const unsigned v7 = ++last_used_node_name;
273 const unsigned v8 = ++last_used_node_name;
274 const unsigned v9 = ++last_used_node_name;
275 const unsigned v10 = ++last_used_node_name;
276 constructTetrix(v1, v5, v6, v8, depth - 1, graph);
277 constructTetrix(v2, v6, v7, v9, depth - 1, graph);
278 constructTetrix(v3, v5, v7, v10, depth - 1, graph);
279 constructTetrix(v4, v8, v9, v10, depth - 1, graph);
280 return;
281 }
282 // depth==0, Construct graph:
283 unsigned nedges = graph[v1].nedges;
284 graph[v1].edges[nedges++] = v2;
285 graph[v1].edges[nedges++] = v3;
286 graph[v1].edges[nedges++] = v4;
287 graph[v1].nedges = nedges;
288
289 nedges = graph[v2].nedges;
290 graph[v2].edges[nedges++] = v1;
291 graph[v2].edges[nedges++] = v3;
292 graph[v2].edges[nedges++] = v4;
293 graph[v2].nedges = nedges;
294
295 nedges = graph[v3].nedges;
296 graph[v3].edges[nedges++] = v1;
297 graph[v3].edges[nedges++] = v2;
298 graph[v3].edges[nedges++] = v4;
299 graph[v3].nedges = nedges;
300
301 nedges = graph[v4].nedges;
302 graph[v4].edges[nedges++] = v1;
303 graph[v4].edges[nedges++] = v2;
304 graph[v4].edges[nedges++] = v3;
305 graph[v4].nedges = nedges;
306}
307
308void makeTetrix(unsigned depth, edgefn ef) {
310
311 depth--;
312 const unsigned n = 4 + 2 * (((unsigned)(pow(4.0, depth) + 0.5) - 1));
313
314 graph = gv_calloc(n + 1, sizeof(vtx_data));
315 unsigned *edges = gv_calloc(6 * n, sizeof(unsigned));
316
317 for (unsigned i = 1; i <= n; i++) {
318 graph[i].edges = edges;
319 edges += 6;
320 graph[i].nedges = 0;
321 }
322
323 constructTetrix(1, 2, 3, 4, depth, graph);
324
325 for (unsigned i = 1; i <= n; i++) {
326 // write the neighbors of the node i
327 for (unsigned j = 0; j < graph[i].nedges; j++) {
328 const unsigned nghbr = graph[i].edges[j];
329 if (i < nghbr) ef( i, nghbr);
330 }
331 }
332
333 free(graph[1].edges);
334 free(graph);
335}
336
337void makeHypercube(unsigned dim, edgefn ef) {
338 const unsigned n = 1u << dim;
339
340 for (unsigned i = 0; i < n; i++) {
341 for (unsigned j = 0; j < dim; j++) {
342 const unsigned neighbor = (i ^ (1u << j)) + 1;
343 if (i < neighbor)
344 ef( i + 1, neighbor);
345 }
346 }
347}
348
349void makeTriMesh(unsigned sz, edgefn ef) {
350 if (sz == 1) {
351 ef (1, 0);
352 return;
353 }
354 ef(1,2);
355 ef(1,3);
356 unsigned idx = 2;
357 for (unsigned i = 2; i < sz; i++) {
358 for (unsigned j = 1; j <= i; j++) {
359 ef(idx,idx+i);
360 ef(idx,idx+i+1);
361 if (j < i)
362 ef(idx,idx+1);
363 idx++;
364 }
365 }
366 for (unsigned j = 1; j < sz; j++) {
367 ef (idx,idx+1);
368 idx++;
369 }
370}
371
372void makeBall(unsigned w, unsigned h, edgefn ef) {
373 makeCylinder (w, h, ef);
374
375 for (unsigned i = 1; i <= h; i++)
376 ef (0, i);
377
378 const unsigned cap = w * h + 1;
379 for (unsigned i = (w - 1) * h + 1; i <= w * h; i++)
380 ef (i, cap);
381
382}
383
384/* makeRandom:
385 * No. of nodes is largest 2^n - 1 less than or equal to h.
386 */
387void makeRandom(unsigned h, unsigned w, edgefn ef) {
388 const int type = rand() % 2;
389
390 unsigned size = 0;
391 unsigned depth = 0;
392 while (size <= h) {
393 size += 1u << depth;
394 depth++;
395 }
396 depth--;
397 if (size > h) {
398 size -= 1u << depth;
399 depth--;
400 }
401
402 if (type)
403 makeBinaryTree (depth, ef);
404 else
405 makePath (size, ef);
406
407 for (unsigned i = 3; i <= size; i++) {
408 for (unsigned j = 1; j + 1 < i; j++) {
409 const unsigned th = (unsigned)rand() % (size * size);
410 if ((th <= w * w && (i < 5 || (i + 4 > h && j + 4 > h))) || th <= w)
411 ef(j,i);
412 }
413 }
414}
415
416void makeMobius(unsigned w, unsigned h, edgefn ef) {
417 if (h == 1) {
418 fprintf(stderr, "Warning: degenerate Moebius strip of %u vertices\n", w);
419 makePath(w, ef);
420 return;
421 }
422 if (w == 1) {
423 fprintf(stderr, "Warning: degenerate Moebius strip of %u vertices\n", h);
424 makePath(h, ef);
425 return;
426 }
427
428 for (unsigned i = 0; i + 1 < w; i++) {
429 for (unsigned j = 1; j < h; j++){
430 ef(j + i*h, j + (i+1)*h);
431 ef(j + i*h, j+1 + i*h);
432 }
433 }
434
435 for (unsigned i = 1; i < h; i++){
436 ef (i + (w-1)*h, i+1 + (w-1)*h);
437 }
438 for (unsigned i=1; i < w; i++) {
439 ef(i*h , (i+1)*h);
440 ef(i*h, (w-i)*h+1);
441 }
442
443 ef(1,w*h);
444}
445
446typedef struct {
447 unsigned j, d;
448} pair;
449
450typedef struct {
451 unsigned top, root;
452 unsigned* p;
453} tree_t;
454
455static tree_t *mkTree(unsigned sz) {
456 tree_t* tp = gv_alloc(sizeof(tree_t));
457 tp->root = 0;
458 tp->top = 0;
459 tp->p = gv_calloc(sz, sizeof(unsigned));
460 return tp;
461}
462
463static void
465{
466 free (tp->p);
467 free (tp);
468}
469
470static void
472{
473 tp->root = 0;
474 tp->top = 0;
475}
476
477static unsigned treeRoot(tree_t* tp) {
478 return tp->root;
479}
480
481static unsigned prevRoot(tree_t *tp) {
482 return tp->p[tp->root];
483}
484
485static unsigned treeSize(tree_t *tp) {
486 return tp->top - tp->root + 1;
487}
488
489static unsigned treeTop(tree_t *tp) {
490 return tp->top;
491}
492
493static void
495{
496 tp->root = prevRoot(tp);
497}
498
499static void addTree(tree_t *tp, unsigned sz) {
500 tp->p[tp->top+1] = tp->root;
501 tp->root = tp->top+1;
502 tp->top += sz;
503 if (sz > 1) tp->p[tp->top] = tp->top-1;
504}
505
506static void treeDup(tree_t *tp, unsigned J) {
507 unsigned M = treeSize(tp);
508 unsigned L = treeRoot(tp);
509 unsigned LL = prevRoot(tp);
510 unsigned LS = L + (J-1)*M - 1;
511 for (unsigned i = L; i <= LS; i++) {
512 if ((i-L)%M == 0) tp->p[i+M] = LL;
513 else tp->p[i+M] = tp->p[i] + M;
514 }
515 tp->top = LS + M;
516}
517
518/*****************/
519
520DEFINE_LIST(int_stack, unsigned)
521
522static void push(int_stack_t *sp, unsigned j, unsigned d) {
523 int_stack_push_back(sp, j);
524 int_stack_push_back(sp, d);
525}
526
527static pair pop(int_stack_t *sp) {
528
529 // extract ints in the opposite order in which they were pushed
530 const unsigned d = int_stack_pop_back(sp);
531 const unsigned j = int_stack_pop_back(sp);
532
533 return (pair){j, d};
534}
535
536/*****************/
537
539static uint64_t umul(uint64_t a, uint64_t b) {
540 uint64_t res;
541 if (u64mul_overflow(a, b, &res)) {
542 fprintf(stderr, "integer overflow in %" PRIu64 " * %" PRIu64 "\n", a, b);
543 graphviz_exit(EXIT_FAILURE);
544 }
545 return res;
546}
547
549static uint64_t uadd(uint64_t a, uint64_t b) {
550 uint64_t res;
551 if (u64add_overflow(a, b, &res)) {
552 fprintf(stderr, "integer overflow in %" PRIu64 " + %" PRIu64 "\n", a, b);
553 graphviz_exit(EXIT_FAILURE);
554 }
555 return res;
556}
557
558static uint64_t *genCnt(unsigned NN) {
559 uint64_t *T = gv_calloc(NN + 1, sizeof(uint64_t));
560 unsigned NLAST = 1;
561 T[1] = 1;
562 while (NN > NLAST) {
563 uint64_t SUM = 0;
564 for (unsigned D = 1; D <= NLAST; D++) {
565 unsigned I = NLAST + 1;
566 const uint64_t TD = umul(T[D], D);
567 for (unsigned J = 1; J <= NLAST; J++) {
568 if (I <= D) break;
569 I = I-D;
570 SUM = uadd(SUM, umul(T[I], TD));
571 }
572 }
573 NLAST++;
574 T[NLAST] = SUM/(NLAST-1);
575 }
576 return T;
577}
578
579static void genTree(unsigned NN, uint64_t *T, int_stack_t *stack,
580 tree_t *TREE) {
581 pair p;
582 unsigned J;
583
584 unsigned N = NN;
585
586 while (1) {
587 while (N > 2) {
588 const uint64_t v = umul(N - 1, T[N]);
589 uint64_t Z = gv_random_u64(v);
590 unsigned D = 0;
591 bool more = true;
592 unsigned M;
593 do {
594 D++;
595 const uint64_t TD = umul(D, T[D]);
596 M = N;
597 J = 0;
598 do {
599 J++;
600 if (M < D + 1) break;
601 M -= D;
602 if (Z < umul(T[M], TD)) {
603 more = false;
604 break;
605 }
606 Z -= umul(T[M], TD);
607 } while (true);
608 } while (more);
609 push(stack, J, D);
610 N = M;
611 }
612 addTree (TREE, N);
613
614 while (1) {
615 p = pop(stack);
616 N = p.d;
617 if (N != 0) {
618 push(stack,p.j,0);
619 break;
620 }
621 J = p.j;
622 if (J > 1) treeDup (TREE, J);
623 if (treeTop(TREE) == NN) return;
624 treePop(TREE);
625 }
626 }
627
628}
629
630static void
632{
633 for (unsigned i = 2; i <= tp->top; i++)
634 ef (tp->p[i], i);
635}
636
637struct treegen_s {
638 unsigned N;
639 uint64_t *T;
640 int_stack_t sp;
642};
643
645 treegen_t* tg = gv_alloc(sizeof(treegen_t));
646
647 tg->N = N;
648 tg->T = genCnt(N);
649 tg->sp = (int_stack_t){0};
650 tg->tp = mkTree(N+1);
651
652 return tg;
653}
654
656{
657 int_stack_clear(&tg->sp);
658 resetTree(tg->tp);
659 genTree(tg->N, tg->T, &tg->sp, tg->tp);
660 writeTree (tg->tp, ef);
661}
662
663void
665{
666 free (tg->T);
667 int_stack_free(&tg->sp);
668 freeTree (tg->tp);
669 free (tg);
670}
671
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define N(n)
Definition bcomps.c:58
static Agnode_t * pop(void)
Definition ccomps.c:221
static NORETURN void graphviz_exit(int status)
Definition exit.h:23
expr procedure type
Definition exparse.y:206
#define I
Definition expr.h:71
static attrs_t * L
Definition gmlparse.c:93
void free(void *)
static void treePop(tree_t *tp)
static uint64_t * genCnt(unsigned NN)
void makeTriMesh(unsigned sz, edgefn ef)
static unsigned prevRoot(tree_t *tp)
void makeHypercube(unsigned dim, edgefn ef)
static void addTree(tree_t *tp, unsigned sz)
static unsigned treeSize(tree_t *tp)
static void constructSierpinski(unsigned v1, unsigned v2, unsigned v3, unsigned depth, vtx_data *graph)
void makeCircle(unsigned n, edgefn ef)
void makeTree(unsigned depth, unsigned nary, edgefn ef)
static uint64_t umul(uint64_t a, uint64_t b)
multiply two 64-bit unsigned integers, exiting on overflow
static void writeTree(tree_t *tp, edgefn ef)
void makeWheel(unsigned n, edgefn ef)
void makeSquareGrid(unsigned dim1, unsigned dim2, int connect_corners, int partial, edgefn ef)
void makeBinaryTree(unsigned depth, edgefn ef)
static void constructTetrix(unsigned v1, unsigned v2, unsigned v3, unsigned v4, unsigned depth, vtx_data *graph)
void makeComplete(unsigned n, edgefn ef)
void makeMobius(unsigned w, unsigned h, edgefn ef)
treegen_t * makeTreeGen(unsigned N)
void makeCompleteB(unsigned dim1, unsigned dim2, edgefn ef)
static void push(int_stack_t *sp, unsigned j, unsigned d)
void makeBall(unsigned w, unsigned h, edgefn ef)
static void genTree(unsigned NN, uint64_t *T, int_stack_t *stack, tree_t *TREE)
void makePath(unsigned n, edgefn ef)
static unsigned treeRoot(tree_t *tp)
static void resetTree(tree_t *tp)
void makeTetrix(unsigned depth, edgefn ef)
void makeCylinder(unsigned dim1, unsigned dim2, edgefn ef)
void makeStar(unsigned n, edgefn ef)
static void treeDup(tree_t *tp, unsigned J)
void freeTreeGen(treegen_t *tg)
void makeTorus(unsigned dim1, unsigned dim2, edgefn ef)
void makeTwistedTorus(unsigned dim1, unsigned dim2, unsigned t1, unsigned t2, edgefn ef)
#define OUTE(h)
void makeRandomTree(treegen_t *tg, edgefn ef)
void makeRandom(unsigned h, unsigned w, edgefn ef)
static void freeTree(tree_t *tp)
void makeSierpinski(unsigned depth, edgefn ef)
static uint64_t uadd(uint64_t a, uint64_t b)
add two 64-bit unsigned integers, exiting on overflow
static tree_t * mkTree(unsigned sz)
static unsigned treeTop(tree_t *tp)
Agraph_t * graph(char *name)
Definition gv.cpp:30
#define D
Definition hierarchy.c:120
static Agedge_t * top(edge_stack_t *sp)
Definition tred.c:73
#define DEFINE_LIST(name, type)
Definition list.h:22
#define neighbor(t, i, edim, elist)
Definition make_map.h:41
static const int dim
arithmetic overflow helpers
static bool u64mul_overflow(uint64_t a, uint64_t b, uint64_t *res)
Definition overflow.h:77
static bool u64add_overflow(uint64_t a, uint64_t b, uint64_t *res)
Definition overflow.h:51
uint64_t gv_random_u64(uint64_t bound)
Definition random.c:59
random number generation
#define M
Definition randomkit.c:90
static int nedges
total no. of edges used in routing
Definition routespl.c:31
unsigned j
unsigned d
unsigned top
unsigned root
unsigned * p
uint64_t * T
int_stack_t sp
unsigned nedges
unsigned * edges
static mytime_t T
Definition timing.c:41
void(* edgefn)(Agraph_t *, Agedge_t *, glCompColor)