Graphviz 13.1.3~dev.20250829.0113
Loading...
Searching...
No Matches
circpos.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11
12#include "config.h"
13/* TODO:
14 * If cut point is in exactly 2 blocks, expand block circles to overlap
15 * especially in the case where one block is the sole child of the other.
16 */
17
18#include <circogen/blockpath.h>
19#include <circogen/circpos.h>
20#include <circogen/nodelist.h>
21#include <math.h>
22#include <stddef.h>
23#include <util/alloc.h>
24#include <util/list.h>
25
26/* The function determines how much the block should be rotated
27 * for best positioning with parent, assuming its center is at x and y
28 * relative to the parent.
29 * angle gives the angle of the new position, i.e., tan(angle) = y/x.
30 * If sn has 2 nodes, we arrange the line of the 2 normal to angle.
31 * If sn has 1 node, parent_pos has already been set to the
32 * correct angle assuming no rotation.
33 * Otherwise, we find the node in sn connected to the parent and rotate
34 * the block so that it is closer or at least visible to its node in the
35 * parent.
36 *
37 * For COALESCED blocks, if neighbor is in left half plane,
38 * use unCOALESCED case.
39 * Else let theta be angle, R = LEN(x,y), pho the radius of actual
40 * child block, phi be angle of neighbor in actual child block,
41 * and r the distance from center of coalesced block to center of
42 * actual block. Then, the angle to rotate the coalesced block to
43 * that the edge from the parent is tangent to the neighbor on the
44 * actual child block circle is
45 * alpha = theta + M_PI/2 - phi - arcsin((l/R)*(sin B))
46 * where l = r - rho/(cos phi) and beta = M_PI/2 + phi.
47 * Thus,
48 * alpha = theta + M_PI/2 - phi - arcsin((l/R)*(cos phi))
49 */
50static double getRotation(block_t *sn, double x, double y, double theta) {
51 double mindist2;
52 Agraph_t *subg;
53 Agnode_t *n, *closest_node, *neighbor;
54 double len2, newX, newY;
55
56 subg = sn->sub_graph;
57
58 nodelist_t *list = &sn->circle_list;
59
60 if (sn->parent_pos >= 0) {
61 theta += M_PI - sn->parent_pos;
62 if (theta < 0)
63 theta += 2 * M_PI;
64
65 return theta;
66 }
67
68 size_t count = LIST_SIZE(list);
69 if (count == 2) {
70 return theta - M_PI / 2.0;
71 }
72
73 /* Find node in block connected to block's parent */
74 neighbor = CHILD(sn);
75 newX = ND_pos(neighbor)[0] + x;
76 newY = ND_pos(neighbor)[1] + y;
77 mindist2 = LEN2(newX, newY); /* save sqrts by using sqr of dist to find min */
78 closest_node = neighbor;
79
80 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
81 if (n == neighbor)
82 continue;
83
84 newX = ND_pos(n)[0] + x;
85 newY = ND_pos(n)[1] + y;
86
87 len2 = LEN2(newX, newY);
88 if (len2 < mindist2) {
89 mindist2 = len2;
90 closest_node = n;
91 }
92 }
93
94 if (neighbor != closest_node) {
95 double rho = sn->rad0;
96 double r = sn->radius - rho;
97 double n_x = ND_pos(neighbor)[0];
98 if (COALESCED(sn) && -r < n_x) {
99 const double R = hypot(x, y);
100 double n_y = ND_pos(neighbor)[1];
101 double phi = atan2(n_y, n_x + r);
102 double l = r - rho / cos(phi);
103
104 theta += M_PI / 2.0 - phi - asin(l / R * cos(phi));
105 } else { /* Origin still at center of this block */
106 double phi = atan2(ND_pos(neighbor)[1], ND_pos(neighbor)[0]);
107 theta += M_PI - phi - PSI(neighbor);
108 if (theta > 2 * M_PI)
109 theta -= 2 * M_PI;
110 }
111 } else
112 theta = 0;
113 return theta;
114}
115
116/* Recursively apply rotation rotate followed by translation (x,y)
117 * to block sn and its children.
118 */
119static void applyDelta(block_t * sn, double x, double y, double rotate)
120{
121 block_t *child;
122 Agraph_t *subg;
123 Agnode_t *n;
124
125 subg = sn->sub_graph;
126
127 for (n = agfstnode(subg); n; n = agnxtnode(subg, n)) {
128
129 const double tmpX = ND_pos(n)[0];
130 const double tmpY = ND_pos(n)[1];
131 const double cosR = cos(rotate);
132 const double sinR = sin(rotate);
133
134 const double X = tmpX * cosR - tmpY * sinR;
135 const double Y = tmpX * sinR + tmpY * cosR;
136
137 /* translate */
138 ND_pos(n)[0] = X + x;
139 ND_pos(n)[1] = Y + y;
140 }
141
142 for (child = sn->children.first; child; child = child->next)
143 applyDelta(child, x, y, rotate);
144}
145
146/* firstangle and lastangle give the range of child angles.
147 * These are set and used only when a block has just 1 node.
148 * And are used to give the center angle between the two extremes.
149 * The parent will then be attached at PI - center angle (parent_pos).
150 * If this block has no children, this is PI. Otherwise, positionChildren will
151 * be called once with the blocks node. firstangle will be 0, with
152 * succeeding angles increasing.
153 * position can always return the center angle - PI, since the block
154 * must have children and if the block has 1 node, the limits will be
155 * correctly set. If the block has more than 1 node, the value is
156 * unused.
157 */
158typedef struct {
159 double radius; /* Basic radius of block */
160 double subtreeR; /* Max of subtree radii */
161 double nodeAngle; /* Angle allocated to each node in block */
162 double firstAngle; /* Smallest child angle when block has 1 node */
163 double lastAngle; /* Largest child angle when block has 1 node */
164 block_t *cp; /* Children of block */
165 node_t *neighbor; /* Node connected to parent block, if any */
166} posstate;
167
168typedef struct {
170 double theta; /* angle of node */
171 double minRadius; /* minimum radius for child circle */
172 double maxRadius; /* maximum radius of child blocks */
173 double diameter; /* length of arc needed for child blocks */
174 double scale; /* scale factor to increase minRadius to parents' children don't overlap */
175 int childCount; /* no. of child blocks attached at n */
176} posinfo_t;
177
179static double
180getInfo (posinfo_t* pi, posstate * stp, double min_dist)
181{
182 block_t *child;
183 double maxRadius = 0; /* Max. radius of children */
184 double diameter = 0; /* sum of child diameters */
185 int childCount = 0;
186
187 for (child = stp->cp; child; child = child->next) {
188 if (BLK_PARENT(child) == pi->n) {
189 childCount++;
190 maxRadius = fmax(maxRadius, child->radius);
191 diameter += 2 * child->radius + min_dist;
192 }
193 }
194
195 pi->diameter = diameter;
196 pi->childCount = childCount;
197 pi->minRadius = stp->radius + min_dist + maxRadius;
198 pi->maxRadius = maxRadius;
199 return maxRadius;
200}
201
202static void
204{
205 double t = p0->diameter * p1->minRadius + p1->diameter * p0->minRadius;
206
207 t /= 2*delta*p0->minRadius*p1->minRadius;
208
209 t = fmax(t, 1);
210
211 p0->scale = fmax(p0->scale, t);
212 p1->scale = fmax(p1->scale, t);
213}
214
215static void positionChildren(posinfo_t *info, posstate *stp, size_t length,
216 double min_dist) {
217 block_t *child;
218 double childAngle, childRadius, incidentAngle;
219 double mindistAngle, rotateAngle, midAngle = 0.0;
220 int midChild, cnt = 0;
221 double snRadius = stp->subtreeR; /* max subtree radius */
222 double firstAngle = stp->firstAngle;
223 double lastAngle = stp->lastAngle;
224 double d, deltaX, deltaY;
225
226 childRadius = info->scale * info->minRadius;
227 if (length == 1) {
228 childAngle = 0;
229 d = info->diameter / (2 * M_PI);
230 childRadius = fmax(childRadius, d);
231 d = 2 * M_PI * childRadius - info->diameter;
232 if (d > 0)
233 min_dist += d / info->childCount;
234 }
235 else
236 childAngle = info->theta - info->diameter / (2 * childRadius);
237
238 snRadius = fmax(snRadius, childRadius + info->maxRadius);
239
240 mindistAngle = min_dist / childRadius;
241
242 midChild = (info->childCount + 1) / 2;
243 for (child = stp->cp; child; child = child->next) {
244 if (BLK_PARENT(child) != info->n)
245 continue;
246 if (LIST_IS_EMPTY(&child->circle_list))
247 continue;
248
249 incidentAngle = child->radius / childRadius;
250 if (length == 1) {
251 if (childAngle != 0) {
252 if (info->childCount == 2)
253 childAngle = M_PI;
254 else
255 childAngle += incidentAngle;
256 }
257
258 if (firstAngle < 0)
259 firstAngle = childAngle;
260
261 lastAngle = childAngle;
262 } else {
263 if (info->childCount == 1) {
264 childAngle = info->theta;
265 } else {
266 childAngle += incidentAngle + mindistAngle / 2;
267 }
268 }
269
270 deltaX = childRadius * cos(childAngle);
271 deltaY = childRadius * sin(childAngle);
272
273 /* first apply the delta to the immediate child and see if we need
274 * to rotate it for better edge link
275 * should return the theta value if there was a rotation else zero
276 */
277
278 rotateAngle = getRotation(child, deltaX, deltaY, childAngle);
279 applyDelta(child, deltaX, deltaY, rotateAngle);
280
281 if (length == 1) {
282 childAngle += incidentAngle + mindistAngle;
283 } else {
284 childAngle += incidentAngle + mindistAngle / 2;
285 }
286 cnt++;
287 if (cnt == midChild)
288 midAngle = childAngle;
289 }
290
291 if (length > 1 && info->n == stp->neighbor) {
292 PSI(info->n) = midAngle;
293 }
294
295 stp->subtreeR = snRadius;
296 stp->firstAngle = firstAngle;
297 stp->lastAngle = lastAngle;
298}
299
300/* Assume childCount > 0
301 * For each node in the block with children, getInfo is called, with the
302 * information stored in the parents array.
303 * This information is used by setInfo to compute the amount of space allocated
304 * to each parent and the radius at which to place its children.
305 * Finally, positionChildren is called to do the actual positioning.
306 * If length is 1, keeps track of minimum and maximum child angle.
307 */
308static double position(size_t childCount, size_t length, nodelist_t *nodepath,
309 block_t * sn, double min_dist)
310{
311 posstate state;
312 int i, counter = 0;
313 double maxRadius = 0.0;
314 double angle;
315 double theta = 0.0;
316 posinfo_t* parents = gv_calloc(childCount, sizeof(posinfo_t));
317 int num_parents = 0;
318 posinfo_t* next;
319 posinfo_t* curr;
320 double delta;
321
322 state.cp = sn->children.first;
323 state.subtreeR = sn->radius;
324 state.radius = sn->radius;
325 state.neighbor = CHILD(sn);
326 state.nodeAngle = 2 * M_PI / (double)length;
327 state.firstAngle = -1;
328 state.lastAngle = -1;
329
330 for (size_t item = 0; item < LIST_SIZE(nodepath); ++item) {
331 Agnode_t *n = LIST_GET(nodepath, item);
332
333 theta = counter * state.nodeAngle;
334 counter++;
335
336 if (ISPARENT(n)) {
337 parents[num_parents].n = n;
338 parents[num_parents].theta = theta;
339 maxRadius = getInfo (parents+num_parents, &state, min_dist);
340 num_parents++;
341 }
342 }
343
344 if (num_parents == 1)
345 parents->scale = 1.0;
346 else if (num_parents == 2) {
347 curr = parents;
348 next = parents+1;
349 delta = next->theta - curr->theta;
350 if (delta > M_PI)
351 delta = 2*M_PI - delta;
352 setInfo (curr, next, delta);
353 }
354 else {
355 curr = parents;
356 for (i = 0; i < num_parents; i++) {
357 if (i+1 == num_parents) {
358 next = parents;
359 delta = next->theta - curr->theta + 2*M_PI;
360 }
361 else {
362 next = curr+1;
363 delta = next->theta - curr->theta;
364 }
365 setInfo (curr, next, delta);
366 curr++;
367 }
368 }
369
370 for (i = 0; i < num_parents; i++) {
371 positionChildren(parents + i, &state, length, min_dist);
372 }
373
374 free (parents);
375
376 /* If block has only 1 child, to save space, we coalesce it with the
377 * child. Instead of having final radius sn->radius + max child radius,
378 * we have half that. However, the origin of the block is no longer in
379 * the center of the block, so we cannot do a simple rotation to get
380 * the neighbor node next to the parent block in getRotate.
381 */
382 if (childCount == 1) {
383 applyDelta(sn, -(maxRadius + min_dist / 2), 0, 0);
384 sn->radius += min_dist / 2 + maxRadius;
385 SET_COALESCED(sn);
386 } else
387 sn->radius = state.subtreeR;
388
389 angle = (state.firstAngle + state.lastAngle) / 2.0 - M_PI;
390 return angle;
391}
392
396static void doBlock(Agraph_t *g, block_t *sn, double min_dist,
397 circ_state *state) {
398 block_t *child;
399 double centerAngle = M_PI;
400
401 /* layout child subtrees */
402 size_t childCount = 0;
403 for (child = sn->children.first; child; child = child->next) {
404 doBlock(g, child, min_dist, state);
405 childCount++;
406 }
407
408 /* layout this block */
409 nodelist_t longest_path = layout_block(g, sn, min_dist, state);
410 sn->circle_list = longest_path;
411 size_t length = LIST_SIZE(&longest_path); // path contains everything in block
412
413 /* attach children */
414 if (childCount > 0)
415 centerAngle = position(childCount, length, &longest_path, sn, min_dist);
416
417 if (length == 1 && BLK_PARENT(sn)) {
418 sn->parent_pos = centerAngle;
419 if (sn->parent_pos < 0)
420 sn->parent_pos += 2 * M_PI;
421 }
422}
423
424void circPos(Agraph_t * g, block_t * sn, circ_state * state)
425{
426 doBlock(g, sn, state->min_dist, state);
427}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define M_PI
Definition arith.h:41
nodelist_t layout_block(Agraph_t *g, block_t *sn, double min_dist, circ_state *state)
Definition blockpath.c:584
#define BLK_PARENT(b)
Definition block.h:51
#define CHILD(b)
Definition block.h:50
#define COALESCED(b)
Definition block.h:55
#define SET_COALESCED(b)
Definition block.h:56
static void applyDelta(block_t *sn, double x, double y, double rotate)
Definition circpos.c:119
static void doBlock(Agraph_t *g, block_t *sn, double min_dist, circ_state *state)
Definition circpos.c:396
static void setInfo(posinfo_t *p0, posinfo_t *p1, double delta)
Definition circpos.c:203
static void positionChildren(posinfo_t *info, posstate *stp, size_t length, double min_dist)
Definition circpos.c:215
static double getRotation(block_t *sn, double x, double y, double theta)
Definition circpos.c:50
static double getInfo(posinfo_t *pi, posstate *stp, double min_dist)
get size info for blocks attached to the given node.
Definition circpos.c:180
void circPos(Agraph_t *g, block_t *sn, circ_state *state)
Definition circpos.c:424
#define ISPARENT(n)
Definition circular.h:106
#define PSI(n)
Definition circular.h:96
static Extype_t length(Exid_t *rhs, Exdisc_t *disc)
Definition compile.c:1606
#define Y(i)
Definition gdefs.h:3
#define X(prefix, name, str, type, subtype,...)
Definition gdefs.h:14
#define LEN2(a, b)
Definition geom.h:53
void free(void *)
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
#define ND_pos(n)
Definition types.h:520
type-generic dynamically expanding list
#define LIST_SIZE(list)
Definition list.h:80
#define LIST_IS_EMPTY(list)
Definition list.h:90
#define LIST_GET(list, index)
Definition list.h:165
#define neighbor(t, i, edim, elist)
Definition make_map.h:41
#define delta
Definition maze.c:136
static void rotate(int n, int dim, double *x, double angle)
graph or subgraph
Definition cgraph.h:424
Definition block.h:26
double radius
Definition block.h:30
nodelist_t circle_list
Definition block.h:32
blocklist_t children
Definition block.h:33
Agraph_t * sub_graph
Definition block.h:29
double parent_pos
Definition block.h:34
block_t * next
Definition block.h:28
double rad0
Definition block.h:31
block_t * first
Definition block.h:22
double min_dist
Definition circular.h:24
Definition utils.c:751
double maxRadius
Definition circpos.c:172
double theta
Definition circpos.c:170
Agnode_t * n
Definition circpos.c:169
int childCount
Definition circpos.c:175
double scale
Definition circpos.c:174
double diameter
Definition circpos.c:173
double minRadius
Definition circpos.c:171
node_t * neighbor
Definition circpos.c:165
double radius
Definition circpos.c:159
double lastAngle
Definition circpos.c:163
double nodeAngle
Definition circpos.c:161
double subtreeR
Definition circpos.c:160
double firstAngle
Definition circpos.c:162
block_t * cp
Definition circpos.c:164