/************************************************************************* * 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 *************************************************************************/ /* xlayout.c: * Written by Emden R. Gansner * * Layout routine to expand initial layout to accommodate node * sizes. */ #ifdef FIX Allow sep to be absolute additive (margin of n points) Increase less between tries #endif /* uses PRIVATE interface */ #define FDP_PRIVATE 1 #include #include #include #include #include #define DFLT_overlap "9:prism" /* default overlap value */ static xparams xParams = { 60, /* numIters */ 0.0, /* T0 */ 0.3, /* K */ 1.5, /* C */ 0 /* loopcnt */ }; static expand_t X_marg; static double WD2(Agnode_t *n) { return X_marg.doAdd ? (ND_width(n) / 2.0 + X_marg.x) : (ND_width(n) * X_marg.x / 2.0); } static double HT2(Agnode_t *n) { return X_marg.doAdd ? (ND_height(n) / 2.0 + X_marg.y) : (ND_height(n) * X_marg.y / 2.0); } #ifdef DEBUG static void pr2graphs(Agraph_t *g0, Agraph_t *g1) { fprintf(stderr,"%s",agnameof(g0)); fprintf(stderr,"(%s)",agnameof(g1)); } #endif static double RAD(Agnode_t * n) { double w = WD2(n); double h = HT2(n); return hypot(w, h); } /* xinit_params: * Initialize local parameters */ static double xinit_params(graph_t *g, int n, xparams *xpms) { (void)g; xParams.K = xpms->K; xParams.numIters = xpms->numIters; xParams.T0 = xpms->T0; xParams.loopcnt = xpms->loopcnt; if (xpms->C > 0.0) xParams.C = xpms->C; const double K2 = xParams.K * xParams.K; if (xParams.T0 == 0.0) xParams.T0 = xParams.K * sqrt(n) / 5; #ifdef DEBUG if (Verbose) { prIndent(); fprintf(stderr, "xLayout "); pr2graphs(g,GORIG(agroot(g))); fprintf(stderr, " : n = %d K = %f T0 = %f loop %d C %f\n", xParams.numIters, xParams.K, xParams.T0, xParams.loopcnt, xParams.C); } #endif return K2; } #define X_T0 xParams.T0 #define X_K xParams.K #define X_numIters xParams.numIters #define X_loopcnt xParams.loopcnt #define X_C xParams.C static double cool(int t) { return X_T0 * (X_numIters - t) / X_numIters; } /* overlap: * Return true if nodes overlap */ static int overlap(node_t * p, node_t * q) { const double xdelta = fabs(ND_pos(q)[0] - ND_pos(p)[0]); const double ydelta = fabs(ND_pos(q)[1] - ND_pos(p)[1]); return xdelta <= WD2(p) + WD2(q) && ydelta <= HT2(p) + HT2(q); } /* cntOverlaps: * Return number of overlaps. */ static int cntOverlaps(graph_t * g) { int cnt = 0; for (node_t *p = agfstnode(g); p; p = agnxtnode(g, p)) { for (node_t *q = agnxtnode(g, p); q; q = agnxtnode(g, q)) { cnt += overlap(p, q); } } return cnt; } /* doRep: * Return 1 if nodes overlap */ static int doRep(node_t *p, node_t *q, double xdelta, double ydelta, double dist2, double X_ov, double X_nonov) { int ov; double force; while (dist2 == 0.0) { xdelta = 5 - rand() % 10; ydelta = 5 - rand() % 10; dist2 = xdelta * xdelta + ydelta * ydelta; } if ((ov = overlap(p, q))) force = X_ov / dist2; else force = X_nonov / dist2; #ifdef DEBUG if (Verbose == 4) { prIndent(); const double dist = sqrt(dist2); fprintf(stderr, " ov Fr %f dist %f\n", force * dist, dist); } #endif DISP(q)[0] += xdelta * force; DISP(q)[1] += ydelta * force; DISP(p)[0] -= xdelta * force; DISP(p)[1] -= ydelta * force; return ov; } /* applyRep: * Repulsive force = (K*K)/d * Return 1 if nodes overlap */ static int applyRep(Agnode_t *p, Agnode_t *q, double X_ov, double X_nonov) { const double xdelta = ND_pos(q)[0] - ND_pos(p)[0]; const double ydelta = ND_pos(q)[1] - ND_pos(p)[1]; return doRep(p, q, xdelta, ydelta, xdelta * xdelta + ydelta * ydelta, X_ov, X_nonov); } static void applyAttr(Agnode_t * p, Agnode_t * q) { if (overlap(p, q)) { #ifdef DEBUG if (Verbose == 4) { prIndent(); fprintf(stderr, "ov 1 Fa 0 din %f\n", RAD(p) + RAD(q)); } #endif return; } const double xdelta = ND_pos(q)[0] - ND_pos(p)[0]; const double ydelta = ND_pos(q)[1] - ND_pos(p)[1]; const double dist = hypot(xdelta, ydelta); const double din = RAD(p) + RAD(q); const double dout = dist - din; const double force = dout * dout / ((X_K + din) * dist); #ifdef DEBUG if (Verbose == 4) { prIndent(); fprintf(stderr, " ov 0 Fa %f din %f \n", force * dist, din); } #endif DISP(q)[0] -= xdelta * force; DISP(q)[1] -= ydelta * force; DISP(p)[0] += xdelta * force; DISP(p)[1] += ydelta * force; } /* adjust: * Return 0 if definitely no overlaps. * Return non-zero if we had overlaps before most recent move. */ static int adjust(Agraph_t *g, double temp, double X_ov, double X_nonov) { int overlaps = 0; #ifdef DEBUG if (Verbose == 4) fprintf(stderr, "=================\n"); #endif for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) { DISP(n)[0] = DISP(n)[1] = 0; } for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) { int ov; for (Agnode_t *n1 = agnxtnode(g, n); n1; n1 = agnxtnode(g, n1)) { ov = applyRep(n, n1, X_ov, X_nonov); overlaps += ov; } for (Agedge_t *e = agfstout(g, n); e; e = agnxtout(g, e)) { applyAttr(n,aghead(e)); } } if (overlaps == 0) return 0; const double temp2 = temp * temp; for (Agnode_t *n = agfstnode(g); n; n = agnxtnode(g, n)) { if (ND_pinned(n) == P_PIN) continue; const double disp[] = {DISP(n)[0], DISP(n)[1]}; // incremental displacement const double len2 = disp[0] * disp[0] + disp[1] * disp[1]; if (len2 < temp2) { ND_pos(n)[0] += disp[0]; ND_pos(n)[1] += disp[1]; } else { /* to avoid sqrt, consider abs(x) + abs(y) */ const double len = sqrt(len2); ND_pos(n)[0] += disp[0] * temp / len; ND_pos(n)[1] += disp[1] * temp / len; } } return overlaps; } /* x_layout: * Given graph g with initial layout, adjust g so that nodes * do not overlap. * Assume g is connected. * g may have ports. At present, we do not use ports in the layout * at this stage. * Returns non-zero if overlaps still exist. * TODO (possible): * Allow X_T0 independent of T_TO or percentage of, so the cooling would * be piecewise linear. This would allow longer, cooler expansion. * In tries > 1, increase X_T0 and/or lengthen cooling */ static int x_layout(graph_t * g, xparams * pxpms, int tries) { int nnodes = agnnodes(g); int nedges = agnedges(g); X_marg = sepFactor (g); if (X_marg.doAdd) { X_marg.x = PS2INCH(X_marg.x); /* sepFactor is in points */ X_marg.y = PS2INCH(X_marg.y); } int ov = cntOverlaps(g); if (ov == 0) return 0; xparams xpms = *pxpms; const double K = xpms.K; for (int try = 0; ov && try < tries; ++try) { const double K2 = xinit_params(g, nnodes, &xpms); const double X_ov = X_C * K2; const double X_nonov = nedges * X_ov * 2.0 / (nnodes * (nnodes - 1)); #ifdef DEBUG if (Verbose) { prIndent(); fprintf(stderr, "try %d (%d): %d overlaps on ", try, tries, ov); pr2graphs(g,GORIG(agroot(g))); fprintf(stderr," \n"); } #endif for (int i = 0; i < X_loopcnt; i++) { const double temp = cool(i); if (temp <= 0.0) break; ov = adjust(g, temp, X_ov, X_nonov); if (ov == 0) break; } xpms.K += K; /* increase distance */ } #ifdef DEBUG if (Verbose && ov) fprintf(stderr, "Warning: %d overlaps remain on ", ov); pr2graphs(g,GORIG(agroot(g))); fprintf(stderr,"\n"); #endif return ov; } /* fdp_xLayout: * Use overlap parameter to determine if and how to remove overlaps. * In addition to the usual values accepted by removeOverlap, overlap * can begin with "n:" to indicate the given number of tries using * x_layout to remove overlaps. * Thus, * NULL or "" => dflt overlap * "mode" => "0:mode", i.e. removeOverlap with mode only * "true" => "0:true", i.e., no overlap removal * "n:" => n tries only * "n:mode" => n tries, then removeOverlap with mode * "0:" => no overlap removal */ void fdp_xLayout(graph_t * g, xparams * xpms) { int tries; char* ovlp = agget (g, "overlap"); char* cp; char* rest; if (Verbose) { #ifdef DEBUG prIndent(); #endif fprintf (stderr, "xLayout "); } if (!ovlp || *ovlp == '\0') { ovlp = DFLT_overlap; } /* look for optional ":" or "number:" */ if ((cp = strchr(ovlp, ':')) && (cp == ovlp || gv_isdigit(*ovlp))) { cp++; rest = cp; tries = atoi (ovlp); if (tries < 0) tries = 0; } else { tries = 0; rest = ovlp; } if (Verbose) { #ifdef DEBUG prIndent(); #endif fprintf (stderr, "tries = %d, mode = %s\n", tries, rest); } if (tries && !x_layout(g, xpms, tries)) return; removeOverlapAs(g, rest); }