pack.c

Go to the documentation of this file.

/*************************************************************************
 * 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
 *************************************************************************/
 
 
/* 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 <math.h>
#include <assert.h>
#include <cgraph/alloc.h>
#include <cgraph/prisize_t.h>
#include <cgraph/sort.h>
#include <cgraph/startswith.h>
#include <cgraph/streq.h>
#include <common/render.h>
#include <pack/pack.h>
#include <common/pointset.h>
#include <stdbool.h>
#include <stddef.h>
 
#define C 100                   /* Max. avg. polyomino size */
 
#define MOVEPT(p) ((p).x += dx, (p).y += dy)
/* Given cell size s, GRID(x:double,s:int) returns how many cells are required by size x */
#define GRID(x,s) ((int)ceil((x)/(s)))
/* Given grid cell size s, CVAL(v:int,s:int) returns index of cell containing point v */
#define CVAL(v,s) ((v) >= 0 ? (v)/(s) : (((v)+1)/(s))-1)
/* Given grid cell size s, CELL(p:point,s:int) sets p to cell containing point p */
#define CELL(p,s) ((p).x = CVAL((p).x,s), (p).y = CVAL((p).y,(s)))
 
typedef struct {
    int perim;                  /* half size of bounding rectangle perimeter */
    pointf *cells;              
    int nc;                     /* no. of cells */
    size_t index; 
} ginfo;
 
typedef struct {
    double width, height;
    size_t index; 
} ainfo;
 
/* 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(size_t ng, boxf *bbs, unsigned int margin) {
    double l1, l2;
    double a, b, c, d, r;
    double W, H;                /* width and height of graph, with margin */
    int root;
 
    a = C * (double)ng - 1;
    c = 0;
    b = 0;
    for (size_t i = 0; i < ng; i++) {
        boxf bb = bbs[i];
        W = bb.UR.x - bb.LL.x + 2 * margin;
        H = bb.UR.y - bb.LL.y + 2 * margin;
        b -= (W + H);
        c -= (W * H);
    }
    d = b * b - 4.0 * a * c;
    if (d < 0) {
        agerrorf("libpack: disc = %f ( < 0)\n", d);
        return -1;
    }
    r = sqrt(d);
    l1 = (-b + r) / (2 * a);
    l2 = (-b - r) / (2 * a);
    root = (int) l1;
    if (root == 0) root = 1;
    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", root, l1, (int) l2,
                l2);
        fprintf(stderr, " r1 %f r2 %f\n", a * l1 * l1 + b * l1 + c,
                a * l2 * l2 + b * l2 + c);
    }
 
    return root;
}
 
/* Comparison function for polyominoes.
 * Size is determined by perimeter.
 */
static int cmpf(const void *X, const void *Y)
{
    const ginfo *x = *(ginfo *const *) X;
    const ginfo *y = *(ginfo *const *) Y;
    /* flip order to get descending array */
    if (y->perim < x->perim) {
        return -1;
    }
    if (y->perim > x->perim) {
      return 1;
    }
    return 0;
}
 
static int sgn(int x) {
  return x > 0 ? 1 : -1;
}
 
/* Mark cells crossed by line from cell p to cell q.
 * Bresenham's algorithm, from Graphics Gems I, pp. 99-100.
 */
static void fillLine(pointf p, pointf q, PointSet * ps)
{
    int x1 = ROUND(p.x);
    int y1 = ROUND(p.y);
    int x2 = ROUND(q.x);
    int y2 = ROUND(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);
 
    x = x1;
    y = y1;
    if (ax > ay) {              /* x dominant */
        d = ay - (ax >> 1);
        for (;;) {
            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 (;;) {
            addPS(ps, x, y);
            if (y == y2)
                return;
            if (d >= 0) {
                x += sx;
                d -= ay;
            }
            y += sy;
            d += ax;
        }
    }
}
 
/* 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, pointf p, PointSet *ps, double dx, double dy,
         int ssize, bool doS) {
    size_t k;
    bezier bz;
    pointf pt, hpt;
    Agnode_t *h;
 
    pt = p;
 
    /* If doS is false or the edge has not splines, use line segment */
    if (!doS || !ED_spl(e)) {
        h = aghead(e);
        hpt = coord(h);
        MOVEPT(hpt);
        CELL(hpt, ssize);
        fillLine(pt, hpt, ps);
        return;
    }
 
    for (size_t 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);
        }
    }
 
}
 
