adjust.c   [plain text]

/*
    This software may only be used by you under license from AT&T Corp.
    ("AT&T").  A copy of AT&T's Source Code Agreement is available at
    AT&T's Internet website having the URL:
    <http://www.research.att.com/sw/tools/graphviz/license/source.html>
    If you received this software without first entering into a license
    with AT&T, you have an infringing copy of this software and cannot use
    it without violating AT&T's intellectual property rights.
*/
#pragma prototyped
/* adjust.c
 * Routines for repositioning nodes after initial layout in
 * order to reduce/remove node overlaps.
 */

#include "neato.h"
#include "utils.h"
#include "voronoi.h"
#include "info.h"
#include "edges.h"
#include "site.h"
#include "heap.h"
#include "hedges.h"

static double    margin = 0.05;     /* Create initial bounding box by adding
                                    * margin * dimension around box enclosing
                                    * nodes.
                                    */
static double    incr = 0.05;       /* Increase bounding box by adding
                                    * incr * dimension around box.
                                    */
static double    pmargin = 5.0/POINTS_PER_INCH;  /* Margin around polygons, in inches */
static int      iterations = -1;  /* Number of iterations */
static int      useIter    = 0;   /* Use specified number of iterations */

static int      doAll      = 0;  /* Move all nodes, regardless of overlap */
static Site**   sites;           /* Array of pointers to sites; used in qsort */
static Site**   endSite;         /* Sentinel on sites array */
static Point nw, ne, sw, se;     /* Corners of clipping window */

static Site** nextSite;

static void
setBoundBox (Point* ll, Point* ur)
{
    pxmin = ll->x;
    pxmax = ur->x;
    pymin = ll->y;
    pymax = ur->y;
    nw.x = sw.x = pxmin;
    ne.x = se.x = pxmax;
    nw.y = ne.y = pymax;
    sw.y = se.y = pymin;
}

 /* freeNodes:
  * Free node resources.
  */
static void
freeNodes ()
{
    int          i;
    Info_t*      ip = nodeInfo;

    for (i=0; i < nsites; i++) {
      breakPoly (&ip->poly);
      ip++;
    }
    polyFree ();
    infoinit ();       /* Free vertices */
    free (nodeInfo);
}

/* chkBoundBox:
 *   Compute extremes of graph, then set up bounding box.
 *   If user supplied a bounding box, use that;
 *   else if "window" is a graph attribute, use that; 
 *   otherwise, define bounding box as a percentage expansion of
 *   graph extremes.
 *   In the first two cases, check that graph fits in bounding box.
 */
static void
chkBoundBox (Agraph_t* graph)
{
    char*        marg;
    Point        ll, ur;
    int          i;
    double        x, y;
    double        xmin, xmax, ymin, ymax;
    double        xmn, xmx, ymn, ymx;
    double        ydelta, xdelta;
    Info_t*      ip;
    Poly*        pp;
    /* int          cnt; */

    ip = nodeInfo;
    pp = &ip->poly;
    x = ip->site.coord.x;
    y = ip->site.coord.y;
    xmin = pp->origin.x + x;
    ymin = pp->origin.y + y;
    xmax = pp->corner.x + x;
    ymax = pp->corner.y + y;
    for(i = 1; i < nsites; i++) {
        ip++;
        pp = &ip->poly;
        x = ip->site.coord.x;
        y = ip->site.coord.y;
        xmn = pp->origin.x + x;
        ymn = pp->origin.y + y;
        xmx = pp->corner.x + x;
        ymx = pp->corner.y + y;
        if(xmn < xmin) xmin = xmn;
        if(ymn < ymin) ymin = ymn;
        if(xmx > xmax) xmax = xmx;
        if(ymx > ymax) ymax = ymx;
    }

    marg = agget (graph, "voro_margin");
    if (marg && (*marg != '\0')) {
      margin = atof (marg);
    }
    ydelta = margin * (ymax - ymin);
    xdelta = margin * (xmax - xmin);
    ll.x = xmin - xdelta;
    ll.y = ymin - ydelta;
    ur.x = xmax + xdelta;
    ur.y = ymax + ydelta;

    setBoundBox (&ll, &ur);
}

 /* makeInfo:
  * For each node in the graph, create a Info data structure 
  */
static void
makeInfo(Agraph_t* graph)
{
    Agnode_t*    node;
    int          i;
    Info_t*      ip;
    char*        marg;

    nsites = agnnodes (graph);
    geominit ();

    nodeInfo = N_GNEW(nsites,Info_t);

    node = agfstnode (graph);
    ip = nodeInfo;

#ifdef OLD
    marg = agget (graph, "voro_pmargin");
    if (marg && (*marg != '\0')) {
      pmargin = atof (marg);
    }
#else
    if ((marg = agget(graph,"sep"))) {pmargin = 1.0 + atof(marg);}
    else pmargin = 1.01;
#endif

    for (i = 0; i < nsites; i++) {
        ip->site.coord.x = ND_pos(node)[0];
        ip->site.coord.y = ND_pos(node)[1];

        makePoly (&ip->poly, node, pmargin);

        ip->site.sitenbr = i;
        ip->site.refcnt = 1;
        ip->node = node;
        ip->verts = NULL;
        node = agnxtnode (graph, node);
        ip++;
    }
}

