Graphviz  2.41.20170921.2350
pack.c
Go to the documentation of this file.
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  */
56 static int computeStep(int ng, boxf* bbs, 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  */
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  */
111 /* static */
112 void fillLine(pointf p, pointf q, PointSet * ps)
113 {
114  int x1 = ROUND(p.x);
115  int y1 = ROUND(p.y);
116  int x2 = ROUND(q.x);
117  int y2 = ROUND(q.y);
118  int d, x, y, ax, ay, sx, sy, dx, dy;
119 
120  dx = x2 - x1;
121  ax = ABS(dx) << 1;
122  sx = SGN(dx);
123  dy = y2 - y1;
124  ay = ABS(dy) << 1;
125  sy = SGN(dy);
126 
127 /* fprintf (stderr, "fillLine %d %d - %d %d\n", x1,y1,x2,y2); */
128  x = x1;
129  y = y1;
130  if (ax > ay) { /* x dominant */
131  d = ay - (ax >> 1);
132  for (;;) {
133 /* fprintf (stderr, " addPS %d %d\n", x,y); */
134  addPS(ps, x, y);
135  if (x == x2)
136  return;
137  if (d >= 0) {
138  y += sy;
139  d -= ax;
140  }
141  x += sx;
142  d += ay;
143  }
144  } else { /* y dominant */
145  d = ax - (ay >> 1);
146  for (;;) {
147 /* fprintf (stderr, " addPS %d %d\n", x,y); */
148  addPS(ps, x, y);
149  if (y == y2)
150  return;
151  if (d >= 0) {
152  x += sx;
153  d -= ay;
154  }
155  y += sy;
156  d += ax;
157  }
158  }
159 }
160 
161 /* fillEdge:
162  * It appears that spline_edges always have the start point at the
163  * beginning and the end point at the end.
164  */
165 static void
166 fillEdge(Agedge_t * e, point p, PointSet * ps, int dx, int dy,
167  int ssize, int doS)
168 {
169  int j, k;
170  bezier bz;
171  pointf pt, hpt;
172  Agnode_t *h;
173 
174  P2PF(p, pt);
175 
176  /* If doS is false or the edge has not splines, use line segment */
177  if (!doS || !ED_spl(e)) {
178  h = aghead(e);
179  hpt = coord(h);
180  MOVEPT(hpt);
181  CELL(hpt, ssize);
182  fillLine(pt, hpt, ps);
183  return;
184  }
185 
186  for (j = 0; j < ED_spl(e)->size; j++) {
187  bz = ED_spl(e)->list[j];
188  if (bz.sflag) {
189  pt = bz.sp;
190  hpt = bz.list[0];
191  k = 1;
192  } else {
193  pt = bz.list[0];
194  hpt = bz.list[1];
195  k = 2;
196  }
197  MOVEPT(pt);
198  CELL(pt, ssize);
199  MOVEPT(hpt);
200  CELL(hpt, ssize);
201  fillLine(pt, hpt, ps);
202 
203  for (; k < bz.size; k++) {
204  pt = hpt;
205  hpt = bz.list[k];
206  MOVEPT(hpt);
207  CELL(hpt, ssize);
208  fillLine(pt, hpt, ps);
209  }
210 
211  if (bz.eflag) {
212  pt = hpt;
213  hpt = bz.ep;
214  MOVEPT(hpt);
215  CELL(hpt, ssize);
216  fillLine(pt, hpt, ps);
217  }
218  }
219 
220 }
221 
222 /* genBox:
223  * Generate polyomino info from graph using the bounding box of
224  * the graph.
225  */
226 static void
227 genBox(boxf bb0, ginfo * info, int ssize, int margin, point center, 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
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  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
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
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
490 placeGraph(int i, ginfo * info, PointSet * ps, point * place, int step,
491  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
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  */
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  */
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 *
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*
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*
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 
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 *
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
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  */
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  */
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
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  */
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
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
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*
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*
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
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
1365 {
1366  return parsePackModeInfo (agget(g, "packmode"), dflt, pinfo);
1367 }
1368 
1369 pack_mode
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  */
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
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 %d\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 
void dotneato_postprocess(Agraph_t *g)
Definition: postproc.c:693
void freePS(PointSet *ps)
Definition: pointset.c:68
#define GD_label(g)
Definition: types.h:381
void insertPS(PointSet *ps, point pt)
Definition: pointset.c:73
PointSet * newPS(void)
Definition: pointset.c:63
#define MAX(a, b)
Definition: agerror.c:17
int packRects(int ng, boxf *bbs, pack_info *pinfo)
Definition: pack.c:982
#define strneq(a, b, n)
Definition: pack.c:27
Definition: cgraph.h:388
packval_t * vals
Definition: pack.h:56
#define ABS(a)
Definition: arith.h:45
int eflag
Definition: types.h:112
#define N_NEW(n, t)
Definition: memory.h:36
pack_mode
Definition: pack.h:37
Definition: pack.h:49
#define ND_xlabel(n)
Definition: types.h:510
int flags
Definition: pack.h:57
int size
Definition: types.h:110
Definition: pack.h:37
#define SLEN(s)
Definition: pack.c:1205
int index
Definition: pack.c:48
double width
Definition: pack.c:47
#define MIN(a, b)
Definition: arith.h:35
#define GD_n_cluster(g)
Definition: types.h:396
int index
Definition: pack.c:43
#define PK_RIGHT_ALIGN
Definition: pack.h:42
#define C
Definition: pack.c:29
#define SGN(a)
Definition: arith.h:48
#define CELL(p, s)
Definition: pack.c:37
#define ROUND(f)
Definition: arith.h:84
#define assert(x)
Definition: cghdr.h:47
Definition: geom.h:28
#define PF2P(pf, p)
Definition: geom.h:72
int nc
Definition: pack.c:42
#define ED_label(e)
Definition: types.h:592
Definition: pack.c:39
Definition: pack.h:37
point * cells
Definition: pack.c:41
#define ND_pos(n)
Definition: types.h:526
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
double height
Definition: pack.c:47
#define PK_TOP_ALIGN
Definition: pack.h:43
#define GRID(x, s)
Definition: pack.c:33
pack_mode getPackInfo(Agraph_t *g, pack_mode dflt, int dfltMargin, pack_info *pinfo)
Definition: pack.c:1398
int packGraphs(int ng, Agraph_t **gs, Agraph_t *root, pack_info *info)
Definition: pack.c:1145
#define ND_ysize(n)
Definition: types.h:544
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
pack_mode mode
Definition: pack.h:54
#define P2PF(p, pf)
Definition: geom.h:71
#define ED_tail_label(e)
Definition: types.h:599
void fillLine(pointf p, pointf q, PointSet *ps)
Definition: pack.c:112
point UR
Definition: geom.h:33
int x
Definition: geom.h:26
#define ASPECT
Definition: pack.c:1204
int shiftGraphs(int ng, Agraph_t **gs, point *pp, Agraph_t *root, int doSplines)
Definition: pack.c:1088
#define ND_clust(n)
Definition: types.h:495
#define PS2INCH(a_points)
Definition: geom.h:69
char * agget(void *obj, char *name)
Definition: attr.c:428
boolean * fixed
Definition: pack.h:55
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
#define ARRAY
Definition: pack.c:1203
int
Definition: grammar.c:1264
#define ED_spl(e)
Definition: types.h:598
#define PK_COL_MAJOR
Definition: pack.h:39
int doSplines
Definition: pack.h:53
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
unsigned int margin
Definition: pack.h:52
pack_mode getPackMode(Agraph_t *g, pack_mode dflt)
Definition: pack.c:1370
double y
Definition: geom.h:28
int sflag
Definition: types.h:111
pack_mode getPackModeInfo(Agraph_t *g, pack_mode dflt, pack_info *pinfo)
Definition: pack.c:1364
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
int pack_graph(int ng, Agraph_t **gs, Agraph_t *root, boolean *fixed)
Definition: pack.c:1190
Definition: grid.h:37
pointf sp
Definition: types.h:113
int sizeOf(PointSet *ps)
Definition: pointset.c:109
point * pointsOf(PointSet *ps)
Definition: pointset.c:114
#define PK_USER_VALS
Definition: pack.h:40
void compute_bb(graph_t *g)
Definition: utils.c:852
Definition: pack.h:37
point * putRects(int ng, boxf *bbs, pack_info *pinfo)
Definition: pack.c:959
point LL
Definition: geom.h:33
pointf * list
Definition: types.h:109
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
Definition: grammar.c:79
#define PK_INPUT_ORDER
Definition: pack.h:45
#define GD_clust(g)
Definition: types.h:364
int sz
Definition: pack.h:51
#define CL_OFFSET
Definition: const.h:155
pointf ep
Definition: types.h:114
#define PK_BOT_ALIGN
Definition: pack.h:44
#define ND_alg(n)
Definition: types.h:490
int packSubgraphs(int ng, Agraph_t **gs, Agraph_t *root, pack_info *info)
Definition: pack.c:1163
Definition: pack.h:37
#define NULL
Definition: logic.h:39
void addPS(PointSet *ps, int x, int y)
Definition: pointset.c:82
#define ED_head_label(e)
Definition: types.h:590
Definition: geom.h:26
double x
Definition: geom.h:28
#define ED_xlabel(e)
Definition: types.h:593
#define ND_coord(n)
Definition: types.h:496
#define streq(s, t)
Definition: cghdr.h:52
int getPack(Agraph_t *g, int not_def, int dflt)
Definition: pack.c:1381
EXTERN unsigned char Verbose
Definition: globals.h:64
Definition: types.h:108
unsigned int packval_t
Definition: pack.h:47
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
#define PK_LEFT_ALIGN
Definition: pack.h:41
int inPS(PointSet *ps, point pt)
Definition: pointset.c:94
Definition: pack.h:37
pointf LL
Definition: geom.h:35
Definition: pack.c:46
Definition: pack.h:37
#define ND_xsize(n)
Definition: types.h:543
Definition: cdt.h:99
#define GD_bb(g)
Definition: types.h:357
point * putGraphs(int ng, Agraph_t **gs, Agraph_t *root, pack_info *pinfo)
Definition: pack.c:916
pack_mode parsePackModeInfo(char *p, pack_mode dflt, pack_info *pinfo)
Definition: pack.c:1287
#define BF2B(bf, b)
Definition: geom.h:75
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
pointf coord(node_t *n)
Definition: utils.c:202
int perim
Definition: pack.c:40
int y
Definition: geom.h:26
pointf UR
Definition: geom.h:35
Definition: geom.h:35
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define EXPANDBB(b0, b1)
Definition: geom.h:51
#define MOVEPT(p)
Definition: pack.c:31
float aspect
Definition: pack.h:50
Definition: geom.h:33
#define INC(m, c, r)
Definition: pack.c:603