gvpack.cpp

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 v2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html
 *
 * Contributors: Details at https://graphviz.org
 *************************************************************************/
 
/*
 * Written by Emden R. Gansner
 */
 
#include "config.h"
 
#include "openFile.h"
#include <algorithm>
#include <cassert>
#include <cgraph/cgraph.h>
#include <cgraph/ingraphs.h>
#include <common/render.h>
#include <common/utils.h>
#include <cstdio>
#include <getopt.h>
#include <gvc/gvc.h>
#include <iostream>
#include <limits>
#include <map>
#include <neatogen/neatoprocs.h>
#include <optional>
#include <pack/pack.h>
#include <set>
#include <stddef.h>
#include <string>
#include <util/alloc.h>
#include <util/exit.h>
#include <util/gv_ctype.h>
#include <utility>
#include <vector>
 
extern "C" {
#ifdef GVDLL
__declspec(dllimport)
#endif
extern gvplugin_library_t gvplugin_neato_layout_LTX_library;
}
 
lt_symlist_t lt_preloaded_symbols[] = {{"gvplugin_neato_layout_LTX_library", 0},
                                       {0, 0}};
 
/* gvpack:
 * Input consists of graphs in dot format.
 * The graphs should have pos, width and height set for nodes,
 * bb set for clusters, and, optionally, spline info for edges.
 * The graphs are packed geometrically and combined
 * into a single output graph, ready to be sent to neato -s -n2.
 *  -m <i> specifies the margin, in points, about each graph.
 */
 
typedef struct {
  char *name;
  char *value;
} attr_t;
 
static int verbose = 0;
static char **myFiles = 0;
static FILE *outfp;                /* output; stdout by default */
static std::vector<attr_t> G_args; // Storage for -G arguments
static bool doPack;                /* Do packing if true */
static char *gname = const_cast<char *>("root");
static bool errored; 
 
static int handle_error(char *message) {
 
  errored = true;
 
  // `fputs`, escaping characters that may interfere with a terminal
  for (const char *p = message; *p != '\0'; ++p) {
 
    if (gv_iscntrl(*p) && !gv_isspace(*p)) {
      const int rc = fprintf(stderr, "\\%03o", (unsigned)*p);
      if (rc < 0) {
        return rc;
      }
      continue;
    }
 
    const int rc = putc(*p, stderr);
    if (rc < 0) {
      return rc;
    }
  }
  return 0;
}
 
#define NEWNODE(n) ((node_t *)ND_alg(n))
 
static const char useString[] =
    "Usage: gvpack [-gnuv?] [-m<margin>] {-array[_rc][n]] [-o<outf>] <files>\n\
  -n          - use node granularity\n\
  -g          - use graph granularity\n\
  -array*     - pack as array of graphs\n\
  -G<n>=<v>   - attach name/value attribute to output graph\n\
  -m<n>       - set margin to <n> points\n\
  -s<gname>   - use <gname> for name of root graph\n\
  -o<outfile> - write output to <outfile>\n\
  -u          - no packing; just combine graphs\n\
  -v          - verbose\n\
  -?          - print usage\n\
If no files are specified, stdin is used\n";
 
static void usage(int v) {
  std::cout << useString;
  graphviz_exit(v);
}
 
/* If arg is a name-value pair, add it to the list
 * and return 0; otherwise, return 1.
 */
static int setNameValue(char *arg) {
  char *rhs = const_cast<char *>("true");
 
  if (char *p = strchr(arg, '=')) {
    *p++ = '\0';
    rhs = p;
  }
  G_args.push_back(attr_t{arg, rhs});
 
  return 0;
}
 
/* If arg is an integer, value is stored in v
 * and function returns 0; otherwise, returns 1.
 */
static int setUInt(unsigned int *v, char *arg) {
  char *p;
  unsigned int i;
 
  i = (unsigned int)strtol(arg, &p, 10);
  if (p == arg) {
    std::cerr << "Error: bad value in flag -" << (arg - 1) << " - ignored\n";
    return 1;
  }
  *v = i;
  return 0;
}
 
