/*
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
/* Module for packing disconnected graphs together.
* Based on "Disconnected Graph Layout and the Polyomino Packing Approach",
* K. Freivalds et al., GD0'01, LNCS 2265, pp. 378-391.
*/
#include <stdlib.h>
#include <pointset.h>
#include <neatoprocs.h>
#include <pack.h>
#include <math.h>
#define C 100 /* Max. avg. polyomino size */
#define MOVEPT(p) ((p).x += dx, (p).y += dy)
#define GRID(x,s) (((x) + ((s)-1)) / (s))
#define CELL(p,s) ((p).x = (p).x/(s), (p).y = ((p).y/(s)))
#define SGN(a) (((a)<0)? -1 : 1)
typedef struct {
Agraph_t* graph; /* related graph */
int perim; /* half size of bounding rectangle perimeter */
point* cells; /* cells in covering polyomino */
int nc; /* no. of cells */
int index; /* index in original array */
} ginfo;
/* computeStep:
* Compute grid step size. This is a root of the
* quadratic equation al^2 +bl + c, where a, b and
* c are defined below.
*/
static int
computeStep (int ng, Agraph_t** gs, int margin)
{
double l1, l2;
double a, b, c, d, r;
double W, H; /* width and height of graph, with margin */
Agraph_t* g;
int i;
a = C*ng - 1;
c = 0;
b = 0;
for (i=0;i<ng;i++) {
g = gs[i];
W = GD_bb(g).UR.x - GD_bb(g).LL.x + 2*margin;
H = GD_bb(g).UR.y - GD_bb(g).LL.y + 2*margin;
b -= (W + H);
c -= (W * H);
}
d = b*b - 4.0*a*c;
if (d < 0) {
agerr (AGERR, "libpack: disc = %f ( < 0)\n", d);
return -1;
}
r = sqrt (d);
l1 = (-b + r)/(2*a);
l2 = (-b - r)/(2*a);
if (Verbose > 2) {
fprintf (stderr, "Packing: compute grid size\n");
fprintf (stderr, "a %f b %f c %f d %f r %f\n", a, b, c,d,r);
fprintf (stderr, "root %d (%f) %d (%f)\n", (int)l1, l1, (int)l2, l2);
fprintf (stderr, " r1 %f r2 %f\n", a*l1*l1 + b*l1 + c, a*l2*l2 + b*l2 +c);
}
return (int)l1;
}
/* cmpf;
* Comparison function for polyominoes.
* Size is determined by perimeter.
*/
static int
cmpf (const void* X, const void* Y)
{
ginfo* x = *(ginfo**)X;
ginfo* y = *(ginfo**)Y;
/* flip order to get descending array */
return (y->perim - x->perim);
}
/* fillLine:
* Mark cells crossed by line from cell p to cell q.
* Bresenham's algorithm, from Graphics Gems I, pp. 99-100.
*/
/* static */
void
fillLine (point p, point q, PointSet* ps)
{
int x1 = p.x;
int y1 = p.y;
int x2 = q.x;
int y2 = q.y;
int d, x, y, ax, ay, sx, sy, dx, dy;
dx = x2-x1; ax = ABS(dx)<<1; sx = SGN(dx);
dy = y2-y1; ay = ABS(dy)<<1; sy = SGN(dy);
/* fprintf (stderr, "fillLine %d %d - %d %d\n", x1,y1,x2,y2); */
x = x1;
y = y1;
if (ax>ay) { /* x dominant */
d = ay-(ax>>1);
for (;;) {
/* fprintf (stderr, " addPS %d %d\n", x,y); */
addPS(ps,x, y);
if (x==x2) return;
if (d>=0) {
y += sy;
d -= ax;
}
x += sx;
d += ay;
}
}
else { /* y dominant */
d = ax-(ay>>1);
for (;;) {
/* fprintf (stderr, " addPS %d %d\n", x,y); */
addPS(ps, x, y);
if (y==y2) return;
if (d>=0) {
x += sx;
d -= ay;
}
y += sy;
d += ax;
}
}
}
/* fillEdge:
* It appears that spline_edges always have the start point at the
* beginning and the end point at the end.
*/
static void
fillEdge (Agedge_t* e, point pt, PointSet* ps, int dx, int dy,
int ssize, boolean doS)
{
int j, k;
bezier bz;
point hpt;
Agnode_t* h;
/* If doS is false or the edge has not splines, use line segment */
if (!doS || !ED_spl(e)) {
h = e->head;
hpt = coord(h);
MOVEPT(hpt);
CELL(hpt,ssize);
fillLine (pt,hpt,ps);
return;
}
for (j = 0; j < ED_spl(e)->size; j++) {
bz = ED_spl(e)->list[j];
if (bz.sflag){
pt = bz.sp;
hpt = bz.list[0];
k = 1;
}
else {
pt = bz.list[0];
hpt = bz.list[1];
k = 2;
}
MOVEPT(pt); CELL(pt,ssize);
MOVEPT(hpt); CELL(hpt,ssize);
fillLine (pt,hpt,ps);
for (; k < bz.size; k++) {
pt = hpt;
hpt = bz.list[k];
MOVEPT(hpt); CELL(hpt,ssize);
fillLine (pt,hpt,ps);
}
if (bz.eflag) {
pt = hpt;
hpt = bz.ep;
MOVEPT(hpt); CELL(hpt,ssize);
fillLine (pt,hpt,ps);
}
}
}
/* genBox:
* Generate polyomino info from graph using the bounding box of
* the graph.
*/
static void
genBox (Agraph_t* g, ginfo* info, int ssize, int margin, point center)
{
PointSet* ps;
int W, H;
point UR, LL;
box bb = GD_bb(g);
int x,y;
ps = newPS();
LL.x = center.x - margin;
LL.y = center.y - margin;
UR.x = center.x + bb.UR.x - bb.LL.x + margin;
UR.y = center.y + bb.UR.y - bb.LL.y + margin;
CELL (LL,ssize);
CELL (UR,ssize);
for (x = LL.x; x <= UR.x; x++)
for (y = LL.y; y <= UR.y; y++)
addPS(ps,x,y);
info->graph = g;
info->cells = pointsOf(ps);
info->nc = sizeOf(ps);
W = GRID(bb.UR.x - bb.LL.x + 2*margin,ssize);
H = GRID(bb.UR.y - bb.LL.y + 2*margin,ssize);
info->perim = W + H;
if (Verbose > 2) {
int i;
fprintf (stderr, "%s no. cells %d W %d H %d\n", g->name, info->nc, W, H);
for (i = 0; i < info->nc; i++)
fprintf (stderr, " %d %d cell\n", info->cells[i].x, info->cells[i].y);
}
freePS(ps);
}
/* genPoly:
* Generate polyomino info from graph.
* We add all cells covered partially by the bounding box of the
* node. If doSplines is true and an edge has a spline, we use the
* polyline determined by the control point. Otherwise,
* we use each cell crossed by a straight edge between the head and tail.
* If mode = l_clust, we use the graph's GD_clust array to treat the
* top level clusters like large nodes.
* Returns 0 if okay.
*/
static int
genPoly (Agraph_t* root, Agraph_t* g, ginfo* info,
int ssize, pack_info* pinfo, point center)
{
PointSet* ps;
int W, H;
point LL, UR;
point pt, s2;
Agraph_t* eg; /* graph containing edges */
Agnode_t* n;
Agedge_t* e;
int x,y;
int dx,dy;
graph_t* subg;
int margin = pinfo->margin;
int doSplines = pinfo->doSplines;
box bb;
if (root) eg = root;
else eg = g;
ps = newPS();
dx = center.x - GD_bb(g).LL.x;
dy = center.y - GD_bb(g).LL.y;
if (pinfo->mode == l_clust) {
int i;
void** alg;
/* backup the alg data */
alg = N_GNEW(agnnodes(g), void*);
for (i = 0, n = agfstnode(g); n; n = agnxtnode(g,n)) {
alg[i++] = n->u.alg;
n->u.alg = 0;
}
/* do bbox of top clusters */
for (i = 1; i <= GD_n_cluster(g); i++) {
subg = GD_clust(g)[i];
bb = GD_bb(subg);
if ((bb.UR.x > bb.LL.x) && (bb.UR.y > bb.LL.y)) {
MOVEPT(bb.LL);
MOVEPT(bb.UR);
bb.LL.x -= margin;
bb.LL.y -= margin;
bb.UR.x += margin;
bb.UR.y += margin;
CELL (bb.LL,ssize);
CELL (bb.UR,ssize);
for (x = bb.LL.x; x <= bb.UR.x; x++)
for (y = bb.LL.y; y <= bb.UR.y; y++)
addPS(ps,x,y);
/* note which nodes are in clusters */
for (n = agfstnode(subg); n; n = agnxtnode(subg,n))
ND_clust(n) = subg;
}
}
/* now do remaining nodes and edges */
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
pt = coord(n);
MOVEPT(pt);
if (!ND_clust(n)) { /* n is not in a top-level cluster */
s2.x = margin + ND_xsize(n)/2; s2.y = margin + ND_ysize(n)/2;
LL = sub_points(pt,s2);
UR = add_points(pt,s2);
CELL (LL,ssize);
CELL (UR,ssize);
for (x = LL.x; x <= UR.x; x++)
for (y = LL.y; y <= UR.y; y++)
addPS(ps,x,y);
CELL(pt,ssize);
for (e = agfstout(eg,n); e; e = agnxtout(eg,e)) {
fillEdge (e, pt, ps, dx, dy, ssize, doSplines);
}
}
else {
CELL(pt,ssize);
for (e = agfstout(eg,n); e; e = agnxtout(eg,e)) {
if (ND_clust(n) == ND_clust(e->head)) continue;
fillEdge (e, pt, ps, dx, dy, ssize, doSplines);
}
}
}
/* restore the alg data */
for (i = 0, n = agfstnode(g); n; n = agnxtnode(g,n)) {
n->u.alg = alg[i++];
}
free(alg);
}
else for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
pt = coord(n);
MOVEPT(pt);
s2.x = margin + ND_xsize(n)/2; s2.y = margin + ND_ysize(n)/2;
LL = sub_points(pt,s2);
UR = add_points(pt,s2);
CELL (LL,ssize);
CELL (UR,ssize);
for (x = LL.x; x <= UR.x; x++)
for (y = LL.y; y <= UR.y; y++)
addPS(ps,x,y);
CELL(pt,ssize);
for (e = agfstout(eg,n); e; e = agnxtout(eg,e)) {
fillEdge (e, pt, ps, dx, dy, ssize, doSplines);
}
}
info->graph = g;
info->cells = pointsOf(ps);
info->nc = sizeOf(ps);
W = GRID(GD_bb(g).UR.x - GD_bb(g).LL.x + 2*margin,ssize);
H = GRID(GD_bb(g).UR.y - GD_bb(g).LL.y + 2*margin,ssize);
info->perim = W + H;
if (Verbose > 2) {
int i;
fprintf (stderr, "%s no. cells %d W %d H %d\n", g->name, info->nc, W, H);
for (i = 0; i < info->nc; i++)
fprintf (stderr, " %d %d cell\n", info->cells[i].x, info->cells[i].y);
}
freePS(ps);
return 0;
}
/* fits:
* Check if polyomino fits at given point.
* If so, add cells to pointset, store point in place and return true.
*/
static int
fits (int x, int y, ginfo* info, PointSet* ps, point* place, int step)
{
point* cells = info->cells;
int n = info->nc;
point cell;
int i;
point LL;
for (i=0; i < n; i++) {
cell = *cells;
cell.x += x;
cell.y += y;
if (inPS(ps,cell)) return 0;
cells++;
}
LL = GD_bb(info->graph).LL;
place->x = step*x - LL.x;
place->y = step*y - LL.y;
cells = info->cells;
for (i=0; i < n; i++) {
cell = *cells;
cell.x += x;
cell.y += y;
insertPS(ps,cell);
cells++;
}
if (Verbose >= 2)
fprintf (stderr, "cc (%d cells) at (%d,%d)\n", n, place->x, place->y);
return 1;
}
/* placeFixed:
* Position fixed graph. Store final translation and
* fill polyomino set. Note that polyomino set for the
* graph is constructed where it will be.
*/
static void
placeFixed (ginfo* info, PointSet* ps, point* place, point center)
{
point* cells = info->cells;
int n = info->nc;
int i;
place->x = - center.x;
place->y = - center.y;
for (i=0; i < n; i++) {
insertPS(ps,*cells++);
}
if (Verbose >= 2)
fprintf (stderr, "cc (%d cells) at (%d,%d)\n", n, place->x, place->y);
}
/* placeGraph:
* Search for points on concentric "circles" out
* from the origin. Check if polyomino can be placed
* with bounding box origin at point.
* First graph (i == 0) is centered on the origin if possible.
*/
static void
placeGraph (int i, ginfo* info, PointSet* ps, point* place, int step, int margin)
{
int x,y;
int W,H;
int bnd;
if (i == 0) {
Agraph_t* g = info->graph;
W = GRID(GD_bb(g).UR.x - GD_bb(g).LL.x + 2*margin,step);
H = GRID(GD_bb(g).UR.y - GD_bb(g).LL.y + 2*margin,step);
if (fits(-W/2,-H/2,info,ps,place,step)) return;
}
if (fits(0,0,info,ps,place,step)) return;
W = GD_bb(info->graph).UR.x - GD_bb(info->graph).LL.x;
H = GD_bb(info->graph).UR.y - GD_bb(info->graph).LL.y;
if (W >= H) {
for (bnd = 1; ; bnd++) {
x = 0;
y = -bnd;
for (; x < bnd; x++)
if (fits(x,y,info,ps,place,step)) return;
for (; y < bnd; y++)
if (fits(x,y,info,ps,place,step)) return;
for (; x > -bnd; x--)
if (fits(x,y,info,ps,place,step)) return;
for (; y > -bnd; y--)
if (fits(x,y,info,ps,place,step)) return;
for (; x < 0; x++)
if (fits(x,y,info,ps,place,step)) return;
}
}
else {
for (bnd = 1; ; bnd++) {
y = 0;
x = -bnd;
for (; y > -bnd; y--)
if (fits(x,y,info,ps,place,step)) return;
for (; x < bnd; x++)
if (fits(x,y,info,ps,place,step)) return;
for (; y < bnd; y++)
if (fits(x,y,info,ps,place,step)) return;
for (; x > -bnd; x--)
if (fits(x,y,info,ps,place,step)) return;
for (; y > 0; y--)
if (fits(x,y,info,ps,place,step)) return;
}
}
}
#ifdef DEBUG
void
dumpp (ginfo* info, char* pfx)
{
point* cells = info->cells;
int i, c_cnt = info->nc;
fprintf (stderr, "%s\n", pfx);
for (i = 0; i < c_cnt; i++) {
fprintf (stderr, "%d %d box\n", cells[i].x, cells[i].y);
}
}
#endif
/* putGraphs:
* Given a collection of graphs, reposition them in the plane
* to not overlap but pack "nicely".
* ng is the number of graphs
* gs is a pointer to an array of graph pointers
* root gives the graph containing the edges; if null, the function
* looks in each graph in gs for its edges
* pinfo->margin gives the amount of extra space left around nodes in points
* If pinfo->doSplines is true, use edge splines, if computed,
* in calculating polyomino.
* pinfo->mode specifies the packing granularity and technique:
* l_node : pack at the node/cluster level
* l_graph : pack at the bounding box level
* Returns array of points to which graphs should be translated;
* the array needs to be freed;
* Returns NULL if problem occur or if ng == 0.
*
* Depends on graph fields bb, node fields pos, xsize and ysize, and
* edge field spl.
*/
point*
putGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* pinfo)
{
int stepSize;
ginfo* info;
ginfo** sinfo;
point* places;
Dict_t* ps;
int i;
boolean* fixed = pinfo->fixed;
int fixed_cnt = 0;
box fixed_bb;
point center;
if (ng <= 0) return 0;
/* update bounding box info for each graph */
/* If fixed, compute bbox of fixed graphs */
for (i = 0; i < ng; i++) {
Agraph_t* g = gs[i];
neato_compute_bb (g);
if (fixed && fixed[i]) {
if (fixed_cnt) {
box bb = GD_bb(g);
fixed_bb.LL.x = MIN(bb.LL.x, fixed_bb.LL.x);
fixed_bb.LL.y = MIN(bb.LL.y, fixed_bb.LL.y);
fixed_bb.UR.x = MAX(bb.UR.x, fixed_bb.UR.x);
fixed_bb.UR.y = MAX(bb.UR.y, fixed_bb.UR.y);
}
else fixed_bb = GD_bb(g);
fixed_cnt++;
}
if (Verbose > 2) {
fprintf (stderr, "bb[%s] %d %d %d %d\n", g->name, GD_bb(g).LL.x,
GD_bb(g).LL.y, GD_bb(g).UR.x, GD_bb(g).UR.y);
}
}
/* calculate grid size */
stepSize = computeStep (ng, gs, pinfo->margin);
if (stepSize < 0) return 0;
/* generate polyomino cover for the graphs */
if (fixed) {
center.x = (fixed_bb.LL.x + fixed_bb.UR.x)/2;
center.y = (fixed_bb.LL.y + fixed_bb.UR.y)/2;
}
else center.x = center.y = 0;
info = N_NEW(ng, ginfo);
for (i=0; i < ng; i++) {
info[i].index = i;
if (pinfo->mode == l_graph)
genBox (gs[i], info+i, stepSize, pinfo->margin, center);
else if (genPoly (root, gs[i], info+i, stepSize, pinfo, center)) {
return 0;
}
}
/* sort */
sinfo = N_NEW(ng, ginfo*);
for (i=0; i < ng; i++) {
sinfo[i] = info + i;
}
qsort(sinfo,ng,sizeof(ginfo*),cmpf);
ps = newPS ();
places = N_NEW(ng, point);
if (fixed) {
for (i=0; i < ng; i++) {
if (fixed[i])
placeFixed (sinfo[i], ps, places+(sinfo[i]->index), center);
}
for (i=0; i < ng; i++) {
if (!fixed[i])
placeGraph (i, sinfo[i], ps, places+(sinfo[i]->index),
stepSize, pinfo->margin);
}
}
else {
for (i=0; i < ng; i++)
placeGraph (i, sinfo[i], ps, places+(sinfo[i]->index),
stepSize, pinfo->margin);
}
free (sinfo);
for (i=0; i < ng; i++)
free (info[i].cells);
free (info);
freePS (ps);
if (Verbose > 1)
for (i=0; i < ng; i++)
fprintf (stderr, "pos[%d] %d %d\n", i, places[i].x, places[i].y);
return places;
}
/* shiftEdge:
* Translate all of the edge components by the given offset.
*/
static void
shiftEdge (Agedge_t* e, int dx, int dy)
{
int j,k;
bezier bz;
if (ED_label(e)) MOVEPT(ED_label(e)->p);
if (ED_head_label(e)) MOVEPT(ED_head_label(e)->p);
if (ED_tail_label(e)) MOVEPT(ED_tail_label(e)->p);
if (ED_spl(e) == NULL)
return;
for (j = 0; j < ED_spl(e)->size; j++) {
bz = ED_spl(e)->list[j];
for (k = 0; k < bz.size; k++)
MOVEPT(bz.list[k]);
if (bz.sflag)
MOVEPT(ED_spl(e)->list[j].sp);
if (bz.eflag)
MOVEPT(ED_spl(e)->list[j].ep);
}
}
/* shiftGraph:
*/
static void
shiftGraph (Agraph_t* g, int dx, int dy)
{
graph_t* subg;
box bb = GD_bb(g);
int i;
bb.LL.x += dx;
bb.UR.x += dx;
bb.LL.y += dy;
bb.UR.y += dy;
GD_bb(g) = bb;
if (GD_label(g)) MOVEPT(GD_label(g)->p);
for (i = 1; i <= GD_n_cluster(g); i++) {
subg = GD_clust(g)[i];
shiftGraph (subg, dx, dy);
}
}
/* shiftGraphs:
* Uses points computed from putGraphs to shift points, edges and clusters.
* Always shifts pos.
* If doSplines is true, assumes node position is also in coord,
* and edges and edge labels have been placed, so it shifts those.
* If root is non-null, it is used to find edges.
*
* Depends on graph field bb, node field pos and coord, and edge field spl.
* as well as labels in graphs and edges
*/
int
shiftGraphs (int ng, Agraph_t** gs, point* pp, Agraph_t* root, int doSplines)
{
int i;
int dx, dy;
double fx, fy;
point p;
Agraph_t* g;
Agraph_t* eg;
Agnode_t* n;
Agedge_t* e;
if (ng <= 0) return abs(ng);
for (i = 0; i < ng; i++) {
g = gs[i];
if (root) eg = root;
else eg = g;
p = pp[i];
dx = p.x;
dy = p.y;
fx = PS2INCH(dx);
fy = PS2INCH(dy);
for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
ND_pos(n)[0] += fx;
ND_pos(n)[1] += fy;
if (doSplines) {
MOVEPT(ND_coord_i(n));
for (e = agfstout(eg,n); e; e = agnxtout(eg,e)) shiftEdge(e,dx,dy);
}
}
shiftGraph (g, dx, dy);
}
return 0;
}
/* packGraphs:
* Packs graphs.
* ng - number of graphs
* gs - pointer to array of graphs
* root - graph used to find edges
* info - parameters used in packing
* info->doSplines - if true, use already computed spline control points
* This decides where to layout the graphs and repositions the graph's
* position info.
*
* Returns 0 on success.
*/
int
packGraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* info)
{
int ret;
point* pp = putGraphs (ng, gs, root, info);
if (!pp) return 1;
ret = shiftGraphs(ng, gs, pp, root, info->doSplines);
free (pp);
return ret;
}
/* packSubgraphs:
* Packs subgraphs of given root graph, then recalculates root's bounding
* box.
* Note that it does not recompute subgraph bounding boxes.
* Cluster bounding boxes are recomputed in shiftGraphs.
*/
int
packSubgraphs (int ng, Agraph_t** gs, Agraph_t* root, pack_info* info)
{
int ret;
ret = packGraphs (ng,gs,root,info);
if (ret == 0) neato_compute_bb (root);
return ret;
}
/* getPackMode;
* Return pack_mode of graph using "packmode" attribute.
* If not defined, return dflt
*/
pack_mode
getPackMode (Agraph_t* g, pack_mode dflt)
{
char* p = agget (g, "packmode");
pack_mode mode = dflt;
if (p && *p) {
switch (*p) {
#ifdef NOT_IMPLEMENTED
case 'b' :
if (streq(p,"bisect")) mode = l_bisect;
break;
#endif
case 'c' :
if (streq(p,"cluster")) mode = l_clust;
break;
case 'g' :
if (streq(p,"graph")) mode = l_graph;
break;
#ifdef NOT_IMPLEMENTED
case 'h' :
if (streq(p,"hull")) mode = l_hull;
break;
#endif
case 'n' :
if (streq(p,"node")) mode = l_node;
break;
#ifdef NOT_IMPLEMENTED
case 't' :
if (streq(p,"tile")) mode = l_tile;
break;
#endif
}
}
return mode;
}
/* getPack;
* Return "pack" attribute of g.
* If not defined or negative, return not_def.
* If defined but not specified, return dflt.
*/
int
getPack (Agraph_t* g, int not_def, int dflt)
{
char *p;
int i;
int v = not_def;
if ((p = agget(g,"pack"))) {
if ((sscanf(p,"%d",&i) == 1) && (i >= 0)) v = i;
else if ((*p == 't') || (*p == 'T')) v = dflt;
}
return v;
}
|
