Graphviz  2.41.20170921.2350
tlayout.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 /* tlayout.c:
15  * Written by Emden R. Gansner
16  *
17  * Module for initial layout, using point nodes and ports.
18  *
19  * Note: If interior nodes are not connected, they tend to fly apart,
20  * despite being tied to port nodes. This occurs because, as initially
21  * coded, as the nodes tend to straighten into a line, the radius
22  * grows causing more expansion. Is the problem really here and not
23  * with disconnected nodes in xlayout? If here, we can either forbid
24  * expansion or eliminate repulsion between nodes only connected
25  * via port nodes.
26  */
27 
28 #include "config.h"
29 
30 /* uses PRIVATE interface */
31 #define FDP_PRIVATE 1
32 
33 #ifdef HAVE_SYS_TYPES_H
34 #include <sys/types.h>
35 #endif
36 #include <stdlib.h>
37 #include <time.h>
38 #ifndef _WIN32
39 #include <unistd.h>
40 #endif
41 #include <ctype.h>
42 #include <dbg.h>
43 #include <grid.h>
44 #include <neato.h>
45 
46 #ifndef HAVE_SRAND48
47 #define srand48 srand
48 #endif
49 #ifndef HAVE_DRAND48
50 extern double drand48(void);
51 #endif
52 
53 #include "tlayout.h"
54 #include "globals.h"
55 
56 #define D_useGrid (fdp_parms->useGrid)
57 #define D_useNew (fdp_parms->useNew)
58 #define D_numIters (fdp_parms->numIters)
59 #define D_unscaled (fdp_parms->unscaled)
60 #define D_C (fdp_parms->C)
61 #define D_Tfact (fdp_parms->Tfact)
62 #define D_K (fdp_parms->K)
63 #define D_T0 (fdp_parms->T0)
64 
65  /* Actual parameters used; initialized using fdp_parms, then possibly
66  * updated with graph-specific values.
67  */
68 typedef struct {
69  int useGrid; /* use grid for speed up */
70  int useNew; /* encode x-K into attractive force */
71  long seed; /* seed for position RNG */
72  int numIters; /* actual iterations in layout */
73  int maxIters; /* max iterations in layout */
74  int unscaled; /* % of iterations used in pass 1 */
75  double C; /* Repulsion factor in xLayout */
76  double Tfact; /* scale temp from default expression */
77  double K; /* spring constant; ideal distance */
78  double T0; /* initial temperature */
79  int smode; /* seed mode */
80  double Cell; /* grid cell size */
81  double Cell2; /* Cell*Cell */
82  double K2; /* K*K */
83  double Wd; /* half-width of boundary */
84  double Ht; /* half-height of boundary */
85  double Wd2; /* Wd*Wd */
86  double Ht2; /* Ht*Ht */
87  int pass1; /* iterations used in pass 1 */
88  int loopcnt; /* actual iterations in this pass */
89 } parms_t;
90 
91 static parms_t parms;
92 
93 #define T_useGrid (parms.useGrid)
94 #define T_useNew (parms.useNew)
95 #define T_seed (parms.seed)
96 #define T_numIters (parms.numIters)
97 #define T_maxIters (parms.maxIters)
98 #define T_unscaled (parms.unscaled)
99 #define T_C (parms.C)
100 #define T_Tfact (parms.Tfact)
101 #define T_K (parms.K)
102 #define T_T0 (parms.T0)
103 #define T_smode (parms.smode)
104 #define T_Cell (parms.Cell)
105 #define T_Cell2 (parms.Cell2)
106 #define T_K2 (parms.K2)
107 #define T_Wd (parms.Wd)
108 #define T_Ht (parms.Ht)
109 #define T_Wd2 (parms.Wd2)
110 #define T_Ht2 (parms.Ht2)
111 #define T_pass1 (parms.pass1)
112 #define T_loopcnt (parms.loopcnt)
113 
114 #define EXPFACTOR 1.2
115 #define DFLT_maxIters 600
116 #define DFLT_K 0.3
117 #define DFLT_Cell 0.0
118 #define DFLT_seed 1
119 #define DFLT_smode INIT_RANDOM
120 
121 static double cool(double temp, int t)
122 {
123  return (T_T0 * (T_maxIters - t)) / T_maxIters;
124 }
125 
126 /* reset_params:
127  */
128 static void reset_params(void)
129 {
130  T_T0 = -1.0;
131 }
132 
133 /* init_params:
134  * Set parameters for expansion phase based on initial
135  * layout parameters. If T0 is not set, we set it here
136  * based on the size of the graph. In this case, we
137  * return 1, so that fdp_tLayout can unset T0, to be
138  * reset by a recursive call to fdp_tLayout.
139  */
140 static int init_params(graph_t * g, xparams * xpms)
141 {
142  int ret = 0;
143 
144  if (T_T0 == -1.0) {
145  int nnodes = agnnodes(g);
146 
147  T_T0 = T_Tfact * T_K * sqrt(nnodes) / 5;
148 #ifdef DEBUG
149  if (Verbose) {
150  prIndent();
151  fprintf(stderr, "tlayout %s", agnameof(g));
152  fprintf(stderr, "(%s) : T0 %f\n", agnameof(GORIG(g->root)), T_T0);
153  }
154 #endif
155  ret = 1;
156  }
157 
158  xpms->T0 = cool(T_T0, T_pass1);
159  xpms->K = T_K;
160  xpms->C = T_C;
161  xpms->numIters = T_maxIters - T_pass1;
162 
163  if (T_numIters >= 0) {
164  if (T_numIters <= T_pass1) {
166  xpms->loopcnt = 0;
167  } else if (T_numIters <= T_maxIters) {
168  T_loopcnt = T_pass1;
169  xpms->loopcnt = T_numIters - T_pass1;
170  }
171  } else {
172  T_loopcnt = T_pass1;
173  xpms->loopcnt = xpms->numIters;
174  }
175  return ret;
176 }
177 
178 /* fdp_initParams:
179  * Initialize parameters based on root graph attributes.
180  */
182 {
184  T_useNew = D_useNew;
187  T_Cell = DFLT_Cell;
188  T_C = D_C;
189  T_Tfact = D_Tfact;
190  T_maxIters = late_int(g, agattr(g,AGRAPH, "maxiter", NULL), DFLT_maxIters, 0);
191  D_K = T_K = late_double(g, agattr(g,AGRAPH, "K", NULL), DFLT_K, 0.0);
192  if (D_T0 == -1.0) {
193  T_T0 = late_double(g, agattr(g,AGRAPH, "T0", NULL), -1.0, 0.0);
194  } else
195  T_T0 = D_T0;
196  T_seed = DFLT_seed;
197  T_smode = setSeed (g, DFLT_smode, &T_seed);
198  if (T_smode == INIT_SELF) {
199  agerr(AGWARN, "fdp does not support start=self - ignoring\n");
200  T_seed = DFLT_smode;
201  }
202 
203  T_pass1 = (T_unscaled * T_maxIters) / 100;
204  T_K2 = T_K * T_K;
205 
206  if (T_useGrid) {
207  if (T_Cell <= 0.0)
208  T_Cell = 3 * T_K;
209  T_Cell2 = T_Cell * T_Cell;
210  }
211 #ifdef DEBUG
212  if (Verbose) {
213  prIndent();
214  fprintf(stderr,
215  "Params %s : K %f T0 %f Tfact %f maxIters %d unscaled %d\n",
216  agnameof(g),
218  }
219 #endif
220 }
221 
222 static void
223 doRep(node_t * p, node_t * q, double xdelta, double ydelta, double dist2)
224 {
225  double force;
226  double dist;
227 
228  while (dist2 == 0.0) {
229  xdelta = 5 - rand() % 10;
230  ydelta = 5 - rand() % 10;
231  dist2 = xdelta * xdelta + ydelta * ydelta;
232  }
233  if (T_useNew) {
234  dist = sqrt(dist2);
235  force = T_K2 / (dist * dist2);
236  } else
237  force = T_K2 / dist2;
238  if (IS_PORT(p) && IS_PORT(q))
239  force *= 10.0;
240  DISP(q)[0] += xdelta * force;
241  DISP(q)[1] += ydelta * force;
242  DISP(p)[0] -= xdelta * force;
243  DISP(p)[1] -= ydelta * force;
244 }
245 
246 /* applyRep:
247  * Repulsive force = (K*K)/d
248  * or K*K/d*d
249  */
250 static void applyRep(Agnode_t * p, Agnode_t * q)
251 {
252  double xdelta, ydelta;
253 
254  xdelta = ND_pos(q)[0] - ND_pos(p)[0];
255  ydelta = ND_pos(q)[1] - ND_pos(p)[1];
256  doRep(p, q, xdelta, ydelta, xdelta * xdelta + ydelta * ydelta);
257 }
258 
259 static void doNeighbor(Grid * grid, int i, int j, node_list * nodes)
260 {
261  cell *cellp = findGrid(grid, i, j);
262  node_list *qs;
263  Agnode_t *p;
264  Agnode_t *q;
265  double xdelta, ydelta;
266  double dist2;
267 
268  if (cellp) {
269 #ifdef DEBUG
270  if (Verbose >= 3) {
271  prIndent();
272  fprintf(stderr, " doNeighbor (%d,%d) : %d\n", i, j,
273  gLength(cellp));
274  }
275 #endif
276  for (; nodes != 0; nodes = nodes->next) {
277  p = nodes->node;
278  for (qs = cellp->nodes; qs != 0; qs = qs->next) {
279  q = qs->node;
280  xdelta = (ND_pos(q))[0] - (ND_pos(p))[0];
281  ydelta = (ND_pos(q))[1] - (ND_pos(p))[1];
282  dist2 = xdelta * xdelta + ydelta * ydelta;
283  if (dist2 < T_Cell2)
284  doRep(p, q, xdelta, ydelta, dist2);
285  }
286  }
287  }
288 }
289 
290 static int gridRepulse(Dt_t * dt, cell * cellp, Grid * grid)
291 {
292  node_list *nodes = cellp->nodes;
293  int i = cellp->p.i;
294  int j = cellp->p.j;
295  node_list *p;
296  node_list *q;
297 
298  NOTUSED(dt);
299 #ifdef DEBUG
300  if (Verbose >= 3) {
301  prIndent();
302  fprintf(stderr, "gridRepulse (%d,%d) : %d\n", i, j,
303  gLength(cellp));
304  }
305 #endif
306  for (p = nodes; p != 0; p = p->next) {
307  for (q = nodes; q != 0; q = q->next)
308  if (p != q)
309  applyRep(p->node, q->node);
310  }
311 
312  doNeighbor(grid, i - 1, j - 1, nodes);
313  doNeighbor(grid, i - 1, j, nodes);
314  doNeighbor(grid, i - 1, j + 1, nodes);
315  doNeighbor(grid, i, j - 1, nodes);
316  doNeighbor(grid, i, j + 1, nodes);
317  doNeighbor(grid, i + 1, j - 1, nodes);
318  doNeighbor(grid, i + 1, j, nodes);
319  doNeighbor(grid, i + 1, j + 1, nodes);
320 
321  return 0;
322 }
323 
324 /* applyAttr:
325  * Attractive force = weight*(d*d)/K
326  * or force = (d - L(e))*weight(e)
327  */
328 static void applyAttr(Agnode_t * p, Agnode_t * q, Agedge_t * e)
329 {
330  double xdelta, ydelta;
331  double force;
332  double dist;
333  double dist2;
334 
335  xdelta = ND_pos(q)[0] - ND_pos(p)[0];
336  ydelta = ND_pos(q)[1] - ND_pos(p)[1];
337  dist2 = xdelta * xdelta + ydelta * ydelta;
338  while (dist2 == 0.0) {
339  xdelta = 5 - rand() % 10;
340  ydelta = 5 - rand() % 10;
341  dist2 = xdelta * xdelta + ydelta * ydelta;
342  }
343  dist = sqrt(dist2);
344  if (T_useNew)
345  force = (ED_factor(e) * (dist - ED_dist(e))) / dist;
346  else
347  force = (ED_factor(e) * dist) / ED_dist(e);
348  DISP(q)[0] -= xdelta * force;
349  DISP(q)[1] -= ydelta * force;
350  DISP(p)[0] += xdelta * force;
351  DISP(p)[1] += ydelta * force;
352 }
353 
354 static void updatePos(Agraph_t * g, double temp, bport_t * pp)
355 {
356  Agnode_t *n;
357  double temp2;
358  double len2;
359  double x, y, d;
360  double dx, dy;
361 
362  temp2 = temp * temp;
363  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
364  if (ND_pinned(n) & P_FIX)
365  continue;
366  dx = DISP(n)[0];
367  dy = DISP(n)[1];
368  len2 = dx * dx + dy * dy;
369 
370  /* limit by temperature */
371  if (len2 < temp2) {
372  x = ND_pos(n)[0] + dx;
373  y = ND_pos(n)[1] + dy;
374  } else {
375  double fact = temp / (sqrt(len2));
376  x = ND_pos(n)[0] + dx * fact;
377  y = ND_pos(n)[1] + dy * fact;
378  }
379 
380  /* if ports, limit by boundary */
381  if (pp) {
382  d = sqrt((x * x) / T_Wd2 + (y * y) / T_Ht2);
383  if (IS_PORT(n)) {
384  ND_pos(n)[0] = x / d;
385  ND_pos(n)[1] = y / d;
386  } else if (d >= 1.0) {
387  ND_pos(n)[0] = 0.95 * x / d;
388  ND_pos(n)[1] = 0.95 * y / d;
389  } else {
390  ND_pos(n)[0] = x;
391  ND_pos(n)[1] = y;
392  }
393  } else {
394  ND_pos(n)[0] = x;
395  ND_pos(n)[1] = y;
396  }
397  }
398 }
399 
400 #define FLOOR(d) ((int)floor(d))
401 
402 /* gAdjust:
403  */
404 static void gAdjust(Agraph_t * g, double temp, bport_t * pp, Grid * grid)
405 {
406  Agnode_t *n;
407  Agedge_t *e;
408 
409  if (temp <= 0.0)
410  return;
411 
412  clearGrid(grid);
413 
414  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
415  DISP(n)[0] = DISP(n)[1] = 0;
416  addGrid(grid, FLOOR((ND_pos(n))[0] / T_Cell), FLOOR((ND_pos(n))[1] / T_Cell),
417  n);
418  }
419 
420  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
421  for (e = agfstout(g, n); e; e = agnxtout(g, e))
422  if (n != aghead(e))
423  applyAttr(n, aghead(e), e);
424  }
425  walkGrid(grid, gridRepulse);
426 
427 
428  updatePos(g, temp, pp);
429 }
430 
431 /* adjust:
432  */
433 static void adjust(Agraph_t * g, double temp, bport_t * pp)
434 {
435  Agnode_t *n;
436  Agnode_t *n1;
437  Agedge_t *e;
438 
439  if (temp <= 0.0)
440  return;
441 
442  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
443  DISP(n)[0] = DISP(n)[1] = 0;
444  }
445 
446  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
447  for (n1 = agnxtnode(g, n); n1; n1 = agnxtnode(g, n1)) {
448  applyRep(n, n1);
449  }
450  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
451  if (n != aghead(e))
452  applyAttr(n, aghead(e), e);
453  }
454  }
455 
456  updatePos(g, temp, pp);
457 }
458 
459 /* initPositions:
460  * Create initial layout of nodes
461  * TODO :
462  * Position nodes near neighbors with positions.
463  * Use bbox to reset K.
464  */
465 static pointf initPositions(graph_t * g, bport_t * pp)
466 {
467  int nG = agnnodes(g) - NPORTS(g);
468  double size;
469  Agnode_t *np;
470  int n_pos = 0; /* no. of nodes with position info */
471  boxf bb = { {0, 0}, {0, 0} };
472  pointf ctr; /* center of boundary ellipse */
473  long local_seed;
474  double PItimes2 = M_PI * 2.0;
475 
476  for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
477  if (ND_pinned(np)) {
478  if (n_pos) {
479  bb.LL.x = MIN(ND_pos(np)[0], bb.LL.x);
480  bb.LL.y = MIN(ND_pos(np)[1], bb.LL.y);
481  bb.UR.x = MAX(ND_pos(np)[0], bb.UR.x);
482  bb.UR.y = MAX(ND_pos(np)[1], bb.UR.y);
483  } else {
484  bb.UR.x = bb.LL.x = ND_pos(np)[0];
485  bb.UR.y = bb.LL.y = ND_pos(np)[1];
486  }
487  n_pos++;
488  }
489  }
490 
491  size = T_K * (sqrt((double) nG) + 1.0);
492  T_Wd = T_Ht = EXPFACTOR * (size / 2.0);
493  if (n_pos == 1) {
494  ctr.x = bb.LL.x;
495  ctr.y = bb.LL.y;
496  } else if (n_pos > 1) {
497  double alpha, area, width, height, quot;
498  ctr.x = (bb.LL.x + bb.UR.x) / 2.0;
499  ctr.y = (bb.LL.y + bb.UR.y) / 2.0;
500  width = EXPFACTOR * (bb.UR.x - bb.LL.x);
501  height = EXPFACTOR * (bb.UR.y - bb.LL.y);
502  area = 4.0 * T_Wd * T_Ht;
503  quot = (width * height) / area;
504  if (quot >= 1.0) { /* If bbox has large enough area, use it */
505  T_Wd = width / 2.0;
506  T_Ht = height / 2.0;
507  } else if (quot > 0.0) { /* else scale up to have enough area */
508  quot = 2.0 * sqrt(quot);
509  T_Wd = width / quot;
510  T_Ht = height / quot;
511  } else { /* either width or height is 0 */
512  if (width > 0) {
513  height = area / width;
514  T_Wd = width / 2.0;
515  T_Ht = height / 2.0;
516  } else if (height > 0) {
517  width = area / height;
518  T_Wd = width / 2.0;
519  T_Ht = height / 2.0;
520  }
521  /* If width = height = 0, use Wd and Ht as defined above for
522  * the case the n_pos == 0.
523  */
524  }
525 
526  /* Construct enclosing ellipse */
527  alpha = atan2(T_Ht, T_Wd);
528  T_Wd = T_Wd / cos(alpha);
529  T_Ht = T_Ht / sin(alpha);
530  } else {
531  ctr.x = ctr.y = 0;
532  }
533  T_Wd2 = T_Wd * T_Wd;
534  T_Ht2 = T_Ht * T_Ht;
535 
536  /* Set seed value */
537  if (T_smode == INIT_RANDOM)
538  local_seed = T_seed;
539  else {
540 #if defined(_WIN32)
541  local_seed = time(NULL);
542 #else
543  local_seed = getpid() ^ time(NULL);
544 #endif
545  }
546  srand48(local_seed);
547 
548  /* If ports, place ports on and nodes within an ellipse centered at origin
549  * with halfwidth Wd and halfheight Ht.
550  * If no ports, place nodes within a rectangle centered at origin
551  * with halfwidth Wd and halfheight Ht. Nodes with a given position
552  * are translated. Wd and Ht are set to contain all positioned points.
553  * The reverse translation will be applied to all
554  * nodes at the end of the layout.
555  * TODO: place unfixed points using adjacent ports or fixed pts.
556  */
557  if (pp) {
558 /* fprintf (stderr, "initPos %s ctr (%g,%g) Wd %g Ht %g\n", agnameof(g), ctr.x, ctr.y, T_Wd, T_Ht); */
559  while (pp->e) { /* position ports on ellipse */
560  np = pp->n;
561  ND_pos(np)[0] = T_Wd * cos(pp->alpha) + ctr.x;
562  ND_pos(np)[1] = T_Ht * sin(pp->alpha) + ctr.y;
563  ND_pinned(np) = P_SET;
564 /* fprintf (stderr, "%s pt (%g,%g) %g\n", agnameof(np), ND_pos(np)[0], ND_pos(np)[1], pp->alpha); */
565  pp++;
566  }
567  for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
568  if (IS_PORT(np))
569  continue;
570  if (ND_pinned(np)) {
571  ND_pos(np)[0] -= ctr.x;
572  ND_pos(np)[1] -= ctr.y;
573  } else {
574  pointf p = { 0.0, 0.0 };
575  int cnt = 0;
576  node_t *op;
577  edge_t *ep;
578  for (ep = agfstedge(g, np); ep; ep = agnxtedge(g, ep, np)) {
579  if (aghead(ep) == agtail(ep))
580  continue;
581  op = (aghead(ep) == np ? agtail(ep) : aghead(ep));
582  if (!hasPos(op))
583  continue;
584  if (cnt) {
585  p.x = (p.x * cnt + ND_pos(op)[0]) / (cnt + 1);
586  p.y = (p.y * cnt + ND_pos(op)[1]) / (cnt + 1);
587  } else {
588  p.x = ND_pos(op)[0];
589  p.y = ND_pos(op)[1];
590  }
591  cnt++;
592  }
593  if (cnt > 1) {
594  ND_pos(np)[0] = p.x;
595  ND_pos(np)[1] = p.y;
596 /* fprintf (stderr, "%s 1 (%g,%g)\n", agnameof(np), p.x, p.y); */
597  } else if (cnt == 1) {
598  ND_pos(np)[0] = 0.98 * p.x + 0.1 * ctr.x;
599  ND_pos(np)[1] = 0.9 * p.y + 0.1 * ctr.y;
600 /* fprintf (stderr, "%s %d (%g,%g)\n", agnameof(np), cnt, ND_pos(np)[0], ND_pos(np)[1]); */
601  } else {
602  double angle = PItimes2 * drand48();
603  double radius = 0.9 * drand48();
604  ND_pos(np)[0] = radius * T_Wd * cos(angle);
605  ND_pos(np)[1] = radius * T_Ht * sin(angle);
606 /* fprintf (stderr, "%s 0 (%g,%g)\n", agnameof(np), ND_pos(np)[0], ND_pos(np)[1]); */
607  }
608  ND_pinned(np) = P_SET;
609  }
610  }
611  } else {
612  if (n_pos) { /* If positioned nodes */
613  for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
614  if (ND_pinned(np)) {
615  ND_pos(np)[0] -= ctr.x;
616  ND_pos(np)[1] -= ctr.y;
617  } else {
618  ND_pos(np)[0] = T_Wd * (2.0 * drand48() - 1.0);
619  ND_pos(np)[1] = T_Ht * (2.0 * drand48() - 1.0);
620  }
621  }
622  } else { /* No ports or positions; place randomly */
623  for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
624  ND_pos(np)[0] = T_Wd * (2.0 * drand48() - 1.0);
625  ND_pos(np)[1] = T_Ht * (2.0 * drand48() - 1.0);
626  }
627  }
628  }
629 
630  return ctr;
631 }
632 
633 void dumpstat(graph_t * g)
634 {
635  double dx, dy;
636  double l, max2 = 0.0;
637  node_t *np;
638  edge_t *ep;
639  for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
640  dx = DISP(np)[0];
641  dy = DISP(np)[1];
642  l = dx * dx + dy * dy;
643  if (l > max2)
644  max2 = l;
645  fprintf(stderr, "%s: (%f,%f) (%f,%f)\n", agnameof(np),
646  ND_pos(np)[0], ND_pos(np)[1], DISP(np)[0], DISP(np)[1]);
647  }
648  fprintf(stderr, "max delta = %f\n", sqrt(max2));
649  for (np = agfstnode(g); np; np = agnxtnode(g, np)) {
650  for (ep = agfstout(g, np); ep; ep = agnxtout(g, ep)) {
651  dx = ND_pos(np)[0] - ND_pos(aghead(ep))[0];
652  dy = ND_pos(np)[1] - ND_pos(aghead(ep))[1];
653  fprintf(stderr, " %s -- %s (%f)\n", agnameof(np),
654  agnameof(aghead(ep)), sqrt(dx * dx + dy * dy));
655  }
656  }
657 }
658 
659 /* fdp_tLayout:
660  * Given graph g with ports nodes, layout g respecting ports.
661  * If some node have position information, it may be useful to
662  * reset temperature and other parameters to reflect this.
663  */
664 void fdp_tLayout(graph_t * g, xparams * xpms)
665 {
666  int i;
667  int reset;
668  bport_t *pp = PORTS(g);
669  double temp;
670  Grid *grid;
671  pointf ctr;
672  Agnode_t *n;
673 
674  reset = init_params(g, xpms);
675  temp = T_T0;
676 
677  ctr = initPositions(g, pp);
678 
679  if (T_useGrid) {
680  grid = mkGrid(agnnodes(g));
681  adjustGrid(grid, agnnodes(g));
682  for (i = 0; i < T_loopcnt; i++) {
683  temp = cool(temp, i);
684  gAdjust(g, temp, pp, grid);
685  }
686  delGrid(grid);
687  } else {
688  for (i = 0; i < T_loopcnt; i++) {
689  temp = cool(temp, i);
690  adjust(g, temp, pp);
691  }
692  }
693 
694  if ((ctr.x != 0.0) || (ctr.y != 0.0)) {
695  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
696  ND_pos(n)[0] += ctr.x;
697  ND_pos(n)[1] += ctr.y;
698  }
699  }
700 /* dumpstat (g); */
701  if (reset)
702  reset_params();
703 }
int numIters
Definition: xlayout.h:24
#define MAX(a, b)
Definition: agerror.c:17
#define DFLT_K
Definition: tlayout.c:116
#define ND_pinned(n)
Definition: types.h:525
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
double K2
Definition: tlayout.c:82
#define T_numIters
Definition: tlayout.c:96
int loopcnt
Definition: tlayout.c:88
Agnode_t * node
Definition: grid.h:29
double Cell2
Definition: tlayout.c:81
#define MIN(a, b)
Definition: arith.h:35
#define DFLT_Cell
Definition: tlayout.c:117
double Ht
Definition: tlayout.c:84
#define D_T0
Definition: tlayout.c:63
double T0
Definition: tlayout.c:78
double K
Definition: xlayout.h:26
int maxIters
Definition: tlayout.c:73
#define T_Wd2
Definition: tlayout.c:109
#define hasPos(n)
Definition: macros.h:26
gridpt p
Definition: grid.h:38
Definition: geom.h:28
int j
Definition: grid.h:34
#define NOTUSED(var)
Definition: cghdr.h:54
double K
Definition: tlayout.c:77
int useGrid
Definition: tlayout.c:69
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
#define P_SET
Definition: const.h:283
#define ND_pos(n)
Definition: types.h:526
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
#define T_loopcnt
Definition: tlayout.c:112
#define P_FIX
Definition: const.h:284
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
double Cell
Definition: tlayout.c:80
Definition: cgraph.h:388
#define T_C
Definition: tlayout.c:99
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
int numIters
Definition: tlayout.c:72
#define D_K
Definition: tlayout.c:62
#define D_useNew
Definition: tlayout.c:57
#define T_Cell
Definition: tlayout.c:104
node_list * nodes
Definition: grid.h:39
struct _node_list * next
Definition: grid.h:30
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
#define T_Tfact
Definition: tlayout.c:100
#define DFLT_seed
Definition: tlayout.c:118
#define T_pass1
Definition: tlayout.c:111
#define T_Cell2
Definition: tlayout.c:105
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
double y
Definition: geom.h:28
#define DFLT_smode
Definition: tlayout.c:119
double Wd2
Definition: tlayout.c:85
Definition: grid.c:69
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
void addGrid(Grid *g, int i, int j, Agnode_t *n)
Definition: grid.c:221
#define T_K2
Definition: tlayout.c:106
Definition: grid.h:37
#define T_maxIters
Definition: tlayout.c:97
Grid * mkGrid(int cellHint)
Definition: grid.c:163
#define EXPFACTOR
Definition: tlayout.c:114
#define D_numIters
Definition: tlayout.c:58
void fdp_initParams(graph_t *g)
Definition: tlayout.c:181
#define T_unscaled
Definition: tlayout.c:98
int pass1
Definition: tlayout.c:87
double drand48(void)
Definition: utils.c:2005
#define INIT_SELF
Definition: neato.h:31
int i
Definition: grid.h:34
int smode
Definition: tlayout.c:79
#define FLOOR(d)
Definition: tlayout.c:400
int unscaled
Definition: tlayout.c:74
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
int late_int(void *obj, attrsym_t *attr, int def, int low)
Definition: utils.c:71
void dumpstat(graph_t *g)
Definition: tlayout.c:633
int loopcnt
Definition: xlayout.h:28
COORD dist2(Ppoint_t, Ppoint_t)
Definition: visibility.c:213
void walkGrid(Grid *g, int(*walkf)(Dt_t *, cell *, Grid *))
Definition: grid.c:243
void adjustGrid(Grid *g, int nnodes)
Definition: grid.c:182
void delGrid(Grid *g)
Definition: grid.c:210
#define T_K
Definition: tlayout.c:101
long seed
Definition: tlayout.c:71
#define ED_factor(e)
Definition: types.h:588
#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 D_unscaled
Definition: tlayout.c:59
double x
Definition: geom.h:28
#define T_Ht2
Definition: tlayout.c:110
double late_double(void *obj, attrsym_t *attr, double def, double low)
Definition: utils.c:87
EXTERN unsigned char Verbose
Definition: globals.h:64
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
int setSeed(graph_t *G, int dflt, long *seedp)
Definition: neatoinit.c:958
#define D_useGrid
Definition: tlayout.c:56
#define T_useGrid
Definition: tlayout.c:93
cell * findGrid(Grid *g, int i, int j)
Definition: grid.c:252
pointf LL
Definition: geom.h:35
#define alpha
Definition: shapes.c:3902
#define INIT_RANDOM
Definition: neato.h:33
void clearGrid(Grid *g)
Definition: grid.c:199
#define T_useNew
Definition: tlayout.c:94
void fdp_tLayout(graph_t *g, xparams *xpms)
Definition: tlayout.c:664
double T0
Definition: xlayout.h:25
double Wd
Definition: tlayout.c:83
#define T_T0
Definition: tlayout.c:102
Definition: cdt.h:99
double Ht2
Definition: tlayout.c:86
#define M_PI
Definition: arith.h:77
#define srand48
Definition: tlayout.c:47
double C
Definition: xlayout.h:27
Agraph_t * root
Definition: cgraph.h:247
#define T_Wd
Definition: tlayout.c:107
double dist(Site *s, Site *t)
Definition: site.c:41
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define DFLT_maxIters
Definition: tlayout.c:115
int gLength(cell *p)
Definition: grid.c:264
#define D_Tfact
Definition: tlayout.c:61
#define T_Ht
Definition: tlayout.c:108
#define ED_dist(e)
Definition: types.h:605
pointf UR
Definition: geom.h:35
#define T_seed
Definition: tlayout.c:95
double Tfact
Definition: tlayout.c:76
Definition: geom.h:35
#define D_C
Definition: tlayout.c:60
int useNew
Definition: tlayout.c:70
double C
Definition: tlayout.c:75
#define AGRAPH
Definition: cgraph.h:100
#define T_smode
Definition: tlayout.c:103