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
47static jmp_buf jbuf;
48
49typedef struct {
50 graph_t* rootg; /* logical root; graph passed in to fdp_layout */
51 attrsym_t *G_coord;
52 attrsym_t *G_width;
53 attrsym_t *G_height;
54 int gid;
55 pack_info pack;
56} layout_info;
57
58typedef struct {
59 edge_t *e;
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 */
75static void
76finalCC(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 */
184static 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
196static void freeDeriveNode(node_t * n)
197{
198 free(ND_alg(n));
199 free(ND_pos(n));
200 agdelrec(n, "Agnodeinfo_t");
201}
202
203static void freeGData(graph_t * g)
204{
205 free(GD_alg(g));
206}
207
208static 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 */
243static 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
280typedef struct {
281 graph_t **cl;
282 int sz;
283 int cnt;
284} clist_t;
285
286static 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 */
299static 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 */
319static 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 */
345static 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 */
388static 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 */
403static void
404copyAttr (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 */
426static 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 */
589static 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 */
612static 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 */
680static int
681genPorts(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 */
732static 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 */
787static void
788setClustNodes(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 */
857static
858void 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 */
986static 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 */
1005static 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 */
1022static void
1023mkClusters (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
1058static 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
1070static 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
1086static void
1087fdpSplines (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
1114void fdp_layout(graph_t * g)
1115{
1116 /* Agnode_t* n; */
1117
1118 double save_scale = PSinputscale;
1119
1120 PSinputscale = get_inputscale (g);
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}
1138