/* Generate polyomino info from graph using the bounding box of
 * the graph.
 */
static void genBox(boxf bb0, ginfo *info, int ssize, unsigned int margin,
                   pointf center, char *s) {
    PointSet *ps;
    int W, H;
    pointf UR, LL;
    boxf bb;
    double x, y;
 
    bb = bb0;
    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->cells = pointsOf(ps);
    info->nc = sizeOf(ps);
    W = GRID(bb0.UR.x - bb0.LL.x + 2 * margin, ssize);
    H = GRID(bb0.UR.y - bb0.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",
                s, info->nc, W, H);
        for (i = 0; i < info->nc; i++)
            fprintf(stderr, "  %.0f %.0f cell\n", info->cells[i].x,
                    info->cells[i].y);
    }
 
    freePS(ps);
}
 
/* 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, pointf center) {
    PointSet *ps;
    int W, H;
    Agraph_t *eg;               /* graph containing edges */
    Agnode_t *n;
    Agedge_t *e;
    graph_t *subg;
    unsigned int margin = pinfo->margin;
    bool doSplines = pinfo->doSplines;
 
    if (root)
        eg = root;
    else
        eg = g;
 
    ps = newPS();
    const double dx = center.x - round(GD_bb(g).LL.x);
    const double dy = center.y - round(GD_bb(g).LL.y);
 
    if (pinfo->mode == l_clust) {
        int i;
 
        /* backup the alg data */
        void **alg = gv_calloc(agnnodes(g), sizeof(void*));
        for (i = 0, n = agfstnode(g); n; n = agnxtnode(g, n)) {
            alg[i++] = ND_alg(n);
            ND_alg(n) = 0;
        }
 
        /* do bbox of top clusters */
        for (i = 1; i <= GD_n_cluster(g); i++) {
            subg = GD_clust(g)[i];
            boxf 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 (double x = bb.LL.x; x <= bb.UR.x; x++)
                    for (double 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)) {
            pointf pt = coord(n);
            MOVEPT(pt);
            if (!ND_clust(n)) { /* n is not in a top-level cluster */
                const pointf s2 = {.x = margin + ND_xsize(n) / 2,
                                   .y = margin + ND_ysize(n) / 2};
                pointf LL = sub_pointf(pt, s2);
                pointf UR = add_pointf(pt, s2);
                CELL(LL, ssize);
                CELL(UR, ssize);
 
                for (double x = LL.x; x <= UR.x; x++)
                    for (double 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(aghead(e)))
                        continue;
                    fillEdge(e, pt, ps, dx, dy, ssize, doSplines);
                }
            }
        }
 
        /* restore the alg data */
        for (i = 0, n = agfstnode(g); n; n = agnxtnode(g, n)) {
            ND_alg(n)= alg[i++];
        }
        free(alg);
 
    } else
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
            pointf pt = coord(n);
            MOVEPT(pt);
            pointf s2 = {.x = margin + ND_xsize(n) / 2,
                         .y = margin + ND_ysize(n) / 2};
            pointf LL = sub_pointf(pt, s2);
            pointf UR = add_pointf(pt, s2);
            CELL(LL, ssize);
            CELL(UR, ssize);
 
            for (double x = LL.x; x <= UR.x; x++)
                for (double 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->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",
                agnameof(g), info->nc, W, H);
        for (i = 0; i < info->nc; i++)
            fprintf(stderr, "  %.0f %.0f cell\n", info->cells[i].x,
                    info->cells[i].y);
    }
 
    freePS(ps);
    return 0;
}
 
