/************************************************************************* * Copyright (c) 2011 AT&T Intellectual Property * All rights reserved. This program and the accompanying materials * are made available under the terms of the Eclipse Public License v1.0 * which accompanies this distribution, and is available at * https://www.eclipse.org/legal/epl-v10.html * * Contributors: Details at https://graphviz.org *************************************************************************/ /* tlayout.c: * Written by Emden R. Gansner * * Module for initial layout, using point nodes and ports. * * Note: If interior nodes are not connected, they tend to fly apart, * despite being tied to port nodes. This occurs because, as initially * coded, as the nodes tend to straighten into a line, the radius * grows causing more expansion. Is the problem really here and not * with disconnected nodes in xlayout? If here, we can either forbid * expansion or eliminate repulsion between nodes only connected * via port nodes. */ #include "config.h" /* uses PRIVATE interface */ #define FDP_PRIVATE 1 #ifdef HAVE_SYS_TYPES_H #include #endif #include #include #include #ifndef _WIN32 #include #endif #include #include #include #include #ifndef HAVE_SRAND48 #define srand48 srand #endif #include #include #define D_useGrid (fdp_parms->useGrid) #define D_useNew (fdp_parms->useNew) #define D_numIters (fdp_parms->numIters) #define D_unscaled (fdp_parms->unscaled) #define D_C (fdp_parms->C) #define D_Tfact (fdp_parms->Tfact) #define D_K (fdp_parms->K) #define D_T0 (fdp_parms->T0) /* Actual parameters used; initialized using fdp_parms, then possibly * updated with graph-specific values. */ typedef struct { int useGrid; /* use grid for speed up */ int useNew; /* encode x-K into attractive force */ long seed; /* seed for position RNG */ int numIters; /* actual iterations in layout */ int maxIters; /* max iterations in layout */ int unscaled; /* % of iterations used in pass 1 */ double C; /* Repulsion factor in xLayout */ double Tfact; /* scale temp from default expression */ double K; /* spring constant; ideal distance */ double T0; /* initial temperature */ int smode; /* seed mode */ double Cell; /* grid cell size */ double Wd; /* half-width of boundary */ double Ht; /* half-height of boundary */ int pass1; /* iterations used in pass 1 */ int loopcnt; /* actual iterations in this pass */ } parms_t; static parms_t parms; #define T_useGrid (parms.useGrid) #define T_useNew (parms.useNew) #define T_seed (parms.seed) #define T_numIters (parms.numIters) #define T_maxIters (parms.maxIters) #define T_unscaled (parms.unscaled) #define T_C (parms.C) #define T_Tfact (parms.Tfact) #define T_K (parms.K) #define T_T0 (parms.T0) #define T_smode (parms.smode) #define T_Cell (parms.Cell) #define T_Wd (parms.Wd) #define T_Ht (parms.Ht) #define T_pass1 (parms.pass1) #define T_loopcnt (parms.loopcnt) #define EXPFACTOR 1.2 #define DFLT_maxIters 600 #define DFLT_K 0.3 #define DFLT_Cell 0.0 #define DFLT_seed 1 #define DFLT_smode INIT_RANDOM static double cool(int t) { return T_T0 * (T_maxIters - t) / T_maxIters; } /* reset_params: */ static void reset_params(void) { T_T0 = -1.0; } /* init_params: * Set parameters for expansion phase based on initial * layout parameters. If T0 is not set, we set it here * based on the size of the graph. In this case, we * return 1, so that fdp_tLayout can unset T0, to be * reset by a recursive call to fdp_tLayout. */ static int init_params(graph_t * g, xparams * xpms) { int ret = 0; if (T_T0 == -1.0) { int nnodes = agnnodes(g); T_T0 = T_Tfact * T_K * sqrt(nnodes) / 5; #ifdef DEBUG if (Verbose) { prIndent(); fprintf(stderr, "tlayout %s", agnameof(g)); fprintf(stderr, "(%s) : T0 %f\n", agnameof(GORIG(g->root)), T_T0); } #endif ret = 1; } xpms->T0 = cool(T_pass1); xpms->K = T_K; xpms->C = T_C; xpms->numIters = T_maxIters - T_pass1; if (T_numIters >= 0) { if (T_numIters <= T_pass1) { T_loopcnt = T_numIters; xpms->loopcnt = 0; } else if (T_numIters <= T_maxIters) { T_loopcnt = T_pass1; xpms->loopcnt = T_numIters - T_pass1; } } else { T_loopcnt = T_pass1; xpms->loopcnt = xpms->numIters; } return ret; } /* fdp_initParams: * Initialize parameters based on root graph attributes. */ void fdp_initParams(graph_t * g) { T_useGrid = D_useGrid; T_useNew = D_useNew; T_numIters = D_numIters; T_unscaled = D_unscaled; T_Cell = DFLT_Cell; T_C = D_C; T_Tfact = D_Tfact; T_maxIters = late_int(g, agattr(g,AGRAPH, "maxiter", NULL), DFLT_maxIters, 0); D_K = T_K = late_double(g, agattr(g,AGRAPH, "K", NULL), DFLT_K, 0.0); if (D_T0 == -1.0) { T_T0 = late_double(g, agattr(g,AGRAPH, "T0", NULL), -1.0, 0.0); } else T_T0 = D_T0; T_seed = DFLT_seed; T_smode = setSeed (g, DFLT_smode, &T_seed); if (T_smode == INIT_SELF) { agwarningf("fdp does not support start=self - ignoring\n"); T_seed = DFLT_smode; } T_pass1 = T_unscaled * T_maxIters / 100; if (T_useGrid) { if (T_Cell <= 0.0) T_Cell = 3 * T_K; } #ifdef DEBUG if (Verbose) { prIndent(); fprintf(stderr, "Params %s : K %f T0 %f Tfact %f maxIters %d unscaled %d\n", agnameof(g), T_K, T_T0, T_Tfact, T_maxIters, T_unscaled); } #endif } static void doRep(node_t * p, node_t * q, double xdelta, double ydelta, double dist2) { double force; double dist; while (dist2 == 0.0) { xdelta = 5 - rand() % 10; ydelta = 5 - rand() % 10; dist2 = xdelta * xdelta + ydelta * ydelta; } if (T_useNew) { dist = sqrt(dist2); force = T_K * T_K / (dist * dist2); } else force = T_K * T_K / dist2; if (IS_PORT(p) && IS_PORT(q)) force *= 10.0; DISP(q)[0] += xdelta * force; DISP(q)[1] += ydelta * force; DISP(p)[0] -= xdelta * force; DISP(p)[1] -= ydelta * force; } /* applyRep: * Repulsive force = (K*K)/d * or K*K/d*d */ static void applyRep(Agnode_t * p, Agnode_t * q) { double xdelta, ydelta; xdelta = ND_pos(q)[0] - ND_pos(p)[0]; ydelta = ND_pos(q)[1] - ND_pos(p)[1]; doRep(p, q, xdelta, ydelta, xdelta * xdelta + ydelta * ydelta); } static void doNeighbor(Grid * grid, int i, int j, node_list * nodes) { cell *cellp = findGrid(grid, i, j); node_list *qs; Agnode_t *p; Agnode_t *q; double xdelta, ydelta; double dist2; if (cellp) { #ifdef DEBUG if (Verbose >= 3) { prIndent(); fprintf(stderr, " doNeighbor (%d,%d) : %d\n", i, j, gLength(cellp)); } #endif for (; nodes != 0; nodes = nodes->next) { p = nodes->node; for (qs = cellp->nodes; qs != 0; qs = qs->next) { q = qs->node; xdelta = (ND_pos(q))[0] - (ND_pos(p))[0]; ydelta = (ND_pos(q))[1] - (ND_pos(p))[1]; dist2 = xdelta * xdelta + ydelta * ydelta; if (dist2 < T_Cell * T_Cell) doRep(p, q, xdelta, ydelta, dist2); } } } } static int gridRepulse(cell *cellp, Grid *grid) { node_list *nodes = cellp->nodes; int i = cellp->p.i; int j = cellp->p.j; node_list *p; node_list *q; #ifdef DEBUG if (Verbose >= 3) { prIndent(); fprintf(stderr, "gridRepulse (%d,%d) : %d\n", i, j, gLength(cellp)); } #endif for (p = nodes; p != 0; p = p->next) { for (q = nodes; q != 0; q = q->next) if (p != q) applyRep(p->node, q->node); } doNeighbor(grid, i - 1, j - 1, nodes); doNeighbor(grid, i - 1, j, nodes); doNeighbor(grid, i - 1, j + 1, nodes); doNeighbor(grid, i, j - 1, nodes); doNeighbor(grid, i, j + 1, nodes); doNeighbor(grid, i + 1, j - 1, nodes); doNeighbor(grid, i + 1, j, nodes); doNeighbor(grid, i + 1, j + 1, nodes); return 0; } /* applyAttr: * Attractive force = weight*(d*d)/K * or force = (d - L(e))*weight(e) */ static void applyAttr(Agnode_t * p, Agnode_t * q, Agedge_t * e) { double xdelta, ydelta; double force; double dist; double dist2; xdelta = ND_pos(q)[0] - ND_pos(p)[0]; ydelta = ND_pos(q)[1] - ND_pos(p)[1]; dist2 = xdelta * xdelta + ydelta * ydelta; while (dist2 == 0.0) { xdelta = 5 - rand() % 10; ydelta = 5 - rand() % 10; dist2 = xdelta * xdelta + ydelta * ydelta; } dist = sqrt(dist2); if (T_useNew) force = ED_factor(e) * (dist - ED_dist(e)) / dist; else force = ED_factor(e) * dist / ED_dist(e); DISP(q)[0] -= xdelta * force; DISP(q)[1] -= ydelta * force; DISP(p)[0] += xdelta * force; DISP(p)[1] += ydelta * force; } static void updatePos(Agraph_t * g, double temp, bport_t * pp) { Agnode_t *n; double temp2; double len2; double x, y, d; double dx, dy; temp2 = temp * temp; for (n = agfstnode(g); n; n = agnxtnode(g, n)) { if (ND_pinned(n) & P_FIX) continue; dx = DISP(n)[0]; dy = DISP(n)[1]; len2 = dx * dx + dy * dy; /* limit by temperature */ if (len2 < temp2) { x = ND_pos(n)[0] + dx; y = ND_pos(n)[1] + dy; } else { double fact = temp / sqrt(len2); x = ND_pos(n)[0] + dx * fact; y = ND_pos(n)[1] + dy * fact; } /* if ports, limit by boundary */ if (pp) { d = sqrt(x * x / (T_Wd * T_Wd) + y * y / (T_Ht * T_Ht)); if (IS_PORT(n)) { ND_pos(n)[0] = x / d; ND_pos(n)[1] = y / d; } else if (d >= 1.0) { ND_pos(n)[0] = 0.95 * x / d; ND_pos(n)[1] = 0.95 * y / d; } else { ND_pos(n)[0] = x; ND_pos(n)[1] = y; } } else { ND_pos(n)[0] = x; ND_pos(n)[1] = y; } } } #define FLOOR(d) ((int)floor(d)) /* gAdjust: */ static void gAdjust(Agraph_t * g, double temp, bport_t * pp, Grid * grid) { Agnode_t *n; Agedge_t *e; if (temp <= 0.0) return; clearGrid(grid); for (n = agfstnode(g); n; n = agnxtnode(g, n)) { DISP(n)[0] = DISP(n)[1] = 0; addGrid(grid, FLOOR((ND_pos(n))[0] / T_Cell), FLOOR((ND_pos(n))[1] / T_Cell), n); } for (n = agfstnode(g); n; n = agnxtnode(g, n)) { for (e = agfstout(g, n); e; e = agnxtout(g, e)) if (n != aghead(e)) applyAttr(n, aghead(e), e); } walkGrid(grid, gridRepulse); updatePos(g, temp, pp); } /* adjust: */ static void adjust(Agraph_t * g, double temp, bport_t * pp) { Agnode_t *n; Agnode_t *n1; Agedge_t *e; if (temp <= 0.0) return; for (n = agfstnode(g); n; n = agnxtnode(g, n)) { DISP(n)[0] = DISP(n)[1] = 0; } for (n = agfstnode(g); n; n = agnxtnode(g, n)) { for (n1 = agnxtnode(g, n); n1; n1 = agnxtnode(g, n1)) { applyRep(n, n1); } for (e = agfstout(g, n); e; e = agnxtout(g, e)) { if (n != aghead(e)) applyAttr(n, aghead(e), e); } } updatePos(g, temp, pp); } /* initPositions: * Create initial layout of nodes * TODO : * Position nodes near neighbors with positions. * Use bbox to reset K. */ static pointf initPositions(graph_t * g, bport_t * pp) { int nG = agnnodes(g) - NPORTS(g); double size; Agnode_t *np; int n_pos = 0; /* no. of nodes with position info */ boxf bb = { {0, 0}, {0, 0} }; pointf ctr; /* center of boundary ellipse */ long local_seed; double PItimes2 = M_PI * 2.0; for (np = agfstnode(g); np; np = agnxtnode(g, np)) { if (ND_pinned(np)) { if (n_pos) { bb.LL.x = MIN(ND_pos(np)[0], bb.LL.x); bb.LL.y = MIN(ND_pos(np)[1], bb.LL.y); bb.UR.x = MAX(ND_pos(np)[0], bb.UR.x); bb.UR.y = MAX(ND_pos(np)[1], bb.UR.y); } else { bb.UR.x = bb.LL.x = ND_pos(np)[0]; bb.UR.y = bb.LL.y = ND_pos(np)[1]; } n_pos++; } } size = T_K * (sqrt((double) nG) + 1.0); T_Wd = T_Ht = EXPFACTOR * (size / 2.0); if (n_pos == 1) { ctr.x = bb.LL.x; ctr.y = bb.LL.y; } else if (n_pos > 1) { double alpha, area, width, height, quot; ctr.x = (bb.LL.x + bb.UR.x) / 2.0; ctr.y = (bb.LL.y + bb.UR.y) / 2.0; width = EXPFACTOR * (bb.UR.x - bb.LL.x); height = EXPFACTOR * (bb.UR.y - bb.LL.y); area = 4.0 * T_Wd * T_Ht; quot = width * height / area; if (quot >= 1.0) { /* If bbox has large enough area, use it */ T_Wd = width / 2.0; T_Ht = height / 2.0; } else if (quot > 0.0) { /* else scale up to have enough area */ quot = 2.0 * sqrt(quot); T_Wd = width / quot; T_Ht = height / quot; } else { /* either width or height is 0 */ if (width > 0) { height = area / width; T_Wd = width / 2.0; T_Ht = height / 2.0; } else if (height > 0) { width = area / height; T_Wd = width / 2.0; T_Ht = height / 2.0; } /* If width = height = 0, use Wd and Ht as defined above for * the case the n_pos == 0. */ } /* Construct enclosing ellipse */ alpha = atan2(T_Ht, T_Wd); T_Wd = T_Wd / cos(alpha); T_Ht = T_Ht / sin(alpha); } else { ctr.x = ctr.y = 0; } /* Set seed value */ if (T_smode == INIT_RANDOM) local_seed = T_seed; else { #if defined(_WIN32) local_seed = (long)time(NULL); #else local_seed = getpid() ^ time(NULL); #endif } srand48(local_seed); /* If ports, place ports on and nodes within an ellipse centered at origin * with halfwidth Wd and halfheight Ht. * If no ports, place nodes within a rectangle centered at origin * with halfwidth Wd and halfheight Ht. Nodes with a given position * are translated. Wd and Ht are set to contain all positioned points. * The reverse translation will be applied to all * nodes at the end of the layout. * TODO: place unfixed points using adjacent ports or fixed pts. */ if (pp) { while (pp->e) { /* position ports on ellipse */ np = pp->n; ND_pos(np)[0] = T_Wd * cos(pp->alpha) + ctr.x; ND_pos(np)[1] = T_Ht * sin(pp->alpha) + ctr.y; ND_pinned(np) = P_SET; pp++; } for (np = agfstnode(g); np; np = agnxtnode(g, np)) { if (IS_PORT(np)) continue; if (ND_pinned(np)) { ND_pos(np)[0] -= ctr.x; ND_pos(np)[1] -= ctr.y; } else { pointf p = { 0.0, 0.0 }; int cnt = 0; node_t *op; edge_t *ep; for (ep = agfstedge(g, np); ep; ep = agnxtedge(g, ep, np)) { if (aghead(ep) == agtail(ep)) continue; op = aghead(ep) == np ? agtail(ep) : aghead(ep); if (!hasPos(op)) continue; if (cnt) { p.x = (p.x * cnt + ND_pos(op)[0]) / (cnt + 1); p.y = (p.y * cnt + ND_pos(op)[1]) / (cnt + 1); } else { p.x = ND_pos(op)[0]; p.y = ND_pos(op)[1]; } cnt++; } if (cnt > 1) { ND_pos(np)[0] = p.x; ND_pos(np)[1] = p.y; } else if (cnt == 1) { ND_pos(np)[0] = 0.98 * p.x + 0.1 * ctr.x; ND_pos(np)[1] = 0.9 * p.y + 0.1 * ctr.y; } else { double angle = PItimes2 * drand48(); double radius = 0.9 * drand48(); ND_pos(np)[0] = radius * T_Wd * cos(angle); ND_pos(np)[1] = radius * T_Ht * sin(angle); } ND_pinned(np) = P_SET; } } } else { if (n_pos) { /* If positioned nodes */ for (np = agfstnode(g); np; np = agnxtnode(g, np)) { if (ND_pinned(np)) { ND_pos(np)[0] -= ctr.x; ND_pos(np)[1] -= ctr.y; } else { ND_pos(np)[0] = T_Wd * (2.0 * drand48() - 1.0); ND_pos(np)[1] = T_Ht * (2.0 * drand48() - 1.0); } } } else { /* No ports or positions; place randomly */ for (np = agfstnode(g); np; np = agnxtnode(g, np)) { ND_pos(np)[0] = T_Wd * (2.0 * drand48() - 1.0); ND_pos(np)[1] = T_Ht * (2.0 * drand48() - 1.0); } } } return ctr; } /* fdp_tLayout: * Given graph g with ports nodes, layout g respecting ports. * If some node have position information, it may be useful to * reset temperature and other parameters to reflect this. */ void fdp_tLayout(graph_t * g, xparams * xpms) { int i; int reset; bport_t *pp = PORTS(g); double temp; Grid *grid; pointf ctr; Agnode_t *n; reset = init_params(g, xpms); temp = T_T0; ctr = initPositions(g, pp); if (T_useGrid) { grid = mkGrid(agnnodes(g)); adjustGrid(grid, agnnodes(g)); for (i = 0; i < T_loopcnt; i++) { temp = cool(i); gAdjust(g, temp, pp, grid); } delGrid(grid); } else { for (i = 0; i < T_loopcnt; i++) { temp = cool(i); adjust(g, temp, pp); } } if (ctr.x != 0.0 || ctr.y != 0.0) { for (n = agfstnode(g); n; n = agnxtnode(g, n)) { ND_pos(n)[0] += ctr.x; ND_pos(n)[1] += ctr.y; } } if (reset) reset_params(); }