static Agsym_t *agraphattr(Agraph_t *g, char *name, const char *value) {
  return agattr_text(g, AGRAPH, name, value);
}
 
static Agsym_t *agnodeattr(Agraph_t *g, char *name, const char *value) {
  return agattr_text(g, AGNODE, name, value);
}
 
static Agsym_t *agedgeattr(Agraph_t *g, char *name, const char *value) {
  return agattr_text(g, AGEDGE, name, value);
}
 
static void init(int argc, char *argv[], pack_info *pinfo) {
  int c;
 
  agnodeattr(nullptr, const_cast<char *>("label"), NODENAME_ESC);
  pinfo->mode = l_clust;
  pinfo->margin = CL_OFFSET;
  pinfo->doSplines = true; // Use edges in packing
  pinfo->fixed = nullptr;
  pinfo->sz = 0;
 
  opterr = 0;
  while ((c = getopt(argc, argv, ":na:gvum:s:o:G:?")) != -1) {
    switch (c) {
    case 'a': {
      auto buf = std::string("a") + optarg + "\n";
      parsePackModeInfo(buf.c_str(), pinfo->mode, pinfo);
      break;
    }
    case 'n':
      parsePackModeInfo("node", pinfo->mode, pinfo);
      break;
    case 's':
      gname = optarg;
      break;
    case 'g':
      parsePackModeInfo("graph", pinfo->mode, pinfo);
      break;
    case 'm':
      setUInt(&pinfo->margin, optarg);
      break;
    case 'o':
      if (outfp != nullptr)
        fclose(outfp);
      outfp = openFile("gvpack", optarg, "w");
      break;
    case 'u':
      pinfo->mode = l_undef;
      break;
    case 'G':
      if (*optarg)
        setNameValue(optarg);
      else
        std::cerr << "gvpack: option -G missing argument - ignored\n";
      break;
    case 'v':
      verbose = 1;
      Verbose = 1;
      break;
    case ':':
      std::cerr << "gvpack: option -" << (char)optopt
                << " missing argument - ignored\n";
      break;
    case '?':
      if (optopt == '\0' || optopt == '?')
        usage(0);
      else {
        std::cerr << "gvpack: option -" << (char)optopt << " unrecognized\n";
        usage(1);
      }
      break;
    }
  }
  argv += optind;
  argc -= optind;
 
  if (argc > 0) {
    myFiles = argv;
  }
  if (!outfp)
    outfp = stdout; /* stdout the default */
  if (verbose)
    std::cerr << "  margin " << pinfo->margin << '\n';
}
 
static void init_node_edge(Agraph_t *g) {
  node_t *n;
  edge_t *e;
  int nG = agnnodes(g);
  attrsym_t *N_pos = agfindnodeattr(g, const_cast<char *>("pos"));
  attrsym_t *N_pin = agfindnodeattr(g, const_cast<char *>("pin"));
 
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    neato_init_node(n);
    user_pos(N_pos, N_pin, n, nG); /* set user position if given */
  }
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    for (e = agfstout(g, n); e; e = agnxtout(g, e))
      common_init_edge(e);
  }
}
 
/* Initialize attributes. We always do the minimum required by
 * libcommon. If fill is true, we use init_nop (neato -n) to
 * read in attributes relevant to the layout.
 */