/* 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, pointf *place,
                int step, boxf *bbs) {
    pointf *cells = info->cells;
    int n = info->nc;
    int i;
 
    for (i = 0; i < n; i++) {
        pointf cell = *cells;
        cell.x += x;
        cell.y += y;
        if (inPS(ps, cell))
            return 0;
        cells++;
    }
 
    const pointf LL = bbs[info->index].LL;
    place->x = step * x - LL.x;
    place->y = step * y - LL.y;
 
    cells = info->cells;
    for (i = 0; i < n; i++) {
        pointf cell = *cells;
        cell.x += x;
        cell.y += y;
        insertPS(ps, cell);
        cells++;
    }
 
    if (Verbose >= 2)
        fprintf(stderr, "cc (%d cells) at (%d,%d) (%.0f,%.0f)\n", n, x, y,
                place->x, place->y);
    return 1;
}
 
/* 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, pointf *place,
                       pointf center) {
    pointf *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 (%.0f,%.0f)\n", n, place->x,
                place->y);
}
 
/* 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(size_t i, ginfo *info, PointSet *ps, pointf *place,
                       int step, unsigned int margin, boxf* bbs) {
    int x, y;
    int bnd;
    boxf bb = bbs[info->index];
 
    if (i == 0) {
        const int W = GRID(bb.UR.x - bb.LL.x + 2 * margin, step);
        const int H = GRID(bb.UR.y - bb.LL.y + 2 * margin, step);
        if (fits(-W / 2, -H / 2, info, ps, place, step, bbs))
            return;
    }
 
    if (fits(0, 0, info, ps, place, step, bbs))
        return;
    const double W = ceil(bb.UR.x - bb.LL.x);
    const double H = ceil(bb.UR.y - bb.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, bbs))
                    return;
            for (; y < bnd; y++)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
            for (; x > -bnd; x--)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
            for (; y > -bnd; y--)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
            for (; x < 0; x++)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
        }
    } else {
        for (bnd = 1;; bnd++) {
            y = 0;
            x = -bnd;
            for (; y > -bnd; y--)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
            for (; x < bnd; x++)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
            for (; y < bnd; y++)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
            for (; x > -bnd; x--)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
            for (; y > 0; y--)
                if (fits(x, y, info, ps, place, step, bbs))
                    return;
        }
    }
}
 
#ifdef DEBUG
void dumpp(ginfo * info, char *pfx)
{
    pointf *cells = info->cells;
    int i, c_cnt = info->nc;
 
    fprintf(stderr, "%s\n", pfx);
    for (i = 0; i < c_cnt; i++) {
        fprintf(stderr, "%.0f %.0f box\n", cells[i].x, cells[i].y);
    }
}
#endif
 
static int ucmpf(const void *X, const void *Y, void *user_values) {
    const ainfo* x = *(ainfo *const *) X;
    const ainfo* y = *(ainfo *const *) Y;
    const packval_t *userVals = user_values;
 
    const unsigned int dX = userVals[x->index];
    const unsigned int dY = userVals[y->index];
    if (dX > dY) return 1;
    if (dX < dY) return -1;
    return 0;
}
 
static int acmpf(const void *X, const void *Y)
{
    const ainfo* x = *(ainfo *const *) X;
    const ainfo* y = *(ainfo *const *) Y;
    double dX = x->height + x->width; 
    double dY = y->height + y->width; 
    if (dX < dY) return 1;
    if (dX > dY) return -1;
    return 0;
}
 
#define INC(m,c,r) \
    if (m){ c++; if (c == nc) { c = 0; r++; } } \
    else { r++; if (r == nr) { r = 0; c++; } }
 
static pointf *arrayRects(size_t ng, boxf *gs, pack_info *pinfo) {
    size_t nr = 0, nc;
    size_t r, c;
    ainfo *info;
    double v, wd, ht;
    pointf *places = gv_calloc(ng, sizeof(pointf));
    boxf bb;
    int sz, rowMajor;
 
    /* set up no. of rows and columns */
    sz = pinfo->sz;
    if (pinfo->flags & PK_COL_MAJOR) {
        rowMajor = 0;
        if (sz > 0) {
            nr = (size_t)sz;
            nc = (ng + (nr-1))/nr;
        }
        else {
            nr = ceil(sqrt(ng));
            nc = (ng + (nr-1))/nr;
        }
    }
    else {
        rowMajor = 1;
        if (sz > 0) {
            nc = (size_t)sz;
            nr = (ng + (nc-1))/nc;
        }
        else {
            nc = ceil(sqrt(ng));
            nr = (ng + (nc-1))/nc;
        }
    }
    if (Verbose)
        fprintf(stderr, "array packing: %s %" PRISIZE_T " rows %" PRISIZE_T
                " columns\n", rowMajor ? "row major" : "column major", nr, nc);
    double *widths = gv_calloc(nc + 1, sizeof(double));
    double *heights = gv_calloc(nr + 1, sizeof(double));
 
    ainfo *ip = info = gv_calloc(ng, sizeof(ainfo));
    for (size_t i = 0; i < ng; i++, ip++) {
        bb = gs[i];
        ip->width = bb.UR.x - bb.LL.x + pinfo->margin;
        ip->height = bb.UR.y - bb.LL.y + pinfo->margin;
        ip->index = i;
    }
 
    ainfo **sinfo = gv_calloc(ng, sizeof(ainfo*));
    for (size_t i = 0; i < ng; i++) {
        sinfo[i] = info + i;
    }
 
    if (pinfo->vals) {
        gv_sort(sinfo, ng, sizeof(ainfo *), ucmpf, pinfo->vals);
    }
    else if (!(pinfo->flags & PK_INPUT_ORDER)) {
        qsort(sinfo, ng, sizeof(ainfo *), acmpf);
    }
 
    /* compute column widths and row heights */
    r = c = 0;
    for (size_t i = 0; i < ng; i++, ip++) {
        ip = sinfo[i];
        widths[c] = fmax(widths[c], ip->width);
        heights[r] = fmax(heights[r], ip->height);
        INC(rowMajor,c,r);
    }
 
    /* convert widths and heights to positions */
    wd = 0;
    for (size_t i = 0; i <= nc; i++) {
        v = widths[i];
        widths[i] = wd;
        wd += v;
    }
 
    ht = 0;
    for (size_t i = nr; 0 < i; i--) {
        v = heights[i-1];
        heights[i] = ht;
        ht += v;
    }
    heights[0] = ht;
 
    /* position rects */
    r = c = 0;
    for (size_t i = 0; i < ng; i++, ip++) {
        ip = sinfo[i];
        const size_t idx = ip->index;
        bb = gs[idx];
        if (pinfo->flags & PK_LEFT_ALIGN)
            places[idx].x = widths[c];
        else if (pinfo->flags & PK_RIGHT_ALIGN)
            places[idx].x = widths[c+1] - (bb.UR.x - bb.LL.x);
        else
            places[idx].x = (widths[c] + widths[c+1] - bb.UR.x - bb.LL.x)/2.0;
        if (pinfo->flags & PK_TOP_ALIGN)
            places[idx].y = heights[r] - (bb.UR.y - bb.LL.y);
        else if (pinfo->flags & PK_BOT_ALIGN)
            places[idx].y = heights[r+1];
        else
            places[idx].y = (heights[r] + heights[r+1] - bb.UR.y - bb.LL.y)/2.0;
        INC(rowMajor,c,r);
    }
 
    free (info);
    free (sinfo);
    free (widths);
    free (heights);
    return places;
}
 
