Graphviz 13.1.2~dev.20250725.0048
Loading...
Searching...
No Matches
maze.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
12#include "config.h"
13
14#define DEBUG
15
16#include <assert.h>
17#include <float.h>
18#include <limits.h>
19#include <math.h>
20#include <stdbool.h>
21#include <stddef.h>
22#include <ortho/maze.h>
23#include <ortho/partition.h>
24#include <ortho/trap.h>
25#include <common/arith.h>
26#include <util/alloc.h>
27#include <util/list.h>
28
29#define MARGIN 36
30
31#ifdef DEBUG
32char* pre = "%!PS-Adobe-2.0\n\
33/node {\n\
34 /Y exch def\n\
35 /X exch def\n\
36 /y exch def\n\
37 /x exch def\n\
38 newpath\n\
39 x y moveto\n\
40 x Y lineto\n\
41 X Y lineto\n\
42 X y lineto\n\
43 closepath fill\n\
44} def\n\
45/cell {\n\
46 /Y exch def\n\
47 /X exch def\n\
48 /y exch def\n\
49 /x exch def\n\
50 newpath\n\
51 x y moveto\n\
52 x Y lineto\n\
53 X Y lineto\n\
54 X y lineto\n\
55 closepath stroke\n\
56} def\n";
57
58char* post = "showpage\n";
59
61
62static void psdump(cell *gcells, size_t n_gcells, boxf BB, boxf *rects,
63 size_t nrect) {
64 boxf bb;
65 boxf absbb = {.LL = {.y = 10.0, .x = 10.0}};
66
67 absbb.UR.x = absbb.LL.x + BB.UR.x - BB.LL.x;
68 absbb.UR.y = absbb.LL.y + BB.UR.y - BB.LL.y;
69 fputs (pre, stderr);
70 fprintf(stderr, "%%%%Page: 1 1\n%%%%PageBoundingBox: %.0f %.0f %.0f %.0f\n",
71 absbb.LL.x, absbb.LL.y, absbb.UR.x, absbb.UR.y);
72
73
74 fprintf (stderr, "%f %f translate\n", 10-BB.LL.x, 10-BB.LL.y);
75 fputs ("0 0 1 setrgbcolor\n", stderr);
76 for (size_t i = 0; i < n_gcells; i++) {
77 bb = gcells[i].bb;
78 fprintf (stderr, "%f %f %f %f node\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
79 }
80 fputs ("0 0 0 setrgbcolor\n", stderr);
81 for (size_t i = 0; i < nrect; i++) {
82 bb = rects[i];
83 fprintf (stderr, "%f %f %f %f cell\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
84 }
85 fputs ("1 0 0 setrgbcolor\n", stderr);
86 fprintf (stderr, "%f %f %f %f cell\n", BB.LL.x, BB.LL.y, BB.UR.x, BB.UR.y);
87 fputs (post, stderr);
88}
89#endif
90
92
93static int vcmpid(void *k1, void *k2) {
94 const pointf *key1 = k1;
95 const pointf *key2 = k2;
96 int dx = dfp_cmp(key1->x, key2->x);
97 if (dx != 0)
98 return dx;
99 return dfp_cmp(key1->y, key2->y);
100}
101
103
104static int hcmpid(void *k1, void *k2) {
105 const pointf *key1 = k1;
106 const pointf *key2 = k2;
107 int dy = dfp_cmp(key1->y, key2->y);
108 if (dy != 0)
109 return dy;
110 return dfp_cmp(key1->x, key2->x);
111}
112
113typedef struct {
117} snodeitem;
118
120 offsetof(snodeitem,p),
121 sizeof(pointf),
122 offsetof(snodeitem,link),
123 0,
124 0,
125 vcmpid,
126};
128 offsetof(snodeitem,p),
129 sizeof(pointf),
130 offsetof(snodeitem,link),
131 0,
132 0,
133 hcmpid,
134};
135
136#define delta 1 /* weight of length */
137#define mu 500 /* weight of bends */
138
139#define BEND(g,e) ((g->nodes + e->v1)->isVert != (g->nodes + e->v2)->isVert)
140#define HORZ(g,e) ((g->nodes + e->v1)->isVert)
141#define BIG 16384
142#define CHANSZ(w) (((w)-3)/2)
143#define IS_SMALL(v) (CHANSZ(v) < 2)
144
153static void updateWt(sedge *ep, double sz) {
154 ep->cnt++;
155 if (ep->cnt > sz) {
156 ep->cnt = 0;
157 ep->weight += BIG;
158 }
159}
160
170void
172{
173 int i;
174 sedge* e;
175 int isBend = BEND(g,ep);
176 const double hsz = CHANSZ(cp->bb.UR.y - cp->bb.LL.y);
177 const double vsz = CHANSZ(cp->bb.UR.x - cp->bb.LL.x);
178 const double minsz = fmin(hsz, vsz);
179
180 /* Bend edges are added first */
181 for (i = 0; i < cp->nedges; i++) {
182 e = cp->edges[i];
183 if (!BEND(g,e)) break;
184 updateWt (e, minsz);
185}
186
187 for (; i < cp->nedges; i++) {
188 e = cp->edges[i];
189 if (isBend || e == ep) updateWt (e, HORZ(g,e)?hsz:vsz);
190 }
191}
192
198static void
200{
201 snode* onp;
202 cell* ocp;
203
204 if (IS_SMALL(cp->bb.UR.y-cp->bb.LL.y)) {
205 for (size_t i = 0; i < cp->nsides; i++) {
206 onp = cp->sides[i];
207 if (!onp->isVert) continue;
208 if (onp->cells[0] == cp) { /* onp on the right of cp */
209 ocp = onp->cells[1];
210 ocp->flags |= MZ_SMALLV;
211 while ((onp = ocp->sides[M_RIGHT]) && !IsNode(onp->cells[1])) {
212 ocp = onp->cells[1];
213 ocp->flags |= MZ_SMALLV;
214 }
215 }
216 else { /* onp on the left of cp */
217 ocp = onp->cells[0];
218 ocp->flags |= MZ_SMALLV;
219 while ((onp = ocp->sides[M_LEFT]) && !IsNode(onp->cells[0])) {
220 ocp = onp->cells[0];
221 ocp->flags |= MZ_SMALLV;
222 }
223 }
224 }
225 }
226
227 if (IS_SMALL(cp->bb.UR.x-cp->bb.LL.x)) {
228 for (size_t i = 0; i < cp->nsides; i++) {
229 onp = cp->sides[i];
230 if (onp->isVert) continue;
231 if (onp->cells[0] == cp) { /* onp on the top of cp */
232 ocp = onp->cells[1];
233 ocp->flags |= MZ_SMALLH;
234 while ((onp = ocp->sides[M_TOP]) && !IsNode(onp->cells[1])) {
235 ocp = onp->cells[1];
236 ocp->flags |= MZ_SMALLH;
237 }
238 }
239 else { /* onp on the bottom of cp */
240 ocp = onp->cells[0];
241 ocp->flags |= MZ_SMALLH;
242 while ((onp = ocp->sides[M_BOTTOM]) && !IsNode(onp->cells[0])) {
243 ocp = onp->cells[0];
244 ocp->flags |= MZ_SMALLH;
245 }
246 }
247 }
248 }
249}
250
252
253static void
255{
256 boxf bb = cp->bb;
257 double hwt = delta*(bb.UR.x-bb.LL.x);
258 double vwt = delta*(bb.UR.y-bb.LL.y);
259 double wt = (hwt + vwt)/2.0 + mu;
260
261 /* We automatically make small channels have high cost to guide routes to
262 * more spacious channels.
263 */
264 if (IS_SMALL(bb.UR.y-bb.LL.y) && !IsSmallV(cp)) {
265 hwt = BIG;
266 wt = BIG;
267 }
268 if (IS_SMALL(bb.UR.x-bb.LL.x) && !IsSmallH(cp)) {
269 vwt = BIG;
270 wt = BIG;
271 }
272
273 if (cp->sides[M_LEFT] && cp->sides[M_TOP])
274 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_LEFT], cp->sides[M_TOP], wt);
275 if (cp->sides[M_TOP] && cp->sides[M_RIGHT])
276 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_TOP], cp->sides[M_RIGHT], wt);
277 if (cp->sides[M_LEFT] && cp->sides[M_BOTTOM])
278 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_LEFT], cp->sides[M_BOTTOM], wt);
279 if (cp->sides[M_BOTTOM] && cp->sides[M_RIGHT])
280 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_BOTTOM], cp->sides[M_RIGHT], wt);
281 if (cp->sides[M_TOP] && cp->sides[M_BOTTOM])
282 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_TOP], cp->sides[M_BOTTOM], vwt);
283 if (cp->sides[M_LEFT] && cp->sides[M_RIGHT])
284 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_LEFT], cp->sides[M_RIGHT], hwt);
285}
286
288
289static snode*
290findSVert (sgraph* g, Dt_t* cdt, pointf p, snodeitem* ditems, bool isVert)
291{
292 snodeitem* n = dtmatch (cdt, &p);
293
294 if (!n) {
295 snode* np = createSNode (g);
296 assert(ditems);
297 n = ditems + np->index;
298 n->p = p;
299 n->np = np;
300 np->isVert = isVert;
301 dtinsert (cdt, n);
302 }
303
304 return n->np;
305}
306
307static void
309{
310 int i;
311 snode* np;
312
313 for (i = 0; i < g->nnodes; i++) {
314 np = g->nodes+i;
315 if (!np->cells[0]) fprintf (stderr, "failed at node %d[0]\n", i);
316 assert (np->cells[0]);
317 if (!np->cells[1]) fprintf (stderr, "failed at node %d[1]\n", i);
318 assert (np->cells[1]);
319 }
320
321}
322
323DEFINE_LIST(snodes, snode *)
324
325
332static sgraph*
334{
335 const size_t bound = 4 * mp->ncells;
336 sgraph* g = createSGraph (bound + 2);
337 Dt_t* vdict = dtopen(&vdictDisc,Dtoset);
338 Dt_t* hdict = dtopen(&hdictDisc,Dtoset);
339 snodeitem* ditems = gv_calloc(bound, sizeof(snodeitem));
340 snode** sides;
341
342 /* For each cell, create if necessary and attach a node in search
343 * corresponding to each internal face. The node also gets
344 * a pointer to the cell.
345 */
346 sides = gv_calloc(4 * mp->ncells, sizeof(snode*));
347 for (size_t i = 0; i < mp->ncells; i++) {
348 cell* cp = mp->cells+i;
349 snode* np;
350 pointf pt;
351
352 cp->nsides = 4;
353 cp->sides = sides + 4*i;
354 if (cp->bb.UR.x < bb.UR.x) {
355 pt.x = cp->bb.UR.x;
356 pt.y = cp->bb.LL.y;
357 np = findSVert(g, vdict, pt, ditems, true);
358 np->cells[0] = cp;
359 cp->sides[M_RIGHT] = np;
360 }
361 if (cp->bb.UR.y < bb.UR.y) {
362 pt.x = cp->bb.LL.x;
363 pt.y = cp->bb.UR.y;
364 np = findSVert(g, hdict, pt, ditems, false);
365 np->cells[0] = cp;
366 cp->sides[M_TOP] = np;
367 }
368 if (cp->bb.LL.x > bb.LL.x) {
369 np = findSVert(g, vdict, cp->bb.LL, ditems, true);
370 np->cells[1] = cp;
371 cp->sides[M_LEFT] = np;
372 }
373 if (cp->bb.LL.y > bb.LL.y) {
374 np = findSVert(g, hdict, cp->bb.LL, ditems, false);
375 np->cells[1] = cp;
376 cp->sides[M_BOTTOM] = np;
377 }
378 }
379
380 /* For each gcell, corresponding to a node in the input graph,
381 * connect it to its corresponding search nodes.
382 */
383 size_t maxdeg = 0;
384 for (size_t i = 0; i < mp->ngcells; i++) {
385 cell *cp = &mp->gcells[i];
386 pointf pt;
387 snodeitem* np;
388
389 snodes_t cp_sides = {0};
390 pt = cp->bb.LL;
391 np = dtmatch (hdict, &pt);
392 for (; np && np->p.x < cp->bb.UR.x; np = dtnext (hdict, np)) {
393 snodes_append(&cp_sides, np->np);
394 np->np->cells[1] = cp;
395 }
396 np = dtmatch (vdict, &pt);
397 for (; np && np->p.y < cp->bb.UR.y; np = dtnext (vdict, np)) {
398 snodes_append(&cp_sides, np->np);
399 np->np->cells[1] = cp;
400 }
401 pt.y = cp->bb.UR.y;
402 np = dtmatch (hdict, &pt);
403 for (; np && np->p.x < cp->bb.UR.x; np = dtnext (hdict, np)) {
404 snodes_append(&cp_sides, np->np);
405 np->np->cells[0] = cp;
406 }
407 pt.x = cp->bb.UR.x;
408 pt.y = cp->bb.LL.y;
409 np = dtmatch (vdict, &pt);
410 for (; np && np->p.y < cp->bb.UR.y; np = dtnext (vdict, np)) {
411 snodes_append(&cp_sides, np->np);
412 np->np->cells[0] = cp;
413 }
414 cp->nsides = snodes_size(&cp_sides);
415 cp->sides = snodes_detach(&cp_sides);
416 if (cp->nsides > maxdeg) maxdeg = cp->nsides;
417 }
418
419 /* Mark cells that are small because of a small node, not because of the close
420 * alignment of two rectangles.
421 */
422 for (size_t i = 0; i < mp->ngcells; i++) {
423 cell *cp = &mp->gcells[i];
424 markSmall (cp);
425 }
426
427 /* Set index of two dummy nodes used for real nodes */
428 g->nodes[g->nnodes].index = g->nnodes;
429 g->nodes[g->nnodes+1].index = g->nnodes+1;
430
431 /* create edges
432 * For each ordinary cell, there can be at most 6 edges.
433 * At most 2 gcells will be used at a time, and each of these
434 * can have at most degree maxdeg.
435 */
436 initSEdges (g, maxdeg);
437 for (size_t i = 0; i < mp->ncells; i++) {
438 cell* cp = mp->cells+i;
439 createSEdges (cp, g);
440 }
441
442 /* tidy up memory */
443 dtclose (vdict);
444 dtclose (hdict);
445 free (ditems);
446
447chkSgraph (g);
448 /* save core graph state */
449 gsave(g);
450 return g;
451}
452
454
456 node_t* n;
457 maze* mp = gv_alloc(sizeof(maze));
458 boxf* rects;
459 cell* cp;
460 double w2, h2;
461 boxf bb;
462
463 assert(agnnodes(g) >= 0);
464 mp->ngcells = (size_t)agnnodes(g);
465 cp = mp->gcells = gv_calloc(mp->ngcells, sizeof(cell));
466
467 boxf BB = {.LL = {.x = DBL_MAX, .y = DBL_MAX},
468 .UR = {.x = -DBL_MAX, .y = -DBL_MAX}};
469 for (n = agfstnode (g); n; n = agnxtnode(g,n)) {
470 w2 = fmax(1, ND_xsize(n) / 2.0);
471 h2 = fmax(1, ND_ysize(n) / 2.0);
472 bb.LL.x = ND_coord(n).x - w2;
473 bb.UR.x = ND_coord(n).x + w2;
474 bb.LL.y = ND_coord(n).y - h2;
475 bb.UR.y = ND_coord(n).y + h2;
476 BB.LL.x = fmin(BB.LL.x, bb.LL.x);
477 BB.LL.y = fmin(BB.LL.y, bb.LL.y);
478 BB.UR.x = fmax(BB.UR.x, bb.UR.x);
479 BB.UR.y = fmax(BB.UR.y, bb.UR.y);
480 cp->bb = bb;
481 cp->flags |= MZ_ISNODE;
482 ND_alg(n) = cp;
483 cp++;
484 }
485
486 BB.LL.x -= MARGIN;
487 BB.LL.y -= MARGIN;
488 BB.UR.x += MARGIN;
489 BB.UR.y += MARGIN;
490 size_t nrect;
491 rects = partition(mp->gcells, mp->ngcells, &nrect, BB);
492
493#ifdef DEBUG
494 if (odb_flags & ODB_MAZE) psdump (mp->gcells, mp->ngcells, BB, rects, nrect);
495#endif
496 mp->cells = gv_calloc(nrect, sizeof(cell));
497 mp->ncells = nrect;
498 for (size_t i = 0; i < nrect; i++) {
499 mp->cells[i].bb = rects[i];
500 }
501 free (rects);
502
503 mp->sg = mkMazeGraph (mp, BB);
504 return mp;
505}
506
507void freeMaze (maze* mp)
508{
509 free (mp->cells[0].sides);
510 free (mp->cells);
511 for (size_t i = 0; i < mp->ngcells; ++i) {
512 free(mp->gcells[i].sides);
513 }
514 free (mp->gcells);
515 freeSGraph (mp->sg);
516 dtclose (mp->hchans);
517 dtclose (mp->vchans);
518 free (mp);
519}
520
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 dtmatch(d, o)
Definition cdt.h:184
#define dtinsert(d, o)
Definition cdt.h:185
CDT_API int dtclose(Dt_t *)
Definition dtclose.c:8
CDT_API Dtmethod_t * Dtoset
ordered set (self-adjusting tree)
Definition dttree.c:304
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition dtopen.c:9
#define dtnext(d, o)
Definition cdt.h:180
static float dy
Definition draw.c:39
static float dx
Definition draw.c:38
struct pointf_s pointf
void free(void *)
int agnnodes(Agraph_t *g)
Definition graph.c:157
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
#define ND_ysize(n)
Definition types.h:538
#define ND_alg(n)
Definition types.h:484
#define ND_coord(n)
Definition types.h:490
#define ND_xsize(n)
Definition types.h:537
#define DEFINE_LIST(name, type)
Definition list.h:22
static snode * findSVert(sgraph *g, Dt_t *cdt, pointf p, snodeitem *ditems, bool isVert)
finds a snode by point or creates it
Definition maze.c:290
static void createSEdges(cell *cp, sgraph *g)
fills cell::sides and sgraph::edges
Definition maze.c:254
#define mu
Definition maze.c:137
#define BIG
Definition maze.c:141
static int vcmpid(void *k1, void *k2)
compares points by X and then by Y
Definition maze.c:93
char * post
Definition maze.c:58
#define IS_SMALL(v)
Definition maze.c:143
#define HORZ(g, e)
Definition maze.c:140
static void psdump(cell *gcells, size_t n_gcells, boxf BB, boxf *rects, size_t nrect)
dumps maze::gcells and maze::cells via rects to PostScript
Definition maze.c:62
static sgraph * mkMazeGraph(maze *mp, boxf bb)
creates and fills sgraph for maze
Definition maze.c:333
maze * mkMaze(graph_t *g)
creates maze and fills maze::gcells and maze::cells. A subroutine of orthoEdges.
Definition maze.c:455
#define delta
Definition maze.c:136
#define CHANSZ(w)
Definition maze.c:142
void updateWts(sgraph *g, cell *cp, sedge *ep)
updates sedge::weight of cell edges
Definition maze.c:171
#define MARGIN
Definition maze.c:29
void freeMaze(maze *mp)
Definition maze.c:507
char * pre
Definition maze.c:32
static Dtdisc_t vdictDisc
Definition maze.c:119
static int hcmpid(void *k1, void *k2)
compares points by Y and then by X
Definition maze.c:104
static void chkSgraph(sgraph *g)
Definition maze.c:308
static void markSmall(cell *cp)
Definition maze.c:199
#define BEND(g, e)
Definition maze.c:139
static void updateWt(sedge *ep, double sz)
updates single sedge::weight
Definition maze.c:153
static Dtdisc_t hdictDisc
Definition maze.c:127
makes maze with mkMaze for routing orthogonal edges
#define IsSmallH(cp)
cell has small width corresponding to a small width node
Definition maze.h:38
@ M_TOP
Definition maze.h:21
@ M_RIGHT
Definition maze.h:21
@ M_BOTTOM
Definition maze.h:21
@ M_LEFT
Definition maze.h:21
#define IsSmallV(cp)
cell has small height corresponding to a small height node
Definition maze.h:36
#define MZ_SMALLH
Definition maze.h:27
#define MZ_ISNODE
Definition maze.h:23
#define IsNode(cp)
cell corresponds to node
Definition maze.h:30
#define MZ_SMALLV
Definition maze.h:26
int odb_flags
Definition ortho.c:51
boxf * partition(cell *cells, size_t ncells, size_t *nrects, boxf bb)
partitions space around cells (nodes) into rectangular tiles
Definition partition.c:673
function partition, subroutine of mkMaze
void freeSGraph(sgraph *g)
Definition sgraph.c:98
sedge * createSEdge(sgraph *g, snode *v1, snode *v2, double wt)
Definition sgraph.c:80
void gsave(sgraph *G)
Definition sgraph.c:19
snode * createSNode(sgraph *g)
Definition sgraph.c:64
sgraph * createSGraph(size_t nnodes)
Definition sgraph.c:54
void initSEdges(sgraph *g, size_t maxdeg)
Definition sgraph.c:40
graph or subgraph
Definition cgraph.h:424
Definition geom.h:41
pointf UR
Definition geom.h:41
pointf LL
Definition geom.h:41
result of partitioning available space, part of maze
Definition grid.h:33
int flags
Definition maze.h:43
size_t nsides
Definition maze.h:54
int nedges
Definition maze.h:44
boxf bb
Definition maze.h:56
sedge * edges[6]
up to six links (sedge) between four sides (snode) of the cell
Definition maze.h:45
snode ** sides
up to four sides: M_RIGHT, M_TOP, M_LEFT, M_BOTTOM
Definition maze.h:55
Definition cdt.h:100
available channels for orthogonal edges around nodes of graph_t
Definition maze.h:66
cell * cells
cells not corresponding to graph nodes
Definition maze.h:69
cell * gcells
cells corresponding to graph nodes
Definition maze.h:70
size_t ncells
Definition maze.h:67
Dt_t * vchans
set of vertical channels, created by extractVChans
Definition maze.h:73
size_t ngcells
Definition maze.h:68
Dt_t * hchans
set of horizontal channels, created by extractHChans.
Definition maze.h:72
sgraph * sg
search graph
Definition maze.h:71
double x
Definition geom.h:29
double y
Definition geom.h:29
Definition sgraph.h:42
double weight
Definition sgraph.h:43
int cnt
Definition sgraph.h:44
int nnodes
Definition sgraph.h:52
snode * nodes
Definition sgraph.h:54
a node of search graph sgraph, is created as a border segment between two adjusted cells of type cell...
Definition sgraph.h:26
bool isVert
Definition sgraph.h:39
int index
Definition sgraph.h:38
struct cell * cells[2]
[0] - left or botom, [1] - top or right adjusted cell
Definition sgraph.h:32
Dtlink_t link
Definition maze.c:116
snode * np
Definition maze.c:114
pointf p
Definition maze.c:115
trapezoid elements and utilities for partition.c
static int dfp_cmp(double f1, double f2)
double floating point three-way comparison
Definition trap.h:79