Graphviz  2.41.20170921.2350
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 #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  */
49 static double
50 getRotation(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  */
141 static 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  */
189 typedef 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 
199 typedef struct {
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  */
212 static double
213 getInfo (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  */
239 static void
240 setInfo (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  */
257 static void
258 positionChildren (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  */
353 static double
354 position(Agraph_t * g, int childCount, int length, nodelist_t * path,
355  block_t * sn, double min_dist)
356 {
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  */
444 static 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 
475 void circPos(Agraph_t * g, block_t * sn, circ_state * state)
476 {
477  doBlock(g, sn, state->min_dist);
478 }
#define MAX(a, b)
Definition: agerror.c:17
double nodeAngle
Definition: circpos.c:192
#define N_NEW(n, t)
Definition: memory.h:36
void circPos(Agraph_t *g, block_t *sn, circ_state *state)
Definition: circpos.c:475
double minRadius
Definition: circpos.c:202
double parent_pos
Definition: block.h:38
double radius
Definition: block.h:34
double firstAngle
Definition: circpos.c:193
block_t * cp
Definition: circpos.c:195
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
#define ND_pos(n)
Definition: types.h:526
#define parent(i)
Definition: closest.c:88
double diameter
Definition: circpos.c:204
#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:206
#define PSI(n)
Definition: circular.h:101
double lastAngle
Definition: circpos.c:194
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
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
#define LEN(a, b)
Definition: geom.h:57
double subtreeR
Definition: circpos.c:191
nodelistitem_t * first
Definition: nodelist.h:32
block_t * first
Definition: block.h:26
#define COALESCED(b)
Definition: block.h:60
node_t * neighbor
Definition: circpos.c:196
#define ISPARENT(n)
Definition: circular.h:111
nodelist_t * circle_list
Definition: block.h:36
double maxRadius
Definition: circpos.c:203
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
double scale
Definition: circpos.c:205
#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
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
Agnode_t * n
Definition: circpos.c:200
block_t * next
Definition: block.h:32
struct item_s item
double theta
Definition: circpos.c:201
Definition: types.h:100
double radius
Definition: circpos.c:190
#define M_PI
Definition: arith.h:77
#define SET_COALESCED(b)
Definition: block.h:61
blocklist_t children
Definition: block.h:37
#define LEN2(a, b)
Definition: geom.h:56
nodelistitem_t * next
Definition: nodelist.h:27