static pointf *polyRects(size_t ng, boxf *gs, pack_info *pinfo) {
    int stepSize;
    Dict_t *ps;
 
    /* calculate grid size */
    stepSize = computeStep(ng, gs, pinfo->margin);
    if (Verbose)
        fprintf(stderr, "step size = %d\n", stepSize);
    if (stepSize <= 0)
        return 0;
 
    /* generate polyomino cover for the rectangles */
    ginfo *info = gv_calloc(ng, sizeof(ginfo));
    for (size_t i = 0; i < ng; i++) {
        info[i].index = i;
        genBox(gs[i], info + i, stepSize, pinfo->margin, (pointf){0}, "");
    }
 
    /* sort */
    ginfo **sinfo = gv_calloc(ng, sizeof(ginfo*));
    for (size_t i = 0; i < ng; i++) {
        sinfo[i] = info + i;
    }
    qsort(sinfo, ng, sizeof(ginfo *), cmpf);
 
    ps = newPS();
    pointf *places = gv_calloc(ng, sizeof(pointf));
    for (size_t i = 0; i < ng; i++)
        placeGraph(i, sinfo[i], ps, places + sinfo[i]->index,
                       stepSize, pinfo->margin, gs);
 
    free(sinfo);
    for (size_t i = 0; i < ng; i++)
        free(info[i].cells);
    free(info);
    freePS(ps);
 
    if (Verbose > 1)
        for (size_t i = 0; i < ng; i++)
            fprintf(stderr, "pos[%" PRISIZE_T "] %.0f %.0f\n", i, places[i].x,
                    places[i].y);
 
    return places;
}
 
