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 */
25static 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 */
49static 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
69static 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*/
93static 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 */
123static 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
148typedef struct item_s {
149 void* p;
150 struct item_s* s;
151} item_t;
152typedef struct {
153 item_t* head;
154 item_t* tail;
155} queue;
156static 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}
167static 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 */
184static 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 */
215static 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 */
241static 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
258static 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
281static 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. */
288static 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
315static 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 */
328static double*
329getRankseps (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
360static 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 */
385static 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 */
410Agnode_t* circleLayout(Agraph_t * sg, Agnode_t * center)
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}
444