/* sort sites on y, then x, coord */
static int 
scomp(const void *S1, const void *S2)
{
    Site *s1,*s2;

    s1 = *(Site**)S1;
    s2 = *(Site**)S2;
    if(s1 -> coord.y < s2 -> coord.y) return(-1);
    if(s1 -> coord.y > s2 -> coord.y) return(1);
    if(s1 -> coord.x < s2 -> coord.x) return(-1);
    if(s1 -> coord.x > s2 -> coord.x) return(1);
    return(0);
}

 /* sortSites:
  * Fill array of pointer to sites and sort the sites using scomp
  */
static void
sortSites ()
{
    int          i;
    Site**       sp;
    Info_t*      ip;

    if (sites == 0) {
        sites = N_GNEW(nsites, Site*);
        endSite = sites + nsites;
    }

    sp = sites;
    ip = nodeInfo;
    infoinit ();
    for (i=0; i < nsites; i++) {
        *sp++ = &(ip->site);
        ip->verts = NULL;
        ip->site.refcnt = 1;
        ip++;
    }

    qsort(sites, nsites, sizeof (Site *), scomp);

    /* Reset site index for nextOne */
    nextSite = sites;

}

static void
geomUpdate (int doSort)
{
    int      i;

    if (doSort) sortSites ();

    /* compute ranges */
    xmin=sites[0]->coord.x; 
    xmax=sites[0]->coord.x;
    for(i = 1; i < nsites; i++) {
        if(sites[i]->coord.x < xmin) xmin = sites[i]->coord.x;
        if(sites[i]->coord.x > xmax) xmax = sites[i]->coord.x;
    }
    ymin = sites[0]->coord.y;
    ymax = sites[nsites-1]->coord.y;

    deltay = ymax - ymin;
    deltax = xmax - xmin;
}

static 
Site *nextOne()
{
    Site*   s;

    if(nextSite < endSite) {
        s = *nextSite++;
        return (s);
    }
    else
        return((Site *)NULL);
}

/* rmEquality:
 * Check for nodes with identical positions and tweak
 * the positions.
 */
static void
rmEquality ()
{
    int         i, cnt;
    Site**      ip;
    Site**      jp;
    Site**      kp;
    double      xdel;

    sortSites ();
    ip = sites;
    
    while (ip < endSite) {
      jp = ip+1;
      if ((jp >= endSite) || 
          ((*jp)->coord.x != (*ip)->coord.x) ||
          ((*jp)->coord.y != (*ip)->coord.y)) {
        ip = jp;
        continue;
      }

        /* Find first node kp with position different from ip */
      cnt = 2;
      kp = jp+1;
      while ((kp < endSite) &&
          ((*kp)->coord.x == (*ip)->coord.x) &&
          ((*kp)->coord.y == (*ip)->coord.y)) {
        cnt++;
        jp = kp;
        kp = jp+1;
      }

        /* If next node exists and is on the same line */
      if ((kp < endSite) && ((*kp)->coord.y == (*ip)->coord.y)) {
        xdel = ((*kp)->coord.x - (*ip)->coord.x)/cnt;
        i = 1;
        for (jp = ip+1; jp < kp; jp++) {
          (*jp)->coord.x += i*xdel;
          i++;
        }
      }
      else { /* nothing is to the right */
        Info_t*      info;
        for (jp = ip+1; jp < kp; ip++,jp++) {
          info = nodeInfo + (*ip)->sitenbr;
          xdel = info->poly.corner.x - info->poly.origin.x;
          info = nodeInfo + (*jp)->sitenbr;
          xdel += info->poly.corner.x - info->poly.origin.x;
          (*jp)->coord.x = (*ip)->coord.x + xdel/2;
        }
      }
      ip = kp;
    }
}

/* countOverlap:
 * Count number of node-node overlaps at iteration iter.
 */
static int
countOverlap (int iter)
{
    int          count = 0;
    int          i, j;
    Info_t*      ip = nodeInfo;
    Info_t*      jp;

    for (i = 0; i < nsites; i++)
      nodeInfo[i].overlaps = 0;

    for (i = 0; i < nsites-1; i++) {
      jp = ip+1;
      for (j = i+1; j < nsites; j++) {
        if (polyOverlap (ip->site.coord, &ip->poly, jp->site.coord, &jp->poly)){
          count++;
          ip->overlaps = 1;
          jp->overlaps = 1;
        }
        jp++;
      }
      ip++;
    }

    if (Verbose > 1)
      fprintf (stderr, "overlap [%d] : %d\n", iter, count);
    return count;
}

