1/* vim:set shiftwidth=4 ts=8: */
2
3/*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v1.0
7 * which accompanies this distribution, and is available at
8 * http://www.eclipse.org/legal/epl-v10.html
9 *
10 * Contributors: See CVS logs. Details at http://www.graphviz.org/
11 *************************************************************************/
12
13
14/* FIX: handle cluster labels */
15/*
16 * Written by Emden R. Gansner
17 */
18
19#include "osage.h"
20#include "neatoprocs.h"
21#include "pack.h"
22
23#define CL_CHUNK 10
24#define DFLT_SZ 18
25#define PARENT(n) ((Agraph_t*)ND_alg(n))
26
27static void
28indent (int i)
29{
30 for (; i > 0; i--)
31 fputs (" ", stderr);
32}
33
34typedef struct {
35 Agraph_t** cl;
36 int sz;
37 int cnt;
38} clist_t;
39
40static void initCList(clist_t * clist)
41{
42 clist->cl = 0;
43 clist->sz = 0;
44 clist->cnt = 0;
45}
46
47/* addCluster:
48 * Append a new cluster to the list.
49 * NOTE: cl[0] is empty. The clusters are in cl[1..cnt].
50 * Normally, we increase the array when cnt == sz.
51 * The test for cnt > sz is necessary for the first time.
52 */
53static void addCluster(clist_t * clist, graph_t * subg)
54{
55 clist->cnt++;
56 if (clist->cnt >= clist->sz) {
57 clist->sz += CL_CHUNK;
58 clist->cl = RALLOC(clist->sz, clist->cl, graph_t *);
59 }
60 clist->cl[clist->cnt] = subg;
61}
62
63static void cluster_init_graph(graph_t * g)
64{
65 Agnode_t *n;
66 Agedge_t *e;
67
68 setEdgeType (g, ET_LINE);
69 Ndim = GD_ndim(g)=2; /* The algorithm only makes sense in 2D */
70
71 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
72 neato_init_node (n);
73 }
74 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
75 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
76 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE); //edge custom data
77 common_init_edge(e);
78 }
79 }
80}
81
82/* layout:
83 */
84static void
85layout (Agraph_t* g, int depth)
86{
87 int i, j, total, nv;
88 int nvs = 0; /* no. of nodes in subclusters */
89 Agnode_t* n;
90 Agraph_t* subg;
91 boxf* gs;
92 point* pts;
93 boxf bb, rootbb;
94 pointf p;
95 pack_info pinfo;
96 pack_mode pmode;
97 double margin;
98 void** children;
99 Agsym_t* cattr = NULL;
100 Agsym_t* vattr = NULL;
101 Agraph_t* root = g->root;
102
103 if (Verbose > 1) {
104 indent (depth);
105 fprintf (stderr, "layout %s\n", agnameof(g));
106 }
107
108 /* Lay out subclusters */
109 for (i = 1; i <= GD_n_cluster(g); i++) {
110 subg = GD_clust(g)[i];
111 layout (subg, depth+1);
112 nvs += agnnodes (subg);
113 }
114
115 nv = agnnodes(g);
116 total = (nv - nvs) + GD_n_cluster(g);
117
118 if ((total == 0) && (GD_label(g) == NULL)) {
119 GD_bb(g).LL.x = GD_bb(g).LL.y = 0;
120 GD_bb(g).UR.x = GD_bb(g).UR.y = DFLT_SZ;
121 return;
122 }
123
124 pmode = getPackInfo(g, l_array, DFLT_MARGIN, &pinfo);
125 if (pmode < l_graph) pinfo.mode = l_graph;
126
127 /* add user sort values if necessary */
128 if ((pinfo.mode == l_array) && (pinfo.flags & PK_USER_VALS)) {
129 cattr = agattr(root, AGRAPH, "sortv", 0);
130 vattr = agattr(root, AGNODE, "sortv", 0);
131 if (cattr || vattr)
132 pinfo.vals = N_NEW(total, packval_t);
133 else
134 agerr (AGWARN, "Graph %s has array packing with user values but no \"sortv\" attributes are defined.",
135 agnameof(g));
136 }
137
138 gs = N_NEW(total, boxf);
139 children = N_NEW(total, void*);
140 j = 0;
141 for (i = 1; i <= GD_n_cluster(g); i++) {
142 subg = GD_clust(g)[i];
143 gs[j] = GD_bb(subg);
144 if (pinfo.vals && cattr) {
145 pinfo.vals[j] = late_int (subg, cattr, 0, 0);
146 }
147 children[j++] = subg;
148 }
149
150 if (nv-nvs > 0) {
151 for (n = agfstnode (g); n; n = agnxtnode (g,n)) {
152 if (ND_alg(n)) continue;
153 ND_alg(n) = g;
154 bb.LL.y = bb.LL.x = 0;
155 bb.UR.x = ND_xsize(n);
156 bb.UR.y = ND_ysize(n);
157 gs[j] = bb;
158 if (pinfo.vals && vattr) {
159 pinfo.vals[j] = late_int (n, vattr, 0, 0);
160 }
161 children[j++] = n;
162 }
163 }
164
165 /* pack rectangles */
166 pts = putRects (total, gs, &pinfo);
167 if (pinfo.vals) {
168 free (pinfo.vals);
169 }
170
171 rootbb.LL = pointfof(INT_MAX, INT_MAX);
172 rootbb.UR = pointfof(-INT_MAX, -INT_MAX);
173
174 /* reposition children relative to GD_bb(g) */
175 for (j = 0; j < total; j++) {
176 P2PF(pts[j],p);
177 bb = gs[j];
178 bb.LL.x += p.x;
179 bb.UR.x += p.x;
180 bb.LL.y += p.y;
181 bb.UR.y += p.y;
182 EXPANDBB(rootbb, bb);
183 if (j < GD_n_cluster(g)) {
184 subg = (Agraph_t*)children[j];
185 GD_bb(subg) = bb;
186 if (Verbose > 1) {
187 indent (depth);
188 fprintf (stderr, "%s : %f %f %f %f\n", agnameof(subg), bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
189 }
190 }
191 else {
192 n = (Agnode_t*)children[j];
193 ND_coord(n) = mid_pointf (bb.LL, bb.UR);
194 if (Verbose > 1) {
195 indent (depth);
196 fprintf (stderr, "%s : %f %f\n", agnameof(n), ND_coord(n).x, ND_coord(n).y);
197 }
198 }
199 }
200
201 if (GD_label(g)) {
202 pointf p;
203 double d;
204
205 p = GD_label(g)->dimen;
206 if (total == 0) {
207 rootbb.LL.x = 0;
208 rootbb.LL.y = 0;
209 rootbb.UR.x = p.x;
210 rootbb.UR.y = p.y;
211
212 }
213 d = p.x - (rootbb.UR.x - rootbb.LL.x);
214 if (d > 0) { /* height of label is added below */
215 d /= 2;
216 rootbb.LL.x -= d;
217 rootbb.UR.x += d;
218 }
219 }
220
221 if (depth > 0)
222 margin = pinfo.margin/2.0;
223 else
224 margin = 0;
225 rootbb.LL.x -= margin;
226 rootbb.UR.x += margin;
227 rootbb.LL.y -= (margin + GD_border(g)[BOTTOM_IX].y);
228 rootbb.UR.y += (margin + GD_border(g)[TOP_IX].y);
229
230 if (Verbose > 1) {
231 indent (depth);
232 fprintf (stderr, "%s : %f %f %f %f\n", agnameof(g), rootbb.LL.x, rootbb.LL.y, rootbb.UR.x, rootbb.UR.y);
233 }
234
235 /* Translate so that rootbb.LL is origin.
236 * This makes the repositioning simpler; we just translate the clusters and nodes in g by
237 * the final bb.ll of g.
238 */
239 for (j = 0; j < total; j++) {
240 if (j < GD_n_cluster(g)) {
241 subg = (Agraph_t*)children[j];
242 bb = GD_bb(subg);
243 bb.LL = sub_pointf(bb.LL, rootbb.LL);
244 bb.UR = sub_pointf(bb.UR, rootbb.LL);
245 GD_bb(subg) = bb;
246 if (Verbose > 1) {
247 indent (depth);
248 fprintf (stderr, "%s : %f %f %f %f\n", agnameof(subg), bb.LL.x, bb.LL.y, bb.UR.x, bb.UR.y);
249 }
250 }
251 else {
252 n = (Agnode_t*)children[j];
253 ND_coord(n) = sub_pointf (ND_coord(n), rootbb.LL);
254 if (Verbose > 1) {
255 indent (depth);
256 fprintf (stderr, "%s : %f %f\n", agnameof(n), ND_coord(n).x, ND_coord(n).y);
257 }
258 }
259 }
260
261 rootbb.UR = sub_pointf(rootbb.UR, rootbb.LL);
262 rootbb.LL = sub_pointf(rootbb.LL, rootbb.LL);
263 GD_bb(g) = rootbb;
264
265 if (Verbose > 1) {
266 indent (depth);
267 fprintf (stderr, "%s : %f %f %f %f\n", agnameof(g), rootbb.LL.x, rootbb.LL.y, rootbb.UR.x, rootbb.UR.y);
268 }
269
270 free (gs);
271 free (children);
272 free (pts);
273}
274
275static void
276reposition (Agraph_t* g, int depth)
277{
278 boxf sbb, bb = GD_bb(g);
279 Agnode_t* n;
280 Agraph_t* subg;
281 int i;
282
283 if (Verbose > 1) {
284 indent (depth);
285 fprintf (stderr, "reposition %s\n", agnameof(g));
286 }
287
288 /* translate nodes in g but not in a subcluster */
289 if (depth) {
290 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
291 if (PARENT(n) != g)
292 continue;
293 ND_coord(n).x += bb.LL.x;
294 ND_coord(n).y += bb.LL.y;
295 if (Verbose > 1) {
296 indent (depth);
297 fprintf (stderr, "%s : %f %f\n", agnameof(n), ND_coord(n).x, ND_coord(n).y);
298 }
299 }
300 }
301
302 /* translate top-level clusters and recurse */
303 for (i = 1; i <= GD_n_cluster(g); i++) {
304 subg = GD_clust(g)[i];
305 if (depth) {
306 sbb = GD_bb(subg);
307 sbb.LL.x += bb.LL.x;
308 sbb.LL.y += bb.LL.y;
309 sbb.UR.x += bb.LL.x;
310 sbb.UR.y += bb.LL.y;
311 if (Verbose > 1) {
312 indent (depth);
313 fprintf (stderr, "%s : %f %f %f %f\n", agnameof(subg), sbb.LL.x, sbb.LL.y, sbb.UR.x, sbb.UR.y);
314 }
315 GD_bb(subg) = sbb;
316 }
317 reposition (subg, depth+1);
318 }
319
320}
321
322static void
323mkClusters (Agraph_t* g, clist_t* pclist, Agraph_t* parent)
324{
325 graph_t* subg;
326 clist_t list;
327 clist_t* clist;
328
329 if (pclist == NULL) {
330 clist = &list;
331 initCList(clist);
332 }
333 else
334 clist = pclist;
335
336 for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
337 if (!strncmp(agnameof(subg), "cluster", 7)) {
338 agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
339 do_graph_label (subg);
340 addCluster(clist, subg);
341 mkClusters(subg, NULL, subg);
342 }
343 else {
344 mkClusters(subg, clist, parent);
345 }
346 }
347 if (pclist == NULL) {
348 GD_n_cluster(g) = list.cnt;
349 if (list.cnt)
350 GD_clust(g) = RALLOC(list.cnt + 1, list.cl, graph_t*);
351 }
352}
353
354void osage_layout(Agraph_t *g)
355{
356 cluster_init_graph(g);
357 mkClusters(g, NULL, g);
358 layout(g, 0);
359 reposition (g, 0);
360
361 if (GD_drawing(g)->ratio_kind) {
362 Agnode_t* n;
363 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
364 ND_pos(n)[0] = PS2INCH(ND_coord(n).x);
365 ND_pos(n)[1] = PS2INCH(ND_coord(n).y);
366 }
367 spline_edges0(g, TRUE);
368 }
369 else {
370 int et = EDGE_TYPE (g);
371 if (et != ET_NONE) spline_edges1(g, et);
372 }
373 dotneato_postprocess(g);
374}
375
376static void cleanup_graphs (Agraph_t *g)
377{
378 graph_t *subg;
379 int i;
380
381 for (i = 1; i <= GD_n_cluster(g); i++) {
382 subg = GD_clust(g)[i];
383 free_label(GD_label(subg));
384 cleanup_graphs (subg);
385 }
386 free (GD_clust(g));
387}
388
389void osage_cleanup(Agraph_t *g)
390{
391 node_t *n;
392
393 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
394 gv_cleanup_node(n);
395 }
396 cleanup_graphs(g);
397}
398