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#include <stdio.h>
15#include <stdlib.h>
16#include <patchwork.h>
17#include <tree_map.h>
18#include "render.h"
19
20typedef struct treenode_t treenode_t;
21struct treenode_t {
22 double area;
23 double child_area;
24 rectangle r;
25 treenode_t *leftchild, *rightsib;
26 union {
27 Agraph_t *subg;
28 Agnode_t *n;
29 } u;
30 int kind;
31 int n_children;
32};
33
34#define DFLT_SZ 1.0
35#define SCALE 1000.0 /* scale up so that 1 is a reasonable default size */
36
37#ifdef DEBUG
38void dumpTree (treenode_t* r, int ind)
39{
40 int i;
41 treenode_t* cp;
42
43 for (i=0; i < ind; i++) fputs(" ", stderr);
44 fprintf (stderr, "%s (%f)\n", (r->kind == AGNODE?agnameof(r->u.n):agnameof(r->u.subg)), r->area);
45 for (cp = r->leftchild; cp; cp = cp->rightsib)
46 dumpTree (cp, ind+1);
47}
48#endif
49
50/* fullArea:
51 * Allow extra area for specified inset. Assume p->kind = AGRAPH
52 * and p->child_area is set. At present, inset is additive; we
53 * may want to allow a multiplicative inset as well.
54 */
55static double fullArea (treenode_t* p, attrsym_t* mp)
56{
57 double m = late_double (p->u.subg, mp, 0, 0);
58 if (m == 0) return p->child_area;
59 else {
60 double wid = (2.0*m + sqrt(p->child_area));
61 return wid*wid;
62 }
63}
64
65static double getArea (void* obj, attrsym_t* ap)
66{
67 double area = late_double (obj, ap, DFLT_SZ, 0);
68 if (area == 0) area = DFLT_SZ;
69 area *= SCALE;
70 return area;
71}
72
73/* mkTreeNode:
74 */
75static treenode_t* mkTreeNode (Agnode_t* n, attrsym_t* ap)
76{
77 treenode_t *p = NEW(treenode_t);
78
79 p->area = getArea (n, ap);
80 p->kind = AGNODE;
81 p->u.n = n;
82
83 return p;
84}
85
86#define INSERT(cp) if(!first) first=cp; if(prev) prev->rightsib=cp; prev=cp;
87
88/* mkTree:
89 * Recursively build tree from graph
90 * Pre-condition: agnnodes(g) != 0
91 */
92static treenode_t *mkTree (Agraph_t * g, attrsym_t* gp, attrsym_t* ap, attrsym_t* mp)
93{
94 treenode_t *p = NEW(treenode_t);
95 Agraph_t *subg;
96 Agnode_t *n;
97 treenode_t *cp;
98 treenode_t *first = 0;
99 treenode_t *prev = 0;
100 int i, n_children = 0;
101 double area = 0;
102
103 p->kind = AGRAPH;
104 p->u.subg = g;
105
106 for (i = 1; i <= GD_n_cluster(g); i++) {
107 subg = GD_clust(g)[i];
108 cp = mkTree (subg, gp, ap, mp);
109 n_children++;
110 area += cp->area;
111 INSERT(cp);
112 }
113
114 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
115 if (SPARENT(n))
116 continue;
117 cp = mkTreeNode (n, ap);
118 n_children++;
119 area += cp->area;
120 INSERT(cp);
121 SPARENT(n) = g;
122 }
123
124 p->n_children = n_children;
125 if (n_children) {
126 p->child_area = area;
127 p->area = fullArea (p, mp);
128 }
129 else {
130 p->area = getArea (g, gp);
131 }
132 p->leftchild = first;
133
134 return p;
135}
136
137static int nodecmp (treenode_t** p0, treenode_t** p1)
138{
139 double diff = (*p0)->area - (*p1)->area;
140
141 if (diff < 0) return 1;
142 else if (diff > 0) return -1;
143 else return 0;
144}
145
146static void layoutTree(treenode_t * tree)
147{
148 rectangle *recs;
149 treenode_t** nodes;
150 double* areas_sorted;
151 int i, nc;
152 treenode_t* cp;
153
154 /* if (tree->kind == AGNODE) return; */
155 if (tree->n_children == 0) return;
156
157 nc = tree->n_children;
158 nodes = N_NEW(nc, treenode_t*);
159 cp = tree->leftchild;
160 for (i = 0; i < nc; i++) {
161 nodes[i] = cp;
162 cp = cp->rightsib;
163 }
164
165 qsort (nodes, nc, sizeof(treenode_t*), (qsort_cmpf)nodecmp);
166 areas_sorted = N_NEW(nc,double);
167 for (i = 0; i < nc; i++) {
168 areas_sorted[i] = nodes[i]->area;
169 }
170 if (tree->area == tree->child_area)
171 recs = tree_map(nc, areas_sorted, tree->r);
172 else {
173 rectangle crec;
174 double disc, delta, m, h = tree->r.size[1], w = tree->r.size[0];
175 crec.x[0] = tree->r.x[0];
176 crec.x[1] = tree->r.x[1];
177 delta = h - w;
178 disc = sqrt(delta*delta + 4.0*tree->child_area);
179 m = (h + w - disc)/2.0;
180 crec.size[0] = w - m;
181 crec.size[1] = h - m;
182 recs = tree_map(nc, areas_sorted, crec);
183 }
184 if (Verbose)
185 fprintf (stderr, "rec %f %f %f %f\n", tree->r.x[0], tree->r.x[1], tree->r.size[0], tree->r.size[1]);
186 for (i = 0; i < nc; i++) {
187 nodes[i]->r = recs[i];
188 if (Verbose)
189 fprintf (stderr, "%f - %f %f %f %f = %f (%f %f %f %f)\n", areas_sorted[i],
190 recs[i].x[0]-recs[i].size[0]*0.5, recs[i].x[1]-recs[i].size[1]*0.5,
191 recs[i].x[0]+recs[i].size[0]*0.5, recs[i].x[1]+recs[i].size[1]*0.5, recs[i].size[0]*recs[i].size[1],
192 recs[i].x[0], recs[i].x[1], recs[i].size[0], recs[i].size[1]);
193
194 }
195 free (nodes);
196 free (areas_sorted);
197 free (recs);
198
199 cp = tree->leftchild;
200 for (i = 0; i < nc; i++) {
201 if (cp->kind == AGRAPH)
202 layoutTree (cp);
203 cp = cp->rightsib;
204 }
205}
206
207static void finishNode(node_t * n)
208{
209 char buf [40];
210 if (N_fontsize) {
211 char* str = agxget(n, N_fontsize);
212 if (*str == '\0') {
213 sprintf (buf, "%.03f", ND_ht(n)*0.7);
214 agxset(n, N_fontsize, buf);
215 }
216 }
217 common_init_node (n);
218}
219
220static void walkTree(treenode_t * tree)
221{
222 treenode_t *p;
223 Agnode_t *n;
224 pointf center;
225 rectangle rr;
226 boxf r;
227 double x0, y0, wd, ht;
228
229 if (tree->kind == AGRAPH) {
230 for (p = tree->leftchild; p; p = p->rightsib)
231 walkTree (p);
232 x0 = tree->r.x[0];
233 y0 = tree->r.x[1];
234 wd = tree->r.size[0];
235 ht = tree->r.size[1];
236 r.LL.x = x0 - wd/2.0;
237 r.LL.y = y0 - ht/2.0;
238 r.UR.x = r.LL.x + wd;
239 r.UR.y = r.LL.y + ht;
240 GD_bb(tree->u.subg) = r;
241 }
242 else {
243 rr = tree->r;
244 center.x = rr.x[0];
245 center.y = rr.x[1];
246
247 n = tree->u.n;
248 ND_coord(n) = center;
249 ND_width(n) = PS2INCH(rr.size[0]);
250 ND_height(n) = PS2INCH(rr.size[1]);
251 gv_nodesize(n, GD_flip(agraphof(n)));
252 finishNode(n);
253 if (Verbose)
254 fprintf(stderr,"%s coord %.5g %.5g ht %f width %f\n",
255 agnameof(n), ND_coord(n).x, ND_coord(n).y, ND_ht(n), ND_xsize(n));
256 }
257}
258
259/* freeTree:
260 */
261static void freeTree (treenode_t* tp)
262{
263 treenode_t* cp = tp->leftchild;
264 treenode_t* rp;
265 int i, nc = tp->n_children;
266
267 for (i = 0; i < nc; i++) {
268 rp = cp->rightsib;
269 freeTree (cp);
270 cp = rp;
271 }
272 free (tp);
273}
274
275/* patchworkLayout:
276 */
277void patchworkLayout(Agraph_t * g)
278{
279 treenode_t* root;
280 attrsym_t * ap = agfindnodeattr(g, "area");
281 attrsym_t * gp = agfindgraphattr(g, "area");
282 attrsym_t * mp = agfindgraphattr(g, "inset");
283 double total;
284
285 root = mkTree (g,gp,ap,mp);
286 total = root->area;
287 root->r = rectangle_new(0, 0, sqrt(total + 0.1), sqrt(total + 0.1));
288 layoutTree(root);
289 walkTree(root);
290 freeTree (root);
291}
292