static void init_graph(Agraph_t *g, bool fill, GVC_t *gvc) {
  int d;
  node_t *n;
  edge_t *e;
 
  aginit(g, AGRAPH, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
  aginit(g, AGNODE, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true);
  aginit(g, AGEDGE, "Agedgeinfo_t", sizeof(Agedgeinfo_t), true);
  GD_gvc(g) = gvc;
  if (errored)
    graphviz_exit(1);
  graph_init(g, false);
  d = late_int(g, agfindgraphattr(g, const_cast<char *>("dim")), 2, 2);
  if (d != 2) {
    std::cerr << "Error: graph " << agnameof(g) << " has dim = " << d
              << " (!= 2)\n";
    graphviz_exit(1);
  }
  Ndim = GD_ndim(g) = 2;
  init_node_edge(g);
  if (fill) {
    if (int ret = init_nop(g, 0)) {
      if (ret < 0)
        std::cerr << "Error loading layout info from graph " << agnameof(g)
                  << '\n';
      else if (ret > 0)
        std::cerr << "gvpack does not support backgrounds as found in graph "
                  << agnameof(g) << '\n';
      graphviz_exit(1);
    }
    if (Concentrate) { /* check for edges without pos info */
      for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
        for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
          if (ED_spl(e) == nullptr)
            ED_edge_type(e) = IGNORED;
        }
      }
    }
  }
}
 
/* Copy all attributes from old object to new. Assume
 * attributes have been initialized.
 */
static void cloneDfltAttrs(Agraph_t *old, Agraph_t *new_graph, int attr_kind) {
  for (Agsym_t *a = agnxtattr(old, attr_kind, 0); a;
       a = agnxtattr(old, attr_kind, a)) {
    if (aghtmlstr(a->defval)) {
      agattr_html(new_graph, attr_kind, a->name, a->defval);
    } else {
      agattr_text(new_graph, attr_kind, a->name, a->defval);
    }
  }
}
static void cloneAttrs(void *old, void *new_graph) {
  int attr_kind = AGTYPE(old);
  char *s;
  Agraph_t *g = agroot(old);
  Agraph_t *ng = agroot(new_graph);
 
  for (Agsym_t *a = agnxtattr(g, attr_kind, 0); a;
       a = agnxtattr(g, attr_kind, a)) {
    s = agxget(old, a);
    if (aghtmlstr(s)) {
      char *scopy = agstrdup_html(ng, s);
      agset(new_graph, a->name, scopy);
      agstrfree(ng, scopy,
                true); // drop the extra reference count we bumped for scopy
    } else {
      agset(new_graph, a->name, s);
    }
  }
}
 
/* Note that here, and in cloneNode and cloneCluster,
 * we do a shallow copy. We thus assume that attributes
 * are not disturbed. In particular, we assume they are
 * not deallocated.
 */
static void cloneEdge(Agedge_t *old, Agedge_t *new_edge) {
  cloneAttrs(old, new_edge);
  ED_spl(new_edge) = ED_spl(old);
  ED_edge_type(new_edge) = ED_edge_type(old);
  ED_label(new_edge) = ED_label(old);
  ED_head_label(new_edge) = ED_head_label(old);
  ED_tail_label(new_edge) = ED_tail_label(old);
  ED_xlabel(new_edge) = ED_xlabel(old);
}
 
static void cloneNode(Agnode_t *old, Agnode_t *new_node) {
  cloneAttrs(old, new_node);
  ND_coord(new_node).x = POINTS(ND_pos(old)[0]);
  ND_coord(new_node).y = POINTS(ND_pos(old)[1]);
  ND_height(new_node) = ND_height(old);
  ND_ht(new_node) = ND_ht(old);
  ND_width(new_node) = ND_width(old);
  ND_lw(new_node) = ND_lw(old);
  ND_rw(new_node) = ND_rw(old);
  ND_shape(new_node) = ND_shape(old);
  ND_shape_info(new_node) = ND_shape_info(old);
  ND_xlabel(new_node) = ND_xlabel(old);
}
 
static void cloneCluster(Agraph_t *old, Agraph_t *new_cluster) {
  // string attributes were cloned as subgraphs
  GD_label(new_cluster) = GD_label(old);
  GD_bb(new_cluster) = GD_bb(old);
}
 
namespace {
struct AttributeValue {
  std::string value; 
  size_t instances;  
};
} // namespace
 
using attr_map_t = std::map<std::string, AttributeValue>;
 
/* Fill newdict with all the name-value attributes of
 * objp. If the attribute has already been defined and
 * has a different default, set default to "".
 */
