text.mod/graphviz.mod/graphviz/lib/fdpgen/xlayout.c

/*************************************************************************
 * 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 <cgraph/gv_ctype.h>
#include <fdpgen/xlayout.h>
#include <neatogen/adjust.h>
#include <fdpgen/dbg.h>
#include <math.h>

#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);

}