30 for (
unsigned i = 2; i <= n; i++)
39 for (
unsigned i = 1; i < n; i++) {
40 for (
unsigned j = i + 1; j <= n; j++) {
48 fprintf(stderr,
"Warning: degenerate circle of %u vertices\n", n);
53 for (
unsigned i = 1; i < n; i++)
60 fprintf(stderr,
"Warning: degenerate star of %u vertices\n", n);
65 for (
unsigned i = 2; i <= n; i++)
71 fprintf(stderr,
"Warning: degenerate wheel of %u vertices\n", n);
78 for (
unsigned i = 2; i < n; i++)
84 for (
unsigned i = 1; i <= dim1; i++) {
85 for (
unsigned j = 1; j <= dim2; j++) {
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);
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);
104 ef( i, dim2 * (dim1 - 1) + i);
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);
117 lj = (j + t2) % dim2;
118 ef(i+j*dim1+1, li+lj*dim1+1);
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);
128 ef( n + 1, n + dim2);
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);
139#define OUTE(h) if (tl < (hd=(h))) ef( tl, hd)
143 for (
unsigned i = 0; i < dim1; i++)
144 for (
unsigned j = 0; j < dim2; j++) {
146 const unsigned tl = i * dim2 + j + 1;
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);
154 ef(tl, (i + 1) * dim2 + j + 1);
156 if (connect_corners == 1) {
157 if (i == 0 && j == 0) {
158 OUTE((dim1 - 1) * dim2 + dim2);
159 }
else if (i + 1 == dim1 && j == 0) {
161 }
else if (i == 0 && j + 1 == dim2) {
162 OUTE((dim1 - 1) * dim2 + 1);
163 }
else if (i + 1 == dim1 && j + 1 == dim2) {
166 }
else if (connect_corners == 2) {
167 if (i == 0 && j == 0) {
169 }
else if (i + 1 == dim1 && j == 0) {
170 OUTE((dim1 - 1) * dim2 + dim2);
171 }
else if (i == 0 && j + 1 == dim2) {
173 }
else if (i + 1 == dim1 && j + 1 == dim2) {
174 OUTE((dim1 - 1) * dim2 + 1);
181 const double n = (pow(nary, depth) - 1) / (nary - 1);
184 for (
unsigned i = 1; i <= n; i++) {
185 for (
unsigned j = 0; j < nary; j++) {
192 const unsigned n = (1u << depth) - 1;
194 for (
unsigned i = 1; i <= n; i++) {
207 static unsigned last_used_node_name = 3;
210 const unsigned v4 = ++last_used_node_name;
211 const unsigned v5 = ++last_used_node_name;
212 const unsigned v6 = ++last_used_node_name;
240 const unsigned n = 3 * (1 + ((unsigned)(pow(3.0, depth) + 0.5) - 1) / 2);
243 unsigned *edges =
gv_calloc(4 * n,
sizeof(
unsigned));
245 for (
unsigned i = 1; i <= n; i++) {
246 graph[i].edges = edges;
253 for (
unsigned i = 1; i <= n; 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);
267 static unsigned last_used_node_name = 4;
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;
312 const unsigned n = 4 + 2 * (((unsigned)(pow(4.0, depth) + 0.5) - 1));
315 unsigned *edges =
gv_calloc(6 * n,
sizeof(
unsigned));
317 for (
unsigned i = 1; i <= n; i++) {
318 graph[i].edges = edges;
325 for (
unsigned i = 1; i <= n; 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);
338 const unsigned n = 1u <<
dim;
340 for (
unsigned i = 0; i < n; i++) {
341 for (
unsigned j = 0; j <
dim; j++) {
342 const unsigned neighbor = (i ^ (1u << j)) + 1;
357 for (
unsigned i = 2; i < sz; i++) {
358 for (
unsigned j = 1; j <= i; j++) {
366 for (
unsigned j = 1; j < sz; j++) {
375 for (
unsigned i = 1; i <= h; i++)
378 const unsigned cap = w * h + 1;
379 for (
unsigned i = (w - 1) * h + 1; i <= w * h; i++)
388 const int type = rand() % 2;
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)
418 fprintf(stderr,
"Warning: degenerate Moebius strip of %u vertices\n", w);
423 fprintf(stderr,
"Warning: degenerate Moebius strip of %u vertices\n", h);
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);
435 for (
unsigned i = 1; i < h; i++){
436 ef (i + (w-1)*h, i+1 + (w-1)*h);
438 for (
unsigned i=1; i < w; i++) {
482 return tp->
p[tp->
root];
503 if (sz > 1) tp->
p[tp->
top] = tp->
top-1;
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;
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);
530 const unsigned d = int_stack_pop_back(sp);
531 const unsigned j = int_stack_pop_back(sp);
539static uint64_t
umul(uint64_t a, uint64_t b) {
542 fprintf(stderr,
"integer overflow in %" PRIu64
" * %" PRIu64
"\n", a, b);
549static uint64_t
uadd(uint64_t a, uint64_t b) {
552 fprintf(stderr,
"integer overflow in %" PRIu64
" + %" PRIu64
"\n", a, b);
559 uint64_t *
T =
gv_calloc(NN + 1,
sizeof(uint64_t));
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++) {
574 T[NLAST] = SUM/(NLAST-1);
579static void genTree(
unsigned NN, uint64_t *
T, int_stack_t *stack,
588 const uint64_t v =
umul(
N - 1,
T[
N]);
595 const uint64_t TD =
umul(
D,
T[
D]);
600 if (
M <
D + 1)
break;
623 if (
treeTop(TREE) == NN)
return;
633 for (
unsigned i = 2; i <= tp->
top; i++)
649 tg->
sp = (int_stack_t){0};
657 int_stack_clear(&tg->
sp);
667 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 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)
uint64_t gv_random_u64(uint64_t bound)
static int nedges
total no. of edges used in routing
void(* edgefn)(Agraph_t *, Agedge_t *, glCompColor)