static void fillDict(attr_map_t &newdict, Agraph_t *g, int attr_kind) {
 
  for (Agsym_t *a = agnxtattr(g, attr_kind, 0); a;
       a = agnxtattr(g, attr_kind, a)) {
    char *name = a->name;
    char *value = a->defval;
    auto it = newdict.find(name);
    if (it == newdict.end()) {
      newdict.insert({name, AttributeValue{value, 1}});
    } else if (it->second.value == value)
      ++it->second.instances;
  }
}
 
/* Use all the name-value entries in the dictionary d to define
 * to define universal node/edge/graph attributes for g.
 * For a non-empty default value, the attribute must be defined and the
 * same in all graphs.
 */
static void fillGraph(Agraph_t *g, const attr_map_t &d,
                      Agsym_t *(*setf)(Agraph_t *, char *, const char *),
                      size_t cnt) {
  for (const auto &kv : d) {
    const std::string &name = kv.first;
    const std::string &value = kv.second.value;
    const size_t &attr_cnt = kv.second.instances;
    if (cnt == attr_cnt)
      setf(g, const_cast<char *>(name.c_str()), value.c_str());
    else
      setf(g, const_cast<char *>(name.c_str()), "");
  }
}
 
/* Initialize the attributes of root as the union of the
 * attributes in the graphs gs.
 */
static void initAttrs(Agraph_t *root, std::vector<Agraph_t *> &gs) {
  attr_map_t n_attrs;
  attr_map_t e_attrs;
  attr_map_t g_attrs;
 
  for (Agraph_t *g : gs) {
    fillDict(g_attrs, g, AGRAPH);
    fillDict(n_attrs, g, AGNODE);
    fillDict(e_attrs, g, AGEDGE);
  }
 
  fillGraph(root, g_attrs, agraphattr, gs.size());
  fillGraph(root, n_attrs, agnodeattr, gs.size());
  fillGraph(root, e_attrs, agedgeattr, gs.size());
}
 
static void cloneGraphAttr(Agraph_t *g, Agraph_t *ng) {
  cloneAttrs(g, ng);
  cloneDfltAttrs(g, ng, AGNODE);
  cloneDfltAttrs(g, ng, AGEDGE);
}
 
using used_t = std::multiset<std::string>;
 
/* Create a name for an object in the new graph using the
 * dictionary names and the old name. If the old name has not
 * been used, use it and add it to names. If it has been used,
 * create a new name using the old name and a number.
 * Note that returned string will immediately made into an agstring.
 */
static std::string xName(used_t &names, char *oldname) {
  size_t previous_instances = names.count(oldname);
  names.insert(oldname);
  if (previous_instances > 0) {
    return std::string(oldname) + "_gv" + std::to_string(previous_instances);
  }
  return oldname;
}
 
#define MARK(e) (ED_alg(e) = e)
#define MARKED(e) (ED_alg(e))
#define SETCLUST(g, h) (GD_alg(g) = h)
#define GETCLUST(g) ((Agraph_t *)GD_alg(g))
 
/* Create a copy of g in ng, copying attributes, inserting nodes
 * and adding edges.
 */
static void cloneSubg(Agraph_t *g, Agraph_t *ng, Agsym_t *G_bb,
                      used_t &gnames) {
  node_t *n;
  node_t *nn;
  edge_t *e;
  edge_t *ne;
  node_t *nt;
  node_t *nh;
  Agraph_t *subg;
  Agraph_t *nsubg;
 
  cloneGraphAttr(g, ng);
  if (doPack)
    agxset(ng, G_bb, ""); /* Unset all subgraph bb */
 
  /* clone subgraphs */
  for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
    nsubg = agsubg(ng, xName(gnames, agnameof(subg)).data(), 1);
    agbindrec(nsubg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
    cloneSubg(subg, nsubg, G_bb, gnames);
    /* if subgraphs are clusters, point to the new
     * one so we can find it later.
     */
    if (is_a_cluster(subg))
      SETCLUST(subg, nsubg);
  }
 
  /* add remaining nodes */
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    nn = NEWNODE(n);
    agsubnode(ng, nn, 1);
  }
 
  /* add remaining edges. libgraph doesn't provide a way to find
   * multiedges, so we add edges bottom up, marking edges when added.
   */
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
      if (MARKED(e))
        continue;
      nt = NEWNODE(agtail(e));
      nh = NEWNODE(aghead(e));
      ne = agedge(ng, nt, nh, nullptr, 1);
      agbindrec(ne, "Agedgeinfo_t", sizeof(Agedgeinfo_t), true);
      cloneEdge(e, ne);
      MARK(e);
    }
  }
}
 
