Graphviz  2.41.20170921.2350
circle.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 "circle.h"
16 #include <ctype.h>
17 #include <stdlib.h>
18 #define DEF_RANKSEP 1.00
19 #define UNSET 10.00
20 
21 /* dfs to set distance from a particular leaf.
22  * Note that termination is implicit in the test
23  * for reduced number of steps. Proof?
24  */
25 static void setNStepsToLeaf(Agraph_t * g, Agnode_t * n, Agnode_t * prev)
26 {
27  Agnode_t *next;
28  Agedge_t *ep;
29 
30  int nsteps = SLEAF(n) + 1;
31 
32  for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
33  if ((next = agtail(ep)) == n)
34  next = aghead(ep);
35 
36  if (prev == next)
37  continue;
38 
39  if (nsteps < SLEAF(next)) { /* handles loops and multiedges */
40  SLEAF(next) = nsteps;
41  setNStepsToLeaf(g, next, n);
42  }
43  }
44 }
45 
46 /* isLeaf:
47  * Return true if n is a leaf node.
48  */
49 static int isLeaf(Agraph_t * g, Agnode_t * n)
50 {
51  Agedge_t *ep;
52  Agnode_t *neighp = 0;
53  Agnode_t *np;
54 
55  for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
56  if ((np = agtail(ep)) == n)
57  np = aghead(ep);
58  if (n == np)
59  continue; /* loop */
60  if (neighp) {
61  if (neighp != np)
62  return 0; /* two different neighbors */
63  } else
64  neighp = np;
65  }
66  return 1;
67 }
68 
69 static void initLayout(Agraph_t * g)
70 {
71  Agnode_t *n;
72  int nnodes = agnnodes(g);
73  int INF = nnodes * nnodes;
74 
75  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
76  /* STSIZE(n) = 0; */
77  /* NCHILD(n) = 0; */
78  SCENTER(n) = INF;
79  THETA(n) = UNSET; /* marks theta as unset, since 0 <= theta <= 2PI */
80  if (isLeaf(g, n))
81  SLEAF(n) = 0;
82  else
83  SLEAF(n) = INF;
84  }
85 }
86 
87 /*
88  * Working recursively in from each leaf node (ie, each node
89  * with nStepsToLeaf == 0; see initLayout), set the
90  * minimum value of nStepsToLeaf for each node. Using
91  * that information, assign some node to be the centerNode.
92 */
93 static Agnode_t *findCenterNode(Agraph_t * g)
94 {
95  Agnode_t *n;
96  Agnode_t *center = NULL;
97  int maxNStepsToLeaf = 0;
98 
99  /* With just 1 or 2 nodes, return anything. */
100  if (agnnodes(g) <= 2)
101  return (agfstnode(g));
102 
103  /* dfs from each leaf node */
104  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
105  if (SLEAF(n) == 0)
106  setNStepsToLeaf(g, n, 0);
107  }
108 
109  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
110  if (SLEAF(n) > maxNStepsToLeaf) {
111  maxNStepsToLeaf = SLEAF(n);
112  center = n;
113  }
114  }
115  return center;
116 }
117 
118 #if 0
119 /* dfs to set distance from center
120  * Note that termination is implicit in the test
121  * for reduced number of steps. Proof?
122  */
123 static void setNStepsToCenter(Agraph_t * g, Agnode_t * n, Agnode_t * prev)
124 {
125  Agnode_t *next;
126  Agedge_t *ep;
127  int nsteps = SCENTER(n) + 1;
128 
129  for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
130  if ((next = agtail(ep)) == n)
131  next = aghead(ep);
132 
133  if (prev == next)
134  continue;
135 
136  if (nsteps < SCENTER(next)) { /* handles loops and multiedges */
137  SCENTER(next) = nsteps;
138  if (SPARENT(next))
139  NCHILD(SPARENT(next))--;
140  SPARENT(next) = n;
141  NCHILD(n)++;
142  setNStepsToCenter(g, next, n);
143  }
144  }
145 }
146 #endif
147 
148 typedef struct item_s {
149  void* p;
150  struct item_s* s;
151 } item_t;
152 typedef struct {
155 } queue;
156 static void push(queue* q, void* p)
157 {
158  item_t* ip = NEW(item_t);
159  ip->p = p;
160  if (q->tail) { /* non-empty q */
161  q->tail->s = ip;
162  q->tail = ip;
163  }
164  else
165  q->tail = q->head = ip;
166 }
167 static void* pull(queue* q)
168 {
169  item_t* ip;
170  void* p;
171  if ((ip = q->head)) {
172  p = ip->p;
173  q->head = ip->s;
174  free (ip);
175  if (!q->head)
176  q->tail = NULL;
177  return p;
178  }
179  else
180  return NULL;
181 }
182 
183 /* bfs to create tree structure */
184 static void setNStepsToCenter(Agraph_t * g, Agnode_t * n)
185 {
186  Agnode_t *next;
187  Agedge_t *ep;
188  Agsym_t* wt = agfindedgeattr(g,"weight");
189  queue qd;
190  queue* q = &qd;
191 
192  qd.head = qd.tail = NULL;
193  push(q,n);
194  while ((n = (Agnode_t*)pull(q))) {
195  int nsteps = SCENTER(n) + 1;
196  for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
197  if (wt && streq(ag_xget(ep,wt),"0")) continue;
198  if ((next = agtail(ep)) == n)
199  next = aghead(ep);
200  if (nsteps < SCENTER(next)) {
201  SCENTER(next) = nsteps;
202  SPARENT(next) = n;
203  NCHILD(n)++;
204  push (q, next);
205  }
206  }
207  }
208 }
209 
210 /*
211  * Work out from the center and determine the value of
212  * nStepsToCenter and parent node for each node.
213  * Return -1 if some node was not reached.
214  */
215 static int setParentNodes(Agraph_t * sg, Agnode_t * center)
216 {
217  Agnode_t *n;
218  int maxn = 0;
219  int unset = SCENTER(center);
220 
221  SCENTER(center) = 0;
222  SPARENT(center) = 0;
223  setNStepsToCenter(sg, center);
224 
225  /* find the maximum number of steps from the center */
226  for (n = agfstnode(sg); n; n = agnxtnode(sg, n)) {
227  if (SCENTER(n) == unset) {
228  return -1;
229  }
230  else if (SCENTER(n) > maxn) {
231  maxn = SCENTER(n);
232  }
233  }
234  return maxn;
235 }
236 
237 /* Sets each node's subtreeSize, which counts the number of
238  * leaves in subtree rooted at the node.
239  * At present, this is done bottom-up.
240  */
241 static void setSubtreeSize(Agraph_t * g)
242 {
243  Agnode_t *n;
244  Agnode_t *parent;
245 
246  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
247  if (NCHILD(n) > 0)
248  continue;
249  STSIZE(n)++;
250  parent = SPARENT(n);
251  while (parent) {
252  STSIZE(parent)++;
253  parent = SPARENT(parent);
254  }
255  }
256 }
257 
258 static void setChildSubtreeSpans(Agraph_t * g, Agnode_t * n)
259 {
260  Agedge_t *ep;
261  Agnode_t *next;
262  double ratio;
263 
264  ratio = SPAN(n) / STSIZE(n);
265  for (ep = agfstedge(g, n); ep; ep = agnxtedge(g, ep, n)) {
266  if ((next = agtail(ep)) == n)
267  next = aghead(ep);
268  if (SPARENT(next) != n)
269  continue; /* handles loops */
270 
271  if (SPAN(next) != 0.0)
272  continue; /* multiedges */
273  (SPAN(next) = ratio * STSIZE(next));
274 
275  if (NCHILD(next) > 0) {
276  setChildSubtreeSpans(g, next);
277  }
278  }
279 }
280 
281 static void setSubtreeSpans(Agraph_t * sg, Agnode_t * center)
282 {
283  SPAN(center) = 2 * M_PI;
284  setChildSubtreeSpans(sg, center);
285 }
286 
287  /* Set the node positions for the 2nd and later rings. */
288 static void setChildPositions(Agraph_t * sg, Agnode_t * n)
289 {
290  Agnode_t *next;
291  Agedge_t *ep;
292  double theta; /* theta is the lower boundary radius of the fan */
293 
294  if (SPARENT(n) == 0) /* center */
295  theta = 0;
296  else
297  theta = THETA(n) - SPAN(n) / 2;
298 
299  for (ep = agfstedge(sg, n); ep; ep = agnxtedge(sg, ep, n)) {
300  if ((next = agtail(ep)) == n)
301  next = aghead(ep);
302  if (SPARENT(next) != n)
303  continue; /* handles loops */
304  if (THETA(next) != UNSET)
305  continue; /* handles multiedges */
306 
307  THETA(next) = theta + SPAN(next) / 2.0;
308  theta += SPAN(next);
309 
310  if (NCHILD(next) > 0)
311  setChildPositions(sg, next);
312  }
313 }
314 
315 static void setPositions(Agraph_t * sg, Agnode_t * center)
316 {
317  THETA(center) = 0;
318  setChildPositions(sg, center);
319 }
320 
321 /* getRankseps:
322  * Return array of doubles of size maxrank+1 containing the radius of each
323  * rank. Position 0 always contains 0. Use the colon-separated list of
324  * doubles provided by ranksep to get the deltas for each additional rank.
325  * If not enough values are provided, the last value is repeated.
326  * If the ranksep attribute is not provided, use DEF_RANKSEP for all values.
327  */
328 static double*
329 getRankseps (Agraph_t* g, int maxrank)
330 {
331  char *p;
332  char *endp;
333  char c;
334  int i, rk = 1;
335  double* ranks = N_NEW(maxrank+1, double);
336  double xf = 0.0, delx = 0.0, d;
337 
338  if ((p = late_string(g, agfindgraphattr(g->root, "ranksep"), NULL))) {
339  while ((rk <= maxrank) && ((d = strtod (p, &endp)) > 0)) {
340  delx = MAX(d, MIN_RANKSEP);
341  xf += delx;
342  ranks[rk++] = xf;
343  p = endp;
344  while ((c = *p) && (isspace(c) || (c == ':')))
345  p++;
346  }
347  }
348  else {
349  delx = DEF_RANKSEP;
350  }
351 
352  for (i = rk; i <= maxrank; i++) {
353  xf += delx;
354  ranks[i] = xf;
355  }
356 
357  return ranks;
358 }
359 
360 static void setAbsolutePos(Agraph_t * g, int maxrank)
361 {
362  Agnode_t *n;
363  double hyp;
364  double* ranksep;
365  int i;
366 
367  ranksep = getRankseps (g, maxrank);
368  if (Verbose) {
369  fputs ("Rank separation = ", stderr);
370  for (i = 0; i <= maxrank; i++)
371  fprintf (stderr, "%.03lf ", ranksep[i]);
372  fputs ("\n", stderr);
373  }
374 
375  /* Convert circular to cartesian coordinates */
376  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
377  hyp = ranksep[SCENTER(n)];
378  ND_pos(n)[0] = hyp * cos(THETA(n));
379  ND_pos(n)[1] = hyp * sin(THETA(n));
380  }
381  free (ranksep);
382 }
383 
384 #if 0 /* not used */
385 static void dumpGraph(Agraph_t * g)
386 {
387  Agnode_t *n;
388  char *p;
389 
390  fprintf(stderr,
391  " : leaf stsz nkids cntr parent span theta\n");
392  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
393  if (SPARENT(n))
394  p = SPARENT(n)->name;
395  else
396  p = "<C>";
397  fprintf(stderr, "%4s :%6d%6d%6d%6d%7s%7.3f%7.3f%8.3f%8.3f\n",
398  n->name, SLEAF(n), STSIZE(n), NCHILD(n),
399  SCENTER(n), p, SPAN(n), THETA(n), ND_pos(n)[0],
400  ND_pos(n)[1]);
401  }
402 }
403 #endif
404 
405 /* circleLayout:
406  * We assume sg is is connected and non-empty.
407  * Also, if center != 0, we are guaranteed that center is
408  * in the graph.
409  */
411 {
412  int maxNStepsToCenter;
413 
414  if (agnnodes(sg) == 1) {
415  Agnode_t *n = agfstnode(sg);
416  ND_pos(n)[0] = 0;
417  ND_pos(n)[1] = 0;
418  return center;
419  }
420 
421  initLayout(sg);
422 
423  if (!center)
424  center = findCenterNode(sg);
425 
426  maxNStepsToCenter = setParentNodes(sg,center);
427  if (Verbose)
428  fprintf(stderr, "root = %s max steps to root = %d\n", agnameof(center), maxNStepsToCenter);
429  if (maxNStepsToCenter < 0) {
430  agerr(AGERR, "twopi: use of weight=0 creates disconnected component.\n");
431  return center;
432  }
433 
434  setSubtreeSize(sg);
435 
436  setSubtreeSpans(sg, center);
437 
438  setPositions(sg, center);
439 
440  setAbsolutePos(sg, maxNStepsToCenter);
441  /* dumpGraph (sg); */
442  return center;
443 }
#define MAX(a, b)
Definition: agerror.c:17
Definition: cgraph.h:388
#define NCHILD(n)
Definition: circle.h:36
#define DEF_RANKSEP
Definition: circle.c:18
#define N_NEW(n, t)
Definition: memory.h:36
int initLayout(vtx_data *graph, int n, int dim, double **coords, node_t **nodes)
Definition: stress.c:159
item_t * head
Definition: circle.c:153
#define SPAN(n)
Definition: circle.h:39
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
struct item_s * s
Definition: circle.c:150
#define SPARENT(n)
Definition: patchwork.h:29
#define ND_pos(n)
Definition: types.h:526
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
#define SCENTER(n)
Definition: circle.h:37
#define UNSET
Definition: circle.c:19
#define parent(i)
Definition: closest.c:88
Definition: circle.c:152
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
item_t * tail
Definition: circle.c:154
#define ag_xget(x, a)
Definition: types.h:608
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
Agnode_t * circleLayout(Agraph_t *sg, Agnode_t *center)
Definition: circle.c:410
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define MIN_RANKSEP
Definition: const.h:89
struct item_s item_t
#define THETA(n)
Definition: circle.h:40
#define agfindedgeattr(g, a)
Definition: types.h:614
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define push(s, x)
Definition: closest.c:63
#define NULL
Definition: logic.h:39
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
#define agfindgraphattr(g, a)
Definition: types.h:612
#define streq(s, t)
Definition: cghdr.h:52
EXTERN unsigned char Verbose
Definition: globals.h:64
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
#define STSIZE(n)
Definition: circle.h:35
void * p
Definition: circle.c:149
char * late_string(void *obj, attrsym_t *attr, char *def)
Definition: utils.c:122
#define SLEAF(n)
Definition: circle.h:34
#define M_PI
Definition: arith.h:77
Agraph_t * root
Definition: cgraph.h:247
Definition: grammar.c:88
#define NEW(t)
Definition: memory.h:35