1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15#include "config.h"
16
17#define DEBUG
18
19#include <stddef.h>
20#include <maze.h>
21#include <partition.h>
22#include <memory.h>
23#include <arith.h>
24/* #include <values.h> */
25
26#define MARGIN 36;
27
28#ifdef DEBUG
29char* pre = "%!PS-Adobe-2.0\n\
30/node {\n\
31 /Y exch def\n\
32 /X exch def\n\
33 /y exch def\n\
34 /x exch def\n\
35 newpath\n\
36 x y moveto\n\
37 x Y lineto\n\
38 X Y lineto\n\
39 X y lineto\n\
40 closepath fill\n\
41} def\n\
42/cell {\n\
43 /Y exch def\n\
44 /X exch def\n\
45 /y exch def\n\
46 /x exch def\n\
47 newpath\n\
48 x y moveto\n\
49 x Y lineto\n\
50 X Y lineto\n\
51 X y lineto\n\
52 closepath stroke\n\
53} def\n";
54
55char* post = "showpage\n";
56
57static void
58psdump (cell* gcells, int n_gcells, boxf BB, boxf* rects, int nrect)
59{
60 int i;
61 boxf bb;
62 box absbb;
63
64 absbb.LL.y = absbb.LL.x = 10;
65 absbb.UR.x = absbb.LL.x + BB.UR.x - BB.LL.x;
66 absbb.UR.y = absbb.LL.y + BB.UR.y - BB.LL.y;
67 fputs (pre, stderr);
68 fprintf (stderr, "%%%%Page: 1 1\n%%%%PageBoundingBox: %d %d %d %d\n",
69 absbb.LL.x, absbb.LL.y, absbb.UR.x, absbb.UR.y);
70
71
72 fprintf (stderr, "%f %f translate\n", 10-BB.LL.x, 10-BB.LL.y);
73 fputs ("0 0 1 setrgbcolor\n", stderr);
74 for (i = 0; i < n_gcells; i++) {
75 bb = gcells[i].bb;
76 fprintf (stderr, "%f %f %f %f node\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
77 }
78 fputs ("0 0 0 setrgbcolor\n", stderr);
79 for (i = 0; i < nrect; i++) {
80 bb = rects[i];
81 fprintf (stderr, "%f %f %f %f cell\n", bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
82 }
83 fputs ("1 0 0 setrgbcolor\n", stderr);
84 fprintf (stderr, "%f %f %f %f cell\n", BB.LL.x, BB.LL.y, BB.UR.x, BB.UR.y);
85 fputs (post, stderr);
86}
87#endif
88
89static int
90vcmpid(Dt_t* d, pointf* key1, pointf* key2, Dtdisc_t* disc)
91{
92 if (key1->x > key2->x) return 1;
93 else if (key1->x < key2->x) return -1;
94 else if (key1->y > key2->y) return 1;
95 else if (key1->y < key2->y) return -1;
96 else return 0;
97}
98
99static int
100hcmpid(Dt_t* d, pointf* key1, pointf* key2, Dtdisc_t* disc)
101{
102 if (key1->y > key2->y) return 1;
103 else if (key1->y < key2->y) return -1;
104 else if (key1->x > key2->x) return 1;
105 else if (key1->x < key2->x) return -1;
106 else return 0;
107}
108
109typedef struct {
110 snode* np;
111 pointf p;
112 Dtlink_t link;
113} snodeitem;
114
115static Dtdisc_t vdictDisc = {
116 offsetof(snodeitem,p),
117 sizeof(pointf),
118 offsetof(snodeitem,link),
119 0,
120 0,
121 (Dtcompar_f)vcmpid,
122 0,
123 0,
124 0
125};
126static Dtdisc_t hdictDisc = {
127 offsetof(snodeitem,p),
128 sizeof(pointf),
129 offsetof(snodeitem,link),
130 0,
131 0,
132 (Dtcompar_f)hcmpid,
133 0,
134 0,
135 0
136};
137
138#define delta 1 /* weight of length */
139#define mu 500 /* weight of bends */
140
141#define BEND(g,e) ((g->nodes + e->v1)->isVert != (g->nodes + e->v2)->isVert)
142#define HORZ(g,e) ((g->nodes + e->v1)->isVert)
143#define BIG 16384
144#define CHANSZ(w) (((w)-3)/2)
145#define IS_SMALL(v) (CHANSZ(v) < 2)
146/* #define CHANSZ(w) (w) */
147
148/* updateWt:
149 * At present, we use a step function. When a bound is reached, the weight
150 * becomes huge. We might consider bumping up the weight more gradually, the
151 * thinner the channel, the faster the weight rises.
152 */
153static void
154updateWt (cell* cp, sedge* ep, int sz)
155{
156 ep->cnt++;
157 if (ep->cnt > sz) {
158 ep->cnt = 0;
159 ep->weight += BIG;
160 }
161}
162
163/* updateWts:
164 * Iterate over edges in a cell, adjust weights as necessary.
165 * It always updates the bent edges belonging to a cell.
166 * A horizontal/vertical edge is updated only if the edge traversed
167 * is bent, or if it is the traversed edge.
168 */
169void
170updateWts (sgraph* g, cell* cp, sedge* ep)
171{
172 int i;
173 sedge* e;
174 int isBend = BEND(g,ep);
175 int hsz = CHANSZ (cp->bb.UR.y - cp->bb.LL.y);
176 int vsz = CHANSZ (cp->bb.UR.x - cp->bb.LL.x);
177 int minsz = MIN(hsz, vsz);
178
179 /* Bend edges are added first */
180 for (i = 0; i < cp->nedges; i++) {
181 e = cp->edges[i];
182 if (!BEND(g,e)) break;
183 updateWt (cp, e, minsz);
184}
185
186 for (; i < cp->nedges; i++) {
187 e = cp->edges[i];
188 if (isBend || (e == ep)) updateWt (cp, e, (HORZ(g,e)?hsz:vsz));
189 }
190}
191
192/* markSmall:
193 * cp corresponds to a real node. If it is small, its associated cells should
194 * be marked as usable.
195 */
196static void
197markSmall (cell* cp, sgraph* g)
198{
199 int i;
200 snode* onp;
201 cell* ocp;
202
203 if (IS_SMALL(cp->bb.UR.y-cp->bb.LL.y)) {
204 for (i = 0; i < cp->nsides; i++) {
205 onp = cp->sides[i];
206 if (!onp->isVert) continue;
207 if (onp->cells[0] == cp) { /* onp on the right of cp */
208 ocp = onp->cells[1];
209 ocp->flags |= MZ_SMALLV;
210 while ((onp = ocp->sides[M_RIGHT]) && !IsNode(onp->cells[1])) {
211 ocp = onp->cells[1];
212 ocp->flags |= MZ_SMALLV;
213 }
214 }
215 else { /* onp on the left of cp */
216 ocp = onp->cells[0];
217 ocp->flags |= MZ_SMALLV;
218 while ((onp = ocp->sides[M_LEFT]) && !IsNode(onp->cells[0])) {
219 ocp = onp->cells[0];
220 ocp->flags |= MZ_SMALLV;
221 }
222 }
223 }
224 }
225
226 if (IS_SMALL(cp->bb.UR.x-cp->bb.LL.x)) {
227 for (i = 0; i < cp->nsides; i++) {
228 onp = cp->sides[i];
229 if (onp->isVert) continue;
230 if (onp->cells[0] == cp) { /* onp on the top of cp */
231 ocp = onp->cells[1];
232 ocp->flags |= MZ_SMALLH;
233 while ((onp = ocp->sides[M_TOP]) && !IsNode(onp->cells[1])) {
234 ocp = onp->cells[1];
235 ocp->flags |= MZ_SMALLH;
236 }
237 }
238 else { /* onp on the bottom of cp */
239 ocp = onp->cells[0];
240 ocp->flags |= MZ_SMALLH;
241 while ((onp = ocp->sides[M_BOTTOM]) && !IsNode(onp->cells[0])) {
242 ocp = onp->cells[0];
243 ocp->flags |= MZ_SMALLH;
244 }
245 }
246 }
247 }
248}
249
250static void
251createSEdges (cell* cp, sgraph* g)
252{
253 boxf bb = cp->bb;
254 double hwt = delta*(bb.UR.x-bb.LL.x);
255 double vwt = delta*(bb.UR.y-bb.LL.y);
256 double wt = (hwt + vwt)/2.0 + mu;
257
258 /* We automatically make small channels have high cost to guide routes to
259 * more spacious channels.
260 */
261 if (IS_SMALL(bb.UR.y-bb.LL.y) && !IsSmallV(cp)) {
262 hwt = BIG;
263 wt = BIG;
264 }
265 if (IS_SMALL(bb.UR.x-bb.LL.x) && !IsSmallH(cp)) {
266 vwt = BIG;
267 wt = BIG;
268 }
269
270 if (cp->sides[M_LEFT] && cp->sides[M_TOP])
271 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_LEFT], cp->sides[M_TOP], wt);
272 if (cp->sides[M_TOP] && cp->sides[M_RIGHT])
273 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_TOP], cp->sides[M_RIGHT], wt);
274 if (cp->sides[M_LEFT] && cp->sides[M_BOTTOM])
275 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_LEFT], cp->sides[M_BOTTOM], wt);
276 if (cp->sides[M_BOTTOM] && cp->sides[M_RIGHT])
277 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_BOTTOM], cp->sides[M_RIGHT], wt);
278 if (cp->sides[M_TOP] && cp->sides[M_BOTTOM])
279 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_TOP], cp->sides[M_BOTTOM], vwt);
280 if (cp->sides[M_LEFT] && cp->sides[M_RIGHT])
281 cp->edges[cp->nedges++] = createSEdge (g, cp->sides[M_LEFT], cp->sides[M_RIGHT], hwt);
282}
283
284static snode*
285findSVert (sgraph* g, Dt_t* cdt, pointf p, snodeitem* ditems, boolean isVert)
286{
287 snodeitem* n = dtmatch (cdt, &p);
288
289 if (!n) {
290 snode* np = createSNode (g);
291 assert(ditems);
292 n = ditems + np->index;
293 n->p = p;
294 n->np = np;
295 np->isVert = isVert;
296 dtinsert (cdt, n);
297 }
298
299 return n->np;
300}
301
302static void
303chkSgraph (sgraph* g)
304{
305 int i;
306 snode* np;
307
308 for (i = 0; i < g->nnodes; i++) {
309 np = g->nodes+i;
310 if (!np->cells[0]) fprintf (stderr, "failed at node %d[0]\n", i);
311 assert (np->cells[0]);
312 if (!np->cells[1]) fprintf (stderr, "failed at node %d[1]\n", i);
313 assert (np->cells[1]);
314 }
315
316}
317
318/* mkMazeGraph:
319 */
320static sgraph*
321mkMazeGraph (maze* mp, boxf bb)
322{
323 int nsides, i, ncnt, maxdeg;
324 int bound = 4*mp->ncells;
325 sgraph* g = createSGraph (bound + 2);
326 Dt_t* vdict = dtopen(&vdictDisc,Dtoset);
327 Dt_t* hdict = dtopen(&hdictDisc,Dtoset);
328 snodeitem* ditems = N_NEW(bound, snodeitem);
329 snode** sides;
330
331 /* For each cell, create if necessary and attach a node in search
332 * corresponding to each internal face. The node also gets
333 * a pointer to the cell.
334 */
335 sides = N_NEW(4*mp->ncells, snode*);
336 ncnt = 0;
337 for (i = 0; i < mp->ncells; i++) {
338 cell* cp = mp->cells+i;
339 snode* np;
340 pointf pt;
341
342 cp->nsides = 4;
343 cp->sides = sides + 4*i;
344 if (cp->bb.UR.x < bb.UR.x) {
345 pt.x = cp->bb.UR.x;
346 pt.y = cp->bb.LL.y;
347 np = findSVert (g, vdict, pt, ditems, TRUE);
348 np->cells[0] = cp;
349 cp->sides[M_RIGHT] = np;
350 }
351 if (cp->bb.UR.y < bb.UR.y) {
352 pt.x = cp->bb.LL.x;
353 pt.y = cp->bb.UR.y;
354 np = findSVert (g, hdict, pt, ditems, FALSE);
355 np->cells[0] = cp;
356 cp->sides[M_TOP] = np;
357 }
358 if (cp->bb.LL.x > bb.LL.x) {
359 np = findSVert (g, vdict, cp->bb.LL, ditems, TRUE);
360 np->cells[1] = cp;
361 cp->sides[M_LEFT] = np;
362 }
363 if (cp->bb.LL.y > bb.LL.y) {
364 np = findSVert (g, hdict, cp->bb.LL, ditems, FALSE);
365 np->cells[1] = cp;
366 cp->sides[M_BOTTOM] = np;
367 }
368 }
369
370 /* For each gcell, corresponding to a node in the input graph,
371 * connect it to its corresponding search nodes.
372 */
373 maxdeg = 0;
374 sides = N_NEW(g->nnodes, snode*);
375 nsides = 0;
376 for (i = 0; i < mp->ngcells; i++) {
377 cell* cp = mp->gcells+i;
378 pointf pt;
379 snodeitem* np;
380
381 cp->sides = sides+nsides;
382 pt = cp->bb.LL;
383 np = dtmatch (hdict, &pt);
384 for (; np && np->p.x < cp->bb.UR.x; np = dtnext (hdict, np)) {
385 cp->sides[cp->nsides++] = np->np;
386 np->np->cells[1] = cp;
387 }
388 np = dtmatch (vdict, &pt);
389 for (; np && np->p.y < cp->bb.UR.y; np = dtnext (vdict, np)) {
390 cp->sides[cp->nsides++] = np->np;
391 np->np->cells[1] = cp;
392 }
393 pt.y = cp->bb.UR.y;
394 np = dtmatch (hdict, &pt);
395 for (; np && np->p.x < cp->bb.UR.x; np = dtnext (hdict, np)) {
396 cp->sides[cp->nsides++] = np->np;
397 np->np->cells[0] = cp;
398 }
399 pt.x = cp->bb.UR.x;
400 pt.y = cp->bb.LL.y;
401 np = dtmatch (vdict, &pt);
402 for (; np && np->p.y < cp->bb.UR.y; np = dtnext (vdict, np)) {
403 cp->sides[cp->nsides++] = np->np;
404 np->np->cells[0] = cp;
405 }
406 nsides += cp->nsides;
407 if (cp->nsides > maxdeg) maxdeg = cp->nsides;
408 }
409 /* sides = RALLOC (nsides, sides, snode*); */
410
411 /* Mark cells that are small because of a small node, not because of the close
412 * alignment of two rectangles.
413 */
414 for (i = 0; i < mp->ngcells; i++) {
415 cell* cp = mp->gcells+i;
416 markSmall (cp, g);
417 }
418
419 /* Set index of two dummy nodes used for real nodes */
420 g->nodes[g->nnodes].index = g->nnodes;
421 g->nodes[g->nnodes+1].index = g->nnodes+1;
422
423 /* create edges
424 * For each ordinary cell, there can be at most 6 edges.
425 * At most 2 gcells will be used at a time, and each of these
426 * can have at most degree maxdeg.
427 */
428 initSEdges (g, maxdeg);
429 for (i = 0; i < mp->ncells; i++) {
430 cell* cp = mp->cells+i;
431 createSEdges (cp, g);
432 }
433
434 /* tidy up memory */
435 /* g->nodes = RALLOC (g->nnodes+2, g->nodes, snode); */
436 /* g->edges = RALLOC (g->nedges+2*maxdeg, g->edges, sedge); */
437 dtclose (vdict);
438 dtclose (hdict);
439 free (ditems);
440
441chkSgraph (g);
442 /* save core graph state */
443 gsave(g);
444 return g;
445}
446
447/* mkMaze:
448 */
449maze*
450mkMaze (graph_t* g, int doLbls)
451{
452 node_t* n;
453 maze* mp = NEW(maze);
454 boxf* rects;
455 int i, nrect;
456 cell* cp;
457 double w2, h2;
458 boxf bb, BB;
459
460 mp->ngcells = agnnodes(g);
461 cp = mp->gcells = N_NEW(mp->ngcells, cell);
462
463 BB.LL.x = BB.LL.y = MAXDOUBLE;
464 BB.UR.x = BB.UR.y = -MAXDOUBLE;
465 for (n = agfstnode (g); n; n = agnxtnode(g,n)) {
466 w2 = ND_xsize(n)/2.0;
467 if (w2 < 1) w2 = 1;
468 h2 = ND_ysize(n)/2.0;
469 if (h2 < 1) h2 = 1;
470 bb.LL.x = ND_coord(n).x - w2;
471 bb.UR.x = ND_coord(n).x + w2;
472 bb.LL.y = ND_coord(n).y - h2;
473 bb.UR.y = ND_coord(n).y + h2;
474 BB.LL.x = MIN(BB.LL.x, bb.LL.x);
475 BB.LL.y = MIN(BB.LL.y, bb.LL.y);
476 BB.UR.x = MAX(BB.UR.x, bb.UR.x);
477 BB.UR.y = MAX(BB.UR.y, bb.UR.y);
478 cp->bb = bb;
479 cp->flags |= MZ_ISNODE;
480 ND_alg(n) = cp;
481 cp++;
482 }
483
484 if (doLbls) {
485 }
486
487 BB.LL.x -= MARGIN;
488 BB.LL.y -= MARGIN;
489 BB.UR.x += MARGIN;
490 BB.UR.y += MARGIN;
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 = N_NEW(nrect, cell);
497 mp->ncells = nrect;
498 for (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->gcells[0].sides);
511 free (mp->cells);
512 free (mp->gcells);
513 freeSGraph (mp->sg);
514 dtclose (mp->hchans);
515 dtclose (mp->vchans);
516 free (mp);
517}
518
519