Graphviz 13.1.3~dev.20250829.0113
Loading...
Searching...
No Matches
circle.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#include <assert.h>
12#include <twopigen/circle.h>
13#include <inttypes.h>
14#include <limits.h>
15#include <math.h>
16#include <stdbool.h>
17#include <stdint.h>
18#include <stdlib.h>
19#include <string.h>
20#include <util/alloc.h>
21#include <util/gv_ctype.h>
22#include <util/gv_math.h>
23#include <util/list.h>
24#include <util/streq.h>
25#define DEF_RANKSEP 1.00
26#define UNSET 10.00
27
28/* dfs to set distance from a particular leaf.
29 * Note that termination is implicit in the test
30 * for reduced number of steps. Proof?
31 */
33{
34 Agnode_t *next;
35
36 uint64_t nsteps = SLEAF(n) + 1;
37
38 for (Agedge_t *ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
39 if ((next = agtail(ep)) == n)
40 next = aghead(ep);
41
42 if (prev == next)
43 continue;
44
45 if (nsteps < SLEAF(next)) { /* handles loops and multiedges */
46 SLEAF(next) = nsteps;
47 setNStepsToLeaf(g, next, n);
48 }
49 }
50}
51
52/* isLeaf:
53 * Return true if n is a leaf node.
54 */
55static bool isLeaf(Agraph_t * g, Agnode_t * n)
56{
57 Agnode_t *neighp = 0;
58 Agnode_t *np;
59
60 for (Agedge_t *ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
61 if ((np = agtail(ep)) == n)
62 np = aghead(ep);
63 if (n == np)
64 continue; /* loop */
65 if (neighp) {
66 if (neighp != np)
67 return false; /* two different neighbors */
68 } else
69 neighp = np;
70 }
71 return true;
72}
73
74static void initLayout(Agraph_t * g)
75{
76 int nnodes = agnnodes(g);
77 assert(nnodes >= 0);
78 uint64_t INF = (uint64_t)nnodes * (uint64_t)nnodes;
79
80 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
81 SCENTER(n) = INF;
82 THETA(n) = UNSET; /* marks theta as unset, since 0 <= theta <= 2PI */
83 if (isLeaf(g, n))
84 SLEAF(n) = 0;
85 else
86 SLEAF(n) = INF;
87 }
88}
89
90/*
91 * Working recursively in from each leaf node (ie, each node
92 * with nStepsToLeaf == 0; see initLayout), set the
93 * minimum value of nStepsToLeaf for each node. Using
94 * that information, assign some node to be the centerNode.
95*/
97{
99 uint64_t maxNStepsToLeaf = 0;
100
101 /* dfs from each leaf node */
102 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
103 if (SLEAF(n) == 0)
104 setNStepsToLeaf(g, n, 0);
105 }
106
107 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
108 if (center == NULL || SLEAF(n) > maxNStepsToLeaf) {
109 maxNStepsToLeaf = SLEAF(n);
110 center = n;
111 }
112 }
113 return center;
114}
115
116/* bfs to create tree structure */
118{
119 Agnode_t *next;
120 Agsym_t* wt = agfindedgeattr(g,"weight");
121 LIST(Agnode_t *) q = {0};
122
123 LIST_PUSH_BACK(&q, n);
124 while (!LIST_IS_EMPTY(&q)) {
125 n = LIST_POP_FRONT(&q);
126 uint64_t nsteps = SCENTER(n) + 1;
127 for (Agedge_t *ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
128 if (wt && streq(agxget(ep,wt), "0")) continue;
129 if ((next = agtail(ep)) == n)
130 next = aghead(ep);
131 if (nsteps < SCENTER(next)) {
132 SCENTER(next) = nsteps;
133 SPARENT(next) = n;
134 NCHILD(n)++;
135 LIST_PUSH_BACK(&q, next);
136 }
137 }
138 }
139 LIST_FREE(&q);
140}
141
142/*
143 * Work out from the center and determine the value of
144 * nStepsToCenter and parent node for each node.
145 * Return UINT64_MAX if some node was not reached.
146 */
147static uint64_t setParentNodes(Agraph_t * sg, Agnode_t * center)
148{
149 uint64_t maxn = 0;
150 uint64_t unset = SCENTER(center);
151
152 SCENTER(center) = 0;
153 SPARENT(center) = 0;
155
156 /* find the maximum number of steps from the center */
157 for (Agnode_t *n = agfstnode(sg); n; n = agnxtnode(sg, n)) {
158 if (SCENTER(n) == unset) {
159 return UINT64_MAX;
160 }
161 else if (SCENTER(n) > maxn) {
162 maxn = SCENTER(n);
163 }
164 }
165 return maxn;
166}
167
168/* Sets each node's subtreeSize, which counts the number of
169 * leaves in subtree rooted at the node.
170 * At present, this is done bottom-up.
171 */
172static void setSubtreeSize(Agraph_t * g)
173{
174 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
175 if (NCHILD(n) > 0)
176 continue;
177 STSIZE(n)++;
179 STSIZE(parent)++;
180 }
181 }
182}
183
185{
186 Agnode_t *next;
187
188 double ratio = SPAN(n) / STSIZE(n);
189 for (Agedge_t *ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
190 if ((next = agtail(ep)) == n)
191 next = aghead(ep);
192 if (SPARENT(next) != n)
193 continue; /* handles loops */
194
195 if (SPAN(next) != 0.0)
196 continue; /* multiedges */
197 SPAN(next) = ratio * STSIZE(next);
198
199 if (NCHILD(next) > 0) {
200 setChildSubtreeSpans(g, next);
201 }
202 }
203}
204
206{
207 SPAN(center) = 2 * M_PI;
209}
210
212static bool is_set(double a) { return !is_exactly_equal(a, UNSET); }
213
214 /* Set the node positions for the 2nd and later rings. */
215static void setChildPositions(Agraph_t * sg, Agnode_t * n)
216{
217 Agnode_t *next;
218 double theta; /* theta is the lower boundary radius of the fan */
219
220 if (SPARENT(n) == 0) /* center */
221 theta = 0;
222 else
223 theta = THETA(n) - SPAN(n) / 2;
224
225 for (Agedge_t *ep = agfstedge(sg, n); ep; ep = agnxtedge(sg, ep, n)) {
226 if ((next = agtail(ep)) == n)
227 next = aghead(ep);
228 if (SPARENT(next) != n)
229 continue; /* handles loops */
230 if (is_set(THETA(next)))
231 continue; /* handles multiedges */
232
233 THETA(next) = theta + SPAN(next) / 2.0;
234 theta += SPAN(next);
235
236 if (NCHILD(next) > 0)
237 setChildPositions(sg, next);
238 }
239}
240
242{
243 THETA(center) = 0;
245}
246
247/* getRankseps:
248 * Return array of doubles of size maxrank+1 containing the radius of each
249 * rank. Position 0 always contains 0. Use the colon-separated list of
250 * doubles provided by ranksep to get the deltas for each additional rank.
251 * If not enough values are provided, the last value is repeated.
252 * If the ranksep attribute is not provided, use DEF_RANKSEP for all values.
253 */
254static double*
255getRankseps (Agraph_t* g, uint64_t maxrank)
256{
257 char *p;
258 char *endp;
259 char c;
260 uint64_t rk = 1;
261 double* ranks = gv_calloc(maxrank + 1, sizeof(double));
262 double xf = 0.0, delx = 0.0, d;
263
264 if ((p = late_string(g, agfindgraphattr(g->root, "ranksep"), NULL))) {
265 while (rk <= maxrank && (d = strtod (p, &endp)) > 0) {
266 delx = fmax(d, MIN_RANKSEP);
267 xf += delx;
268 ranks[rk++] = xf;
269 p = endp;
270 while ((c = *p) && (gv_isspace(c) || c == ':'))
271 p++;
272 }
273 }
274 else {
275 delx = DEF_RANKSEP;
276 }
277
278 for (uint64_t i = rk; i <= maxrank; i++) {
279 xf += delx;
280 ranks[i] = xf;
281 }
282
283 return ranks;
284}
285
286static void setAbsolutePos(Agraph_t * g, uint64_t maxrank)
287{
288 double* ranksep = getRankseps (g, maxrank);
289 if (Verbose) {
290 fputs ("Rank separation = ", stderr);
291 for (uint64_t i = 0; i <= maxrank; i++)
292 fprintf (stderr, "%.03lf ", ranksep[i]);
293 fputs ("\n", stderr);
294 }
295
296 /* Convert circular to cartesian coordinates */
297 for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) {
298 double hyp = ranksep[SCENTER(n)];
299 ND_pos(n)[0] = hyp * cos(THETA(n));
300 ND_pos(n)[1] = hyp * sin(THETA(n));
301 }
302 free (ranksep);
303}
304
305/* circleLayout:
306 * We assume sg is is connected and non-empty.
307 * Also, if center != 0, we are guaranteed that center is
308 * in the graph.
309 */
311{
312 if (agnnodes(sg) == 1) {
313 Agnode_t *n = agfstnode(sg);
314 ND_pos(n)[0] = 0;
315 ND_pos(n)[1] = 0;
316 return center;
317 }
318
319 initLayout(sg);
320
321 if (!center)
323
324 uint64_t maxNStepsToCenter = setParentNodes(sg,center);
325 if (Verbose)
326 fprintf(stderr, "root = %s max steps to root = %" PRIu64 "\n",
327 agnameof(center), maxNStepsToCenter);
328 if (maxNStepsToCenter == UINT64_MAX) {
329 agerrorf("twopi: use of weight=0 creates disconnected component.\n");
330 return center;
331 }
332
333 setSubtreeSize(sg);
334
336
337 setPositions(sg, center);
338
339 setAbsolutePos(sg, maxNStepsToCenter);
340 return center;
341}
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
static void setNStepsToCenter(Agraph_t *g, Agnode_t *n)
Definition circle.c:117
static double * getRankseps(Agraph_t *g, uint64_t maxrank)
Definition circle.c:255
static void setPositions(Agraph_t *sg, Agnode_t *center)
Definition circle.c:241
static void setSubtreeSize(Agraph_t *g)
Definition circle.c:172
static void setChildPositions(Agraph_t *sg, Agnode_t *n)
Definition circle.c:215
static void setChildSubtreeSpans(Agraph_t *g, Agnode_t *n)
Definition circle.c:184
static bool is_set(double a)
has the given value been assigned?
Definition circle.c:212
static void setNStepsToLeaf(Agraph_t *g, Agnode_t *n, Agnode_t *prev)
Definition circle.c:32
static void setAbsolutePos(Agraph_t *g, uint64_t maxrank)
Definition circle.c:286
static void initLayout(Agraph_t *g)
Definition circle.c:74
static Agnode_t * findCenterNode(Agraph_t *g)
Definition circle.c:96
Agnode_t * circleLayout(Agraph_t *sg, Agnode_t *center)
Definition circle.c:310
#define UNSET
Definition circle.c:26
static void setSubtreeSpans(Agraph_t *sg, Agnode_t *center)
Definition circle.c:205
#define DEF_RANKSEP
Definition circle.c:25
static uint64_t setParentNodes(Agraph_t *sg, Agnode_t *center)
Definition circle.c:147
static bool isLeaf(Agraph_t *g, Agnode_t *n)
Definition circle.c:55
#define SLEAF(n)
Definition circle.h:30
#define THETA(n)
Definition circle.h:36
#define NCHILD(n)
Definition circle.h:32
#define SCENTER(n)
Definition circle.h:33
#define SPAN(n)
Definition circle.h:35
#define STSIZE(n)
Definition circle.h:31
#define parent(i)
Definition closest.c:81
char * late_string(void *obj, attrsym_t *attr, char *defaultValue)
Definition utils.c:81
#define MIN_RANKSEP
Definition const.h:88
static bool Verbose
Definition gml2gv.c:24
void free(void *)
node NULL
Definition grammar.y:181
int agnnodes(Agraph_t *g)
Definition graph.c:155
char * agxget(void *obj, Agsym_t *sym)
Definition attr.c:458
#define agfindedgeattr(g, a)
Definition types.h:617
#define agtail(e)
Definition cgraph.h:988
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition edge.c:96
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:87
void agerrorf(const char *fmt,...)
Definition agerror.c:165
#define agfindgraphattr(g, a)
Definition types.h:613
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
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
replacements for ctype.h functions
static bool gv_isspace(int c)
Definition gv_ctype.h:55
Arithmetic helper functions.
static bool is_exactly_equal(double a, double b)
are two values precisely the same?
Definition gv_math.h:45
$2 u p prev
Definition htmlparse.y:291
type-generic dynamically expanding list
#define LIST(type)
Definition list.h:55
#define LIST_POP_FRONT(list)
Definition list.h:403
#define LIST_FREE(list)
Definition list.h:379
#define LIST_IS_EMPTY(list)
Definition list.h:90
#define LIST_PUSH_BACK(list, item)
Definition list.h:393
#define SPARENT(n)
Definition patchwork.h:25
#define INF
Definition sccmap.c:41
static bool streq(const char *a, const char *b)
are a and b equal?
Definition streq.h:11
graph or subgraph
Definition cgraph.h:424
Agraph_t * root
subgraphs - ancestors
Definition cgraph.h:433
string attribute descriptor symbol in Agattr_s.dict
Definition cgraph.h:651
static point center(point vertex[], size_t n)