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