29 for (
unsigned i = 2; i <= n; i++)
38 for (
unsigned i = 1; i < n; i++) {
39 for (
unsigned j = i + 1; j <= n; j++) {
47 fprintf(stderr,
"Warning: degenerate circle of %u vertices\n", n);
52 for (
unsigned i = 1; i < n; i++)
59 fprintf(stderr,
"Warning: degenerate star of %u vertices\n", n);
64 for (
unsigned i = 2; i <= n; i++)
70 fprintf(stderr,
"Warning: degenerate wheel of %u vertices\n", n);
77 for (
unsigned i = 2; i < n; i++)
83 for (
unsigned i = 1; i <= dim1; i++) {
84 for (
unsigned j = 1; j <= dim2; j++) {
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);
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);
103 ef( i, dim2 * (dim1 - 1) + i);
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);
116 lj = (j + t2) % dim2;
117 ef(i+j*dim1+1, li+lj*dim1+1);
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);
127 ef( n + 1, n + dim2);
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);
138#define OUTE(h) if (tl < (hd=(h))) ef( tl, hd)
142 for (
unsigned i = 0; i < dim1; i++)
143 for (
unsigned j = 0; j < dim2; j++) {
145 const unsigned tl = i * dim2 + j + 1;
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);
153 ef(tl, (i + 1) * dim2 + j + 1);
155 if (connect_corners == 1) {
156 if (i == 0 && j == 0) {
157 OUTE((dim1 - 1) * dim2 + dim2);
158 }
else if (i + 1 == dim1 && j == 0) {
160 }
else if (i == 0 && j + 1 == dim2) {
161 OUTE((dim1 - 1) * dim2 + 1);
162 }
else if (i + 1 == dim1 && j + 1 == dim2) {
165 }
else if (connect_corners == 2) {
166 if (i == 0 && j == 0) {
168 }
else if (i + 1 == dim1 && j == 0) {
169 OUTE((dim1 - 1) * dim2 + dim2);
170 }
else if (i == 0 && j + 1 == dim2) {
172 }
else if (i + 1 == dim1 && j + 1 == dim2) {
173 OUTE((dim1 - 1) * dim2 + 1);
180 const double n = (pow(nary, depth) - 1) / (nary - 1);
183 for (
unsigned i = 1; i <= n; i++) {
184 for (
unsigned j = 0; j < nary; j++) {
191 const unsigned n = (1u << depth) - 1;
193 for (
unsigned i = 1; i <= n; i++) {
206 static unsigned last_used_node_name = 3;
209 const unsigned v4 = ++last_used_node_name;
210 const unsigned v5 = ++last_used_node_name;
211 const unsigned v6 = ++last_used_node_name;
239 const unsigned n = 3 * (1 + ((unsigned)(pow(3.0, depth) + 0.5) - 1) / 2);
242 unsigned *edges =
gv_calloc(4 * n,
sizeof(
unsigned));
244 for (
unsigned i = 1; i <= n; i++) {
245 graph[i].edges = edges;
252 for (
unsigned i = 1; i <= n; 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);
266 static unsigned last_used_node_name = 4;
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;
311 const unsigned n = 4 + 2 * (((unsigned)(pow(4.0, depth) + 0.5) - 1));
314 unsigned *edges =
gv_calloc(6 * n,
sizeof(
unsigned));
316 for (
unsigned i = 1; i <= n; i++) {
317 graph[i].edges = edges;
324 for (
unsigned i = 1; i <= n; 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);
337 const unsigned n = 1u <<
dim;
339 for (
unsigned i = 0; i < n; i++) {
340 for (
unsigned j = 0; j <
dim; j++) {
341 const unsigned neighbor = (i ^ (1u << j)) + 1;
356 for (
unsigned i = 2; i < sz; i++) {
357 for (
unsigned j = 1; j <= i; j++) {
365 for (
unsigned j = 1; j < sz; j++) {
374 for (
unsigned i = 1; i <= h; i++)
377 const unsigned cap = w * h + 1;
378 for (
unsigned i = (w - 1) * h + 1; i <= w * h; i++)
387 const int type = rand() % 2;
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)
417 fprintf(stderr,
"Warning: degenerate Moebius strip of %u vertices\n", w);
422 fprintf(stderr,
"Warning: degenerate Moebius strip of %u vertices\n", h);
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);
434 for (
unsigned i = 1; i < h; i++){
435 ef (i + (w-1)*h, i+1 + (w-1)*h);
437 for (
unsigned i=1; i < w; i++) {
481 return tp->
p[tp->
root];
502 if (sz > 1) tp->
p[tp->
top] = tp->
top-1;
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;
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);
529 const unsigned d = int_stack_pop_back(sp);
530 const unsigned j = int_stack_pop_back(sp);
538static uint64_t
umul(uint64_t a, uint64_t b) {
541 fprintf(stderr,
"integer overflow in %" PRIu64
" * %" PRIu64
"\n", a, b);
548static uint64_t
uadd(uint64_t a, uint64_t b) {
551 fprintf(stderr,
"integer overflow in %" PRIu64
" + %" PRIu64
"\n", a, b);
558 uint64_t *
T =
gv_calloc(NN + 1,
sizeof(uint64_t));
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++) {
573 T[NLAST] = SUM/(NLAST-1);
583 d = d / (RAND_MAX + 1.0);
587static void genTree(
unsigned NN, uint64_t *
T, int_stack_t *stack,
598 double Z = floor(v *
drand());
604 const uint64_t TD =
umul(
D,
T[
D]);
609 if (
M <
D + 1)
break;
632 if (
treeTop(TREE) == NN)
return;
642 for (
unsigned i = 2; i <= tp->
top; i++)
658 tg->
sp = (int_stack_t){0};
666 int_stack_clear(&tg->
sp);
676 int_stack_free(&tg->
sp);
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
static void * gv_alloc(size_t size)
static NORETURN void graphviz_exit(int status)
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)
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)
static Agedge_t * top(edge_stack_t *sp)
#define DEFINE_LIST(name, type)
#define neighbor(t, i, edim, elist)
arithmetic overflow helpers
static bool u64mul_overflow(uint64_t a, uint64_t b, uint64_t *res)
static bool u64add_overflow(uint64_t a, uint64_t b, uint64_t *res)
static int nedges
total no. of edges used in routing
void(* edgefn)(Agraph_t *, Agedge_t *, glCompColor)