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 /* Module for packing disconnected graphs together.
16 * Based on "Disconnected Graph Layout and the Polyomino Packing Approach",
17 * K. Freivalds et al., GD0'01, LNCS 2265, pp. 378-391.
18 */
19
20 #include <math.h>
21 #include <assert.h>
22 #include "render.h"
23 #include "pack.h"
24 #include "pointset.h"
25 #include <assert.h>
26
27 #define strneq(a,b,n) (!strncmp(a,b,n))
28
29 #define C 100 /* Max. avg. polyomino size */
30
31 #define MOVEPT(p) ((p).x += dx, (p).y += dy)
32 /* Given cell size s, GRID(x:double,s:int) returns how many cells are required by size x */
33 #define GRID(x,s) ((int)ceil((x)/(s)))
34 /* Given grid cell size s, CVAL(v:int,s:int) returns index of cell containing point v */
35 #define CVAL(v,s) ((v) >= 0 ? (v)/(s) : (((v)+1)/(s))-1)
36 /* Given grid cell size s, CELL(p:point,s:int) sets p to cell containing point p */
37 #define CELL(p,s) ((p).x = CVAL((p).x,s), (p).y = CVAL((p).y,(s)))
38
39 typedef struct {
40 int perim; /* half size of bounding rectangle perimeter */
41 point *cells; /* cells in covering polyomino */
42 int nc; /* no. of cells */
43 int index; /* index in original array */
44 } ginfo;
45
46 typedef struct {
47 double width, height;
48 int index; /* index in original array */
49 } ainfo;
50
51 /* computeStep:
52 * Compute grid step size. This is a root of the
53 * quadratic equation al^2 +bl + c, where a, b and
54 * c are defined below.
55 */
computeStep(int ng,boxf * bbs,unsigned int margin)56 static int computeStep(int ng, boxf* bbs, unsigned int margin)
57 {
58 double l1, l2;
59 double a, b, c, d, r;
60 double W, H; /* width and height of graph, with margin */
61 int i, root;
62
63 a = C * ng - 1;
64 c = 0;
65 b = 0;
66 for (i = 0; i < ng; i++) {
67 boxf bb = bbs[i];
68 W = bb.UR.x - bb.LL.x + 2 * margin;
69 H = bb.UR.y - bb.LL.y + 2 * margin;
70 b -= (W + H);
71 c -= (W * H);
72 }
73 d = b * b - 4.0 * a * c;
74 if (d < 0) {
75 agerr(AGERR, "libpack: disc = %f ( < 0)\n", d);
76 return -1;
77 }
78 r = sqrt(d);
79 l1 = (-b + r) / (2 * a);
80 l2 = (-b - r) / (2 * a);
81 root = (int) l1;
82 if (root == 0) root = 1;
83 if (Verbose > 2) {
84 fprintf(stderr, "Packing: compute grid size\n");
85 fprintf(stderr, "a %f b %f c %f d %f r %f\n", a, b, c, d, r);
86 fprintf(stderr, "root %d (%f) %d (%f)\n", root, l1, (int) l2,
87 l2);
88 fprintf(stderr, " r1 %f r2 %f\n", a * l1 * l1 + b * l1 + c,
89 a * l2 * l2 + b * l2 + c);
90 }
91
92 return root;
93 }
94
95 /* cmpf;
96 * Comparison function for polyominoes.
97 * Size is determined by perimeter.
98 */
cmpf(const void * X,const void * Y)99 static int cmpf(const void *X, const void *Y)
100 {
101 ginfo *x = *(ginfo **) X;
102 ginfo *y = *(ginfo **) Y;
103 /* flip order to get descending array */
104 return (y->perim - x->perim);
105 }
106
107 /* fillLine:
108 * Mark cells crossed by line from cell p to cell q.
109 * Bresenham's algorithm, from Graphics Gems I, pp. 99-100.
110 */
fillLine(pointf p,pointf q,PointSet * ps)111 static void fillLine(pointf p, pointf q, PointSet * ps)
112 {
113 int x1 = ROUND(p.x);
114 int y1 = ROUND(p.y);
115 int x2 = ROUND(q.x);
116 int y2 = ROUND(q.y);
117 int d, x, y, ax, ay, sx, sy, dx, dy;
118
119 dx = x2 - x1;
120 ax = ABS(dx) << 1;
121 sx = SGN(dx);
122 dy = y2 - y1;
123 ay = ABS(dy) << 1;
124 sy = SGN(dy);
125
126 /* fprintf (stderr, "fillLine %d %d - %d %d\n", x1,y1,x2,y2); */
127 x = x1;
128 y = y1;
129 if (ax > ay) { /* x dominant */
130 d = ay - (ax >> 1);
131 for (;;) {
132 /* fprintf (stderr, " addPS %d %d\n", x,y); */
133 addPS(ps, x, y);
134 if (x == x2)
135 return;
136 if (d >= 0) {
137 y += sy;
138 d -= ax;
139 }
140 x += sx;
141 d += ay;
142 }
143 } else { /* y dominant */
144 d = ax - (ay >> 1);
145 for (;;) {
146 /* fprintf (stderr, " addPS %d %d\n", x,y); */
147 addPS(ps, x, y);
148 if (y == y2)
149 return;
150 if (d >= 0) {
151 x += sx;
152 d -= ay;
153 }
154 y += sy;
155 d += ax;
156 }
157 }
158 }
159
160 /* fillEdge:
161 * It appears that spline_edges always have the start point at the
162 * beginning and the end point at the end.
163 */
164 static void
fillEdge(Agedge_t * e,point p,PointSet * ps,int dx,int dy,int ssize,int doS)165 fillEdge(Agedge_t * e, point p, PointSet * ps, int dx, int dy,
166 int ssize, int doS)
167 {
168 int j, k;
169 bezier bz;
170 pointf pt, hpt;
171 Agnode_t *h;
172
173 P2PF(p, pt);
174
175 /* If doS is false or the edge has not splines, use line segment */
176 if (!doS || !ED_spl(e)) {
177 h = aghead(e);
178 hpt = coord(h);
179 MOVEPT(hpt);
180 CELL(hpt, ssize);
181 fillLine(pt, hpt, ps);
182 return;
183 }
184
185 for (j = 0; j < ED_spl(e)->size; j++) {
186 bz = ED_spl(e)->list[j];
187 if (bz.sflag) {
188 pt = bz.sp;
189 hpt = bz.list[0];
190 k = 1;
191 } else {
192 pt = bz.list[0];
193 hpt = bz.list[1];
194 k = 2;
195 }
196 MOVEPT(pt);
197 CELL(pt, ssize);
198 MOVEPT(hpt);
199 CELL(hpt, ssize);
200 fillLine(pt, hpt, ps);
201
202 for (; k < bz.size; k++) {
203 pt = hpt;
204 hpt = bz.list[k];
205 MOVEPT(hpt);
206 CELL(hpt, ssize);
207 fillLine(pt, hpt, ps);
208 }
209
210 if (bz.eflag) {
211 pt = hpt;
212 hpt = bz.ep;
213 MOVEPT(hpt);
214 CELL(hpt, ssize);
215 fillLine(pt, hpt, ps);
216 }
217 }
218
219 }
220
221 /* genBox:
222 * Generate polyomino info from graph using the bounding box of
223 * the graph.
224 */
225 static void
genBox(boxf bb0,ginfo * info,int ssize,unsigned int margin,point center,char * s)226 genBox(boxf bb0, ginfo * info, int ssize, unsigned int margin, point center,
227 char* s)
228 {
229 PointSet *ps;
230 int W, H;
231 point UR, LL;
232 box bb;
233 int x, y;
234
235 BF2B(bb0, bb);
236 ps = newPS();
237
238 LL.x = center.x - margin;
239 LL.y = center.y - margin;
240 UR.x = center.x + bb.UR.x - bb.LL.x + margin;
241 UR.y = center.y + bb.UR.y - bb.LL.y + margin;
242 CELL(LL, ssize);
243 CELL(UR, ssize);
244
245 for (x = LL.x; x <= UR.x; x++)
246 for (y = LL.y; y <= UR.y; y++)
247 addPS(ps, x, y);
248
249 info->cells = pointsOf(ps);
250 info->nc = sizeOf(ps);
251 W = GRID(bb0.UR.x - bb0.LL.x + 2 * margin, ssize);
252 H = GRID(bb0.UR.y - bb0.LL.y + 2 * margin, ssize);
253 info->perim = W + H;
254
255 if (Verbose > 2) {
256 int i;
257 fprintf(stderr, "%s no. cells %d W %d H %d\n",
258 s, info->nc, W, H);
259 for (i = 0; i < info->nc; i++)
260 fprintf(stderr, " %d %d cell\n", info->cells[i].x,
261 info->cells[i].y);
262 }
263
264 freePS(ps);
265 }
266
267 /* genPoly:
268 * Generate polyomino info from graph.
269 * We add all cells covered partially by the bounding box of the
270 * node. If doSplines is true and an edge has a spline, we use the
271 * polyline determined by the control point. Otherwise,
272 * we use each cell crossed by a straight edge between the head and tail.
273 * If mode = l_clust, we use the graph's GD_clust array to treat the
274 * top level clusters like large nodes.
275 * Returns 0 if okay.
276 */
277 static int
genPoly(Agraph_t * root,Agraph_t * g,ginfo * info,int ssize,pack_info * pinfo,point center)278 genPoly(Agraph_t * root, Agraph_t * g, ginfo * info,
279 int ssize, pack_info * pinfo, point center)
280 {
281 PointSet *ps;
282 int W, H;
283 point LL, UR;
284 point pt, s2;
285 pointf ptf;
286 Agraph_t *eg; /* graph containing edges */
287 Agnode_t *n;
288 Agedge_t *e;
289 int x, y;
290 int dx, dy;
291 graph_t *subg;
292 unsigned int margin = pinfo->margin;
293 int doSplines = pinfo->doSplines;
294 box bb;
295
296 if (root)
297 eg = root;
298 else
299 eg = g;
300
301 ps = newPS();
302 dx = center.x - ROUND(GD_bb(g).LL.x);
303 dy = center.y - ROUND(GD_bb(g).LL.y);
304
305 if (pinfo->mode == l_clust) {
306 int i;
307 void **alg;
308
309 /* backup the alg data */
310 alg = N_GNEW(agnnodes(g), void *);
311 for (i = 0, n = agfstnode(g); n; n = agnxtnode(g, n)) {
312 alg[i++] = ND_alg(n);
313 ND_alg(n) = 0;
314 }
315
316 /* do bbox of top clusters */
317 for (i = 1; i <= GD_n_cluster(g); i++) {
318 subg = GD_clust(g)[i];
319 BF2B(GD_bb(subg), bb);
320 if ((bb.UR.x > bb.LL.x) && (bb.UR.y > bb.LL.y)) {
321 MOVEPT(bb.LL);
322 MOVEPT(bb.UR);
323 bb.LL.x -= margin;
324 bb.LL.y -= margin;
325 bb.UR.x += margin;
326 bb.UR.y += margin;
327 CELL(bb.LL, ssize);
328 CELL(bb.UR, ssize);
329
330 for (x = bb.LL.x; x <= bb.UR.x; x++)
331 for (y = bb.LL.y; y <= bb.UR.y; y++)
332 addPS(ps, x, y);
333
334 /* note which nodes are in clusters */
335 for (n = agfstnode(subg); n; n = agnxtnode(subg, n))
336 ND_clust(n) = subg;
337 }
338 }
339
340 /* now do remaining nodes and edges */
341 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
342 ptf = coord(n);
343 PF2P(ptf, pt);
344 MOVEPT(pt);
345 if (!ND_clust(n)) { /* n is not in a top-level cluster */
346 s2.x = margin + ND_xsize(n) / 2;
347 s2.y = margin + ND_ysize(n) / 2;
348 LL = sub_point(pt, s2);
349 UR = add_point(pt, s2);
350 CELL(LL, ssize);
351 CELL(UR, ssize);
352
353 for (x = LL.x; x <= UR.x; x++)
354 for (y = LL.y; y <= UR.y; y++)
355 addPS(ps, x, y);
356
357 CELL(pt, ssize);
358 for (e = agfstout(eg, n); e; e = agnxtout(eg, e)) {
359 fillEdge(e, pt, ps, dx, dy, ssize, doSplines);
360 }
361 } else {
362 CELL(pt, ssize);
363 for (e = agfstout(eg, n); e; e = agnxtout(eg, e)) {
364 if (ND_clust(n) == ND_clust(aghead(e)))
365 continue;
366 fillEdge(e, pt, ps, dx, dy, ssize, doSplines);
367 }
368 }
369 }
370
371 /* restore the alg data */
372 for (i = 0, n = agfstnode(g); n; n = agnxtnode(g, n)) {
373 ND_alg(n)= alg[i++];
374 }
375 free(alg);
376
377 } else
378 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
379 ptf = coord(n);
380 PF2P(ptf, pt);
381 MOVEPT(pt);
382 s2.x = margin + ND_xsize(n) / 2;
383 s2.y = margin + ND_ysize(n) / 2;
384 LL = sub_point(pt, s2);
385 UR = add_point(pt, s2);
386 CELL(LL, ssize);
387 CELL(UR, ssize);
388
389 for (x = LL.x; x <= UR.x; x++)
390 for (y = LL.y; y <= UR.y; y++)
391 addPS(ps, x, y);
392
393 CELL(pt, ssize);
394 for (e = agfstout(eg, n); e; e = agnxtout(eg, e)) {
395 fillEdge(e, pt, ps, dx, dy, ssize, doSplines);
396 }
397 }
398
399 info->cells = pointsOf(ps);
400 info->nc = sizeOf(ps);
401 W = GRID(GD_bb(g).UR.x - GD_bb(g).LL.x + 2 * margin, ssize);
402 H = GRID(GD_bb(g).UR.y - GD_bb(g).LL.y + 2 * margin, ssize);
403 info->perim = W + H;
404
405 if (Verbose > 2) {
406 int i;
407 fprintf(stderr, "%s no. cells %d W %d H %d\n",
408 agnameof(g), info->nc, W, H);
409 for (i = 0; i < info->nc; i++)
410 fprintf(stderr, " %d %d cell\n", info->cells[i].x,
411 info->cells[i].y);
412 }
413
414 freePS(ps);
415 return 0;
416 }
417
418 /* fits:
419 * Check if polyomino fits at given point.
420 * If so, add cells to pointset, store point in place and return true.
421 */
422 static int
fits(int x,int y,ginfo * info,PointSet * ps,point * place,int step,boxf * bbs)423 fits(int x, int y, ginfo * info, PointSet * ps, point * place, int step, boxf* bbs)
424 {
425 point *cells = info->cells;
426 int n = info->nc;
427 point cell;
428 int i;
429 point LL;
430
431 for (i = 0; i < n; i++) {
432 cell = *cells;
433 cell.x += x;
434 cell.y += y;
435 if (inPS(ps, cell))
436 return 0;
437 cells++;
438 }
439
440 PF2P(bbs[info->index].LL, LL);
441 place->x = step * x - LL.x;
442 place->y = step * y - LL.y;
443
444 cells = info->cells;
445 for (i = 0; i < n; i++) {
446 cell = *cells;
447 cell.x += x;
448 cell.y += y;
449 insertPS(ps, cell);
450 cells++;
451 }
452
453 if (Verbose >= 2)
454 fprintf(stderr, "cc (%d cells) at (%d,%d) (%d,%d)\n", n, x, y,
455 place->x, place->y);
456 return 1;
457 }
458
459 /* placeFixed:
460 * Position fixed graph. Store final translation and
461 * fill polyomino set. Note that polyomino set for the
462 * graph is constructed where it will be.
463 */
464 static void
placeFixed(ginfo * info,PointSet * ps,point * place,point center)465 placeFixed(ginfo * info, PointSet * ps, point * place, point center)
466 {
467 point *cells = info->cells;
468 int n = info->nc;
469 int i;
470
471 place->x = -center.x;
472 place->y = -center.y;
473
474 for (i = 0; i < n; i++) {
475 insertPS(ps, *cells++);
476 }
477
478 if (Verbose >= 2)
479 fprintf(stderr, "cc (%d cells) at (%d,%d)\n", n, place->x,
480 place->y);
481 }
482
483 /* placeGraph:
484 * Search for points on concentric "circles" out
485 * from the origin. Check if polyomino can be placed
486 * with bounding box origin at point.
487 * First graph (i == 0) is centered on the origin if possible.
488 */
489 static void
placeGraph(int i,ginfo * info,PointSet * ps,point * place,int step,unsigned int margin,boxf * bbs)490 placeGraph(int i, ginfo * info, PointSet * ps, point * place, int step,
491 unsigned int margin, boxf* bbs)
492 {
493 int x, y;
494 int W, H;
495 int bnd;
496 boxf bb = bbs[info->index];
497
498 if (i == 0) {
499 W = GRID(bb.UR.x - bb.LL.x + 2 * margin, step);
500 H = GRID(bb.UR.y - bb.LL.y + 2 * margin, step);
501 if (fits(-W / 2, -H / 2, info, ps, place, step, bbs))
502 return;
503 }
504
505 if (fits(0, 0, info, ps, place, step, bbs))
506 return;
507 W = ceil(bb.UR.x - bb.LL.x);
508 H = ceil(bb.UR.y - bb.LL.y);
509 if (W >= H) {
510 for (bnd = 1;; bnd++) {
511 x = 0;
512 y = -bnd;
513 for (; x < bnd; x++)
514 if (fits(x, y, info, ps, place, step, bbs))
515 return;
516 for (; y < bnd; y++)
517 if (fits(x, y, info, ps, place, step, bbs))
518 return;
519 for (; x > -bnd; x--)
520 if (fits(x, y, info, ps, place, step, bbs))
521 return;
522 for (; y > -bnd; y--)
523 if (fits(x, y, info, ps, place, step, bbs))
524 return;
525 for (; x < 0; x++)
526 if (fits(x, y, info, ps, place, step, bbs))
527 return;
528 }
529 } else {
530 for (bnd = 1;; bnd++) {
531 y = 0;
532 x = -bnd;
533 for (; y > -bnd; y--)
534 if (fits(x, y, info, ps, place, step, bbs))
535 return;
536 for (; x < bnd; x++)
537 if (fits(x, y, info, ps, place, step, bbs))
538 return;
539 for (; y < bnd; y++)
540 if (fits(x, y, info, ps, place, step, bbs))
541 return;
542 for (; x > -bnd; x--)
543 if (fits(x, y, info, ps, place, step, bbs))
544 return;
545 for (; y > 0; y--)
546 if (fits(x, y, info, ps, place, step, bbs))
547 return;
548 }
549 }
550 }
551
552 #ifdef DEBUG
dumpp(ginfo * info,char * pfx)553 void dumpp(ginfo * info, char *pfx)
554 {
555 point *cells = info->cells;
556 int i, c_cnt = info->nc;
557
558 fprintf(stderr, "%s\n", pfx);
559 for (i = 0; i < c_cnt; i++) {
560 fprintf(stderr, "%d %d box\n", cells[i].x, cells[i].y);
561 }
562 }
563 #endif
564
565 static packval_t* userVals;
566
567 /* ucmpf;
568 * Sort by user values.
569 */
ucmpf(const void * X,const void * Y)570 static int ucmpf(const void *X, const void *Y)
571 {
572 ainfo* x = *(ainfo **) X;
573 ainfo* y = *(ainfo **) Y;
574
575 int dX = userVals[x->index];
576 int dY = userVals[y->index];
577 if (dX > dY) return 1;
578 else if (dX < dY) return -1;
579 else return 0;
580 }
581
582 /* acmpf;
583 * Sort by height + width
584 */
acmpf(const void * X,const void * Y)585 static int acmpf(const void *X, const void *Y)
586 {
587 ainfo* x = *(ainfo **) X;
588 ainfo* y = *(ainfo **) Y;
589 #if 0
590 if (x->height < y->height) return 1;
591 else if (x->height > y->height) return -1;
592 else if (x->width < y->width) return 1;
593 else if (x->width > y->width) return -1;
594 else return 0;
595 #endif
596 double dX = x->height + x->width;
597 double dY = y->height + y->width;
598 if (dX < dY) return 1;
599 else if (dX > dY) return -1;
600 else return 0;
601 }
602
603 #define INC(m,c,r) \
604 if (m){ c++; if (c == nc) { c = 0; r++; } } \
605 else { r++; if (r == nr) { r = 0; c++; } }
606
607 /* arrayRects:
608 */
609 static point *
arrayRects(int ng,boxf * gs,pack_info * pinfo)610 arrayRects (int ng, boxf* gs, pack_info* pinfo)
611 {
612 int i;
613 int nr = 0, nc;
614 int r, c;
615 ainfo *info;
616 ainfo *ip;
617 ainfo **sinfo;
618 double* widths;
619 double* heights;
620 double v, wd, ht;
621 point* places = N_NEW(ng, point);
622 boxf bb;
623 int sz, rowMajor;
624
625 /* set up no. of rows and columns */
626 sz = pinfo->sz;
627 if (pinfo->flags & PK_COL_MAJOR) {
628 rowMajor = 0;
629 if (sz > 0) {
630 nr = sz;
631 nc = (ng + (nr-1))/nr;
632 }
633 else {
634 nr = ceil(sqrt(ng));
635 nc = (ng + (nr-1))/nr;
636 }
637 }
638 else {
639 rowMajor = 1;
640 if (sz > 0) {
641 nc = sz;
642 nr = (ng + (nc-1))/nc;
643 }
644 else {
645 nc = ceil(sqrt(ng));
646 nr = (ng + (nc-1))/nc;
647 }
648 }
649 if (Verbose)
650 fprintf (stderr, "array packing: %s %d rows %d columns\n", (rowMajor?"row major":"column major"), nr, nc);
651 widths = N_NEW(nc+1, double);
652 heights = N_NEW(nr+1, double);
653
654 ip = info = N_NEW(ng, ainfo);
655 for (i = 0; i < ng; i++, ip++) {
656 bb = gs[i];
657 ip->width = bb.UR.x - bb.LL.x + pinfo->margin;
658 ip->height = bb.UR.y - bb.LL.y + pinfo->margin;
659 ip->index = i;
660 }
661
662 sinfo = N_NEW(ng, ainfo*);
663 for (i = 0; i < ng; i++) {
664 sinfo[i] = info + i;
665 }
666
667 if (pinfo->vals) {
668 userVals = pinfo->vals;
669 qsort(sinfo, ng, sizeof(ainfo *), ucmpf);
670 }
671 else if (!(pinfo->flags & PK_INPUT_ORDER)) {
672 qsort(sinfo, ng, sizeof(ainfo *), acmpf);
673 }
674
675 /* compute column widths and row heights */
676 r = c = 0;
677 for (i = 0; i < ng; i++, ip++) {
678 ip = sinfo[i];
679 widths[c] = MAX(widths[c],ip->width);
680 heights[r] = MAX(heights[r],ip->height);
681 INC(rowMajor,c,r);
682 }
683
684 /* convert widths and heights to positions */
685 wd = 0;
686 for (i = 0; i <= nc; i++) {
687 v = widths[i];
688 widths[i] = wd;
689 wd += v;
690 }
691
692 ht = 0;
693 for (i = nr; 0 < i; i--) {
694 v = heights[i-1];
695 heights[i] = ht;
696 ht += v;
697 }
698 heights[0] = ht;
699
700 /* position rects */
701 r = c = 0;
702 for (i = 0; i < ng; i++, ip++) {
703 int idx;
704 ip = sinfo[i];
705 idx = ip->index;
706 bb = gs[idx];
707 if (pinfo->flags & PK_LEFT_ALIGN)
708 places[idx].x = widths[c];
709 else if (pinfo->flags & PK_RIGHT_ALIGN)
710 places[idx].x = widths[c+1] - (bb.UR.x - bb.LL.x);
711 else
712 places[idx].x = (widths[c] + widths[c+1] - bb.UR.x - bb.LL.x)/2.0;
713 if (pinfo->flags & PK_TOP_ALIGN)
714 places[idx].y = heights[r] - (bb.UR.y - bb.LL.y);
715 else if (pinfo->flags & PK_BOT_ALIGN)
716 places[idx].y = heights[r+1];
717 else
718 places[idx].y = (heights[r] + heights[r+1] - bb.UR.y - bb.LL.y)/2.0;
719 INC(rowMajor,c,r);
720 }
721
722 free (info);
723 free (sinfo);
724 free (widths);
725 free (heights);
726 return places;
727 }
728
729 static point*
polyRects(int ng,boxf * gs,pack_info * pinfo)730 polyRects(int ng, boxf* gs, pack_info * pinfo)
731 {
732 int stepSize;
733 ginfo *info;
734 ginfo **sinfo;
735 point *places;
736 Dict_t *ps;
737 int i;
738 point center;
739
740 /* calculate grid size */
741 stepSize = computeStep(ng, gs, pinfo->margin);
742 if (Verbose)
743 fprintf(stderr, "step size = %d\n", stepSize);
744 if (stepSize <= 0)
745 return 0;
746
747 /* generate polyomino cover for the rectangles */
748 center.x = center.y = 0;
749 info = N_NEW(ng, ginfo);
750 for (i = 0; i < ng; i++) {
751 info[i].index = i;
752 genBox(gs[i], info + i, stepSize, pinfo->margin, center, "");
753 }
754
755 /* sort */
756 sinfo = N_NEW(ng, ginfo *);
757 for (i = 0; i < ng; i++) {
758 sinfo[i] = info + i;
759 }
760 qsort(sinfo, ng, sizeof(ginfo *), cmpf);
761
762 ps = newPS();
763 places = N_NEW(ng, point);
764 for (i = 0; i < ng; i++)
765 placeGraph(i, sinfo[i], ps, places + (sinfo[i]->index),
766 stepSize, pinfo->margin, gs);
767
768 free(sinfo);
769 for (i = 0; i < ng; i++)
770 free(info[i].cells);
771 free(info);
772 freePS(ps);
773
774 if (Verbose > 1)
775 for (i = 0; i < ng; i++)
776 fprintf(stderr, "pos[%d] %d %d\n", i, places[i].x,
777 places[i].y);
778
779 return places;
780 }
781
782 /* polyGraphs:
783 * Given a collection of graphs, reposition them in the plane
784 * to not overlap but pack "nicely".
785 * ng is the number of graphs
786 * gs is a pointer to an array of graph pointers
787 * root gives the graph containing the edges; if null, the function
788 * looks in each graph in gs for its edges
789 * pinfo->margin gives the amount of extra space left around nodes in points
790 * If pinfo->doSplines is true, use edge splines, if computed,
791 * in calculating polyomino.
792 * pinfo->mode specifies the packing granularity and technique:
793 * l_node : pack at the node/cluster level
794 * l_graph : pack at the bounding box level
795 * Returns array of points to which graphs should be translated;
796 * the array needs to be freed;
797 * Returns NULL if problem occur or if ng == 0.
798 *
799 * Depends on graph fields GD_bb, node fields ND_pos(inches), ND_xsize and
800 * ND_ysize, and edge field ED_spl.
801 *
802 * FIX: fixed mode does not always work. The fixed ones get translated
803 * back to be centered on the origin.
804 * FIX: Check CELL and GRID macros for negative coordinates
805 * FIX: Check width and height computation
806 */
807 static point*
polyGraphs(int ng,Agraph_t ** gs,Agraph_t * root,pack_info * pinfo)808 polyGraphs(int ng, Agraph_t ** gs, Agraph_t * root, pack_info * pinfo)
809 {
810 int stepSize;
811 ginfo *info;
812 ginfo **sinfo;
813 point *places;
814 Dict_t *ps;
815 int i;
816 boolean *fixed = pinfo->fixed;
817 int fixed_cnt = 0;
818 box bb, fixed_bb = { {0, 0}, {0, 0} };
819 point center;
820 boxf* bbs;
821
822 if (ng <= 0)
823 return 0;
824
825 /* update bounding box info for each graph */
826 /* If fixed, compute bbox of fixed graphs */
827 for (i = 0; i < ng; i++) {
828 Agraph_t *g = gs[i];
829 compute_bb(g);
830 if (fixed && fixed[i]) {
831 BF2B(GD_bb(g), bb);
832 if (fixed_cnt) {
833 fixed_bb.LL.x = MIN(bb.LL.x, fixed_bb.LL.x);
834 fixed_bb.LL.y = MIN(bb.LL.y, fixed_bb.LL.y);
835 fixed_bb.UR.x = MAX(bb.UR.x, fixed_bb.UR.x);
836 fixed_bb.UR.y = MAX(bb.UR.y, fixed_bb.UR.y);
837 } else
838 fixed_bb = bb;
839 fixed_cnt++;
840 }
841 if (Verbose > 2) {
842 fprintf(stderr, "bb[%s] %.5g %.5g %.5g %.5g\n", agnameof(g),
843 GD_bb(g).LL.x, GD_bb(g).LL.y,
844 GD_bb(g).UR.x, GD_bb(g).UR.y);
845 }
846 }
847
848 /* calculate grid size */
849 bbs = N_GNEW(ng, boxf);
850 for (i = 0; i < ng; i++)
851 bbs[i] = GD_bb(gs[i]);
852 stepSize = computeStep(ng, bbs, pinfo->margin);
853 if (Verbose)
854 fprintf(stderr, "step size = %d\n", stepSize);
855 if (stepSize <= 0)
856 return 0;
857
858 /* generate polyomino cover for the graphs */
859 if (fixed) {
860 center.x = (fixed_bb.LL.x + fixed_bb.UR.x) / 2;
861 center.y = (fixed_bb.LL.y + fixed_bb.UR.y) / 2;
862 } else
863 center.x = center.y = 0;
864 info = N_NEW(ng, ginfo);
865 for (i = 0; i < ng; i++) {
866 Agraph_t *g = gs[i];
867 info[i].index = i;
868 if (pinfo->mode == l_graph)
869 genBox(GD_bb(g), info + i, stepSize, pinfo->margin, center, agnameof(g));
870 else if (genPoly(root, gs[i], info + i, stepSize, pinfo, center)) {
871 return 0;
872 }
873 }
874
875 /* sort */
876 sinfo = N_NEW(ng, ginfo *);
877 for (i = 0; i < ng; i++) {
878 sinfo[i] = info + i;
879 }
880 qsort(sinfo, ng, sizeof(ginfo *), cmpf);
881
882 ps = newPS();
883 places = N_NEW(ng, point);
884 if (fixed) {
885 for (i = 0; i < ng; i++) {
886 if (fixed[i])
887 placeFixed(sinfo[i], ps, places + (sinfo[i]->index),
888 center);
889 }
890 for (i = 0; i < ng; i++) {
891 if (!fixed[i])
892 placeGraph(i, sinfo[i], ps, places + (sinfo[i]->index),
893 stepSize, pinfo->margin, bbs);
894 }
895 } else {
896 for (i = 0; i < ng; i++)
897 placeGraph(i, sinfo[i], ps, places + (sinfo[i]->index),
898 stepSize, pinfo->margin, bbs);
899 }
900
901 free(sinfo);
902 for (i = 0; i < ng; i++)
903 free(info[i].cells);
904 free(info);
905 freePS(ps);
906 free (bbs);
907
908 if (Verbose > 1)
909 for (i = 0; i < ng; i++)
910 fprintf(stderr, "pos[%d] %d %d\n", i, places[i].x,
911 places[i].y);
912
913 return places;
914 }
915
putGraphs(int ng,Agraph_t ** gs,Agraph_t * root,pack_info * pinfo)916 point *putGraphs(int ng, Agraph_t ** gs, Agraph_t * root,
917 pack_info * pinfo)
918 {
919 int i, v;
920 boxf* bbs;
921 Agraph_t* g;
922 point* pts = NULL;
923 char* s;
924
925 if (ng <= 0) return NULL;
926
927 if (pinfo->mode <= l_graph)
928 return polyGraphs (ng, gs, root, pinfo);
929
930 bbs = N_GNEW(ng, boxf);
931
932 for (i = 0; i < ng; i++) {
933 g = gs[i];
934 compute_bb(g);
935 bbs[i] = GD_bb(g);
936 }
937
938 if (pinfo->mode == l_array) {
939 if (pinfo->flags & PK_USER_VALS) {
940 pinfo->vals = N_NEW(ng, packval_t);
941 for (i = 0; i < ng; i++) {
942 s = agget (gs[i], "sortv");
943 if (s && (sscanf (s, "%d", &v) > 0) && (v >= 0))
944 pinfo->vals[i] = v;
945 }
946
947 }
948 pts = arrayRects (ng, bbs, pinfo);
949 if (pinfo->flags & PK_USER_VALS)
950 free (pinfo->vals);
951 }
952
953 free (bbs);
954
955 return pts;
956 }
957
958 point *
putRects(int ng,boxf * bbs,pack_info * pinfo)959 putRects(int ng, boxf* bbs, pack_info* pinfo)
960 {
961 if (ng <= 0) return NULL;
962 if ((pinfo->mode == l_node) || (pinfo->mode == l_clust)) return NULL;
963 if (pinfo->mode == l_graph)
964 return polyRects (ng, bbs, pinfo);
965 else if (pinfo->mode == l_array)
966 return arrayRects (ng, bbs, pinfo);
967 else
968 return NULL;
969 }
970
971 /* packRects:
972 * Packs rectangles.
973 * ng - number of rectangles
974 * bbs - array of rectangles
975 * info - parameters used in packing
976 * This decides where to layout the rectangles and repositions
977 * the bounding boxes.
978 *
979 * Returns 0 on success.
980 */
981 int
packRects(int ng,boxf * bbs,pack_info * pinfo)982 packRects(int ng, boxf* bbs, pack_info* pinfo)
983 {
984 int i;
985 point *pp;
986 boxf bb;
987 point p;
988
989 if (ng < 0) return -1;
990 if (ng <= 1) return 0;
991
992 pp = putRects(ng, bbs, pinfo);
993 if (!pp)
994 return 1;
995
996 for (i = 0; i < ng; i++) {
997 bb = bbs[i];
998 p = pp[i];
999 bb.LL.x += p.x;
1000 bb.UR.x += p.x;
1001 bb.LL.y += p.y;
1002 bb.UR.y += p.y;
1003 bbs[i] = bb;
1004 }
1005 free(pp);
1006 return 0;
1007 }
1008
1009 /* shiftEdge:
1010 * Translate all of the edge components by the given offset.
1011 */
shiftEdge(Agedge_t * e,int dx,int dy)1012 static void shiftEdge(Agedge_t * e, int dx, int dy)
1013 {
1014 int j, k;
1015 bezier bz;
1016
1017 if (ED_label(e))
1018 MOVEPT(ED_label(e)->pos);
1019 if (ED_xlabel(e))
1020 MOVEPT(ED_xlabel(e)->pos);
1021 if (ED_head_label(e))
1022 MOVEPT(ED_head_label(e)->pos);
1023 if (ED_tail_label(e))
1024 MOVEPT(ED_tail_label(e)->pos);
1025
1026 if (ED_spl(e) == NULL)
1027 return;
1028
1029 for (j = 0; j < ED_spl(e)->size; j++) {
1030 bz = ED_spl(e)->list[j];
1031 for (k = 0; k < bz.size; k++)
1032 MOVEPT(bz.list[k]);
1033 if (bz.sflag)
1034 MOVEPT(ED_spl(e)->list[j].sp);
1035 if (bz.eflag)
1036 MOVEPT(ED_spl(e)->list[j].ep);
1037 }
1038 }
1039
1040 /* shiftGraph:
1041 */
shiftGraph(Agraph_t * g,int dx,int dy)1042 static void shiftGraph(Agraph_t * g, int dx, int dy)
1043 {
1044 graph_t *subg;
1045 boxf bb = GD_bb(g);
1046 int i;
1047
1048 bb = GD_bb(g);
1049 bb.LL.x += dx;
1050 bb.UR.x += dx;
1051 bb.LL.y += dy;
1052 bb.UR.y += dy;
1053 GD_bb(g) = bb;
1054
1055 if (GD_label(g) && GD_label(g)->set)
1056 MOVEPT(GD_label(g)->pos);
1057
1058 for (i = 1; i <= GD_n_cluster(g); i++) {
1059 subg = GD_clust(g)[i];
1060 shiftGraph(subg, dx, dy);
1061 }
1062 }
1063
1064 /* shiftGraphs:
1065 * The function takes ng graphs gs and a similar
1066 * number of points pp and translates each graph so
1067 * that the lower left corner of the bounding box of graph gs[i] is at
1068 * point ps[i]. To do this, it assumes the bb field in
1069 * Agraphinfo_t accurately reflects the current graph layout.
1070 * The graph is repositioned by translating the pos and coord fields of
1071 * each node appropriately.
1072 *
1073 * If doSplines is non-zero, the function also translates splines coordinates
1074 * of each edge, if they have been calculated. In addition, edge labels are
1075 * repositioned.
1076 *
1077 * If root is non-NULL, it is taken as the root graph of
1078 * the graphs in gs and is used to find the edges. Otherwise, the function
1079 * uses the edges found in each graph gs[i].
1080 *
1081 * It returns 0 on success.
1082 *
1083 * This function uses the bb field in Agraphinfo_t,
1084 * the pos and coord fields in nodehinfo_t and
1085 * the spl field in Aedgeinfo_t.
1086 */
1087 int
shiftGraphs(int ng,Agraph_t ** gs,point * pp,Agraph_t * root,int doSplines)1088 shiftGraphs(int ng, Agraph_t ** gs, point * pp, Agraph_t * root,
1089 int doSplines)
1090 {
1091 int i;
1092 int dx, dy;
1093 double fx, fy;
1094 point p;
1095 Agraph_t *g;
1096 Agraph_t *eg;
1097 Agnode_t *n;
1098 Agedge_t *e;
1099
1100 if (ng <= 0)
1101 return abs(ng);
1102
1103 for (i = 0; i < ng; i++) {
1104 g = gs[i];
1105 if (root)
1106 eg = root;
1107 else
1108 eg = g;
1109 p = pp[i];
1110 dx = p.x;
1111 dy = p.y;
1112 fx = PS2INCH(dx);
1113 fy = PS2INCH(dy);
1114
1115 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1116 ND_pos(n)[0] += fx;
1117 ND_pos(n)[1] += fy;
1118 MOVEPT(ND_coord(n));
1119 if (ND_xlabel(n)) {
1120 MOVEPT(ND_xlabel(n)->pos);
1121 }
1122 if (doSplines) {
1123 for (e = agfstout(eg, n); e; e = agnxtout(eg, e))
1124 shiftEdge(e, dx, dy);
1125 }
1126 }
1127 shiftGraph(g, dx, dy);
1128 }
1129
1130 return 0;
1131 }
1132
1133 /* packGraphs:
1134 * Packs graphs.
1135 * ng - number of graphs
1136 * gs - pointer to array of graphs
1137 * root - graph used to find edges
1138 * info - parameters used in packing
1139 * info->doSplines - if true, use already computed spline control points
1140 * This decides where to layout the graphs and repositions the graph's
1141 * position info.
1142 *
1143 * Returns 0 on success.
1144 */
packGraphs(int ng,Agraph_t ** gs,Agraph_t * root,pack_info * info)1145 int packGraphs(int ng, Agraph_t ** gs, Agraph_t * root, pack_info * info)
1146 {
1147 int ret;
1148 point *pp = putGraphs(ng, gs, root, info);
1149
1150 if (!pp)
1151 return 1;
1152 ret = shiftGraphs(ng, gs, pp, root, info->doSplines);
1153 free(pp);
1154 return ret;
1155 }
1156
1157 /* packSubgraphs:
1158 * Packs subgraphs of given root graph, then recalculates root's bounding box.
1159 * Note that it does not recompute subgraph bounding boxes.
1160 * Cluster bounding boxes are recomputed in shiftGraphs.
1161 */
1162 int
packSubgraphs(int ng,Agraph_t ** gs,Agraph_t * root,pack_info * info)1163 packSubgraphs(int ng, Agraph_t ** gs, Agraph_t * root, pack_info * info)
1164 {
1165 int ret;
1166
1167 ret = packGraphs(ng, gs, root, info);
1168 if (ret == 0) {
1169 int i, j;
1170 boxf bb;
1171 graph_t* g;
1172
1173 compute_bb(root);
1174 bb = GD_bb(root);
1175 for (i = 0; i < ng; i++) {
1176 g = gs[i];
1177 for (j = 1; j <= GD_n_cluster(g); j++) {
1178 EXPANDBB(bb,GD_bb(GD_clust(g)[j]));
1179 }
1180 }
1181 GD_bb(root) = bb;
1182 }
1183 return ret;
1184 }
1185
1186 /* pack_graph:
1187 * Pack subgraphs followed by postprocessing.
1188 */
1189 int
pack_graph(int ng,Agraph_t ** gs,Agraph_t * root,boolean * fixed)1190 pack_graph(int ng, Agraph_t** gs, Agraph_t* root, boolean* fixed)
1191 {
1192 int ret;
1193 pack_info info;
1194
1195 getPackInfo(root, l_graph, CL_OFFSET, &info);
1196 info.doSplines = 1;
1197 info.fixed = fixed;
1198 ret = packSubgraphs(ng, gs, root, &info);
1199 if (ret == 0) dotneato_postprocess (root);
1200 return ret;
1201 }
1202
1203 #define ARRAY "array"
1204 #define ASPECT "aspect"
1205 #define SLEN(s) (sizeof(s)/sizeof(char) - 1)
1206
1207 static char*
chkFlags(char * p,pack_info * pinfo)1208 chkFlags (char* p, pack_info* pinfo)
1209 {
1210 int c, more;
1211
1212 if (*p != '_') return p;
1213 p++;
1214 more = 1;
1215 while (more && (c = *p)) {
1216 switch (c) {
1217 case 'c' :
1218 pinfo->flags |= PK_COL_MAJOR;
1219 p++;
1220 break;
1221 case 'i' :
1222 pinfo->flags |= PK_INPUT_ORDER;
1223 p++;
1224 break;
1225 case 'u' :
1226 pinfo->flags |= PK_USER_VALS;
1227 p++;
1228 break;
1229 case 't' :
1230 pinfo->flags |= PK_TOP_ALIGN;
1231 p++;
1232 break;
1233 case 'b' :
1234 pinfo->flags |= PK_BOT_ALIGN;
1235 p++;
1236 break;
1237 case 'l' :
1238 pinfo->flags |= PK_LEFT_ALIGN;
1239 p++;
1240 break;
1241 case 'r' :
1242 pinfo->flags |= PK_RIGHT_ALIGN;
1243 p++;
1244 break;
1245 default :
1246 more = 0;
1247 break;
1248 }
1249 }
1250 return p;
1251 }
1252
1253 static char*
mode2Str(pack_mode m)1254 mode2Str (pack_mode m)
1255 {
1256 char *s;
1257
1258 switch (m) {
1259 case l_clust:
1260 s = "cluster";
1261 break;
1262 case l_node:
1263 s = "node";
1264 break;
1265 case l_graph:
1266 s = "graph";
1267 break;
1268 case l_array:
1269 s = "array";
1270 break;
1271 case l_aspect:
1272 s = "aspect";
1273 break;
1274 case l_undef:
1275 default:
1276 s = "undefined";
1277 break;
1278 }
1279 return s;
1280 }
1281
1282 /* parsePackModeInfo;
1283 * Return pack_mode of graph using "packmode" attribute.
1284 * If not defined, return dflt
1285 */
1286 pack_mode
parsePackModeInfo(char * p,pack_mode dflt,pack_info * pinfo)1287 parsePackModeInfo(char* p, pack_mode dflt, pack_info* pinfo)
1288 {
1289 float v;
1290 int i;
1291
1292 assert (pinfo);
1293 pinfo->flags = 0;
1294 pinfo->mode = dflt;
1295 pinfo->sz = 0;
1296 pinfo->vals = NULL;
1297 if (p && *p) {
1298 switch (*p) {
1299 case 'a':
1300 if (strneq(p, ARRAY, SLEN(ARRAY))) {
1301 pinfo->mode = l_array;
1302 p += SLEN(ARRAY);
1303 p = chkFlags (p, pinfo);
1304 if ((sscanf (p, "%d", &i)>0) && (i > 0))
1305 pinfo->sz = i;
1306 }
1307 else if (strneq(p, ASPECT, SLEN(ASPECT))) {
1308 pinfo->mode = l_aspect;
1309 if ((sscanf (p + SLEN(ARRAY), "%f", &v)>0) && (v > 0))
1310 pinfo->aspect = v;
1311 else
1312 pinfo->aspect = 1;
1313 }
1314 break;
1315 #ifdef NOT_IMPLEMENTED
1316 case 'b':
1317 if (streq(p, "bisect"))
1318 pinfo->mode = l_bisect;
1319 break;
1320 #endif
1321 case 'c':
1322 if (streq(p, "cluster"))
1323 pinfo->mode = l_clust;
1324 break;
1325 case 'g':
1326 if (streq(p, "graph"))
1327 pinfo->mode = l_graph;
1328 break;
1329 #ifdef NOT_IMPLEMENTED
1330 case 'h':
1331 if (streq(p, "hull"))
1332 pinfo->mode = l_hull;
1333 break;
1334 #endif
1335 case 'n':
1336 if (streq(p, "node"))
1337 pinfo->mode = l_node;
1338 break;
1339 #ifdef NOT_IMPLEMENTED
1340 case 't':
1341 if (streq(p, "tile"))
1342 pinfo->mode = l_tile;
1343 break;
1344 #endif
1345 }
1346 }
1347
1348 if (Verbose) {
1349 fprintf (stderr, "pack info:\n");
1350 fprintf (stderr, " mode %s\n", mode2Str(pinfo->mode));
1351 if (pinfo->mode == l_aspect)
1352 fprintf (stderr, " aspect %f\n", pinfo->aspect);
1353 fprintf (stderr, " size %d\n", pinfo->sz);
1354 fprintf (stderr, " flags %d\n", pinfo->flags);
1355 }
1356 return pinfo->mode;
1357 }
1358
1359 /* getPackModeInfo;
1360 * Return pack_mode of graph using "packmode" attribute.
1361 * If not defined, return dflt
1362 */
1363 pack_mode
getPackModeInfo(Agraph_t * g,pack_mode dflt,pack_info * pinfo)1364 getPackModeInfo(Agraph_t * g, pack_mode dflt, pack_info* pinfo)
1365 {
1366 return parsePackModeInfo (agget(g, "packmode"), dflt, pinfo);
1367 }
1368
1369 pack_mode
getPackMode(Agraph_t * g,pack_mode dflt)1370 getPackMode(Agraph_t * g, pack_mode dflt)
1371 {
1372 pack_info info;
1373 return getPackModeInfo (g, dflt, &info);
1374 }
1375
1376 /* getPack:
1377 * Return "pack" attribute of g.
1378 * If not defined or negative, return not_def.
1379 * If defined but not specified, return dflt.
1380 */
getPack(Agraph_t * g,int not_def,int dflt)1381 int getPack(Agraph_t * g, int not_def, int dflt)
1382 {
1383 char *p;
1384 int i;
1385 int v = not_def;
1386
1387 if ((p = agget(g, "pack"))) {
1388 if ((sscanf(p, "%d", &i) == 1) && (i >= 0))
1389 v = i;
1390 else if ((*p == 't') || (*p == 'T'))
1391 v = dflt;
1392 }
1393
1394 return v;
1395 }
1396
1397 pack_mode
getPackInfo(Agraph_t * g,pack_mode dflt,int dfltMargin,pack_info * pinfo)1398 getPackInfo(Agraph_t * g, pack_mode dflt, int dfltMargin, pack_info* pinfo)
1399 {
1400 assert (pinfo);
1401
1402 pinfo->margin = getPack(g, dfltMargin, dfltMargin);
1403 if (Verbose) {
1404 fprintf (stderr, " margin %u\n", pinfo->margin);
1405 }
1406 pinfo->doSplines = 0;
1407 pinfo->fixed = 0;
1408 getPackModeInfo(g, dflt, pinfo);
1409
1410 return pinfo->mode;
1411 }
1412
1413
1414