static void
increaseBoundBox ()
{
    double        ydelta, xdelta;
    Point        ll, ur;
    
    ur.x = pxmax;
    ur.y = pymax;
    ll.x = pxmin;
    ll.y = pymin;
    
    ydelta = incr * (ur.y - ll.y);
    xdelta = incr * (ur.x - ll.x);

    ur.x += xdelta;
    ur.y += ydelta;
    ll.x -= xdelta;
    ll.y -= ydelta;

    setBoundBox (&ll, &ur);
}

 /* areaOf:
  * Area of triangle whose vertices are a,b,c
  */
static double
areaOf (Point a,Point b,Point c)
{
    double area;

    area = (double)(fabs(a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y))/2);
    return area;
}

 /* centroidOf:
  * Compute centroid of triangle with vertices a, b, c.
  * Return coordinates in x and y.
  */
static void
centroidOf (Point a,Point b,Point c, double *x, double *y)
{
    *x = (a.x + b.x + c.x)/3;
    *y = (a.y + b.y + c.y)/3;
}

 /* newpos;
  * The new position is the centroid of the
  * voronoi polygon. This is the weighted sum of the
  * centroids of a triangulation, normalized to the
  * total area.
  */
static void
newpos (Info_t* ip)
{
    PtItem*  anchor = ip->verts;
    PtItem   *p, *q;
    double    totalArea = 0.0;
    double    cx = 0.0;
    double    cy = 0.0;
    double    x;
    double    y;
    double    area;

    p = anchor->next;
    q = p->next;
    while(q != NULL) {
      area = areaOf (anchor->p, p->p, q->p);
      centroidOf (anchor->p, p->p, q->p, &x, &y);
      cx = cx + area*x;
      cy = cy + area*y;
      totalArea = totalArea + area;
      p = q;
      q = q->next;
    }

    ip->site.coord.x = cx/totalArea;
    ip->site.coord.y = cy/totalArea;
}

 /* addCorners:
  * Add corners of clipping window to appropriate sites.
  * A site gets a corner if it is the closest site to that corner.
  */
static void
addCorners ()
{
    Info_t    *ip = nodeInfo;
    Info_t    *sws = ip;
    Info_t    *nws = ip;
    Info_t    *ses = ip;
    Info_t    *nes = ip;
    double   swd = dist_2(&ip->site.coord, &sw);
    double   nwd = dist_2(&ip->site.coord, &nw);
    double   sed = dist_2(&ip->site.coord, &se);
    double   ned = dist_2(&ip->site.coord, &ne);
    double   d;
    int     i;
    
    ip++;
    for (i = 1; i < nsites; i++) {
        d = dist_2(&ip->site.coord, &sw);
        if (d < swd) {
            swd = d;
            sws = ip;
        }
        d = dist_2(&ip->site.coord, &se);
        if (d < sed) {
            sed = d;
            ses = ip;
        }
        d = dist_2(&ip->site.coord, &nw);
        if (d < nwd) {
            nwd = d;
            nws = ip;
        }
        d = dist_2(&ip->site.coord, &ne);
        if (d < ned) {
            ned = d;
            nes = ip;
        }
        ip++;
    }

    addVertex (&sws->site, sw.x, sw.y);
    addVertex (&ses->site, se.x, se.y);
    addVertex (&nws->site, nw.x, nw.y);
    addVertex (&nes->site, ne.x, ne.y);
}

 /* newPos:
  * Calculate the new position of a site as the centroid
  * of its voronoi polygon, if it overlaps other nodes.
  * The polygons are finite by being clipped to the clipping
  * window.
  * We first add the corner of the clipping windows to the
  * vertex lists of the appropriate sites.
  */
static void
newPos ()
{
    int      i;
    Info_t*    ip = nodeInfo;

    addCorners ();
    for (i = 0; i < nsites; i++) {
        if (doAll || ip->overlaps) newpos (ip);
        ip++;
    }
}

/* cleanup:
 * Cleanup voronoi memory.
 * Note that PQcleanup and ELcleanup rely on the number
 * of sites, so should at least be reset everytime we use
 * vAdjust.
 * This could be optimized, over multiple components or
 * even multiple graphs, but probably not worth it.
 */
static void
cleanup ()
{
	PQcleanup();
	ELcleanup();
	siteinit();  /* free memory */
	edgeinit();  /* free memory */
}

