Graphviz  2.41.20170921.2350
layout.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 /* layout.c:
16  * Written by Emden R. Gansner
17  *
18  * This module provides the main bookkeeping for the fdp layout.
19  * In particular, it handles the recursion and the creation of
20  * ports and auxiliary graphs.
21  *
22  * TODO : can we use ports to aid in layout of edges? Note that
23  * at present, they are deleted.
24  *
25  * Can we delay all repositioning of nodes until evalPositions, so
26  * finalCC only sets the bounding boxes?
27  *
28  * Make sure multiple edges have an effect.
29  */
30 
31 /* uses PRIVATE interface */
32 #define FDP_PRIVATE 1
33 
34 #include "config.h"
35 #include <limits.h>
36 #include <inttypes.h>
37 #include <assert.h>
38 #include "tlayout.h"
39 #include "neatoprocs.h"
40 #include "adjust.h"
41 #include "comp.h"
42 #include "pack.h"
43 #include "clusteredges.h"
44 #include "dbg.h"
45 #include <setjmp.h>
46 
47 static jmp_buf jbuf;
48 
49 typedef struct {
50  graph_t* rootg; /* logical root; graph passed in to fdp_layout */
54  int gid;
56 } layout_info;
57 
58 typedef struct {
60  double alpha;
61  double dist2;
62 } erec;
63 
64 #define NEW_EDGE(e) (ED_to_virt(e) == 0)
65 
66 /* finalCC:
67  * Set graph bounding box given list of connected
68  * components, each with its bounding box set.
69  * If c_cnt > 1, then pts != NULL and gives translations for components.
70  * Add margin about whole graph unless isRoot is true.
71  * Reposition nodes based on final position of
72  * node's connected component.
73  * Also, entire layout is translated to origin.
74  */
75 static void
76 finalCC(graph_t * g, int c_cnt, graph_t ** cc, point * pts, graph_t * rg,
77  layout_info* infop)
78 {
79  attrsym_t * G_width = infop->G_width;
80  attrsym_t * G_height = infop->G_height;
81  graph_t *cg;
82  box b, bb;
83  boxf bbf;
84  point pt;
85  int margin;
86  graph_t **cp = cc;
87  point *pp = pts;
88  int isRoot = (rg == infop->rootg);
89  int isEmpty = 0;
90 
91  /* compute graph bounding box in points */
92  if (c_cnt) {
93  cg = *cp++;
94  BF2B(GD_bb(cg), bb);
95  if (c_cnt > 1) {
96  pt = *pp++;
97  bb.LL.x += pt.x;
98  bb.LL.y += pt.y;
99  bb.UR.x += pt.x;
100  bb.UR.y += pt.y;
101  while ((cg = *cp++)) {
102  BF2B(GD_bb(cg), b);
103  pt = *pp++;
104  b.LL.x += pt.x;
105  b.LL.y += pt.y;
106  b.UR.x += pt.x;
107  b.UR.y += pt.y;
108  bb.LL.x = MIN(bb.LL.x, b.LL.x);
109  bb.LL.y = MIN(bb.LL.y, b.LL.y);
110  bb.UR.x = MAX(bb.UR.x, b.UR.x);
111  bb.UR.y = MAX(bb.UR.y, b.UR.y);
112  }
113  }
114  } else { /* empty graph */
115  bb.LL.x = 0;
116  bb.LL.y = 0;
117  bb.UR.x = late_int(rg, G_width, POINTS(DEFAULT_NODEWIDTH), 3);
118  bb.UR.y = late_int(rg, G_height, POINTS(DEFAULT_NODEHEIGHT), 3);
119  isEmpty = 1;
120  }
121 
122  if (GD_label(rg)) {
123  point p;
124  int d;
125 
126  isEmpty = 0;
127  PF2P(GD_label(rg)->dimen, p);
128  d = p.x - (bb.UR.x - bb.LL.x);
129  if (d > 0) { /* height of label added below */
130  d /= 2;
131  bb.LL.x -= d;
132  bb.UR.x += d;
133  }
134  }
135 
136  if (isRoot || isEmpty)
137  margin = 0;
138  else
139  margin = late_int (rg, G_margin, CL_OFFSET, 0);
140  pt.x = -bb.LL.x + margin;
141  pt.y = -bb.LL.y + margin + GD_border(rg)[BOTTOM_IX].y;
142  bb.LL.x = 0;
143  bb.LL.y = 0;
144  bb.UR.x += pt.x + margin;
145  bb.UR.y += pt.y + margin + GD_border(rg)[TOP_IX].y;
146 
147  /* translate nodes */
148  if (c_cnt) {
149  cp = cc;
150  pp = pts;
151  while ((cg = *cp++)) {
152  point p;
153  node_t *n;
154  pointf del;
155 
156  if (pp) {
157  p = *pp++;
158  p.x += pt.x;
159  p.y += pt.y;
160  } else {
161  p = pt;
162  }
163  del.x = PS2INCH(p.x);
164  del.y = PS2INCH(p.y);
165  for (n = agfstnode(cg); n; n = agnxtnode(cg, n)) {
166  ND_pos(n)[0] += del.x;
167  ND_pos(n)[1] += del.y;
168  }
169  }
170  }
171 
172  bbf.LL.x = PS2INCH(bb.LL.x);
173  bbf.LL.y = PS2INCH(bb.LL.y);
174  bbf.UR.x = PS2INCH(bb.UR.x);
175  bbf.UR.y = PS2INCH(bb.UR.y);
176  BB(g) = bbf;
177 
178 }
179 
180 /* mkDeriveNode:
181  * Constructor for a node in a derived graph.
182  * Allocates dndata.
183  */
184 static node_t *mkDeriveNode(graph_t * dg, char *name)
185 {
186  node_t *dn;
187 
188  dn = agnode(dg, name,1);
189  agbindrec(dn, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE); //node custom data
190  ND_alg(dn) = (void *) NEW(dndata); /* free in freeDeriveNode */
191  ND_pos(dn) = N_GNEW(GD_ndim(dg), double);
192  /* fprintf (stderr, "Creating %s\n", dn->name); */
193  return dn;
194 }
195 
196 static void freeDeriveNode(node_t * n)
197 {
198  free(ND_alg(n));
199  free(ND_pos(n));
200  agdelrec(n, "Agnodeinfo_t");
201 }
202 
203 static void freeGData(graph_t * g)
204 {
205  free(GD_alg(g));
206 }
207 
208 static void freeDerivedGraph(graph_t * g, graph_t ** cc)
209 {
210  graph_t *cg;
211  node_t *dn;
212  node_t *dnxt;
213  edge_t *e;
214 
215  while ((cg = *cc++)) {
216  freeGData(cg);
217  agdelrec(cg, "Agraphinfo_t");
218  }
219  if (PORTS(g))
220  free(PORTS(g));
221  freeGData(g);
222  agdelrec(g, "Agraphinfo_t");
223  for (dn = agfstnode(g); dn; dn = dnxt) {
224  dnxt = agnxtnode(g, dn);
225  for (e = agfstout(g, dn); e; e = agnxtout(g, e)) {
226  free (ED_to_virt(e));
227  agdelrec(e, "Agedgeinfo_t");
228  }
229  freeDeriveNode(dn);
230  }
231  agclose(g);
232 }
233 
234 /* evalPositions:
235  * The input is laid out, but node coordinates
236  * are relative to smallest containing cluster.
237  * Walk through all nodes and clusters, translating
238  * the positions to absolute coordinates.
239  * Assume that when called, g's bounding box is
240  * in absolute coordinates and that box of root graph
241  * has LL at origin.
242  */
243 static void evalPositions(graph_t * g, graph_t* rootg)
244 {
245  int i;
246  graph_t *subg;
247  node_t *n;
248  boxf bb;
249  boxf sbb;
250 
251  bb = BB(g);
252 
253  /* translate nodes in g */
254  if (g != rootg) {
255  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
256  if (PARENT(n) != g)
257  continue;
258  ND_pos(n)[0] += bb.LL.x;
259  ND_pos(n)[1] += bb.LL.y;
260  }
261  }
262 
263  /* translate top-level clusters and recurse */
264  for (i = 1; i <= GD_n_cluster(g); i++) {
265  subg = GD_clust(g)[i];
266  if (g != rootg) {
267  sbb = BB(subg);
268  sbb.LL.x += bb.LL.x;
269  sbb.LL.y += bb.LL.y;
270  sbb.UR.x += bb.LL.x;
271  sbb.UR.y += bb.LL.y;
272  BB(subg) = sbb;
273  }
274  evalPositions(subg, rootg);
275  }
276 }
277 
278 #define CL_CHUNK 10
279 
280 typedef struct {
282  int sz;
283  int cnt;
284 } clist_t;
285 
286 static void initCList(clist_t * clist)
287 {
288  clist->cl = 0;
289  clist->sz = 0;
290  clist->cnt = 0;
291 }
292 
293 /* addCluster:
294  * Append a new cluster to the list.
295  * NOTE: cl[0] is empty. The clusters are in cl[1..cnt].
296  * Normally, we increase the array when cnt == sz.
297  * The test for cnt > sz is necessary for the first time.
298  */
299 static void addCluster(clist_t * clist, graph_t * subg)
300 {
301  clist->cnt++;
302  if (clist->cnt >= clist->sz) {
303  clist->sz += CL_CHUNK;
304  clist->cl = RALLOC(clist->sz, clist->cl, graph_t *);
305  }
306  clist->cl[clist->cnt] = subg;
307 }
308 
309 #define BSZ 1000
310 
311 /* portName:
312  * Generate a name for a port.
313  * We use the name of the subgraph and names of the nodes on the edge,
314  * if possible. Otherwise, we use the ids of the nodes.
315  * This is for debugging. For production, just use edge id and some
316  * id for the graph. Note that all the graphs are subgraphs of the
317  * root graph.
318  */
319 static char *portName(graph_t * g, bport_t * p)
320 {
321  edge_t *e = p->e;
322  node_t *h = aghead(e);
323  node_t *t = agtail(e);
324  static char buf[BSZ + 1];
325  int len = 8;
326 
327  len += strlen(agnameof(g)) + strlen(agnameof(h)) + strlen(agnameof(t));
328  if (len >= BSZ)
329  sprintf(buf, "_port_%s_%s_%s_%ld", agnameof(g), agnameof(t), agnameof(h),
330  (uint64_t)AGSEQ(e));
331  else
332  sprintf(buf, "_port_%s_(%d)_(%d)_%ld",agnameof(g), ND_id(t), ND_id(h),
333  (uint64_t)AGSEQ(e));
334  return buf;
335 }
336 
337 /* chkPos:
338  * If cluster has coords attribute, use to supply initial position
339  * of derived node.
340  * Only called if G_coord is defined.
341  * We also look at the parent graph's G_coord attribute. If this
342  * is identical to the child graph, we have to assume the child
343  * inherited it.
344  */
345 static void chkPos(graph_t* g, node_t* n, layout_info* infop, boxf* bbp)
346 {
347  char *p;
348  char *pp;
349  boxf bb;
350  char c;
351  graph_t *parent;
352  attrsym_t *G_coord = infop->G_coord;
353 
354  p = agxget(g, G_coord);
355  if (p[0]) {
356  if (g != infop->rootg) {
357  parent =agparent(g);
358  pp = agxget(parent, G_coord);
359  if ((pp == p) || !strcmp(p, pp))
360  return;
361  }
362  c = '\0';
363  if (sscanf(p, "%lf,%lf,%lf,%lf%c",
364  &bb.LL.x, &bb.LL.y, &bb.UR.x, &bb.UR.y, &c) >= 4) {
365  if (PSinputscale > 0.0) {
366  bb.LL.x /= PSinputscale;
367  bb.LL.y /= PSinputscale;
368  bb.UR.x /= PSinputscale;
369  bb.UR.y /= PSinputscale;
370  }
371  if (c == '!')
372  ND_pinned(n) = P_PIN;
373  else if (c == '?')
374  ND_pinned(n) = P_FIX;
375  else
376  ND_pinned(n) = P_SET;
377  *bbp = bb;
378  } else
379  agerr(AGWARN, "graph %s, coord %s, expected four doubles\n",
380  agnameof(g), p);
381  }
382 }
383 
384 /* addEdge:
385  * Add real edge e to its image de in the derived graph.
386  * We use the to_virt and count fields to store the list.
387  */
388 static void addEdge(edge_t * de, edge_t * e)
389 {
390  short cnt = ED_count(de);
391  edge_t **el;
392 
393  el = (edge_t **) (ED_to_virt(de));
394  el = ALLOC(cnt + 1, el, edge_t *);
395  el[cnt] = e;
396  ED_to_virt(de) = (edge_t *) el;
397  ED_count(de)++;
398 }
399 
400 /* copyAttr:
401  * Copy given attribute from g to dg.
402  */
403 static void
404 copyAttr (graph_t* g, graph_t* dg, char* attr)
405 {
406  char* ov_val;
407  Agsym_t* ov;
408 
409  if ((ov = agattr(g,AGRAPH, attr, NULL))) {
410  ov_val = agxget(g,ov);
411  ov = agattr(dg,AGRAPH, attr, NULL);
412  if (ov)
413  agxset (dg, ov, ov_val);
414  else
415  agattr(dg, AGRAPH, attr, ov_val);
416  }
417 }
418 
419 /* deriveGraph:
420  * Create derived graph of g by collapsing clusters into
421  * nodes. An edge is created between nodes if there is
422  * an edge between two nodes in the clusters of the base graph.
423  * Such edges record all corresponding real edges.
424  * In addition, we add a node and edge for each port.
425  */
426 static graph_t *deriveGraph(graph_t * g, layout_info * infop)
427 {
428  graph_t *dg;
429  node_t *dn;
430  graph_t *subg;
431  char name[100];
432  bport_t *pp;
433  node_t *n;
434  edge_t *de;
435  int i, id = 0;
436 
437  sprintf(name, "_dg_%d", infop->gid++);
438  if (Verbose >= 2)
439  fprintf(stderr, "derive graph %s of %s\n", name, agnameof(g));
440 
441  dg = agopen("derived", Agstrictdirected,NIL(Agdisc_t *));
442  agbindrec(dg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
443  GD_alg(dg) = (void *) NEW(gdata); /* freed in freeDeriveGraph */
444 #ifdef DEBUG
445  GORIG(dg) = g;
446 #endif
447  GD_ndim(dg) = GD_ndim(g);
448 
449  /* Copy attributes from g.
450  */
451  copyAttr(g,dg,"overlap");
452  copyAttr(g,dg,"sep");
453  copyAttr(g,dg,"K");
454 
455  /* create derived nodes from clusters */
456  for (i = 1; i <= GD_n_cluster(g); i++) {
457  boxf fix_bb = {{ MAXDOUBLE, MAXDOUBLE },{ -MAXDOUBLE, -MAXDOUBLE }};
458  subg = GD_clust(g)[i];
459 
460  do_graph_label(subg);
461  dn = mkDeriveNode(dg, agnameof(subg));
462  ND_clust(dn) = subg;
463  ND_id(dn) = id++;
464  if (infop->G_coord)
465  chkPos(subg, dn, infop, &fix_bb);
466  for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
467  DNODE(n) = dn;
468 #ifdef UNIMPLEMENTED
469 /* This code starts the implementation of supporting pinned nodes
470  * within clusters. This needs more work. In particular, we may need
471  * a separate notion of pinning related to contained nodes, which will
472  * allow the cluster itself to wiggle.
473  */
474  if (ND_pinned(n)) {
475  fix_bb.LL.x = MIN(fix_bb.LL.x, ND_pos(n)[0]);
476  fix_bb.LL.y = MIN(fix_bb.LL.y, ND_pos(n)[1]);
477  fix_bb.UR.x = MAX(fix_bb.UR.x, ND_pos(n)[0]);
478  fix_bb.UR.y = MAX(fix_bb.UR.y, ND_pos(n)[1]);
479  ND_pinned(dn) = MAX(ND_pinned(dn), ND_pinned(n));
480  }
481 #endif
482  }
483  if (ND_pinned(dn)) {
484  ND_pos(dn)[0] = (fix_bb.LL.x + fix_bb.UR.x) / 2;
485  ND_pos(dn)[1] = (fix_bb.LL.y + fix_bb.UR.y) / 2;
486  }
487  }
488 
489  /* create derived nodes from remaining nodes */
490  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
491  if (!DNODE(n)) {
492  if (PARENT(n) && (PARENT(n) != GPARENT(g))) {
493  agerr (AGERR, "node \"%s\" is contained in two non-comparable clusters \"%s\" and \"%s\"\n", agnameof(n), agnameof(g), agnameof(PARENT(n)));
494  longjmp (jbuf, 1);
495  }
496  PARENT(n) = g;
497  if (IS_CLUST_NODE(n))
498  continue;
499  dn = mkDeriveNode(dg, agnameof(n));
500  DNODE(n) = dn;
501  ND_id(dn) = id++;
502  ND_width(dn) = ND_width(n);
503  ND_height(dn) = ND_height(n);
504  ND_lw(dn) = ND_lw(n);
505  ND_rw(dn) = ND_rw(n);
506  ND_ht(dn) = ND_ht(n);
507  ND_shape(dn) = ND_shape(n);
508  ND_shape_info(dn) = ND_shape_info(n);
509  if (ND_pinned(n)) {
510  ND_pos(dn)[0] = ND_pos(n)[0];
511  ND_pos(dn)[1] = ND_pos(n)[1];
512  ND_pinned(dn) = ND_pinned(n);
513  }
514  ANODE(dn) = n;
515  }
516  }
517 
518  /* add edges */
519  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
520  edge_t *e;
521  node_t *hd;
522  node_t *tl = DNODE(n);
523  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
524  hd = DNODE(aghead(e));
525  if (hd == tl)
526  continue;
527  if (hd > tl)
528  de = agedge(dg, tl, hd, NULL,1);
529  else
530  de = agedge(dg, hd, tl, NULL,1);
531  agbindrec(de, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);
532  ED_dist(de) = ED_dist(e);
533  ED_factor(de) = ED_factor(e);
534  /* fprintf (stderr, "edge %s -- %s\n", tl->name, hd->name); */
535  WDEG(hd)++;
536  WDEG(tl)++;
537  if (NEW_EDGE(de)) {
538  DEG(hd)++;
539  DEG(tl)++;
540  }
541  addEdge(de, e);
542  }
543  }
544 
545  /* transform ports */
546  if ((pp = PORTS(g))) {
547  bport_t *pq;
548  node_t *m;
549  int sz = NPORTS(g);
550 
551  /* freed in freeDeriveGraph */
552  PORTS(dg) = pq = N_NEW(sz + 1, bport_t);
553  sz = 0;
554  while (pp->e) {
555  m = DNODE(pp->n);
556  /* Create port in derived graph only if hooks to internal node */
557  if (m) {
558  dn = mkDeriveNode(dg, portName(g, pp));
559  sz++;
560  ND_id(dn) = id++;
561  if (dn > m)
562  de = agedge(dg, m, dn, NULL,1);
563  else
564  de = agedge(dg, dn, m, NULL,1);
565  agbindrec(de, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);
566  ED_dist(de) = ED_dist(pp->e);
567  ED_factor(de) = ED_factor(pp->e);
568  addEdge(de, pp->e);
569  WDEG(dn)++;
570  WDEG(m)++;
571  DEG(dn)++; /* ports are unique, so this will be the first and */
572  DEG(m)++; /* only time the edge is touched. */
573  pq->n = dn;
574  pq->alpha = pp->alpha;
575  pq->e = de;
576  pq++;
577  }
578  pp++;
579  }
580  NPORTS(dg) = sz;
581  }
582 
583  return dg;
584 }
585 
586 /* ecmp:
587  * Sort edges by angle, then distance.
588  */
589 static int ecmp(const void *v1, const void *v2)
590 {
591  erec *e1 = (erec *) v1;
592  erec *e2 = (erec *) v2;
593  if (e1->alpha > e2->alpha)
594  return 1;
595  else if (e1->alpha < e2->alpha)
596  return -1;
597  else if (e1->dist2 > e2->dist2)
598  return 1;
599  else if (e1->dist2 < e2->dist2)
600  return -1;
601  else
602  return 0;
603 }
604 
605 #define ANG (M_PI/90) /* Maximum angular change: 2 degrees */
606 
607 /* getEdgeList:
608  * Generate list of edges in derived graph g using
609  * node n. The list is in counterclockwise order.
610  * This, of course, assumes we have an initial layout for g.
611  */
612 static erec *getEdgeList(node_t * n, graph_t * g)
613 {
614  erec *erecs;
615  int deg = DEG(n);
616  int i;
617  double dx, dy;
618  edge_t *e;
619  node_t *m;
620 
621  /* freed in expandCluster */
622  erecs = N_NEW(deg + 1, erec);
623  i = 0;
624  for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
625  if (aghead(e) == n)
626  m = agtail(e);
627  else
628  m = aghead(e);
629  dx = ND_pos(m)[0] - ND_pos(n)[0];
630  dy = ND_pos(m)[1] - ND_pos(n)[1];
631  erecs[i].e = e;
632  erecs[i].alpha = atan2(dy, dx);
633  erecs[i].dist2 = dx * dx + dy * dy;
634  i++;
635  }
636  assert(i == deg);
637  qsort(erecs, deg, sizeof(erec), ecmp);
638 
639  /* ensure no two angles are equal */
640  if (deg >= 2) {
641  int j;
642  double a, inc, delta, bnd;
643 
644  i = 0;
645  while (i < deg - 1) {
646  a = erecs[i].alpha;
647  j = i + 1;
648  while ((j < deg) && (erecs[j].alpha == a))
649  j++;
650  if (j == i + 1)
651  i = j;
652  else {
653  if (j == deg)
654  bnd = M_PI; /* all values equal up to end */
655  else
656  bnd = erecs[j].alpha;
657  delta = (bnd - a) / (j - i);
658  if (delta > ANG)
659  delta = ANG;
660  inc = 0;
661  for (; i < j; i++) {
662  erecs[i].alpha += inc;
663  inc += delta;
664  }
665  }
666  }
667  }
668 
669  return erecs;
670 }
671 
672 /* genPorts:
673  * Given list of edges with node n in derived graph, add corresponding
674  * ports to port list pp, starting at index idx. Return next index.
675  * If an edge in the derived graph corresponds to multiple real edges,
676  * add them in order if address of n is smaller than other node address.
677  * Otherwise, reverse order.
678  * Attach angles. The value bnd gives next angle after er->alpha.
679  */
680 static int
681 genPorts(node_t * n, erec * er, bport_t * pp, int idx, double bnd)
682 {
683  node_t *other;
684  int cnt;
685  edge_t *e = er->e;
686  edge_t *el;
687  edge_t **ep;
688  double angle, delta;
689  int i, j, inc;
690 
691  cnt = ED_count(e);
692 
693  if (aghead(e) == n)
694  other = agtail(e);
695  else
696  other = aghead(e);
697 
698  delta = (bnd - er->alpha) / cnt;
699  angle = er->alpha;
700  if (delta > ANG)
701  delta = ANG;
702 
703  if (n < other) {
704  i = idx;
705  inc = 1;
706  } else {
707  i = idx + cnt - 1;
708  inc = -1;
709  angle += delta * (cnt - 1);
710  delta = -delta;
711  }
712 
713  ep = (edge_t **) (el = ED_to_virt(e));
714  for (j = 0; j < ED_count(e); j++, ep++) {
715  el = *ep;
716  pp[i].e = el;
717  pp[i].n = (DNODE(agtail(el)) == n ? agtail(el) : aghead(el));
718  pp[i].alpha = angle;
719  i += inc;
720  angle += delta;
721  }
722  return (idx + cnt);
723 }
724 
725 /* expandCluster;
726  * Given positioned derived graph cg with node n which corresponds
727  * to a cluster, generate a graph containing the interior of the
728  * cluster, plus port information induced by the layout of cg.
729  * Basically, we use the cluster subgraph to which n corresponds,
730  * attached with port information.
731  */
732 static graph_t *expandCluster(node_t * n, graph_t * cg)
733 {
734  erec *es;
735  erec *ep;
736  erec *next;
737  graph_t *sg = ND_clust(n);
738  bport_t *pp;
739  int sz = WDEG(n);
740  int idx = 0;
741  double bnd;
742 
743  if (sz != 0) {
744  /* freed in cleanup_subgs */
745  pp = N_NEW(sz + 1, bport_t);
746 
747  /* create sorted list of edges of n */
748  es = ep = getEdgeList(n, cg);
749 
750  /* generate ports from edges */
751  while (ep->e) {
752  next = ep + 1;
753  if (next->e)
754  bnd = next->alpha;
755  else
756  bnd = 2 * M_PI + es->alpha;
757  idx = genPorts(n, ep, pp, idx, bnd);
758  ep = next;
759  }
760  assert(idx == sz);
761 
762  PORTS(sg) = pp;
763  NPORTS(sg) = sz;
764  free(es);
765  }
766  return sg;
767 }
768 
769 /* setClustNodes:
770  * At present, cluster nodes are not assigned a position during layout,
771  * but positioned in the center of its associated cluster. Because the
772  * dummy edge associated with a cluster node may not occur at a sufficient
773  * level of cluster, the edge may not be used during layout and we cannot
774  * therefore rely find these nodes via ports.
775  *
776  * In this implementation, we just do a linear pass over all nodes in the
777  * root graph. At some point, we may use a better method, like having each
778  * cluster contain its list of cluster nodes, or have the graph keep a list.
779  *
780  * As nodes, we need to assign cluster nodes the coordinates in the
781  * coordinates of its cluster p. Note that p's bbox is in its parent's
782  * coordinates.
783  *
784  * If routing, we may decide to place on cluster boundary,
785  * and use polyline.
786  */
787 static void
788 setClustNodes(graph_t* root)
789 {
790  boxf bb;
791  graph_t* p;
792  pointf ctr;
793  node_t *n;
794  double w, h, h_pts;
795  double h2, w2;
796  pointf *vertices;
797 
798  for (n = agfstnode(root); n; n = agnxtnode(root, n)) {
799  if (!IS_CLUST_NODE(n)) continue;
800 
801  p = PARENT(n);
802  bb = BB(p); /* bbox in parent cluster's coordinates */
803  w = bb.UR.x - bb.LL.x;
804  h = bb.UR.y - bb.LL.y;
805  ctr.x = w / 2.0;
806  ctr.y = h / 2.0;
807  w2 = INCH2PS(w / 2.0);
808  h2 = INCH2PS(h / 2.0);
809  h_pts = INCH2PS(h);
810  ND_pos(n)[0] = ctr.x;
811  ND_pos(n)[1] = ctr.y;
812  ND_width(n) = w;
813  ND_height(n) = h;
814  /* ND_xsize(n) = POINTS(w); */
815  ND_lw(n) = ND_rw(n) = w2;
816  ND_ht(n) = h_pts;
817 
818  vertices = ((polygon_t *) ND_shape_info(n))->vertices;
819  vertices[0].x = ND_rw(n);
820  vertices[0].y = h2;
821  vertices[1].x = -ND_lw(n);
822  vertices[1].y = h2;
823  vertices[2].x = -ND_lw(n);
824  vertices[2].y = -h2;
825  vertices[3].x = ND_rw(n);
826  vertices[3].y = -h2;
827  }
828 }
829 
830 /* layout:
831  * Given g with ports:
832  * Derive g' from g by reducing clusters to points (deriveGraph)
833  * Compute connected components of g' (findCComp)
834  * For each cc of g':
835  * Layout cc (tLayout)
836  * For each node n in cc of g' <-> cluster c in g:
837  * Add ports based on layout of cc to get c' (expandCluster)
838  * Layout c' (recursion)
839  * Remove ports from cc
840  * Expand nodes of cc to reflect size of c' (xLayout)
841  * Pack connected components to get layout of g (putGraphs)
842  * Translate layout so that bounding box of layout + margin
843  * has the origin as LL corner.
844  * Set position of top level clusters and real nodes.
845  * Set bounding box of graph
846  *
847  * TODO:
848  *
849  * Possibly should modify so that only do connected components
850  * on top-level derived graph. Unconnected parts of a cluster
851  * could just rattle within cluster boundaries. This may mix
852  * up components but give a tighter packing.
853  *
854  * Add edges per components to get better packing, rather than
855  * wait until the end.
856  */
857 static
858 void layout(graph_t * g, layout_info * infop)
859 {
860  point *pts = NULL;
861  graph_t *dg;
862  node_t *dn;
863  node_t *n;
864  graph_t *cg;
865  graph_t *sg;
866  graph_t **cc;
867  graph_t **pg;
868  int c_cnt;
869  int pinned;
870  xparams xpms;
871 
872 #ifdef DEBUG
873  incInd();
874 #endif
875  if (Verbose) {
876 #ifdef DEBUG
877  prIndent();
878 #endif
879  fprintf (stderr, "layout %s\n", agnameof(g));
880  }
881  /* initialize derived node pointers */
882  for (n = agfstnode(g); n; n = agnxtnode(g, n))
883  DNODE(n) = 0;
884 
885  dg = deriveGraph(g, infop);
886  cc = pg = findCComp(dg, &c_cnt, &pinned);
887 
888  while ((cg = *pg++)) {
889  node_t* nxtnode;
890  fdp_tLayout(cg, &xpms);
891  for (n = agfstnode(cg); n; n = nxtnode) {
892  nxtnode = agnxtnode(cg, n);
893  if (ND_clust(n)) {
894  pointf pt;
895  sg = expandCluster(n, cg); /* attach ports to sg */
896  layout(sg, infop);
897  /* bb.LL == origin */
898  ND_width(n) = BB(sg).UR.x;
899  ND_height(n) = BB(sg).UR.y;
900  pt.x = POINTS_PER_INCH * BB(sg).UR.x;
901  pt.y = POINTS_PER_INCH * BB(sg).UR.y;
902  ND_rw(n) = ND_lw(n) = pt.x/2;
903  ND_ht(n) = pt.y;
904  } else if (IS_PORT(n))
905  agdelete(cg, n); /* remove ports from component */
906  }
907 
908  /* Remove overlaps */
909  if (agnnodes(cg) >= 2) {
910  if (g == infop->rootg)
911  normalize (cg);
912  fdp_xLayout(cg, &xpms);
913  }
914  /* set bounding box but don't use ports */
915  /* setBB (cg); */
916  }
917 
918  /* At this point, each connected component has its nodes correctly
919  * positioned. If we have multiple components, we pack them together.
920  * All nodes will be moved to their new positions.
921  * NOTE: packGraphs uses nodes in components, so if port nodes are
922  * not removed, it won't work.
923  */
924  /* Handle special cases well: no ports to real internal nodes
925  * Place cluster edges separately, after layout.
926  * How to combine parts, especially with disparate components?
927  */
928  if (c_cnt > 1) {
929  boolean *bp;
930  if (pinned) {
931  bp = N_NEW(c_cnt, boolean);
932  bp[0] = TRUE;
933  } else
934  bp = 0;
935  infop->pack.fixed = bp;
936  pts = putGraphs(c_cnt, cc, NULL, &infop->pack);
937  if (bp)
938  free(bp);
939  } else {
940  pts = NULL;
941  if (c_cnt == 1)
942  compute_bb(cc[0]);
943  }
944 
945  /* set bounding box of dg and reposition nodes */
946  finalCC(dg, c_cnt, cc, pts, g, infop);
947  free (pts);
948 
949  /* record positions from derived graph to input graph */
950  /* At present, this does not record port node info */
951  /* In fact, as noted above, we have removed port nodes */
952  for (dn = agfstnode(dg); dn; dn = agnxtnode(dg, dn)) {
953  if ((sg = ND_clust(dn))) {
954  BB(sg).LL.x = ND_pos(dn)[0] - ND_width(dn) / 2;
955  BB(sg).LL.y = ND_pos(dn)[1] - ND_height(dn) / 2;
956  BB(sg).UR.x = BB(sg).LL.x + ND_width(dn);
957  BB(sg).UR.y = BB(sg).LL.y + ND_height(dn);
958  } else if ((n = ANODE(dn))) {
959  ND_pos(n)[0] = ND_pos(dn)[0];
960  ND_pos(n)[1] = ND_pos(dn)[1];
961  }
962  }
963  BB(g) = BB(dg);
964 #ifdef DEBUG
965  if (g == infop->rootg)
966  dump(g, 1, 0);
967 #endif
968 
969  /* clean up temp graphs */
970  freeDerivedGraph(dg, cc);
971  free(cc);
972  if (Verbose) {
973 #ifdef DEBUG
974  prIndent ();
975 #endif
976  fprintf (stderr, "end %s\n", agnameof(g));
977  }
978 #ifdef DEBUG
979  decInd();
980 #endif
981 }
982 
983 /* setBB;
984  * Set point box g->bb from inch box BB(g).
985  */
986 static void setBB(graph_t * g)
987 {
988  int i;
989  boxf bb;
990 
991  bb.LL.x = POINTS_PER_INCH * BB(g).LL.x;
992  bb.LL.y = POINTS_PER_INCH * BB(g).LL.y;
993  bb.UR.x = POINTS_PER_INCH * BB(g).UR.x;
994  bb.UR.y = POINTS_PER_INCH * BB(g).UR.y;
995  GD_bb(g) = bb;
996  for (i = 1; i <= GD_n_cluster(g); i++) {
997  setBB(GD_clust(g)[i]);
998  }
999 }
1000 
1001 /* init_info:
1002  * Initialize graph-dependent information and
1003  * state variable.s
1004  */
1005 static void init_info(graph_t * g, layout_info * infop)
1006 {
1007  infop->G_coord = agattr(g, AGRAPH, "coords", NULL);
1008  infop->G_width = agattr(g, AGRAPH, "width", NULL);
1009  infop->G_height = agattr(g, AGRAPH, "height", NULL);
1010  infop->rootg = g;
1011  infop->gid = 0;
1012  infop->pack.mode = getPackInfo(g, l_node, CL_OFFSET / 2, &(infop->pack));
1013 }
1014 
1015 /* mkClusters:
1016  * Attach list of immediate child clusters.
1017  * NB: By convention, the indexing starts at 1.
1018  * If pclist is NULL, the graph is the root graph or a cluster
1019  * If pclist is non-NULL, we are recursively scanning a non-cluster
1020  * subgraph for cluster children.
1021  */
1022 static void
1023 mkClusters (graph_t * g, clist_t* pclist, graph_t* parent)
1024 {
1025  graph_t* subg;
1026  clist_t list;
1027  clist_t* clist;
1028 
1029  if (pclist == NULL) {
1030  clist = &list;
1031  initCList(clist);
1032  }
1033  else
1034  clist = pclist;
1035 
1036  for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg))
1037  {
1038  if (!strncmp(agnameof(subg), "cluster", 7)) {
1039  agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
1040  GD_alg(subg) = (void *) NEW(gdata); /* freed in cleanup_subgs */
1041  GD_ndim(subg) = GD_ndim(parent);
1042  LEVEL(subg) = LEVEL(parent) + 1;
1043  GPARENT(subg) = parent;
1044  addCluster(clist, subg);
1045  mkClusters(subg, NULL, subg);
1046  }
1047  else {
1048  mkClusters(subg, clist, parent);
1049  }
1050  }
1051  if (pclist == NULL) {
1052  GD_n_cluster(g) = list.cnt;
1053  if (list.cnt)
1054  GD_clust(g) = RALLOC(list.cnt + 1, list.cl, graph_t*);
1055  }
1056 }
1057 
1058 static void fdp_init_graph(Agraph_t * g)
1059 {
1060  setEdgeType (g, ET_LINE);
1061  GD_alg(g) = (void *) NEW(gdata); /* freed in cleanup_graph */
1062  GD_ndim(g) = late_int(g, agattr(g,AGRAPH, "dim", NULL), 2, 2);
1063  Ndim = GD_ndim(g) = MIN(GD_ndim(g), MAXDIM);
1064 
1065  mkClusters (g, NULL, g);
1066  fdp_initParams(g);
1067  fdp_init_node_edge(g);
1068 }
1069 
1070 static void fdpLayout(graph_t * g)
1071 {
1072  layout_info info;
1073 
1074  init_info(g, &info);
1075  layout(g, &info);
1076  setClustNodes(g);
1077  evalPositions(g,g);
1078 
1079  /* Set bbox info for g and all clusters. This is needed for
1080  * spline drawing. We already know the graph bbox is at the origin.
1081  * On return from spline drawing, all bounding boxes should be correct.
1082  */
1083  setBB(g);
1084 }
1085 
1086 static void
1087 fdpSplines (graph_t * g)
1088 {
1089  int trySplines = 0;
1090  int et = EDGE_TYPE(g);
1091 
1092  if (et > ET_ORTHO) {
1093  if (et == ET_COMPOUND) {
1094  trySplines = splineEdges(g, compoundEdges, ET_SPLINE);
1095  /* When doing the edges again, accept edges done by compoundEdges */
1096  if (trySplines)
1097  Nop = 2;
1098  }
1099  if (trySplines || (et != ET_COMPOUND)) {
1100  if (HAS_CLUST_EDGE(g)) {
1101  agerr(AGWARN,
1102  "splines and cluster edges not supported - using line segments\n");
1103  et = ET_LINE;
1104  } else {
1105  spline_edges1(g, et);
1106  }
1107  }
1108  Nop = 0;
1109  }
1110  if (State < GVSPLINES)
1111  spline_edges1(g, et);
1112 }
1113 
1115 {
1116  /* Agnode_t* n; */
1117 
1118  double save_scale = PSinputscale;
1119 
1121  fdp_init_graph(g);
1122  if (setjmp(jbuf)) {
1123  return;
1124  }
1125  fdpLayout(g);
1126 #if 0
1127  /* free ND_alg field so it can be used in spline routing */
1128  if ((n = agfstnode(g)))
1129  free(ND_alg(n));
1130 #endif
1131  neato_set_aspect(g);
1132 
1133  if (EDGE_TYPE(g) != ET_NONE) fdpSplines (g);
1134 
1135  gv_postprocess(g, 0);
1136  PSinputscale = save_scale;
1137 }
#define BSZ
Definition: layout.c:309
#define GD_label(g)
Definition: types.h:381
#define MAX(a, b)
Definition: agerror.c:17
#define AGSEQ(obj)
Definition: cgraph.h:115
graph_t ** findCComp(graph_t *g, int *cnt, int *pinned)
Definition: comp.c:60
graph_t * rootg
Definition: layout.c:50
CGRAPH_API Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition: node.c:142
Definition: cgraph.h:388
#define RALLOC(size, ptr, type)
Definition: memory.h:42
#define ND_pinned(n)
Definition: types.h:525
CGRAPH_API Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
Definition: graph.c:44
#define ET_SPLINE
Definition: const.h:275
#define DEFAULT_NODEWIDTH
Definition: const.h:77
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
#define N_NEW(n, t)
Definition: memory.h:36
double alpha
Definition: layout.c:60
Definition: pack.h:49
Definition: pack.h:37
bool layout(Agraph_t *g, const char *engine)
Definition: gv.cpp:809
#define MIN(a, b)
Definition: arith.h:35
#define GD_n_cluster(g)
Definition: types.h:396
#define GD_border(g)
Definition: types.h:362
EXTERN int State
Definition: globals.h:80
attrsym_t * G_coord
Definition: layout.c:51
graph_t ** cl
Definition: layout.c:281
int agxset(void *obj, Agsym_t *sym, char *value)
Definition: attr.c:468
EXTERN int Nop
Definition: globals.h:70
#define ALLOC(size, ptr, type)
Definition: memory.h:41
#define DEFAULT_NODEHEIGHT
Definition: const.h:75
#define assert(x)
Definition: cghdr.h:47
Definition: geom.h:28
#define PF2P(pf, p)
Definition: geom.h:72
edge_t * e
Definition: layout.c:59
EXTERN Agsym_t * G_margin
Definition: globals.h:88
void gv_postprocess(Agraph_t *g, int allowTranslation)
Definition: postproc.c:603
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
#define EDGE_TYPE(g)
Definition: macros.h:33
CGRAPH_API int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
#define P_SET
Definition: const.h:283
#define GVSPLINES
Definition: const.h:181
#define ND_pos(n)
Definition: types.h:526
void do_graph_label(graph_t *sg)
Definition: input.c:892
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
#define P_FIX
Definition: const.h:284
CGRAPH_API Agraph_t * agfstsubg(Agraph_t *g)
Definition: subg.c:72
int splineEdges(graph_t *, int(*edgefn)(graph_t *, expand_t *, int), int)
Definition: neatosplines.c:700
#define parent(i)
Definition: closest.c:88
pack_mode getPackInfo(Agraph_t *g, pack_mode dflt, int dfltMargin, pack_info *pinfo)
Definition: pack.c:1398
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
#define ND_shape_info(n)
Definition: types.h:535
pack_mode mode
Definition: pack.h:54
point UR
Definition: geom.h:33
int x
Definition: geom.h:26
int cnt
Definition: layout.c:283
#define POINTS(a_inches)
Definition: geom.h:67
int compoundEdges(graph_t *g, expand_t *pm, int edgetype)
Definition: clusteredges.c:255
#define PARENT(n)
Definition: circular.h:89
#define POINTS_PER_INCH
Definition: geom.h:62
#define ND_clust(n)
Definition: types.h:495
Definition: cgraph.h:388
#define PS2INCH(a_points)
Definition: geom.h:69
CGRAPH_API Agraph_t * agnxtsubg(Agraph_t *subg)
Definition: subg.c:77
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
#define BOTTOM_IX
Definition: const.h:112
CGRAPH_API Agdesc_t Agstrictdirected
Definition: cgraph.h:419
int normalize(graph_t *g)
Definition: adjust.c:922
boolean * fixed
Definition: pack.h:55
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
#define NIL(t)
Definition: dthdr.h:13
#define ND_ht(n)
Definition: types.h:506
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
#define ND_shape(n)
Definition: types.h:534
#define ET_COMPOUND
Definition: const.h:276
void fdp_layout(Agraph_t *g)
Definition: layout.c:1114
double y
Definition: geom.h:28
CGRAPH_API int agclose(Agraph_t *g)
Definition: graph.c:93
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define ND_height(n)
Definition: types.h:504
#define ND_id(n)
Definition: types.h:489
CGRAPH_API Agraph_t * agparent(Agraph_t *g)
Definition: subg.c:85
#define INCH2PS(a_inches)
Definition: geom.h:68
#define ET_NONE
Definition: const.h:270
#define ED_count(e)
Definition: types.h:583
void fdp_initParams(graph_t *g)
Definition: tlayout.c:181
#define ND_rw(n)
Definition: types.h:531
#define ET_LINE
Definition: const.h:271
void compute_bb(graph_t *g)
Definition: utils.c:852
point LL
Definition: geom.h:33
#define GD_ndim(g)
Definition: types.h:398
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define GD_alg(g)
Definition: types.h:361
int late_int(void *obj, attrsym_t *attr, int def, int low)
Definition: utils.c:71
#define GD_clust(g)
Definition: types.h:364
#define CL_CHUNK
Definition: layout.c:278
Definition: layout.c:58
int sz
Definition: layout.c:282
#define CL_OFFSET
Definition: const.h:155
#define ND_width(n)
Definition: types.h:542
double get_inputscale(graph_t *g)
Definition: utils.c:112
#define ED_to_virt(e)
Definition: types.h:602
#define ND_lw(n)
Definition: types.h:513
#define ND_alg(n)
Definition: types.h:490
#define ED_factor(e)
Definition: types.h:588
void fdp_xLayout(graph_t *g, xparams *xpms)
Definition: xlayout.c:525
#define NULL
Definition: logic.h:39
real cg(Operator Ax, Operator precond, int n, int dim, real *x0, real *rhs, real tol, int maxit, int *flag)
Definition: sparse_solve.c:227
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
CGRAPH_API int agdelrec(void *obj, char *name)
Definition: rec.c:145
Definition: geom.h:26
double x
Definition: geom.h:28
EXTERN unsigned char Verbose
Definition: globals.h:64
pack_info pack
Definition: layout.c:55
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
pointf LL
Definition: geom.h:35
#define NEW_EDGE(e)
Definition: layout.c:64
double dist2
Definition: layout.c:61
CGRAPH_API Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition: edge.c:281
#define alpha
Definition: shapes.c:3902
#define DNODE(n)
Definition: circular.h:79
#define IS_CLUST_NODE(n)
Definition: macros.h:31
void fdp_tLayout(graph_t *g, xparams *xpms)
Definition: tlayout.c:664
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
void setEdgeType(graph_t *g, int dflt)
Definition: utils.c:1802
#define MAXDIM
Definition: const.h:177
#define GD_bb(g)
Definition: types.h:357
#define M_PI
Definition: arith.h:77
#define HAS_CLUST_EDGE(g)
Definition: macros.h:32
point * putGraphs(int ng, Agraph_t **gs, Agraph_t *root, pack_info *pinfo)
Definition: pack.c:916
int gid
Definition: layout.c:54
int spline_edges1(graph_t *g, int)
Definition: neatosplines.c:748
EXTERN double PSinputscale
Definition: globals.h:71
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
#define BF2B(bf, b)
Definition: geom.h:75
#define ANG
Definition: layout.c:605
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
int y
Definition: geom.h:26
void fdp_init_node_edge(Agraph_t *g)
Definition: fdpinit.c:83
#define ED_dist(e)
Definition: types.h:605
char * el(GVJ_t *job, char *template,...)
pointf UR
Definition: geom.h:35
Definition: geom.h:35
#define P_PIN
Definition: const.h:285
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define TOP_IX
Definition: const.h:114
#define MAXDOUBLE
Definition: arith.h:64
#define ET_ORTHO
Definition: const.h:274
EXTERN int Ndim
Definition: globals.h:79
attrsym_t * G_width
Definition: layout.c:52
Definition: geom.h:33
#define NEW(t)
Definition: memory.h:35
#define AGRAPH
Definition: cgraph.h:100
boolean neato_set_aspect(graph_t *g)
attrsym_t * G_height
Definition: layout.c:53
#define TRUE
Definition: cgraph.h:38