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/* xlayout.c:
16 * Written by Emden R. Gansner
17 *
18 * Layout routine to expand initial layout to accommodate node
19 * sizes.
20 */
21
22#ifdef FIX
23Allow sep to be absolute additive (margin of n points)
24Increase less between tries
25#endif
26
27/* uses PRIVATE interface */
28#define FDP_PRIVATE 1
29
30#include <xlayout.h>
31#include <adjust.h>
32#include <dbg.h>
33#include <ctype.h>
34
35/* Use bbox based force function */
36/* #define MS */
37/* Use alternate force function */
38/* #define ALT */
39/* Add repulsive force even if nodes don't overlap */
40/* #define ORIG */
41#define BOX /* Use bbox to determine overlap, else use circles */
42
43#define DFLT_overlap "9:prism" /* default overlap value */
44
45#define WD2(n) (X_marg.doAdd ? (ND_width(n)/2.0 + X_marg.x): ND_width(n)*X_marg.x/2.0)
46#define HT2(n) (X_marg.doAdd ? (ND_height(n)/2.0 + X_marg.y): ND_height(n)*X_marg.y/2.0)
47
48static xparams xParams = {
49 60, /* numIters */
50 0.0, /* T0 */
51 0.3, /* K */
52 1.5, /* C */
53 0 /* loopcnt */
54};
55static double K2;
56static expand_t X_marg;
57static double X_nonov;
58static double X_ov;
59
60void pr2graphs(Agraph_t *g0, Agraph_t *g1)
61{
62 fprintf(stderr,"%s",agnameof(g0));
63 fprintf(stderr,"(%s)",agnameof(g1));
64}
65
66static double RAD(Agnode_t * n)
67{
68 double w = WD2(n);
69 double h = HT2(n);
70 return sqrt(w * w + h * h);
71}
72
73/* xinit_params:
74 * Initialize local parameters
75 */
76static void xinit_params(graph_t* g, int n, xparams * xpms)
77{
78 xParams.K = xpms->K;
79 xParams.numIters = xpms->numIters;
80 xParams.T0 = xpms->T0;
81 xParams.loopcnt = xpms->loopcnt;
82 if (xpms->C > 0.0)
83 xParams.C = xpms->C;
84 K2 = xParams.K * xParams.K;
85 if (xParams.T0 == 0.0)
86 xParams.T0 = xParams.K * sqrt(n) / 5;
87#ifdef DEBUG
88 if (Verbose) {
89 prIndent();
90 fprintf(stderr, "xLayout ");
91 pr2graphs(g,GORIG(agroot(g)));
92 fprintf(stderr, " : n = %d K = %f T0 = %f loop %d C %f\n",
93 xParams.numIters, xParams.K, xParams.T0, xParams.loopcnt,
94 xParams.C);
95 }
96#endif
97}
98
99#define X_T0 xParams.T0
100#define X_K xParams.K
101#define X_numIters xParams.numIters
102#define X_loopcnt xParams.loopcnt
103#define X_C xParams.C
104
105
106static double cool(int t)
107{
108 return (X_T0 * (X_numIters - t)) / X_numIters;
109}
110
111#define EPSILON 0.01
112
113#ifdef MS
114/* dist:
115 * Distance between two points
116 */
117static double dist(pointf p, pointf q)
118{
119 double dx, dy;
120
121 dx = p.x - q.x;
122 dy = p.y - q.y;
123 return (sqrt(dx * dx + dy * dy));
124}
125
126/* bBox:
127 * Compute bounding box of point
128 */
129static void bBox(node_t * p, pointf * ll, pointf * ur)
130{
131 double w2 = WD2(p);
132 double h2 = HT2(p);
133
134 ur->x = ND_pos(p)[0] + w2;
135 ur->y = ND_pos(p)[1] + h2;
136 ll->x = ND_pos(p)[0] - w2;
137 ll->y = ND_pos(p)[1] - h2;
138}
139
140/* boxDist:
141 * Return the distance between two boxes; 0 if they overlap
142 */
143static double boxDist(node_t * p, node_t * q)
144{
145 pointf p_ll, p_ur;
146 pointf q_ll, q_ur;
147
148 bBox(p, &p_ll, &p_ur);
149 bBox(q, &q_ll, &q_ur);
150
151 if (q_ll.x > p_ur.x) {
152 if (q_ll.y > p_ur.y) {
153 return (dist(p_ur, q_ll));
154 } else if (q_ll.y >= p_ll.y) {
155 return (q_ll.x - p_ur.x);
156 } else {
157 if (q_ur.y >= p_ll.y)
158 return (q_ll.x - p_ur.x);
159 else {
160 p_ur.y = p_ll.y; /* p_ur is now lower right */
161 q_ll.y = q_ur.y; /* q_ll is now upper left */
162 return (dist(p_ur, q_ll));
163 }
164 }
165 } else if (q_ll.x >= p_ll.x) {
166 if (q_ll.y > p_ur.y) {
167 return (q_ll.y - p_ur.x);
168 } else if (q_ll.y >= p_ll.y) {
169 return 0.0;
170 } else {
171 if (q_ur.y >= p_ll.y)
172 return 0.0;
173 else
174 return (p_ll.y - q_ur.y);
175 }
176 } else {
177 if (q_ll.y > p_ur.y) {
178 if (q_ur.x >= p_ll.x)
179 return (q_ll.y - p_ur.y);
180 else {
181 p_ur.x = p_ll.x; /* p_ur is now upper left */
182 q_ll.x = q_ur.x; /* q_ll is now lower right */
183 return (dist(p_ur, q_ll));
184 }
185 } else if (q_ll.y >= p_ll.y) {
186 if (q_ur.x >= p_ll.x)
187 return 0.0;
188 else
189 return (p_ll.x - q_ur.x);
190 } else {
191 if (q_ur.x >= p_ll.x) {
192 if (q_ur.y >= p_ll.y)
193 return 0.0;
194 else
195 return (p_ll.y - q_ur.y);
196 } else {
197 if (q_ur.y >= p_ll.y)
198 return (p_ll.x - q_ur.x);
199 else
200 return (dist(p_ll, q_ur));
201 }
202 }
203 }
204}
205#endif /* MS */
206
207/* overlap:
208 * Return true if nodes overlap
209 */
210static int overlap(node_t * p, node_t * q)
211{
212#if defined(BOX)
213 double xdelta, ydelta;
214 int ret;
215
216 xdelta = ND_pos(q)[0] - ND_pos(p)[0];
217 if (xdelta < 0)
218 xdelta = -xdelta;
219 ydelta = ND_pos(q)[1] - ND_pos(p)[1];
220 if (ydelta < 0)
221 ydelta = -ydelta;
222 ret = ((xdelta <= (WD2(p) + WD2(q))) && (ydelta <= (HT2(p) + HT2(q))));
223 return ret;
224#else
225 double dist2, xdelta, ydelta;
226 double din;
227
228 din = RAD(p) + RAD(q);
229 xdelta = ND_pos(q)[0] - ND_pos(p)[0];
230 ydelta = ND_pos(q)[1] - ND_pos(p)[1];
231 dist2 = xdelta * xdelta + ydelta * ydelta;
232 return (dist2 <= (din * din));
233#endif
234}
235
236/* cntOverlaps:
237 * Return number of overlaps.
238 */
239static int cntOverlaps(graph_t * g)
240{
241 node_t *p;
242 node_t *q;
243 int cnt = 0;
244
245 for (p = agfstnode(g); p; p = agnxtnode(g, p)) {
246 for (q = agnxtnode(g, p); q; q = agnxtnode(g, q)) {
247 cnt += overlap(p, q);
248 }
249 }
250 return cnt;
251}
252
253/* doRep:
254 * Return 1 if nodes overlap
255 */
256static int
257doRep(node_t * p, node_t * q, double xdelta, double ydelta, double dist2)
258{
259 int ov;
260 double force;
261 /* double dout, din; */
262#if defined(DEBUG) || defined(MS) || defined(ALT)
263 double dist;
264#endif
265 /* double factor; */
266
267 while (dist2 == 0.0) {
268 xdelta = 5 - rand() % 10;
269 ydelta = 5 - rand() % 10;
270 dist2 = xdelta * xdelta + ydelta * ydelta;
271 }
272#if defined(MS)
273 dout = boxDist(p, q);
274 if (dout < EPSILON)
275 dout = EPSILON;
276 dist = sqrt(dist2);
277 force = K2 / (dout * dist);
278#elif defined(ALT)
279 force = K2 / dist2;
280 dist = sqrt(dist2);
281 din = RAD(p) + RAD(q);
282 if (ov = overlap(p, q)) {
283 factor = X_C;
284 } else {
285 ov = 0;
286 if (dist <= din + X_K)
287 factor = X_C * (X_K - (dist - din)) / X_K;
288 else
289 factor = 0.0;
290 }
291 force *= factor;
292#elif defined(ORIG)
293 force = K2 / dist2;
294 if ((ov = overlap(p, q)))
295 force *= X_C;
296#else
297 if ((ov = overlap(p, q)))
298 force = X_ov / dist2;
299 else
300 force = X_nonov / dist2;
301#endif
302#ifdef DEBUG
303 if (Verbose == 4) {
304 prIndent();
305 dist = sqrt(dist2);
306 fprintf(stderr, " ov Fr %f dist %f\n", force * dist, dist);
307 }
308#endif
309 DISP(q)[0] += xdelta * force;
310 DISP(q)[1] += ydelta * force;
311 DISP(p)[0] -= xdelta * force;
312 DISP(p)[1] -= ydelta * force;
313 return ov;
314}
315
316/* applyRep:
317 * Repulsive force = (K*K)/d
318 * Return 1 if nodes overlap
319 */
320static int applyRep(Agnode_t * p, Agnode_t * q)
321{
322 double xdelta, ydelta;
323
324 xdelta = ND_pos(q)[0] - ND_pos(p)[0];
325 ydelta = ND_pos(q)[1] - ND_pos(p)[1];
326 return doRep(p, q, xdelta, ydelta, xdelta * xdelta + ydelta * ydelta);
327}
328
329static void applyAttr(Agnode_t * p, Agnode_t * q)
330{
331 double xdelta, ydelta;
332 double force;
333 double dist;
334 double dout;
335 double din;
336
337#if defined(MS)
338 dout = boxDist(p, q);
339 if (dout == 0.0)
340 return;
341 xdelta = ND_pos(q)[0] - ND_pos(p)[0];
342 ydelta = ND_pos(q)[1] - ND_pos(p)[1];
343 dist = sqrt(xdelta * xdelta + ydelta * ydelta);
344 force = (dout * dout) / (X_K * dist);
345#elif defined(ALT)
346 xdelta = ND_pos(q)[0] - ND_pos(p)[0];
347 ydelta = ND_pos(q)[1] - ND_pos(p)[1];
348 dist = sqrt(xdelta * xdelta + ydelta * ydelta);
349 din = RAD(p) + RAD(q);
350 if (dist < X_K + din)
351 return;
352 dout = dist - din;
353 force = (dout * dout) / ((X_K + din) * dist);
354#else
355 if (overlap(p, q)) {
356#ifdef DEBUG
357 if (Verbose == 4) {
358 prIndent();
359 fprintf(stderr, "ov 1 Fa 0 din %f\n", RAD(p) + RAD(q));
360 }
361#endif
362 return;
363 }
364 xdelta = ND_pos(q)[0] - ND_pos(p)[0];
365 ydelta = ND_pos(q)[1] - ND_pos(p)[1];
366 dist = sqrt(xdelta * xdelta + ydelta * ydelta);
367 din = RAD(p) + RAD(q);
368 dout = dist - din;
369 force = (dout * dout) / ((X_K + din) * dist);
370#endif
371#ifdef DEBUG
372 if (Verbose == 4) {
373 prIndent();
374 fprintf(stderr, " ov 0 Fa %f din %f \n", force * dist, din);
375 }
376#endif
377 DISP(q)[0] -= xdelta * force;
378 DISP(q)[1] -= ydelta * force;
379 DISP(p)[0] += xdelta * force;
380 DISP(p)[1] += ydelta * force;
381}
382
383/* adjust:
384 * Return 0 if definitely no overlaps.
385 * Return non-zero if we had overlaps before most recent move.
386 */
387static int adjust(Agraph_t * g, double temp)
388{
389 Agnode_t *n;
390 Agnode_t *n1;
391 Agedge_t *e;
392 double temp2;
393 double len;
394 double len2;
395 double disp[NDIM]; /* incremental displacement */
396 int overlaps = 0;
397
398#ifdef DEBUG
399 if (Verbose == 4)
400 fprintf(stderr, "=================\n");
401#endif
402
403 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
404 DISP(n)[0] = DISP(n)[1] = 0;
405 }
406
407 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
408 int ov;
409 for (n1 = agnxtnode(g, n); n1; n1 = agnxtnode(g, n1)) {
410 ov = applyRep(n, n1);
411/* if (V && ov) */
412 /* fprintf (stderr,"%s ov %s\n", n->name, n1->name); */
413 overlaps += ov;
414 }
415 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
416 applyAttr(n,aghead(e));
417 }
418 }
419 if (overlaps == 0)
420 return 0;
421
422 temp2 = temp * temp;
423 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
424 if (ND_pinned(n) == P_PIN)
425 continue;
426 disp[0] = DISP(n)[0];
427 disp[1] = DISP(n)[1];
428 len2 = disp[0] * disp[0] + disp[1] * disp[1];
429
430 if (len2 < temp2) {
431 ND_pos(n)[0] += disp[0];
432 ND_pos(n)[1] += disp[1];
433 } else {
434 /* to avoid sqrt, consider abs(x) + abs(y) */
435 len = sqrt(len2);
436 ND_pos(n)[0] += (disp[0] * temp) / len;
437 ND_pos(n)[1] += (disp[1] * temp) / len;
438 }
439 }
440 return overlaps;
441}
442
443/* x_layout:
444 * Given graph g with initial layout, adjust g so that nodes
445 * do not overlap.
446 * Assume g is connected.
447 * g may have ports. At present, we do not use ports in the layout
448 * at this stage.
449 * Returns non-zero if overlaps still exist.
450 * TODO (possible):
451 * Allow X_T0 independent of T_TO or percentage of, so the cooling would
452 * be piecewise linear. This would allow longer, cooler expansion.
453 * In tries > 1, increase X_T0 and/or lengthen cooling
454 */
455static int x_layout(graph_t * g, xparams * pxpms, int tries)
456{
457 int i;
458 int try;
459 int ov;
460 double temp;
461 int nnodes = agnnodes(g);
462 int nedges = agnedges(g);
463 double K;
464 xparams xpms;
465
466 X_marg = sepFactor (g);
467 if (X_marg.doAdd) {
468 X_marg.x = PS2INCH(X_marg.x); /* sepFactor is in points */
469 X_marg.y = PS2INCH(X_marg.y);
470 }
471 ov = cntOverlaps(g);
472 if (ov == 0)
473 return 0;
474
475 try = 0;
476 xpms = *pxpms;
477 K = xpms.K;
478 while (ov && (try < tries)) {
479 xinit_params(g, nnodes, &xpms);
480 X_ov = X_C * K2;
481 X_nonov = (nedges*X_ov*2.0)/(nnodes*(nnodes-1));
482#ifdef DEBUG
483 if (Verbose) {
484 prIndent();
485 fprintf(stderr, "try %d (%d): %d overlaps on ", try, tries, ov);
486 pr2graphs(g,GORIG(agroot(g)));
487 fprintf(stderr," \n");
488 }
489#endif
490
491 for (i = 0; i < X_loopcnt; i++) {
492 temp = cool(i);
493 if (temp <= 0.0)
494 break;
495 ov = adjust(g, temp);
496 if (ov == 0)
497 break;
498 }
499 try++;
500 xpms.K += K; /* increase distance */
501 }
502#ifdef DEBUG
503 if (Verbose && ov)
504 fprintf(stderr, "Warning: %d overlaps remain on ", ov);
505 pr2graphs(g,GORIG(agroot(g)));
506 fprintf(stderr,"\n");
507#endif
508
509 return ov;
510}
511
512/* fdp_xLayout:
513 * Use overlap parameter to determine if and how to remove overlaps.
514 * In addition to the usual values accepted by removeOverlap, overlap
515 * can begin with "n:" to indicate the given number of tries using
516 * x_layout to remove overlaps.
517 * Thus,
518 * NULL or "" => dflt overlap
519 * "mode" => "0:mode", i.e. removeOverlap with mode only
520 * "true" => "0:true", i.e., no overlap removal
521 * "n:" => n tries only
522 * "n:mode" => n tries, then removeOverlap with mode
523 * "0:" => no overlap removal
524 */
525void fdp_xLayout(graph_t * g, xparams * xpms)
526{
527 int tries;
528 char* ovlp = agget (g, "overlap");
529 char* cp;
530 char* rest;
531
532 if (Verbose) {
533#ifdef DEBUG
534 prIndent();
535#endif
536 fprintf (stderr, "xLayout ");
537 }
538 if (!ovlp || (*ovlp == '\0')) {
539 ovlp = DFLT_overlap;
540 }
541 /* look for optional ":" or "number:" */
542 if ((cp = strchr(ovlp, ':')) && ((cp == ovlp) || isdigit(*ovlp))) {
543 cp++;
544 rest = cp;
545 tries = atoi (ovlp);
546 if (tries < 0) tries = 0;
547 }
548 else {
549 tries = 0;
550 rest = ovlp;
551 }
552 if (Verbose) {
553#ifdef DEBUG
554 prIndent();
555#endif
556 fprintf (stderr, "tries = %d, mode = %s\n", tries, rest);
557 }
558 if (tries && !x_layout(g, xpms, tries))
559 return;
560 removeOverlapAs(g, rest);
561
562}
563