Graphviz  2.39.20141227.0545
xlayout.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 /* 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
23 Allow sep to be absolute additive (margin of n points)
24 Increase 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 
48 static xparams xParams = {
49  60, /* numIters */
50  0.0, /* T0 */
51  0.3, /* K */
52  1.5, /* C */
53  0 /* loopcnt */
54 };
55 static double K2;
56 static expand_t X_marg;
57 static double X_nonov;
58 static double X_ov;
59 
60 void pr2graphs(Agraph_t *g0, Agraph_t *g1)
61 {
62  fprintf(stderr,"%s",agnameof(g0));
63  fprintf(stderr,"(%s)",agnameof(g1));
64 }
65 
66 static 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  */
76 static 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 
106 static 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  */
117 static 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  */
129 static 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  */
143 static 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  */
210 static 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  */
239 static 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  */
256 static int
257 doRep(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  */
320 static 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 
329 static 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  */
387 static 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  */
455 static 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  */
525 void 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 }
boolean doAdd
Definition: adjust.h:45
int numIters
Definition: xlayout.h:24
#define ND_pinned(n)
Definition: types.h:486
Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:502
expand_t sepFactor(graph_t *g)
Definition: adjust.c:1271
int agnedges(Agraph_t *g)
#define X_K
Definition: xlayout.c:100
double K
Definition: xlayout.h:26
void pr2graphs(Agraph_t *g0, Agraph_t *g1)
Definition: xlayout.c:60
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
Definition: geom.h:30
int agnnodes(Agraph_t *g)
#define ND_pos(n)
Definition: types.h:487
char * agget(void *obj, char *name)
Definition: attr.c:428
int removeOverlapAs(graph_t *G, char *flag)
Definition: adjust.c:1215
#define EPSILON
Definition: xlayout.c:111
int i
Definition: gvdevice.c:448
double y
Definition: geom.h:30
#define X_loopcnt
Definition: xlayout.c:102
Agraph_t * agroot(void *obj)
Definition: obj.c:169
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
float y
Definition: adjust.h:44
#define overlap(pb, qb)
Definition: constraint.c:551
Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
int loopcnt
Definition: xlayout.h:28
COORD dist2(Ppoint_t, Ppoint_t)
Definition: visibility.c:213
#define HT2(n)
Definition: xlayout.c:46
void fdp_xLayout(graph_t *g, xparams *xpms)
Definition: xlayout.c:525
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
double x
Definition: geom.h:30
#define X_numIters
Definition: xlayout.c:101
EXTERN unsigned char Verbose
Definition: globals.h:73
char * agnameof(void *)
Definition: id.c:143
#define X_C
Definition: xlayout.c:103
#define WD2(n)
Definition: xlayout.c:45
double T0
Definition: xlayout.h:25
#define X_T0
Definition: xlayout.c:99
double C
Definition: xlayout.h:27
double dist(Site *s, Site *t)
Definition: site.c:41
float x
Definition: adjust.h:44
#define P_PIN
Definition: const.h:284
#define DFLT_overlap
Definition: xlayout.c:43