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