/* 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 GD_bb, node fields ND_pos(inches), ND_xsize and 
 * ND_ysize, and edge field ED_spl.
 *
 * FIX: fixed mode does not always work. The fixed ones get translated
 * back to be centered on the origin.
 * FIX: Check CELL and GRID macros for negative coordinates 
 * FIX: Check width and height computation
 */
static pointf *polyGraphs(size_t ng, Agraph_t **gs, Agraph_t *root,
                          pack_info *pinfo) {
    int stepSize;
    ginfo *info;
    Dict_t *ps;
    bool *fixed = pinfo->fixed;
    int fixed_cnt = 0;
    boxf fixed_bb = { {0, 0}, {0, 0} };
 
    if (ng == 0)
        return 0;
 
    /* update bounding box info for each graph */
    /* If fixed, compute bbox of fixed graphs */
    for (size_t i = 0; i < ng; i++) {
        Agraph_t *g = gs[i];
        compute_bb(g);
        if (fixed && fixed[i]) {
            const boxf bb = GD_bb(g);
            if (fixed_cnt) {
                fixed_bb.LL.x = fmin(bb.LL.x, fixed_bb.LL.x);
                fixed_bb.LL.y = fmin(bb.LL.y, fixed_bb.LL.y);
                fixed_bb.UR.x = fmax(bb.UR.x, fixed_bb.UR.x);
                fixed_bb.UR.y = fmax(bb.UR.y, fixed_bb.UR.y);
            } else
                fixed_bb = bb;
            fixed_cnt++;
        }
        if (Verbose > 2) {
            fprintf(stderr, "bb[%s] %.5g %.5g %.5g %.5g\n", agnameof(g),
                GD_bb(g).LL.x, GD_bb(g).LL.y,
                GD_bb(g).UR.x, GD_bb(g).UR.y);
        }
    }
 
    /* calculate grid size */
    boxf *bbs = gv_calloc(ng, sizeof(boxf));
    for (size_t i = 0; i < ng; i++)
        bbs[i] = GD_bb(gs[i]);
    stepSize = computeStep(ng, bbs, pinfo->margin);
    if (Verbose)
        fprintf(stderr, "step size = %d\n", stepSize);
    if (stepSize <= 0) {
        free(bbs);
        return 0;
    }
 
    /* generate polyomino cover for the graphs */
    pointf center = {0};
    if (fixed) {
        center = mid_pointf(fixed_bb.LL, fixed_bb.UR);
    }
    info = gv_calloc(ng, sizeof(ginfo));
    for (size_t i = 0; i < ng; i++) {
        Agraph_t *g = gs[i];
        info[i].index = i;
        if (pinfo->mode == l_graph)
            genBox(GD_bb(g), info + i, stepSize, pinfo->margin, center, agnameof(g));
        else if (genPoly(root, gs[i], info + i, stepSize, pinfo, center)) {
            free(bbs);
            return 0;
        }
    }
 
    /* sort */
    ginfo **sinfo = gv_calloc(ng, sizeof(ginfo*));
    for (size_t i = 0; i < ng; i++) {
        sinfo[i] = info + i;
    }
    qsort(sinfo, ng, sizeof(ginfo *), cmpf);
 
    ps = newPS();
    pointf *places = gv_calloc(ng, sizeof(pointf));
    if (fixed) {
        for (size_t i = 0; i < ng; i++) {
            if (fixed[i])
                placeFixed(sinfo[i], ps, places + sinfo[i]->index, center);
        }
        for (size_t i = 0; i < ng; i++) {
            if (!fixed[i])
                placeGraph(i, sinfo[i], ps, places + sinfo[i]->index,
                           stepSize, pinfo->margin, bbs);
        }
    } else {
        for (size_t i = 0; i < ng; i++)
            placeGraph(i, sinfo[i], ps, places + sinfo[i]->index,
                       stepSize, pinfo->margin, bbs);
    }
 
    free(sinfo);
    for (size_t i = 0; i < ng; i++)
        free(info[i].cells);
    free(info);
    freePS(ps);
    free (bbs);
 
    if (Verbose > 1)
        for (size_t i = 0; i < ng; i++)
            fprintf(stderr, "pos[%" PRISIZE_T "] %.0f %.0f\n", i, places[i].x,
                    places[i].y);
 
    return places;
}
 