/* Given old and new subgraphs which are corresponding
 * clusters, recursively create the subtree of clusters
 * under ng using the subtree of clusters under g.
 */
static void cloneClusterTree(Agraph_t *g, Agraph_t *ng) {
  int i;
 
  cloneCluster(g, ng);
 
  if (GD_n_cluster(g)) {
    GD_n_cluster(ng) = GD_n_cluster(g);
    void *const p = gv_calloc(1 + GD_n_cluster(g), sizeof(Agraph_t *));
    GD_clust(ng) = new (p) Agraph_t *[1 + GD_n_cluster(g)]{};
    for (i = 1; i <= GD_n_cluster(g); i++) {
      Agraph_t *c = GETCLUST(GD_clust(g)[i]);
      GD_clust(ng)[i] = c;
      cloneClusterTree(GD_clust(g)[i], c);
    }
  }
}
 
/* Create and return a new graph which is the logical union
 * of the graphs gs.
 */
static Agraph_t *cloneGraph(std::vector<Agraph_t *> &gs, GVC_t *gvc,
                            Agdesc_t kind) {
  Agraph_t *root;
  Agraph_t *subg;
  Agnode_t *n;
  Agnode_t *np;
  bool doWarn = true;
 
  if (verbose)
    std::cerr << "Creating clone graph\n";
  root = agopen(gname, kind, &AgDefaultDisc);
  initAttrs(root, gs);
  Agsym_t *const G_bb = agfindgraphattr(root, const_cast<char *>("bb"));
  if (doPack)
    assert(G_bb);
 
  /* add command-line attributes */
  for (attr_t &a : G_args) {
    if (Agsym_t *rv = agfindgraphattr(root, a.name))
      agxset(root, rv, a.value);
    else
      agattr_text(root, AGRAPH, a.name, a.value);
  }
 
  /* do common initialization. This will handle root's label. */
  init_graph(root, false, gvc);
  State = GVSPLINES;
 
  used_t gnames; // dict of used subgraph names
  used_t nnames; // dict of used node names
  for (size_t i = 0; i < gs.size(); i++) {
    Agraph_t *g = gs[i];
    if (verbose)
      std::cerr << "Cloning graph " << agnameof(g) << '\n';
    GD_n_cluster(root) += GD_n_cluster(g);
    GD_has_labels(root) |= GD_has_labels(g);
 
    /* Clone nodes, checking for node name conflicts */
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
      if (doWarn && agfindnode(root, agnameof(n))) {
        std::cerr << "Warning: node " << agnameof(n) << " in graph[" << i
                  << "] " << agnameof(g) << " already defined\n"
                  << "Some nodes will be renamed.\n";
        doWarn = false;
      }
      np = agnode(root, xName(nnames, agnameof(n)).data(), 1);
      agbindrec(np, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true);
      ND_alg(n) = np;
      cloneNode(n, np);
    }
 
    /* wrap the clone of g in a subgraph of root */
    subg = agsubg(root, xName(gnames, agnameof(g)).data(), 1);
    agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
    cloneSubg(g, subg, G_bb, gnames);
  }
 
  /* set up cluster tree */
  if (GD_n_cluster(root)) {
    int j, idx;
    void *const p = gv_calloc(1 + GD_n_cluster(root), sizeof(graph_t *));
    GD_clust(root) = new (p) graph_t *[1 + GD_n_cluster(root)]{};
 
    idx = 1;
    for (Agraph_t *g : gs) {
      for (j = 1; j <= GD_n_cluster(g); j++) {
        Agraph_t *c = GETCLUST(GD_clust(g)[j]);
        GD_clust(root)[idx++] = c;
        cloneClusterTree(GD_clust(g)[j], c);
      }
    }
  }
 
  return root;
}
 
