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