pointf *putGraphs(size_t ng, Agraph_t **gs, Agraph_t *root, pack_info *pinfo) {
    int v;
    Agraph_t* g;
    pointf* pts = NULL;
    char* s;
 
    if (ng == 0) return NULL;
 
    if (pinfo->mode <= l_graph)
        return polyGraphs (ng, gs, root, pinfo);
    
    boxf *bbs = gv_calloc(ng, sizeof(boxf));
 
    for (size_t i = 0; i < ng; i++) {
        g = gs[i];
        compute_bb(g);
        bbs[i] = GD_bb(g);
    }
 
    if (pinfo->mode == l_array) {
        if (pinfo->flags & PK_USER_VALS) {
            pinfo->vals = gv_calloc(ng, sizeof(packval_t));
            for (size_t i = 0; i < ng; i++) {
                s = agget (gs[i], "sortv");
                if (s && sscanf(s, "%d", &v) > 0 && v >= 0)
                    pinfo->vals[i] = v;
            }
 
        }
        pts = arrayRects(ng, bbs, pinfo);
        if (pinfo->flags & PK_USER_VALS)
            free (pinfo->vals);
    }
 
    free (bbs);
 
    return pts;
}
 
pointf *putRects(size_t ng, boxf *bbs, pack_info *pinfo) {
    if (ng == 0) return NULL;
    if (pinfo->mode == l_node || pinfo->mode == l_clust) return NULL;
    if (pinfo->mode == l_graph)
        return polyRects (ng, bbs, pinfo);
    if (pinfo->mode == l_array)
        return arrayRects(ng, bbs, pinfo);
    return NULL;
}
 
/* Packs rectangles.
 *  ng - number of rectangles
 *  bbs - array of rectangles
 *  info - parameters used in packing
 * This decides where to layout the rectangles and repositions 
 * the bounding boxes.
 *
 * Returns 0 on success.
 */
int packRects(size_t ng, boxf *bbs, pack_info *pinfo) {
    boxf bb;
 
    if (ng <= 1) return 0;
 
    pointf *pp = putRects(ng, bbs, pinfo);
    if (!pp)
        return 1;
 
    for (size_t i = 0; i < ng; i++) {
        bb = bbs[i];
        const pointf p = pp[i];
        bb.LL = add_pointf(bb.LL, p);
        bb.UR = add_pointf(bb.UR, p);
        bbs[i] = bb;
    }
    free(pp);
    return 0;
}
 