/* Read input, parse the graphs, use init_nop (neato -n) to
 * read in all attributes need for layout.
 * Return the list of graphs. If cp != nullptr, set it to the number
 * of graphs read.
 * We keep track of the types of graphs read. They all must be
 * either directed or undirected. If all graphs are strict, the
 * combined graph will be strict; other, the combined graph will
 * be non-strict.
 *
 * @param kind [out] The type to use for the combined graph
 */
static std::vector<Agraph_t *> readGraphs(GVC_t *gvc,
                                          std::optional<Agdesc_t> &kind) {
  std::vector<Agraph_t *> gs;
  ingraph_state ig;
 
  /* set various state values */
  PSinputscale = POINTS_PER_INCH;
  Nop = 2;
 
  newIngraph(&ig, myFiles);
  while (Agraph_t *g = nextGraph(&ig)) {
    if (verbose)
      std::cerr << "Reading graph " << agnameof(g) << '\n';
    if (agnnodes(g) == 0) {
      std::cerr << "Graph " << agnameof(g) << " is empty - ignoring\n";
      continue;
    }
    if (!kind.has_value()) {
      kind = g->desc;
    } else if (kind->directed != g->desc.directed) {
      std::cerr << "Error: all graphs must be directed or undirected\n";
      graphviz_exit(1);
    } else if (!agisstrict(g))
      kind = g->desc;
    init_graph(g, doPack, gvc);
    gs.push_back(g);
  }
 
  return gs;
}
 
/* Compute the bounding box containing the graphs.
 * We can just use the bounding boxes of the graphs.
 */
static boxf compBB(std::vector<Agraph_t *> &gs) {
  boxf bb, bb2;
 
  bb = GD_bb(gs[0]);
 
  for (size_t i = 1; i < gs.size(); i++) {
    bb2 = GD_bb(gs[i]);
    bb.LL.x = std::min(bb.LL.x, bb2.LL.x);
    bb.LL.y = std::min(bb.LL.y, bb2.LL.y);
    bb.UR.x = std::max(bb.UR.x, bb2.UR.x);
    bb.UR.y = std::max(bb.UR.y, bb2.UR.y);
  }
 
  return bb;
}
 
int main(int argc, char *argv[]) {
  Agraph_t *g;
  pack_info pinfo;
  GVC_t *gvc;
 
  init(argc, argv, &pinfo);
 
  (void)agseterrf(handle_error);
 
  doPack = (pinfo.mode != l_undef);
 
  lt_preloaded_symbols[0].address = &gvplugin_neato_layout_LTX_library;
  gvc = gvContextPlugins(lt_preloaded_symbols, DEMAND_LOADING);
  std::optional<Agdesc_t> kind; // type of graph
  std::vector<Agraph_t *> gs = readGraphs(gvc, kind);
  if (gs.empty())
    graphviz_exit(0);
 
  /* pack graphs */
  if (doPack) {
    if (packGraphs(gs.size(), gs.data(), 0, &pinfo)) {
      std::cerr << "gvpack: packing of graphs failed.\n";
      graphviz_exit(1);
    }
  }
 
  /* create union graph and copy attributes */
  assert(kind.has_value());
  g = cloneGraph(gs, gvc, *kind);
 
  /* compute new top-level bb and set */
  if (doPack) {
    GD_bb(g) = compBB(gs);
    dotneato_postprocess(g);
    attach_attrs(g);
  }
  agwrite(g, outfp);
  graphviz_exit(0);
}