static int
vAdjust ()
{
    int                iterCnt = 0;
    int                overlapCnt = 0;
    int                badLevel = 0;
    int                increaseCnt = 0;
    int                cnt;

    if (!useIter || (iterations > 0))
      overlapCnt = countOverlap (iterCnt);
    
    if ((overlapCnt == 0) || (iterations == 0))
      return 0;

    rmEquality ();
    geomUpdate (0);
    voronoi(0, nextOne); 
    while (1) {
      newPos ();
      iterCnt++;
      
      if (useIter && (iterCnt == iterations)) break;
      cnt = countOverlap (iterCnt);
      if (cnt == 0) break;
      if (cnt >= overlapCnt) badLevel++;
      else badLevel = 0;
      overlapCnt = cnt;

      switch (badLevel) {
      case 0:
        doAll = 1;
        break;
/*
      case 1:
        doAll = 1;
        break;
*/
      default :
        doAll = 1;
        increaseCnt++;
        increaseBoundBox ();
        break;
      }

      geomUpdate (1);
      voronoi(0, nextOne); 
    }

    if (Verbose) {
      fprintf (stderr, "Number of iterations = %d\n", iterCnt);
      fprintf (stderr, "Number of increases = %d\n", increaseCnt);
    }

	cleanup ();
    return 1;
}

static void
rePos (Point c)
{
    int      i;
    Info_t*    ip = nodeInfo;
    double   f = 1.0 + incr;

  
    for (i = 0; i < nsites; i++) {
      ip->site.coord.x = f*(ip->site.coord.x - c.x) + c.x;
      ip->site.coord.y = f*(ip->site.coord.y - c.y) + c.y;
      ip++;
    }

}

static int
sAdjust ()
{
    int                iterCnt = 0;
    int                overlapCnt = 0;
    int                increaseCnt = 0;
    int                cnt;
    Point              center;

    if (!useIter || (iterations > 0))
      overlapCnt = countOverlap (iterCnt);
    
    if ((overlapCnt == 0) || (iterations == 0))
      return 0;

    rmEquality ();
    center.x =  (pxmin + pxmax)/2.0;
    center.y =  (pymin + pymax)/2.0;
    while (1) {
      rePos (center);
      iterCnt++;
      
      if (useIter && (iterCnt == iterations)) break;
      cnt = countOverlap (iterCnt);
      if (cnt == 0) break;
    }

    if (Verbose) {
      fprintf (stderr, "Number of iterations = %d\n", iterCnt);
      fprintf (stderr, "Number of increases = %d\n", increaseCnt);
    }

    return 1;
}

 /* updateGraph:
  * Enter new node positions into the graph
  */
static void
updateGraph (Agraph_t* graph)
{
    /* Agnode_t*    node; */
    int          i;
    Info_t*        ip;
    /* char         pos[100]; */

    ip = nodeInfo;
    for (i = 0; i < nsites; i++) {
        ND_pos(ip->node)[0] = ip->site.coord.x;
        ND_pos(ip->node)[1] = ip->site.coord.y;
        ip++;
    }
}

static void normalize(graph_t *g)
{
	node_t	*v;
	edge_t	*e;

	double	theta;
	pointf	p;

	if (!mapbool(agget(g,"normalize"))) return;

	v = agfstnode(g); p.x = ND_pos(v)[0]; p.y = ND_pos(v)[1];
	for (v = agfstnode(g); v; v = agnxtnode(g,v))
		{ND_pos(v)[0] -= p.x; ND_pos(v)[1] -= p.y;}

	e = NULL;
	for (v = agfstnode(g); v; v = agnxtnode(g,v))
		if ((e = agfstout(g,v))) break;
	if (e == NULL) return;

	theta = -atan2(ND_pos(e->head)[1] - ND_pos(e->tail)[1],
		ND_pos(e->head)[0] - ND_pos(e->tail)[0]);

	for (v = agfstnode(g); v; v = agnxtnode(g,v)) {
		p.x = ND_pos(v)[0]; p.y = ND_pos(v)[1];
		ND_pos(v)[0] = p.x * cos(theta) - p.y * sin(theta);
		ND_pos(v)[1] = p.x * sin(theta) + p.y * cos(theta);
	}
}

void adjustNodes (graph_t* G)
{
    /* int          userWindow = 0; */
    char*        flag;
    int          doScale = 0;
    int          ret;

	if (agnnodes(G) < 2) return;
    normalize(G);
    flag = agget(G,"overlap");
    if (flag == NULL) return;
	if (!strcasecmp(flag,"scale")) doScale = 1;
    else if (mapbool(flag)) return;

    if (Verbose) fprintf (stderr, "Adjusting nodes using %s\n",
      (doScale ? "scaling" : "Voronoi"));
          /* create main array */
    makeInfo(G);

      /* establish and verify bounding box */
    chkBoundBox (G);

    if (doScale) ret = sAdjust ();
    else ret = vAdjust ();

    if (ret) updateGraph (G);

    freeNodes ();
    free (sites);
	sites = 0;
}