static void shiftEdge(Agedge_t *e, double dx, double dy) {
    bezier bz;
 
    if (ED_label(e))
        MOVEPT(ED_label(e)->pos);
    if (ED_xlabel(e))
        MOVEPT(ED_xlabel(e)->pos);
    if (ED_head_label(e))
        MOVEPT(ED_head_label(e)->pos);
    if (ED_tail_label(e))
        MOVEPT(ED_tail_label(e)->pos);
 
    if (ED_spl(e) == NULL)
        return;
 
    for (size_t j = 0; j < ED_spl(e)->size; j++) {
        bz = ED_spl(e)->list[j];
        for (size_t 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);
    }
}
 
static void shiftGraph(Agraph_t *g, double dx, double dy) {
    graph_t *subg;
    boxf 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) && GD_label(g)->set)
        MOVEPT(GD_label(g)->pos);
 
    for (i = 1; i <= GD_n_cluster(g); i++) {
        subg = GD_clust(g)[i];
        shiftGraph(subg, dx, dy);
    }
}
 
/* The function takes ng graphs gs and a similar
 * number of points pp and translates each graph so
 * that the lower left corner of the bounding box of graph gs[i] is at
 * point ps[i]. To do this, it assumes the bb field in
 * Agraphinfo_t accurately reflects the current graph layout.
 * The graph is repositioned by translating the pos and coord fields of 
 * each node appropriately.
 * 
 * If doSplines is non-zero, the function also translates splines coordinates
 * of each edge, if they have been calculated. In addition, edge labels are
 * repositioned. 
 * 
 * If root is non-NULL, it is taken as the root graph of
 * the graphs in gs and is used to find the edges. Otherwise, the function
 * uses the edges found in each graph gs[i].
 * 
 * It returns 0 on success.
 * 
 * This function uses the bb field in Agraphinfo_t,
 * the pos and coord fields in nodehinfo_t and
 * the spl field in Aedgeinfo_t.
 */
int shiftGraphs(size_t ng, Agraph_t **gs, pointf *pp, Agraph_t *root,
                bool doSplines) {
    double fx, fy;
    Agraph_t *g;
    Agraph_t *eg;
    Agnode_t *n;
    Agedge_t *e;
 
    if (ng == 0)
        return 0;
 
    for (size_t i = 0; i < ng; i++) {
        g = gs[i];
        if (root)
            eg = root;
        else
            eg = g;
        const pointf p = pp[i];
        const double dx = p.x;
        const double 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;
            MOVEPT(ND_coord(n));
            if (ND_xlabel(n)) {
                MOVEPT(ND_xlabel(n)->pos);
            }
            if (doSplines) {
                for (e = agfstout(eg, n); e; e = agnxtout(eg, e))
                    shiftEdge(e, dx, dy);
            }
        }
        shiftGraph(g, dx, dy);
    }
 
    return 0;
}
 
