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#include "config.h"
16
17/* TODO:
18 * If cut point is in exactly 2 blocks, expand block circles to overlap
19 * especially in the case where one block is the sole child of the other.
20 */
21
22#include "blockpath.h"
23
24/* getRotation:
25 * The function determines how much the block should be rotated
26 * for best positioning with parent, assuming its center is at x and y
27 * relative to the parent.
28 * angle gives the angle of the new position, i.e., tan(angle) = y/x.
29 * If sn has 2 nodes, we arrange the line of the 2 normal to angle.
30 * If sn has 1 node, parent_pos has already been set to the
31 * correct angle assuming no rotation.
32 * Otherwise, we find the node in sn connected to the parent and rotate
33 * the block so that it is closer or at least visible to its node in the
34 * parent.
35 *
36 * For COALESCED blocks, if neighbor is in left half plane,
37 * use unCOALESCED case.
38 * Else let theta be angle, R = LEN(x,y), pho the radius of actual
39 * child block, phi be angle of neighbor in actual child block,
40 * and r the distance from center of coalesced block to center of
41 * actual block. Then, the angle to rotate the coalesced block to
42 * that the edge from the parent is tangent to the neighbor on the
43 * actual child block circle is
44 * alpha = theta + M_PI/2 - phi - arcsin((l/R)*(sin B))
45 * where l = r - rho/(cos phi) and beta = M_PI/2 + phi.
46 * Thus,
47 * alpha = theta + M_PI/2 - phi - arcsin((l/R)*(cos phi))
48 */
49static double
50getRotation(block_t * sn, Agraph_t * g, double x, double y, double theta)
51{
52 double mindist2;
53 Agraph_t *subg;
54 /* Agedge_t* e; */
55 Agnode_t *n, *closest_node, *neighbor;
56 nodelist_t *list;
57 double len2, newX, newY;
58 int count;
59
60 subg = sn->sub_graph;
61#ifdef OLD
62 parent = sn->parent;
63#endif
64
65 list = sn->circle_list;
66
67 if (sn->parent_pos >= 0) {
68 theta += M_PI - sn->parent_pos;
69 if (theta < 0)
70 theta += 2 * M_PI;
71
72 return theta;
73 }
74
75 count = sizeNodelist(list);
76 if (count == 2) {
77 return (theta - M_PI / 2.0);
78 }
79
80 /* Find node in block connected to block's parent */
81 neighbor = CHILD(sn);
82#ifdef OLD
83 for (e = agfstedge(g, parent); e; e = agnxtedge(g, e, parent)) {
84 n = e->head;
85 if (n == parent)
86 n = e->tail;
87
88 if ((BLOCK(n) == sn) && (PARENT(n) == parent)) {
89 neighbor = n;
90 break;
91 }
92 }
93#endif
94 newX = ND_pos(neighbor)[0] + x;
95 newY = ND_pos(neighbor)[1] + y;
96 mindist2 = LEN2(newX, newY); /* save sqrts by using sqr of dist to find min */
97 closest_node = neighbor;
98
99 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
100 if (n == neighbor)
101 continue;
102
103 newX = ND_pos(n)[0] + x;
104 newY = ND_pos(n)[1] + y;
105
106 len2 = LEN2(newX, newY);
107 if (len2 < mindist2) {
108 mindist2 = len2;
109 closest_node = n;
110 }
111 }
112
113 /* if((neighbor != closest_node) && !ISPARENT(neighbor)) { */
114 if (neighbor != closest_node) {
115 double rho = sn->rad0;
116 double r = sn->radius - rho;
117 double n_x = ND_pos(neighbor)[0];
118 if (COALESCED(sn) && (-r < n_x)) {
119 double R = LEN(x, y);
120 double n_y = ND_pos(neighbor)[1];
121 double phi = atan2(n_y, n_x + r);
122 double l = r - rho / (cos(phi));
123
124 theta += M_PI / 2.0 - phi - asin((l / R) * (cos(phi)));
125 } else { /* Origin still at center of this block */
126 double phi = atan2(ND_pos(neighbor)[1], ND_pos(neighbor)[0]);
127 theta += M_PI - phi - PSI(neighbor);
128 if (theta > 2 * M_PI)
129 theta -= 2 * M_PI;
130 }
131 } else
132 theta = 0;
133 return theta;
134}
135
136
137/* applyDelta:
138 * Recursively apply rotation rotate followed by translation (x,y)
139 * to block sn and its children.
140 */
141static void applyDelta(block_t * sn, double x, double y, double rotate)
142{
143 block_t *child;
144 Agraph_t *subg;
145 Agnode_t *n;
146
147 subg = sn->sub_graph;
148
149 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
150 double X, Y;
151
152 if (rotate != 0) {
153 double tmpX, tmpY;
154 double cosR, sinR;
155
156 tmpX = ND_pos(n)[0];
157 tmpY = ND_pos(n)[1];
158 cosR = cos(rotate);
159 sinR = sin(rotate);
160
161 X = tmpX * cosR - tmpY * sinR;
162 Y = tmpX * sinR + tmpY * cosR;
163 } else {
164 X = ND_pos(n)[0];
165 Y = ND_pos(n)[1];
166 }
167
168 /* translate */
169 ND_pos(n)[0] = X + x;
170 ND_pos(n)[1] = Y + y;
171 }
172
173 for (child = sn->children.first; child; child = child->next)
174 applyDelta(child, x, y, rotate);
175}
176
177/* firstangle and lastangle give the range of child angles.
178 * These are set and used only when a block has just 1 node.
179 * And are used to give the center angle between the two extremes.
180 * The parent will then be attached at PI - center angle (parent_pos).
181 * If this block has no children, this is PI. Otherwise, positionChildren will
182 * be called once with the blocks node. firstangle will be 0, with
183 * succeeding angles increasing.
184 * position can always return the center angle - PI, since the block
185 * must have children and if the block has 1 node, the limits will be
186 * correctly set. If the block has more than 1 node, the value is
187 * unused.
188 */
189typedef struct {
190 double radius; /* Basic radius of block */
191 double subtreeR; /* Max of subtree radii */
192 double nodeAngle; /* Angle allocated to each node in block */
193 double firstAngle; /* Smallest child angle when block has 1 node */
194 double lastAngle; /* Largest child angle when block has 1 node */
195 block_t *cp; /* Children of block */
196 node_t *neighbor; /* Node connected to parent block, if any */
197} posstate;
198
199typedef struct {
200 Agnode_t* n;
201 double theta; /* angle of node */
202 double minRadius; /* minimum radius for child circle */
203 double maxRadius; /* maximum radius of child blocks */
204 double diameter; /* length of arc needed for child blocks */
205 double scale; /* scale factor to increase minRadius to parents' children don't overlap */
206 int childCount; /* no. of child blocks attached at n */
207} posinfo_t;
208
209/* getInfo:
210 * get size info for blocks attached to the given node.
211 */
212static double
213getInfo (posinfo_t* pi, posstate * stp, double min_dist)
214{
215 block_t *child;
216 double maxRadius = 0; /* Max. radius of children */
217 double diameter = 0; /* sum of child diameters */
218 int childCount = 0;
219
220 for (child = stp->cp; child; child = child->next) {
221 if (BLK_PARENT(child) == pi->n) {
222 childCount++;
223 if (maxRadius < child->radius) {
224 maxRadius = child->radius;
225 }
226 diameter += 2 * child->radius + min_dist;
227 }
228 }
229
230 pi->diameter = diameter;
231 pi->childCount = childCount;
232 pi->minRadius = stp->radius + min_dist + maxRadius;
233 pi->maxRadius = maxRadius;
234 return maxRadius;
235}
236
237/* setInfo:
238 */
239static void
240setInfo (posinfo_t* p0, posinfo_t* p1, double delta)
241{
242 double t = (p0->diameter*p1->minRadius) + (p1->diameter*p0->minRadius);
243
244 t /= 2*delta*p0->minRadius*p1->minRadius;
245
246 if (t < 1)
247 t = 1;
248
249 if (t > p0->scale)
250 p0->scale = t;
251 if (t > p1->scale)
252 p1->scale = t;
253}
254
255/* positionChildren:
256 */
257static void
258positionChildren (Agraph_t* g, posinfo_t* pi, posstate * stp, int length, double min_dist)
259{
260 block_t *child;
261 double childAngle, childRadius, incidentAngle;
262 double mindistAngle, rotateAngle, midAngle = 0.0;
263 int midChild, cnt = 0;
264 double snRadius = stp->subtreeR; /* max subtree radius */
265 double firstAngle = stp->firstAngle;
266 double lastAngle = stp->lastAngle;
267 double d, deltaX, deltaY;
268
269 childRadius = pi->scale * pi->minRadius;
270 if (length == 1) {
271 childAngle = 0;
272 d = pi->diameter/(2*M_PI);
273 childRadius = MAX(childRadius, d);
274 d = 2*M_PI*childRadius - pi->diameter;
275 if (d > 0)
276 min_dist += d/pi->childCount;
277 }
278 else
279 childAngle = pi->theta - pi->diameter/(2 * childRadius);
280
281 if ((childRadius + pi->maxRadius) > snRadius)
282 snRadius = childRadius + pi->maxRadius;
283
284 mindistAngle = min_dist / childRadius;
285
286 midChild = (pi->childCount + 1) / 2;
287 for (child = stp->cp; child; child = child->next) {
288 if (BLK_PARENT(child) != pi->n)
289 continue;
290 if (sizeNodelist(child->circle_list) <= 0)
291 continue;
292
293 incidentAngle = child->radius / childRadius;
294 if (length == 1) {
295 if (childAngle != 0) {
296 if (pi->childCount == 2)
297 childAngle = M_PI;
298 else
299 childAngle += incidentAngle;
300 }
301
302 if (firstAngle < 0)
303 firstAngle = childAngle;
304
305 lastAngle = childAngle;
306 } else {
307 if (pi->childCount == 1) {
308 childAngle = pi->theta;
309 } else {
310 childAngle += incidentAngle + mindistAngle / 2;
311 }
312 }
313
314 deltaX = childRadius * cos(childAngle);
315 deltaY = childRadius * sin(childAngle);
316
317 /* first apply the delta to the immediate child and see if we need
318 * to rotate it for better edge link
319 * should return the theta value if there was a rotation else zero
320 */
321
322 rotateAngle = getRotation(child, g, deltaX, deltaY, childAngle);
323 applyDelta(child, deltaX, deltaY, rotateAngle);
324
325 if (length == 1) {
326 childAngle += incidentAngle + mindistAngle;
327 } else {
328 childAngle += incidentAngle + mindistAngle / 2;
329 }
330 cnt++;
331 if (cnt == midChild)
332 midAngle = childAngle;
333 }
334
335 if ((length > 1) && (pi->n == stp->neighbor)) {
336 PSI(pi->n) = midAngle;
337 }
338
339 stp->subtreeR = snRadius;
340 stp->firstAngle = firstAngle;
341 stp->lastAngle = lastAngle;
342}
343
344/* position:
345 * Assume childCount > 0
346 * For each node in the block with children, getInfo is called, with the
347 * information stored in the parents array.
348 * This information is used by setInfo to compute the amount of space allocated
349 * to each parent and the radius at which to place its children.
350 * Finally, positionChildren is called to do the actual positioning.
351 * If length is 1, keeps track of minimum and maximum child angle.
352 */
353static double
354position(Agraph_t * g, int childCount, int length, nodelist_t * path,
355 block_t * sn, double min_dist)
356{
357 nodelistitem_t *item;
358 Agnode_t *n;
359 posstate state;
360 int i, counter = 0;
361 double maxRadius = 0.0;
362 double angle;
363 double theta = 0.0;
364 posinfo_t* parents = N_NEW(childCount, posinfo_t);
365 int num_parents = 0;
366 posinfo_t* next;
367 posinfo_t* curr;
368 double delta;
369
370 state.cp = sn->children.first;
371 state.subtreeR = sn->radius;
372 state.radius = sn->radius;
373 state.neighbor = CHILD(sn);
374 state.nodeAngle = 2 * M_PI / length;
375 state.firstAngle = -1;
376 state.lastAngle = -1;
377
378 for (item = path->first; item; item = item->next) {
379 n = item->curr;
380
381 theta = counter * state.nodeAngle;
382 counter++;
383
384 if (ISPARENT(n)) {
385 parents[num_parents].n = n;
386 parents[num_parents].theta = theta;
387 maxRadius = getInfo (parents+num_parents, &state, min_dist);
388 num_parents++;
389 }
390 }
391
392 if (num_parents == 1)
393 parents->scale = 1.0;
394 else if (num_parents == 2) {
395 curr = parents;
396 next = parents+1;
397 delta = next->theta - curr->theta;
398 if (delta > M_PI)
399 delta = 2*M_PI - delta;
400 setInfo (curr, next, delta);
401 }
402 else {
403 curr = parents;
404 for (i = 0; i < num_parents; i++) {
405 if (i+1 == num_parents) {
406 next = parents;
407 delta = next->theta - curr->theta + 2*M_PI;
408 }
409 else {
410 next = curr+1;
411 delta = next->theta - curr->theta;
412 }
413 setInfo (curr, next, delta);
414 curr++;
415 }
416 }
417
418 for (i = 0; i < num_parents; i++) {
419 positionChildren (g, parents + i, &state, length, min_dist);
420 }
421
422 free (parents);
423
424 /* If block has only 1 child, to save space, we coalesce it with the
425 * child. Instead of having final radius sn->radius + max child radius,
426 * we have half that. However, the origin of the block is no longer in
427 * the center of the block, so we cannot do a simple rotation to get
428 * the neighbor node next to the parent block in getRotate.
429 */
430 if (childCount == 1) {
431 applyDelta(sn, -(maxRadius + min_dist / 2), 0, 0);
432 sn->radius += min_dist / 2 + maxRadius;
433 SET_COALESCED(sn);
434 } else
435 sn->radius = state.subtreeR;
436
437 angle = (state.firstAngle + state.lastAngle) / 2.0 - M_PI;
438 return angle;
439}
440
441/* doBlock:
442 * Set positions of block sn and its child blocks.
443 */
444static void doBlock(Agraph_t * g, block_t * sn, double min_dist)
445{
446 block_t *child;
447 nodelist_t *longest_path;
448 int childCount, length;
449 double centerAngle = M_PI;
450
451 /* layout child subtrees */
452 childCount = 0;
453 for (child = sn->children.first; child; child = child->next) {
454 doBlock(g, child, min_dist);
455 childCount++;
456 }
457
458 /* layout this block */
459 longest_path = layout_block(g, sn, min_dist);
460 sn->circle_list = longest_path;
461 length = sizeNodelist(longest_path); /* path contains everything in block */
462
463 /* attach children */
464 if (childCount > 0)
465 centerAngle =
466 position(g, childCount, length, longest_path, sn, min_dist);
467
468 if ((length == 1) && (BLK_PARENT(sn))) {
469 sn->parent_pos = centerAngle;
470 if (sn->parent_pos < 0)
471 sn->parent_pos += 2 * M_PI;
472 }
473}
474
475void circPos(Agraph_t * g, block_t * sn, circ_state * state)
476{
477 doBlock(g, sn, state->min_dist);
478}
479