/* 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(size_t ng, Agraph_t **gs, Agraph_t *root, pack_info *info) {
    int ret;
    pointf *pp = putGraphs(ng, gs, root, info);
 
    if (!pp)
        return 1;
    ret = shiftGraphs(ng, gs, pp, root, info->doSplines);
    free(pp);
    return ret;
}
 
/* 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(size_t ng, Agraph_t **gs, Agraph_t *root, pack_info *info) {
    int ret;
 
    ret = packGraphs(ng, gs, root, info);
    if (ret == 0) {
        int j;
        boxf bb;
        graph_t* g;
 
        compute_bb(root);
        bb = GD_bb(root);
        for (size_t i = 0; i < ng; i++) {
            g = gs[i];
            for (j = 1; j <= GD_n_cluster(g); j++) {
                EXPANDBB(bb,GD_bb(GD_clust(g)[j]));
            }
        }
        GD_bb(root) = bb;
    }
    return ret;
}
 
int pack_graph(size_t ng, Agraph_t **gs, Agraph_t *root, bool *fixed) {
    int ret;
    pack_info info;
 
    getPackInfo(root, l_graph, CL_OFFSET, &info);
    info.doSplines = true;
    info.fixed = fixed;
    ret = packSubgraphs(ng, gs, root, &info);
    if (ret == 0) dotneato_postprocess (root);
    return ret;
}
 
static const char*chkFlags(const char *p, pack_info *pinfo) {
    int c, more;
 
    if (*p != '_') return p;
    p++;
    more = 1;
    while (more && (c = *p)) {
        switch (c) {
        case 'c' :
            pinfo->flags |= PK_COL_MAJOR;
            p++;
            break;
        case 'i' :
            pinfo->flags |= PK_INPUT_ORDER;
            p++;
            break;
        case 'u' :
            pinfo->flags |= PK_USER_VALS;
            p++;
            break;
        case 't' :
            pinfo->flags |= PK_TOP_ALIGN;
            p++;
            break;
        case 'b' :
            pinfo->flags |= PK_BOT_ALIGN;
            p++;
            break;
        case 'l' :
            pinfo->flags |= PK_LEFT_ALIGN;
            p++;
            break;
        case 'r' :
            pinfo->flags |= PK_RIGHT_ALIGN;
            p++;
            break;
        default :
            more = 0;
            break;
        }
    }
    return p;
}
 
static const char *mode2Str(pack_mode m) {
 
    switch (m) {
    case l_clust:
        return "cluster";
    case l_node:
        return "node";
    case l_graph:
        return "graph";
    case l_array:
        return "array";
    case l_aspect:
        return "aspect";
    case l_undef: 
    default:
        break;
    }
    return "undefined";
}
 
/* Return pack_mode of graph using "packmode" attribute.
 * If not defined, return dflt
 */
pack_mode 
parsePackModeInfo(const char* p, pack_mode dflt, pack_info* pinfo)
{
    float v;
    int i;
 
    assert (pinfo);
    pinfo->flags = 0;
    pinfo->mode = dflt;
    pinfo->sz = 0;
    pinfo->vals = NULL;
    if (p) {
        if (startswith(p, "array")) {
            pinfo->mode = l_array;
            p += strlen("array");
            p = chkFlags (p, pinfo);
            if ((sscanf (p, "%d", &i)>0) && (i > 0))
                pinfo->sz = i;
        } else if (startswith(p, "aspect")) {
            pinfo->mode = l_aspect;
            if (sscanf(p + strlen("aspect"), "%f", &v) > 0 && v > 0)
                pinfo->aspect = v;
            else
                pinfo->aspect = 1;
        } else if (streq(p, "cluster")) {
            pinfo->mode = l_clust;
        } else if (streq(p, "graph")) {
            pinfo->mode = l_graph;
        } else if (streq(p, "node")) {
            pinfo->mode = l_node;
        }
    }
 
    if (Verbose) {
        fprintf (stderr, "pack info:\n");
        fprintf (stderr, "  mode   %s\n", mode2Str(pinfo->mode));
        if (pinfo->mode == l_aspect)
            fprintf (stderr, "  aspect %f\n", pinfo->aspect);
        fprintf (stderr, "  size   %d\n", pinfo->sz);
        fprintf (stderr, "  flags  %d\n", pinfo->flags);
    }
    return pinfo->mode;
}
 
/* Return pack_mode of graph using "packmode" attribute.
 * If not defined, return dflt
 */
pack_mode 
getPackModeInfo(Agraph_t * g, pack_mode dflt, pack_info* pinfo)
{
    return parsePackModeInfo (agget(g, "packmode"), dflt, pinfo);
}
 
pack_mode 
getPackMode(Agraph_t * g, pack_mode dflt)
{
  pack_info info;
  return getPackModeInfo (g, dflt, &info);
}
 
/* 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;
}
 
pack_mode 
getPackInfo(Agraph_t * g, pack_mode dflt, int dfltMargin, pack_info* pinfo)
{
    assert (pinfo);
 
    pinfo->margin = getPack(g, dfltMargin, dfltMargin);
    if (Verbose) {
        fprintf (stderr, "  margin %u\n", pinfo->margin);
    }
    pinfo->doSplines = false;
    pinfo->fixed = NULL;
    getPackModeInfo(g, dflt, pinfo);
 
    return pinfo->mode;
}