dotsplines.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
 *************************************************************************/
 
/*
 * set edge splines.
 */
 
#include <assert.h>
#include <common/boxes.h>
#include <dotgen/dot.h>
#include <math.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/gv_math.h>
#include <util/list.h>
 
#ifdef ORTHO
#include <ortho/ortho.h>
#endif
 
#define NSUB 9    /* number of subdivisions, re-aiming splines */
#define CHUNK 128 /* in building list of edges */
 
#define MINW 16 /* minimum width of a box in the edge path */
#define HALFMINW 8
 
#define FWDEDGE 16
#define BWDEDGE 32
 
#define MAINGRAPH 64
#define AUXGRAPH 128
#define GRAPHTYPEMASK 192 /* the OR of the above */
 
#define MAKEFWDEDGE(new, old)                                                  \
  {                                                                            \
    edge_t *newp;                                                              \
    Agedgeinfo_t *info;                                                        \
    newp = new;                                                                \
    info = (Agedgeinfo_t *)newp->base.data;                                    \
    *info = *(Agedgeinfo_t *)old->base.data;                                   \
    *newp = *old;                                                              \
    newp->base.data = (Agrec_t *)info;                                         \
    AGTAIL(newp) = AGHEAD(old);                                                \
    AGHEAD(newp) = AGTAIL(old);                                                \
    ED_tail_port(newp) = ED_head_port(old);                                    \
    ED_head_port(newp) = ED_tail_port(old);                                    \
    ED_edge_type(newp) = VIRTUAL;                                              \
    ED_to_orig(newp) = old;                                                    \
  }
 
typedef struct {
  double LeftBound;
  double RightBound;
  double Splinesep;
  double Multisep;
  boxf *Rank_box;
} spline_info_t;
 
DEFINE_LIST(points, pointf)
 
static void adjustregularpath(path *, size_t, size_t);
static Agedge_t *bot_bound(Agedge_t *, int);
static bool pathscross(Agnode_t *, Agnode_t *, Agedge_t *, Agedge_t *);
static Agraph_t *cl_bound(graph_t *, Agnode_t *, Agnode_t *);
static bool cl_vninside(Agraph_t *, Agnode_t *);
static void completeregularpath(path *, Agedge_t *, Agedge_t *, pathend_t *,
                                pathend_t *, const boxes_t *);
static int edgecmp(const void *, const void *);
static void make_flat_edge(graph_t *, spline_info_t *, path *, Agedge_t **,
                           unsigned, unsigned, int);
static void make_regular_edge(graph_t *g, spline_info_t *, path *, Agedge_t **,
                              unsigned, unsigned, int);
static boxf makeregularend(boxf, int, double);
static boxf maximal_bbox(graph_t *g, spline_info_t *, Agnode_t *, Agedge_t *,
                         Agedge_t *);
static Agnode_t *neighbor(graph_t *, Agnode_t *, Agedge_t *, Agedge_t *, int);
static void place_vnlabel(Agnode_t *);
static boxf rank_box(spline_info_t *sp, Agraph_t *, int);
static void recover_slack(Agedge_t *, path *);
static void resize_vn(Agnode_t *, double, double, double);
static void setflags(Agedge_t *, int, int, int);
static int straight_len(Agnode_t *);
static Agedge_t *straight_path(Agedge_t *, int, points_t *);
static Agedge_t *top_bound(Agedge_t *, int);
 
#define GROWEDGES                                                              \
  do {                                                                         \
    edges = gv_recalloc(edges, n_edges, n_edges + CHUNK, sizeof(edge_t *));    \
  } while (0)
 
static edge_t *getmainedge(edge_t *e) {
  edge_t *le = e;
  while (ED_to_virt(le))
    le = ED_to_virt(le);
  while (ED_to_orig(le))
    le = ED_to_orig(le);
  return le;
}
 
static bool spline_merge(node_t *n) {
  return ND_node_type(n) == VIRTUAL &&
         (ND_in(n).size > 1 || ND_out(n).size > 1);
}
 
static bool swap_ends_p(edge_t *e) {
  while (ED_to_orig(e))
    e = ED_to_orig(e);
  if (ND_rank(aghead(e)) > ND_rank(agtail(e)))
    return false;
  if (ND_rank(aghead(e)) < ND_rank(agtail(e)))
    return true;
  if (ND_order(aghead(e)) >= ND_order(agtail(e)))
    return false;
  return true;
}
 
static splineInfo sinfo = {.swapEnds = swap_ends_p,
                           .splineMerge = spline_merge};
 
int portcmp(port p0, port p1) {
  if (!p1.defined)
    return p0.defined ? 1 : 0;
  if (!p0.defined)
    return -1;
  if (p0.p.x < p1.p.x)
    return -1;
  if (p0.p.x > p1.p.x)
    return 1;
  if (p0.p.y < p1.p.y)
    return -1;
  if (p0.p.y > p1.p.y)
    return 1;
  return 0;
}
 
static void swap_bezier(bezier *b) {
  const size_t sz = b->size;
  for (size_t i = 0; i < sz / 2; ++i) { // reverse list of points
    SWAP(&b->list[i], &b->list[sz - 1 - i]);
  }
 
  SWAP(&b->sflag, &b->eflag);
  SWAP(&b->sp, &b->ep);
}
 
static void swap_spline(splines *s) {
  const size_t sz = s->size;
 
  // reverse list
  for (size_t i = 0; i < sz / 2; ++i) {
    SWAP(&s->list[i], &s->list[sz - 1 - i]);
  }
 
  // swap beziers
  for (size_t i = 0; i < sz; ++i) {
    swap_bezier(&s->list[i]);
  }
}
 
/* edge_normalize:
 * Some back edges are reversed during layout and the reversed edge
 * is used to compute the spline. We would like to guarantee that
 * the order of control points always goes from tail to head, so
 * we reverse them if necessary.
 */
static void edge_normalize(graph_t *g) {
  edge_t *e;
  node_t *n;
 
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
      if (sinfo.swapEnds(e) && ED_spl(e))
        swap_spline(ED_spl(e));
    }
  }
}
 
/* resetRW:
 * In position, each node has its rw stored in mval and,
 * if a node is part of a loop, rw may be increased to
 * reflect the loops and associated labels. We restore
 * the original value here.
 */
static void resetRW(graph_t *g) {
  node_t *n;
 
  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
    if (ND_other(n).list) {
      SWAP(&ND_rw(n), &ND_mval(n));
    }
  }
}
 
/* setEdgeLabelPos:
 * Set edge label position information for regular and non-adjacent flat edges.
 * Dot has allocated space and position for these labels. This info will be
 * used when routing orthogonal edges.
 */
static void setEdgeLabelPos(graph_t *g) {
  node_t *n;
  textlabel_t *l;
 
  /* place regular edge labels */
  for (n = GD_nlist(g); n; n = ND_next(n)) {
    if (ND_node_type(n) == VIRTUAL) {
      if (ND_alg(n)) { // label of non-adjacent flat edge
        edge_t *fe = ND_alg(n);
        l = ED_label(fe);
        assert(l);
        l->pos = ND_coord(n);
        l->set = true;
      } else if ((l = ND_label(n))) { // label of regular edge
        place_vnlabel(n);
      }
      if (l)
        updateBB(g, l);
    }
  }
}
 
static void dot_splines_(graph_t *g, int normalize) {
  int i, j, k, n_nodes;
  node_t *n;
  Agedgeinfo_t fwdedgeai, fwdedgebi;
  Agedgepair_t fwdedgea, fwdedgeb;
  edge_t *e, *e0, *e1, *ea, *eb, *le0, *le1, **edges = NULL;
  path P = {0};
  int et = EDGE_TYPE(g);
  fwdedgea.out.base.data = (Agrec_t *)&fwdedgeai;
  fwdedgeb.out.base.data = (Agrec_t *)&fwdedgebi;
 
  if (et == EDGETYPE_NONE)
    return;
  if (et == EDGETYPE_CURVED) {
    resetRW(g);
    if (GD_has_labels(g->root) & EDGE_LABEL) {
      agwarningf("edge labels with splines=curved not supported in dot - use "
                 "xlabels\n");
    }
  }
#ifdef ORTHO
  if (et == EDGETYPE_ORTHO) {
    resetRW(g);
    if (GD_has_labels(g->root) & EDGE_LABEL) {
      setEdgeLabelPos(g);
      orthoEdges(g, true);
    } else
      orthoEdges(g, false);
    goto finish;
  }
#else
  (void)setEdgeLabelPos;
#endif
 
  mark_lowclusters(g);
  if (routesplinesinit())
    return;
  spline_info_t sd = {.Splinesep = GD_nodesep(g) / 4,
                      .Multisep = GD_nodesep(g)};
  edges = gv_calloc(CHUNK, sizeof(edge_t *));
 
  /* compute boundaries and list of splines */
  unsigned n_edges = 0;
  n_nodes = 0;
  for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
    n_nodes += GD_rank(g)[i].n;
    if ((n = GD_rank(g)[i].v[0]))
      sd.LeftBound = MIN(sd.LeftBound, (ND_coord(n).x - ND_lw(n)));
    if (GD_rank(g)[i].n && (n = GD_rank(g)[i].v[GD_rank(g)[i].n - 1]))
      sd.RightBound = MAX(sd.RightBound, (ND_coord(n).x + ND_rw(n)));
    sd.LeftBound -= MINW;
    sd.RightBound += MINW;
 
    for (j = 0; j < GD_rank(g)[i].n; j++) {
      n = GD_rank(g)[i].v[j];
      /* if n is the label of a flat edge, copy its position to
       * the label.
       */
      if (ND_alg(n)) {
        edge_t *fe = ND_alg(n);
        assert(ED_label(fe));
        ED_label(fe)->pos = ND_coord(n);
        ED_label(fe)->set = true;
      }
      if (ND_node_type(n) != NORMAL && !sinfo.splineMerge(n))
        continue;
      for (k = 0; (e = ND_out(n).list[k]); k++) {
        if (ED_edge_type(e) == FLATORDER || ED_edge_type(e) == IGNORED)
          continue;
        setflags(e, REGULAREDGE, FWDEDGE, MAINGRAPH);
        edges[n_edges++] = e;
        if (n_edges % CHUNK == 0)
          GROWEDGES;
      }
      if (ND_flat_out(n).list)
        for (k = 0; (e = ND_flat_out(n).list[k]); k++) {
          setflags(e, FLATEDGE, 0, AUXGRAPH);
          edges[n_edges++] = e;
          if (n_edges % CHUNK == 0)
            GROWEDGES;
        }
      if (ND_other(n).list) {
        /* In position, each node has its rw stored in mval and,
         * if a node is part of a loop, rw may be increased to
         * reflect the loops and associated labels. We restore
         * the original value here.
         */
        if (ND_node_type(n) == NORMAL) {
          SWAP(&ND_rw(n), &ND_mval(n));
        }
        for (k = 0; (e = ND_other(n).list[k]); k++) {
          setflags(e, 0, 0, AUXGRAPH);
          edges[n_edges++] = e;
          if (n_edges % CHUNK == 0)
            GROWEDGES;
        }
      }
    }
  }
 
  /* Sort so that equivalent edges are contiguous.
   * Equivalence should basically mean that 2 edges have the
   * same set {(tailnode,tailport),(headnode,headport)}, or
   * alternatively, the edges would be routed identically if
   * routed separately.
   */
  qsort(edges, n_edges, sizeof(edges[0]), edgecmp);
 
  /* FIXME: just how many boxes can there be? */
  P.boxes = gv_calloc(n_nodes + 20 * 2 * NSUB, sizeof(boxf));
  sd.Rank_box = gv_calloc(i, sizeof(boxf));
 
  if (et == EDGETYPE_LINE) {
    /* place regular edge labels */
    for (n = GD_nlist(g); n; n = ND_next(n)) {
      if (ND_node_type(n) == VIRTUAL && ND_label(n)) {
        place_vnlabel(n);
      }
    }
  }
 
  for (unsigned l = 0; l < n_edges;) {
    const unsigned ind = l;
    le0 = getmainedge((e0 = edges[l++]));
    if (ED_tail_port(e0).defined || ED_head_port(e0).defined) {
      ea = e0;
    } else {
      ea = le0;
    }
    if (ED_tree_index(ea) & BWDEDGE) {
      MAKEFWDEDGE(&fwdedgea.out, ea);
      ea = &fwdedgea.out;
    }
    unsigned cnt;
    for (cnt = 1; l < n_edges; cnt++, l++) {
      if (le0 != (le1 = getmainedge((e1 = edges[l]))))
        break;
      if (ED_adjacent(e0))
        continue; /* all flat adjacent edges at once */
      if (ED_tail_port(e1).defined || ED_head_port(e1).defined) {
        eb = e1;
      } else {
        eb = le1;
      }
      if (ED_tree_index(eb) & BWDEDGE) {
        MAKEFWDEDGE(&fwdedgeb.out, eb);
        eb = &fwdedgeb.out;
      }
      if (portcmp(ED_tail_port(ea), ED_tail_port(eb)))
        break;
      if (portcmp(ED_head_port(ea), ED_head_port(eb)))
        break;
      if ((ED_tree_index(e0) & EDGETYPEMASK) == FLATEDGE &&
          ED_label(e0) != ED_label(e1))
        break;
      if (ED_tree_index(edges[l]) & MAINGRAPH) /* Aha! -C is on */
        break;
    }
 
    if (et == EDGETYPE_CURVED) {
      edge_t **edgelist = gv_calloc(cnt, sizeof(edge_t *));
      edgelist[0] = getmainedge((edges + ind)[0]);
      for (unsigned ii = 1; ii < cnt; ii++)
        edgelist[ii] = (edges + ind)[ii];
      makeStraightEdges(g, edgelist, cnt, et, &sinfo);
      free(edgelist);
    } else if (agtail(e0) == aghead(e0)) {
      int r;
      double sizey;
      n = agtail(e0);
      r = ND_rank(n);
      if (r == GD_maxrank(g)) {
        if (r > 0)
          sizey = ND_coord(GD_rank(g)[r - 1].v[0]).y - ND_coord(n).y;
        else
          sizey = ND_ht(n);
      } else if (r == GD_minrank(g)) {
        sizey = ND_coord(n).y - ND_coord(GD_rank(g)[r + 1].v[0]).y;
      } else {
        double upy = ND_coord(GD_rank(g)[r - 1].v[0]).y - ND_coord(n).y;
        double dwny = ND_coord(n).y - ND_coord(GD_rank(g)[r + 1].v[0]).y;
        sizey = MIN(upy, dwny);
      }
      makeSelfEdge(edges, ind, cnt, sd.Multisep, sizey / 2, &sinfo);
      for (unsigned b = 0; b < cnt; b++) {
        e = edges[ind + b];
        if (ED_label(e))
          updateBB(g, ED_label(e));
      }
    } else if (ND_rank(agtail(e0)) == ND_rank(aghead(e0))) {
      make_flat_edge(g, &sd, &P, edges, ind, cnt, et);
    } else
      make_regular_edge(g, &sd, &P, edges, ind, cnt, et);
  }
 
  /* place regular edge labels */
  for (n = GD_nlist(g); n; n = ND_next(n)) {
    if (ND_node_type(n) == VIRTUAL && ND_label(n)) {
      place_vnlabel(n);
      updateBB(g, ND_label(n));
    }
  }
 
  /* normalize splines so they always go from tail to head */
  /* place_portlabel relies on this being done first */
  if (normalize)
    edge_normalize(g);
 
#ifdef ORTHO
finish:
#endif
  /* place port labels */
  /* FIX: head and tail labels are not part of cluster bbox */
  if ((E_headlabel || E_taillabel) && (E_labelangle || E_labeldistance)) {
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
      if (E_headlabel) {
        for (e = agfstin(g, n); e; e = agnxtin(g, e))
          if (ED_head_label(AGMKOUT(e))) {
            place_portlabel(AGMKOUT(e), true);
            updateBB(g, ED_head_label(AGMKOUT(e)));
          }
      }
      if (E_taillabel) {
        for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
          if (ED_tail_label(e)) {
            if (place_portlabel(e, false))
              updateBB(g, ED_tail_label(e));
          }
        }
      }
    }
  }
 
#ifdef ORTHO
  if (et != EDGETYPE_ORTHO && et != EDGETYPE_CURVED) {
#else
  if (et != EDGETYPE_CURVED) {
#endif
    free(sd.Rank_box);
    routesplinesterm();
  }
  free(edges);
  free(P.boxes);
  State = GVSPLINES;
  EdgeLabelsDone = 1;
}
 
/* dot_splines:
 * If the splines attribute is defined but equal to "", skip edge routing.
 */
void dot_splines(graph_t *g) { dot_splines_(g, 1); }
 
/* place_vnlabel:
 * assign position of an edge label from its virtual node
 * This is for regular edges only.
 */
static void place_vnlabel(node_t *n) {
  pointf dimen;
  double width;
  edge_t *e;
  if (ND_in(n).size == 0)
    return; /* skip flat edge labels here */
  for (e = ND_out(n).list[0]; ED_edge_type(e) != NORMAL; e = ED_to_orig(e))
    ;
  dimen = ED_label(e)->dimen;
  width = GD_flip(agraphof(n)) ? dimen.y : dimen.x;
  ED_label(e)->pos.x = ND_coord(n).x + width / 2.0;
  ED_label(e)->pos.y = ND_coord(n).y;
  ED_label(e)->set = true;
}
 
static void setflags(edge_t *e, int hint1, int hint2, int f3) {
  int f1, f2;
  if (hint1 != 0)
    f1 = hint1;
  else {
    if (agtail(e) == aghead(e))
      if (ED_tail_port(e).defined || ED_head_port(e).defined)
        f1 = SELFWPEDGE;
      else
        f1 = SELFNPEDGE;
    else if (ND_rank(agtail(e)) == ND_rank(aghead(e)))
      f1 = FLATEDGE;
    else
      f1 = REGULAREDGE;
  }
  if (hint2 != 0)
    f2 = hint2;
  else {
    if (f1 == REGULAREDGE)
      f2 = ND_rank(agtail(e)) < ND_rank(aghead(e)) ? FWDEDGE : BWDEDGE;
    else if (f1 == FLATEDGE)
      f2 = ND_order(agtail(e)) < ND_order(aghead(e)) ? FWDEDGE : BWDEDGE;
    else /* f1 == SELF*EDGE */
      f2 = FWDEDGE;
  }
  ED_tree_index(e) = (f1 | f2 | f3);
}
 
/* edgecmp:
 * lexicographically order edges by
 *  - edge type
 *  - |rank difference of nodes|
 *  - |x difference of nodes|
 *  - id of witness edge for equivalence class
 *  - port comparison
 *  - graph type
 *  - labels if flat edges
 *  - edge id
 */
static int edgecmp(const void *x, const void *y) {
// Suppress Clang/GCC -Wcast-qual warning. Casting away const here is acceptable
// as the later usage is const. We need the cast because the macros use
// non-const pointers for genericity.
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wcast-qual"
#endif
  edge_t **ptr0 = (edge_t **)x;
  edge_t **ptr1 = (edge_t **)y;
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
  Agedgeinfo_t fwdedgeai, fwdedgebi;
  Agedgepair_t fwdedgea, fwdedgeb;
  edge_t *e0, *e1, *ea, *eb, *le0, *le1;
  int et0, et1, v0, v1, rv;
  double t0, t1;
 
  fwdedgea.out.base.data = (Agrec_t *)&fwdedgeai;
  fwdedgeb.out.base.data = (Agrec_t *)&fwdedgebi;
  e0 = *ptr0;
  e1 = *ptr1;
  et0 = ED_tree_index(e0) & EDGETYPEMASK;
  et1 = ED_tree_index(e1) & EDGETYPEMASK;
  if (et0 < et1) {
    return 1;
  }
  if (et0 > et1) {
    return -1;
  }
 
  le0 = getmainedge(e0);
  le1 = getmainedge(e1);
 
  t0 = ND_rank(agtail(le0)) - ND_rank(aghead(le0));
  t1 = ND_rank(agtail(le1)) - ND_rank(aghead(le1));
  v0 = abs((int)t0); /* ugly, but explicit as to how we avoid equality tests on
                        fp numbers */
  v1 = abs((int)t1);
  if (v0 < v1) {
    return -1;
  }
  if (v0 > v1) {
    return 1;
  }
 
  t0 = ND_coord(agtail(le0)).x - ND_coord(aghead(le0)).x;
  t1 = ND_coord(agtail(le1)).x - ND_coord(aghead(le1)).x;
  v0 = abs((int)t0);
  v1 = abs((int)t1);
  if (v0 < v1) {
    return -1;
  }
  if (v0 > v1) {
    return 1;
  }
 
  /* This provides a cheap test for edges having the same set of endpoints.  */
  if (AGSEQ(le0) < AGSEQ(le1)) {
    return -1;
  }
  if (AGSEQ(le0) > AGSEQ(le1)) {
    return 1;
  }
 
  ea = (ED_tail_port(e0).defined || ED_head_port(e0).defined) ? e0 : le0;
  if (ED_tree_index(ea) & BWDEDGE) {
    MAKEFWDEDGE(&fwdedgea.out, ea);
    ea = &fwdedgea.out;
  }
  eb = (ED_tail_port(e1).defined || ED_head_port(e1).defined) ? e1 : le1;
  if (ED_tree_index(eb) & BWDEDGE) {
    MAKEFWDEDGE(&fwdedgeb.out, eb);
    eb = &fwdedgeb.out;
  }
  if ((rv = portcmp(ED_tail_port(ea), ED_tail_port(eb))))
    return rv;
  if ((rv = portcmp(ED_head_port(ea), ED_head_port(eb))))
    return rv;
 
  et0 = ED_tree_index(e0) & GRAPHTYPEMASK;
  et1 = ED_tree_index(e1) & GRAPHTYPEMASK;
  if (et0 < et1) {
    return -1;
  }
  if (et0 > et1) {
    return 1;
  }
 
  if (et0 == FLATEDGE) {
    if (ED_label(e0) < ED_label(e1)) {
      return -1;
    }
    if (ED_label(e0) > ED_label(e1)) {
      return 1;
    }
  }
 
  if (AGSEQ(e0) < AGSEQ(e1)) {
    return -1;
  }
  if (AGSEQ(e0) > AGSEQ(e1)) {
    return 1;
  }
  return 0;
}
 
typedef struct {
  attrsym_t *E_constr;
  attrsym_t *E_dir;
  attrsym_t *E_samehead;
  attrsym_t *E_sametail;
  attrsym_t *E_weight;
  attrsym_t *E_minlen;
  attrsym_t *E_fontcolor;
  attrsym_t *E_fontname;
  attrsym_t *E_fontsize;
  attrsym_t *E_headclip;
  attrsym_t *E_headlabel;
  attrsym_t *E_label;
  attrsym_t *E_label_float;
  attrsym_t *E_labelfontcolor;
  attrsym_t *E_labelfontname;
  attrsym_t *E_labelfontsize;
  attrsym_t *E_tailclip;
  attrsym_t *E_taillabel;
  attrsym_t *E_xlabel;
 
  attrsym_t *N_height;
  attrsym_t *N_width;
  attrsym_t *N_shape;
  attrsym_t *N_style;
  attrsym_t *N_fontsize;
  attrsym_t *N_fontname;
  attrsym_t *N_fontcolor;
  attrsym_t *N_label;
  attrsym_t *N_xlabel;
  attrsym_t *N_showboxes;
  attrsym_t *N_ordering;
  attrsym_t *N_sides;
  attrsym_t *N_peripheries;
  attrsym_t *N_skew;
  attrsym_t *N_orientation;
  attrsym_t *N_distortion;
  attrsym_t *N_fixed;
  attrsym_t *N_nojustify;
  attrsym_t *N_group;
 
  attrsym_t *G_ordering;
  int State;
} attr_state_t;
 
static void setState(graph_t *auxg, attr_state_t *attr_state) {
  /* save state */
  attr_state->E_constr = E_constr;
  attr_state->E_dir = E_dir;
  attr_state->E_samehead = E_samehead;
  attr_state->E_sametail = E_sametail;
  attr_state->E_weight = E_weight;
  attr_state->E_minlen = E_minlen;
  attr_state->E_fontcolor = E_fontcolor;
  attr_state->E_fontname = E_fontname;
  attr_state->E_fontsize = E_fontsize;
  attr_state->E_headclip = E_headclip;
  attr_state->E_headlabel = E_headlabel;
  attr_state->E_label = E_label;
  attr_state->E_label_float = E_label_float;
  attr_state->E_labelfontcolor = E_labelfontcolor;
  attr_state->E_labelfontname = E_labelfontname;
  attr_state->E_labelfontsize = E_labelfontsize;
  attr_state->E_tailclip = E_tailclip;
  attr_state->E_taillabel = E_taillabel;
  attr_state->E_xlabel = E_xlabel;
  attr_state->N_height = N_height;
  attr_state->N_width = N_width;
  attr_state->N_shape = N_shape;
  attr_state->N_style = N_style;
  attr_state->N_fontsize = N_fontsize;
  attr_state->N_fontname = N_fontname;
  attr_state->N_fontcolor = N_fontcolor;
  attr_state->N_label = N_label;
  attr_state->N_xlabel = N_xlabel;
  attr_state->N_showboxes = N_showboxes;
  attr_state->N_ordering = N_ordering;
  attr_state->N_sides = N_sides;
  attr_state->N_peripheries = N_peripheries;
  attr_state->N_skew = N_skew;
  attr_state->N_orientation = N_orientation;
  attr_state->N_distortion = N_distortion;
  attr_state->N_fixed = N_fixed;
  attr_state->N_nojustify = N_nojustify;
  attr_state->N_group = N_group;
  attr_state->State = State;
  attr_state->G_ordering = G_ordering;
 
  E_constr = NULL;
  E_dir = agattr(auxg, AGEDGE, "dir", NULL);
  E_samehead = agattr(auxg, AGEDGE, "samehead", NULL);
  E_sametail = agattr(auxg, AGEDGE, "sametail", NULL);
  E_weight = agattr(auxg, AGEDGE, "weight", NULL);
  if (!E_weight)
    E_weight = agattr(auxg, AGEDGE, "weight", "");
  E_minlen = NULL;
  E_fontcolor = NULL;
  E_fontname = agfindedgeattr(auxg, "fontname");
  E_fontsize = agfindedgeattr(auxg, "fontsize");
  E_headclip = agfindedgeattr(auxg, "headclip");
  E_headlabel = NULL;
  E_label = agfindedgeattr(auxg, "label");
  E_label_float = agfindedgeattr(auxg, "label_float");
  E_labelfontcolor = NULL;
  E_labelfontname = agfindedgeattr(auxg, "labelfontname");
  E_labelfontsize = agfindedgeattr(auxg, "labelfontsize");
  E_tailclip = agfindedgeattr(auxg, "tailclip");
  E_taillabel = NULL;
  E_xlabel = NULL;
  N_height = agfindnodeattr(auxg, "height");
  N_width = agfindnodeattr(auxg, "width");
  N_shape = agfindnodeattr(auxg, "shape");
  N_style = NULL;
  N_fontsize = agfindnodeattr(auxg, "fontsize");
  N_fontname = agfindnodeattr(auxg, "fontname");
  N_fontcolor = NULL;
  N_label = agfindnodeattr(auxg, "label");
  N_xlabel = NULL;
  N_showboxes = NULL;
  N_ordering = agfindnodeattr(auxg, "ordering");
  N_sides = agfindnodeattr(auxg, "sides");
  N_peripheries = agfindnodeattr(auxg, "peripheries");
  N_skew = agfindnodeattr(auxg, "skew");
  N_orientation = agfindnodeattr(auxg, "orientation");
  N_distortion = agfindnodeattr(auxg, "distortion");
  N_fixed = agfindnodeattr(auxg, "fixed");
  N_nojustify = NULL;
  N_group = NULL;
  G_ordering = agfindgraphattr(auxg, "ordering");
}
 
/* cloneGraph:
 * Create clone graph. It stores the global Agsyms, to be
 * restored in cleanupCloneGraph. The graph uses the main
 * graph's settings for certain geometry parameters, and
 * declares all node and edge attributes used in the original
 * graph.
 */
static graph_t *cloneGraph(graph_t *g, attr_state_t *attr_state) {
  Agsym_t *sym;
  graph_t *auxg;
  if (agisdirected(g))
    auxg = agopen("auxg", Agdirected, NULL);
  else
    auxg = agopen("auxg", Agundirected, NULL);
  agbindrec(auxg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
  agattr(auxg, AGRAPH, "rank", "");
  GD_drawing(auxg) = gv_alloc(sizeof(layout_t));
  GD_drawing(auxg)->quantum = GD_drawing(g)->quantum;
  GD_drawing(auxg)->dpi = GD_drawing(g)->dpi;
 
  GD_charset(auxg) = GD_charset(g);
  if (GD_flip(g))
    SET_RANKDIR(auxg, RANKDIR_TB);
  else
    SET_RANKDIR(auxg, RANKDIR_LR);
  GD_nodesep(auxg) = GD_nodesep(g);
  GD_ranksep(auxg) = GD_ranksep(g);
 
  // copy node attrs to auxg
  sym = agnxtattr(agroot(g), AGNODE, NULL); // get the first attr.
  for (; sym; sym = agnxtattr(agroot(g), AGNODE, sym)) {
    const bool is_html = aghtmlstr(sym->defval);
    is_html ? agattr_html(auxg, AGNODE, sym->name, sym->defval)
            : agattr(auxg, AGNODE, sym->name, sym->defval);
  }
 
  // copy edge attributes
  sym = agnxtattr(agroot(g), AGEDGE, NULL); // get the first attr.
  for (; sym; sym = agnxtattr(agroot(g), AGEDGE, sym)) {
    const bool is_html = aghtmlstr(sym->defval);
    is_html ? agattr_html(auxg, AGEDGE, sym->name, sym->defval)
            : agattr(auxg, AGEDGE, sym->name, sym->defval);
  }
 
  if (!agattr(auxg, AGEDGE, "headport", NULL))
    agattr(auxg, AGEDGE, "headport", "");
  if (!agattr(auxg, AGEDGE, "tailport", NULL))
    agattr(auxg, AGEDGE, "tailport", "");
 
  setState(auxg, attr_state);
 
  return auxg;
}
 
static void cleanupCloneGraph(graph_t *g, attr_state_t *attr_state) {
  /* restore main graph syms */
  E_constr = attr_state->E_constr;
  E_dir = attr_state->E_dir;
  E_samehead = attr_state->E_samehead;
  E_sametail = attr_state->E_sametail;
  E_weight = attr_state->E_weight;
  E_minlen = attr_state->E_minlen;
  E_fontcolor = attr_state->E_fontcolor;
  E_fontname = attr_state->E_fontname;
  E_fontsize = attr_state->E_fontsize;
  E_headclip = attr_state->E_headclip;
  E_headlabel = attr_state->E_headlabel;
  E_label = attr_state->E_label;
  E_label_float = attr_state->E_label_float;
  E_labelfontcolor = attr_state->E_labelfontcolor;
  E_labelfontname = attr_state->E_labelfontname;
  E_labelfontsize = attr_state->E_labelfontsize;
  E_tailclip = attr_state->E_tailclip;
  E_taillabel = attr_state->E_taillabel;
  E_xlabel = attr_state->E_xlabel;
  N_height = attr_state->N_height;
  N_width = attr_state->N_width;
  N_shape = attr_state->N_shape;
  N_style = attr_state->N_style;
  N_fontsize = attr_state->N_fontsize;
  N_fontname = attr_state->N_fontname;
  N_fontcolor = attr_state->N_fontcolor;
  N_label = attr_state->N_label;
  N_xlabel = attr_state->N_xlabel;
  N_showboxes = attr_state->N_showboxes;
  N_ordering = attr_state->N_ordering;
  N_sides = attr_state->N_sides;
  N_peripheries = attr_state->N_peripheries;
  N_skew = attr_state->N_skew;
  N_orientation = attr_state->N_orientation;
  N_distortion = attr_state->N_distortion;
  N_fixed = attr_state->N_fixed;
  N_nojustify = attr_state->N_nojustify;
  N_group = attr_state->N_group;
  G_ordering = attr_state->G_ordering;
  State = attr_state->State;
 
  dot_cleanup(g);
  agclose(g);
}
 
/* cloneNode:
 * If original graph has rankdir=LR or RL, records change shape,
 * so we wrap a record node's label in "{...}" to prevent this.
 */
static node_t *cloneNode(graph_t *g, node_t *orign) {
  node_t *n = agnode(g, agnameof(orign), 1);
  agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true);
  agcopyattr(orign, n);
  if (shapeOf(orign) == SH_RECORD) {
    agxbuf buf = {0};
    agxbprint(&buf, "{%s}", ND_label(orign)->text);
    agset(n, "label", agxbuse(&buf));
    agxbfree(&buf);
  }
 
  return n;
}
 
static edge_t *cloneEdge(graph_t *g, node_t *tn, node_t *hn, edge_t *orig) {
  edge_t *e = agedge(g, tn, hn, NULL, 1);
  agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), true);
  agcopyattr(orig, e);
 
  return e;
}
 
/* transformf:
 * Rotate, if necessary, then translate points.
 */
static pointf transformf(pointf p, pointf del, int flip) {
  if (flip) {
    double i = p.x;
    p.x = p.y;
    p.y = -i;
  }
  return add_pointf(p, del);
}
 
/* edgelblcmpfn:
 * lexicographically order edges by
 *  - has label
 *  - label is wider
 *  - label is higher
 */
static int edgelblcmpfn(const void *x, const void *y) {
// Suppress Clang/GCC -Wcast-qual warning. Casting away const here is acceptable
// as the later usage is const. We need the cast because the macros use
// non-const pointers for genericity.
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wcast-qual"
#endif
  edge_t **ptr0 = (edge_t **)x;
  edge_t **ptr1 = (edge_t **)y;
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
  pointf sz0, sz1;
 
  edge_t *e0 = *ptr0;
  edge_t *e1 = *ptr1;
 
  if (ED_label(e0)) {
    if (ED_label(e1)) {
      sz0 = ED_label(e0)->dimen;
      sz1 = ED_label(e1)->dimen;
      if (sz0.x > sz1.x)
        return -1;
      if (sz0.x < sz1.x)
        return 1;
      if (sz0.y > sz1.y)
        return -1;
      if (sz0.y < sz1.y)
        return 1;
      return 0;
    }
    return -1;
  }
  if (ED_label(e1)) {
    return 1;
  }
  return 0;
}
 
#define LBL_SPACE 6 /* space between labels, in points */
 
/* makeSimpleFlatLabels:
 * This handles the second simplest case for flat edges between
 * two adjacent nodes. We still invoke a dot on a rotated problem
 * to handle edges with ports. This usually works, but fails for
 * records because of their weird nature.
 */
static void makeSimpleFlatLabels(node_t *tn, node_t *hn, edge_t **edges,
                                 unsigned ind, unsigned cnt, int et,
                                 unsigned n_lbls) {
  Ppoly_t poly;
  edge_t *e = edges[ind];
  pointf points[10], tp, hp;
  double leftend, rightend, ctrx, ctry, miny, maxy;
  double uminx, umaxx;
  double lminx = 0.0, lmaxx = 0.0;
 
  edge_t **earray = gv_calloc(cnt, sizeof(edge_t *));
 
  for (unsigned i = 0; i < cnt; i++) {
    earray[i] = edges[ind + i];
  }
 
  qsort(earray, cnt, sizeof(edge_t *), edgelblcmpfn);
 
  tp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
  hp = add_pointf(ND_coord(hn), ED_head_port(e).p);
 
  leftend = tp.x + ND_rw(tn);
  rightend = hp.x - ND_lw(hn);
  ctrx = (leftend + rightend) / 2.0;
 
  /* do first edge */
  e = earray[0];
  size_t pointn = 0;
  points[pointn++] = tp;
  points[pointn++] = tp;
  points[pointn++] = hp;
  points[pointn++] = hp;
  clip_and_install(e, aghead(e), points, pointn, &sinfo);
  ED_label(e)->pos.x = ctrx;
  ED_label(e)->pos.y = tp.y + (ED_label(e)->dimen.y + LBL_SPACE) / 2.0;
  ED_label(e)->set = true;
 
  miny = tp.y + LBL_SPACE / 2.0;
  maxy = miny + ED_label(e)->dimen.y;
  uminx = ctrx - ED_label(e)->dimen.x / 2.0;
  umaxx = ctrx + ED_label(e)->dimen.x / 2.0;
 
  unsigned i;
  for (i = 1; i < n_lbls; i++) {
    e = earray[i];
    if (i % 2) { /* down */
      if (i == 1) {
        lminx = ctrx - ED_label(e)->dimen.x / 2.0;
        lmaxx = ctrx + ED_label(e)->dimen.x / 2.0;
      }
      miny -= LBL_SPACE + ED_label(e)->dimen.y;
      points[0] = tp;
      points[1].x = tp.x;
      points[1].y = miny - LBL_SPACE;
      points[2].x = hp.x;
      points[2].y = points[1].y;
      points[3] = hp;
      points[4].x = lmaxx;
      points[4].y = hp.y;
      points[5].x = lmaxx;
      points[5].y = miny;
      points[6].x = lminx;
      points[6].y = miny;
      points[7].x = lminx;
      points[7].y = tp.y;
      ctry = miny + ED_label(e)->dimen.y / 2.0;
    } else { /* up */
      points[0] = tp;
      points[1].x = uminx;
      points[1].y = tp.y;
      points[2].x = uminx;
      points[2].y = maxy;
      points[3].x = umaxx;
      points[3].y = maxy;
      points[4].x = umaxx;
      points[4].y = hp.y;
      points[5].x = hp.x;
      points[5].y = hp.y;
      points[6].x = hp.x;
      points[6].y = maxy + LBL_SPACE;
      points[7].x = tp.x;
      points[7].y = maxy + LBL_SPACE;
      ctry = maxy + ED_label(e)->dimen.y / 2.0 + LBL_SPACE;
      maxy += ED_label(e)->dimen.y + LBL_SPACE;
    }
    poly.pn = 8;
    poly.ps = (Ppoint_t *)points;
    size_t pn;
    pointf *ps = simpleSplineRoute(tp, hp, poly, &pn, et == EDGETYPE_PLINE);
    if (ps == NULL || pn == 0) {
      free(ps);
      free(earray);
      return;
    }
    ED_label(e)->pos.x = ctrx;
    ED_label(e)->pos.y = ctry;
    ED_label(e)->set = true;
    clip_and_install(e, aghead(e), ps, pn, &sinfo);
    free(ps);
  }
 
  /* edges with no labels */
  for (; i < cnt; i++) {
    e = earray[i];
    if (i % 2) { /* down */
      if (i == 1) {
        lminx = (2 * leftend + rightend) / 3.0;
        lmaxx = (leftend + 2 * rightend) / 3.0;
      }
      miny -= LBL_SPACE;
      points[0] = tp;
      points[1].x = tp.x;
      points[1].y = miny - LBL_SPACE;
      points[2].x = hp.x;
      points[2].y = points[1].y;
      points[3] = hp;
      points[4].x = lmaxx;
      points[4].y = hp.y;
      points[5].x = lmaxx;
      points[5].y = miny;
      points[6].x = lminx;
      points[6].y = miny;
      points[7].x = lminx;
      points[7].y = tp.y;
    } else { /* up */
      points[0] = tp;
      points[1].x = uminx;
      points[1].y = tp.y;
      points[2].x = uminx;
      points[2].y = maxy;
      points[3].x = umaxx;
      points[3].y = maxy;
      points[4].x = umaxx;
      points[4].y = hp.y;
      points[5].x = hp.x;
      points[5].y = hp.y;
      points[6].x = hp.x;
      points[6].y = maxy + LBL_SPACE;
      points[7].x = tp.x;
      points[7].y = maxy + LBL_SPACE;
      maxy += +LBL_SPACE;
    }
    poly.pn = 8;
    poly.ps = (Ppoint_t *)points;
    size_t pn;
    pointf *ps = simpleSplineRoute(tp, hp, poly, &pn, et == EDGETYPE_PLINE);
    if (ps == NULL || pn == 0) {
      free(ps);
      free(earray);
      return;
    }
    clip_and_install(e, aghead(e), ps, pn, &sinfo);
    free(ps);
  }
 
  free(earray);
}
 
static void makeSimpleFlat(node_t *tn, node_t *hn, edge_t **edges, unsigned ind,
                           unsigned cnt, int et) {
  edge_t *e = edges[ind];
  pointf points[10], tp, hp;
  double stepy, dy;
 
  tp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
  hp = add_pointf(ND_coord(hn), ED_head_port(e).p);
 
  stepy = cnt > 1 ? ND_ht(tn) / (double)(cnt - 1) : 0.;
  dy = tp.y - (cnt > 1 ? ND_ht(tn) / 2. : 0.);
 
  for (unsigned i = 0; i < cnt; i++) {
    e = edges[ind + i];
    size_t pointn = 0;
    if (et == EDGETYPE_SPLINE || et == EDGETYPE_LINE) {
      points[pointn++] = tp;
      points[pointn++] = (pointf){(2 * tp.x + hp.x) / 3, dy};
      points[pointn++] = (pointf){(2 * hp.x + tp.x) / 3, dy};
      points[pointn++] = hp;
    } else { /* EDGETYPE_PLINE */
      points[pointn++] = tp;
      points[pointn++] = tp;
      points[pointn++] = (pointf){(2 * tp.x + hp.x) / 3, dy};
      points[pointn++] = (pointf){(2 * tp.x + hp.x) / 3, dy};
      points[pointn++] = (pointf){(2 * tp.x + hp.x) / 3, dy};
      points[pointn++] = (pointf){(2 * hp.x + tp.x) / 3, dy};
      points[pointn++] = (pointf){(2 * hp.x + tp.x) / 3, dy};
      points[pointn++] = (pointf){(2 * hp.x + tp.x) / 3, dy};
      points[pointn++] = hp;
      points[pointn++] = hp;
    }
    dy += stepy;
    clip_and_install(e, aghead(e), points, pointn, &sinfo);
  }
}
 
/* make_flat_adj_edges:
 * In the simple case, with no labels or ports, this creates a simple
 * spindle of splines.
 * If there are only labels, cobble something together.
 * Otherwise, we run dot recursively on the 2 nodes and the edges,
 * essentially using rankdir=LR, to get the needed spline info.
 * This is probably to cute and fragile, and should be rewritten in a
 * more straightforward and laborious fashion.
 */
static void make_flat_adj_edges(graph_t *g, edge_t **edges, unsigned ind,
                                unsigned cnt, edge_t *e0, int et) {
  node_t *n;
  node_t *tn, *hn;
  edge_t *e;
  graph_t *auxg;
  graph_t *subg;
  node_t *auxt, *auxh;
  edge_t *auxe;
  double midx, midy, leftx, rightx;
  pointf del;
  edge_t *hvye = NULL;
  static atomic_flag warned;
 
  tn = agtail(e0), hn = aghead(e0);
  if (shapeOf(tn) == SH_RECORD || shapeOf(hn) == SH_RECORD) {
    if (!atomic_flag_test_and_set(&warned)) {
      agwarningf("flat edge between adjacent nodes one of which has a record "
                 "shape - replace records with HTML-like labels\n");
      agerr(AGPREV, "  Edge %s %s %s\n", agnameof(tn),
            agisdirected(g) ? "->" : "--", agnameof(hn));
    }
    return;
  }
  unsigned labels = 0;
  bool ports = false;
  for (unsigned i = 0; i < cnt; i++) {
    e = edges[ind + i];
    if (ED_label(e))
      labels++;
    if (ED_tail_port(e).defined || ED_head_port(e).defined)
      ports = true;
  }
 
  if (!ports) {
    /* flat edges without ports and labels can go straight left to right */
    if (labels == 0) {
      makeSimpleFlat(tn, hn, edges, ind, cnt, et);
    }
    /* flat edges without ports but with labels take more work */
    else {
      makeSimpleFlatLabels(tn, hn, edges, ind, cnt, et, labels);
    }
    return;
  }
 
  attr_state_t attrs = {0};
  auxg = cloneGraph(g, &attrs);
  subg = agsubg(auxg, "xxx", 1);
  agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
  agset(subg, "rank", "source");
  rightx = ND_coord(hn).x;
  leftx = ND_coord(tn).x;
  if (GD_flip(g)) {
    SWAP(&tn, &hn);
  }
  auxt = cloneNode(subg, tn);
  auxh = cloneNode(auxg, hn);
  for (unsigned i = 0; i < cnt; i++) {
    e = edges[ind + i];
    for (; ED_edge_type(e) != NORMAL; e = ED_to_orig(e))
      ;
    if (agtail(e) == tn)
      auxe = cloneEdge(auxg, auxt, auxh, e);
    else
      auxe = cloneEdge(auxg, auxh, auxt, e);
    ED_alg(e) = auxe;
    if (!hvye && !ED_tail_port(e).defined && !ED_head_port(e).defined) {
      hvye = auxe;
      ED_alg(hvye) = e;
    }
  }
  if (!hvye) {
    hvye = agedge(auxg, auxt, auxh, NULL, 1);
  }
  agxset(hvye, E_weight, "10000");
  GD_gvc(auxg) = GD_gvc(g);
  GD_dotroot(auxg) = auxg;
  setEdgeType(auxg, et);
  dot_init_node_edge(auxg);
 
  dot_rank(auxg);
  dot_mincross(auxg);
  dot_position(auxg);
 
  /* reposition */
  midx = (ND_coord(tn).x - ND_rw(tn) + ND_coord(hn).x + ND_lw(hn)) / 2;
  midy = (ND_coord(auxt).x + ND_coord(auxh).x) / 2;
  for (n = GD_nlist(auxg); n; n = ND_next(n)) {
    if (n == auxt) {
      ND_coord(n).y = rightx;
      ND_coord(n).x = midy;
    } else if (n == auxh) {
      ND_coord(n).y = leftx;
      ND_coord(n).x = midy;
    } else
      ND_coord(n).y = midx;
  }
  dot_sameports(auxg);
  dot_splines_(auxg, 0);
  dotneato_postprocess(auxg);
 
  /* copy splines */
  if (GD_flip(g)) {
    del.x = ND_coord(tn).x - ND_coord(auxt).y;
    del.y = ND_coord(tn).y + ND_coord(auxt).x;
  } else {
    del.x = ND_coord(tn).x - ND_coord(auxt).x;
    del.y = ND_coord(tn).y - ND_coord(auxt).y;
  }
  for (unsigned i = 0; i < cnt; i++) {
    bezier *auxbz;
    bezier *bz;
 
    e = edges[ind + i];
    for (; ED_edge_type(e) != NORMAL; e = ED_to_orig(e))
      ;
    auxe = ED_alg(e);
    if ((auxe == hvye) & !ED_alg(auxe))
      continue; /* pseudo-edge */
    auxbz = ED_spl(auxe)->list;
    bz = new_spline(e, auxbz->size);
    bz->sflag = auxbz->sflag;
    bz->sp = transformf(auxbz->sp, del, GD_flip(g));
    bz->eflag = auxbz->eflag;
    bz->ep = transformf(auxbz->ep, del, GD_flip(g));
    for (size_t j = 0; j < auxbz->size;) {
      pointf cp[4];
      cp[0] = bz->list[j] = transformf(auxbz->list[j], del, GD_flip(g));
      j++;
      if (j >= auxbz->size)
        break;
      cp[1] = bz->list[j] = transformf(auxbz->list[j], del, GD_flip(g));
      j++;
      cp[2] = bz->list[j] = transformf(auxbz->list[j], del, GD_flip(g));
      j++;
      cp[3] = transformf(auxbz->list[j], del, GD_flip(g));
      update_bb_bz(&GD_bb(g), cp);
    }
    if (ED_label(e)) {
      ED_label(e)->pos = transformf(ED_label(auxe)->pos, del, GD_flip(g));
      ED_label(e)->set = true;
      updateBB(g, ED_label(e));
    }
  }
 
  cleanupCloneGraph(auxg, &attrs);
}
 
static void makeFlatEnd(graph_t *g, spline_info_t *sp, path *P, node_t *n,
                        edge_t *e, pathend_t *endp, bool isBegin) {
  boxf b;
 
  b = endp->nb = maximal_bbox(g, sp, n, NULL, e);
  endp->sidemask = TOP;
  if (isBegin)
    beginpath(P, e, FLATEDGE, endp, false);
  else
    endpath(P, e, FLATEDGE, endp, false);
  b.UR.y = endp->boxes[endp->boxn - 1].UR.y;
  b.LL.y = endp->boxes[endp->boxn - 1].LL.y;
  b = makeregularend(b, TOP, ND_coord(n).y + GD_rank(g)[ND_rank(n)].ht2);
  if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
    endp->boxes[endp->boxn++] = b;
}
 
static void makeBottomFlatEnd(graph_t *g, spline_info_t *sp, path *P, node_t *n,
                              edge_t *e, pathend_t *endp, bool isBegin) {
  boxf b;
 
  b = endp->nb = maximal_bbox(g, sp, n, NULL, e);
  endp->sidemask = BOTTOM;
  if (isBegin)
    beginpath(P, e, FLATEDGE, endp, false);
  else
    endpath(P, e, FLATEDGE, endp, false);
  b.UR.y = endp->boxes[endp->boxn - 1].UR.y;
  b.LL.y = endp->boxes[endp->boxn - 1].LL.y;
  b = makeregularend(b, BOTTOM, ND_coord(n).y - GD_rank(g)[ND_rank(n)].ht2);
  if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
    endp->boxes[endp->boxn++] = b;
}
 
static void make_flat_labeled_edge(graph_t *g, spline_info_t *sp, path *P,
                                   edge_t *e, int et) {
  node_t *tn, *hn, *ln;
  pointf *ps;
  bool ps_needs_free = false;
  pathend_t tend, hend;
  boxf lb;
  int i;
  edge_t *f;
  pointf points[7];
 
  tn = agtail(e);
  hn = aghead(e);
 
  for (f = ED_to_virt(e); ED_to_virt(f); f = ED_to_virt(f))
    ;
  ln = agtail(f);
  ED_label(e)->pos = ND_coord(ln);
  ED_label(e)->set = true;
 
  size_t pn;
  if (et == EDGETYPE_LINE) {
    pointf startp, endp, lp;
 
    startp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
    endp = add_pointf(ND_coord(hn), ED_head_port(e).p);
 
    lp = ED_label(e)->pos;
    lp.y -= ED_label(e)->dimen.y / 2.0;
    points[1] = points[0] = startp;
    points[2] = points[3] = points[4] = lp;
    points[5] = points[6] = endp;
    ps = points;
    pn = 7;
  } else {
    lb.LL.x = ND_coord(ln).x - ND_lw(ln);
    lb.UR.x = ND_coord(ln).x + ND_rw(ln);
    lb.UR.y = ND_coord(ln).y + ND_ht(ln) / 2;
    double ydelta = ND_coord(ln).y - GD_rank(g)[ND_rank(tn)].ht1 -
                    ND_coord(tn).y + GD_rank(g)[ND_rank(tn)].ht2;
    ydelta /= 6;
    lb.LL.y = lb.UR.y - MAX(5, ydelta);
 
    makeFlatEnd(g, sp, P, tn, e, &tend, true);
    makeFlatEnd(g, sp, P, hn, e, &hend, false);
 
    boxf boxes[] = {
        {
            .LL =
                {
                    .x = tend.boxes[tend.boxn - 1].LL.x,
                    .y = tend.boxes[tend.boxn - 1].UR.y,
                },
            .UR = lb.LL,
        },
        {
            .LL =
                {
                    .x = tend.boxes[tend.boxn - 1].LL.x,
                    .y = lb.LL.y,
                },
            .UR =
                {
                    .x = hend.boxes[hend.boxn - 1].UR.x,
                    .y = lb.UR.y,
                },
        },
        {
            .LL =
                {
                    .x = lb.UR.x,
                    .y = hend.boxes[hend.boxn - 1].UR.y,
                },
            .UR =
                {
                    .x = hend.boxes[hend.boxn - 1].UR.x,
                    .y = lb.LL.y,
                },
        },
    };
    const size_t boxn = sizeof(boxes) / sizeof(boxes[0]);
 
    for (i = 0; i < tend.boxn; i++)
      add_box(P, tend.boxes[i]);
    for (size_t j = 0; j < boxn; j++)
      add_box(P, boxes[j]);
    for (i = hend.boxn - 1; i >= 0; i--)
      add_box(P, hend.boxes[i]);
 
    ps_needs_free = true;
    if (et == EDGETYPE_SPLINE)
      ps = routesplines(P, &pn);
    else
      ps = routepolylines(P, &pn);
    if (pn == 0) {
      free(ps);
      return;
    }
  }
  clip_and_install(e, aghead(e), ps, pn, &sinfo);
  if (ps_needs_free)
    free(ps);
}
 
static void make_flat_bottom_edges(graph_t *g, spline_info_t *sp, path *P,
                                   edge_t **edges, unsigned ind, unsigned cnt,
                                   edge_t *e, bool use_splines) {
  node_t *tn, *hn;
  int j, r;
  double stepx, stepy, vspace;
  rank_t *nextr;
  pathend_t tend, hend;
 
  tn = agtail(e);
  hn = aghead(e);
  r = ND_rank(tn);
  if (r < GD_maxrank(g)) {
    nextr = GD_rank(g) + (r + 1);
    vspace = ND_coord(tn).y - GD_rank(g)[r].pht1 -
             (ND_coord(nextr->v[0]).y + nextr->pht2);
  } else {
    vspace = GD_ranksep(g);
  }
  stepx = sp->Multisep / (cnt + 1);
  stepy = vspace / (cnt + 1);
 
  makeBottomFlatEnd(g, sp, P, tn, e, &tend, true);
  makeBottomFlatEnd(g, sp, P, hn, e, &hend, false);
 
  for (unsigned i = 0; i < cnt; i++) {
    boxf b;
    e = edges[ind + i];
    size_t boxn = 0;
 
    boxf boxes[3];
 
    b = tend.boxes[tend.boxn - 1];
    boxes[boxn].LL.x = b.LL.x;
    boxes[boxn].UR.y = b.LL.y;
    boxes[boxn].UR.x = b.UR.x + (i + 1) * stepx;
    boxes[boxn].LL.y = b.LL.y - (i + 1) * stepy;
    boxn++;
    boxes[boxn].LL.x = tend.boxes[tend.boxn - 1].LL.x;
    boxes[boxn].UR.y = boxes[boxn - 1].LL.y;
    boxes[boxn].UR.x = hend.boxes[hend.boxn - 1].UR.x;
    boxes[boxn].LL.y = boxes[boxn].UR.y - stepy;
    boxn++;
    b = hend.boxes[hend.boxn - 1];
    boxes[boxn].UR.x = b.UR.x;
    boxes[boxn].UR.y = b.LL.y;
    boxes[boxn].LL.x = b.LL.x - (i + 1) * stepx;
    boxes[boxn].LL.y = boxes[boxn - 1].UR.y;
    boxn++;
    assert(boxn == sizeof(boxes) / sizeof(boxes[0]));
 
    for (j = 0; j < tend.boxn; j++)
      add_box(P, tend.boxes[j]);
    for (size_t k = 0; k < boxn; k++)
      add_box(P, boxes[k]);
    for (j = hend.boxn - 1; j >= 0; j--)
      add_box(P, hend.boxes[j]);
 
    pointf *ps = NULL;
    size_t pn = 0;
    if (use_splines)
      ps = routesplines(P, &pn);
    else
      ps = routepolylines(P, &pn);
    if (pn == 0) {
      free(ps);
      return;
    }
    clip_and_install(e, aghead(e), ps, pn, &sinfo);
    free(ps);
    P->nbox = 0;
  }
}
 
/* make_flat_edge:
 * Construct flat edges edges[ind...ind+cnt-1]
 * There are 4 main cases:
 *  - all edges between a and b where a and b are adjacent
 *  - one labeled edge
 *  - all non-labeled edges with identical ports between non-adjacent a and b
 *     = connecting bottom to bottom/left/right - route along bottom
 *     = the rest - route along top
 */
static void make_flat_edge(graph_t *g, spline_info_t *sp, path *P,
                           edge_t **edges, unsigned ind, unsigned cnt, int et) {
  node_t *tn, *hn;
  Agedgeinfo_t fwdedgei;
  Agedgepair_t fwdedge;
  edge_t *e;
  int j, r;
  double stepx, stepy, vspace;
  int tside, hside;
  pathend_t tend, hend;
 
  fwdedge.out.base.data = (Agrec_t *)&fwdedgei;
 
  /* Get sample edge; normalize to go from left to right */
  e = edges[ind];
  bool isAdjacent = ED_adjacent(e) != 0;
  if (ED_tree_index(e) & BWDEDGE) {
    MAKEFWDEDGE(&fwdedge.out, e);
    e = &fwdedge.out;
  }
  for (unsigned i = 1; i < cnt; i++) {
    if (ED_adjacent(edges[ind + i])) {
      isAdjacent = true;
      break;
    }
  }
  /* The lead edge edges[ind] might not have been marked earlier as adjacent,
   * so check them all.
   */
  if (isAdjacent) {
    make_flat_adj_edges(g, edges, ind, cnt, e, et);
    return;
  }
  if (ED_label(e)) { /* edges with labels aren't multi-edges */
    make_flat_labeled_edge(g, sp, P, e, et);
    return;
  }
 
  if (et == EDGETYPE_LINE) {
    makeSimpleFlat(agtail(e), aghead(e), edges, ind, cnt, et);
    return;
  }
 
  tside = ED_tail_port(e).side;
  hside = ED_head_port(e).side;
  if ((tside == BOTTOM && hside != TOP) || (hside == BOTTOM && tside != TOP)) {
    make_flat_bottom_edges(g, sp, P, edges, ind, cnt, e, et == EDGETYPE_SPLINE);
    return;
  }
 
  tn = agtail(e);
  hn = aghead(e);
  r = ND_rank(tn);
  if (r > 0) {
    rank_t *prevr;
    if (GD_has_labels(g->root) & EDGE_LABEL)
      prevr = GD_rank(g) + (r - 2);
    else
      prevr = GD_rank(g) + (r - 1);
    vspace = ND_coord(prevr->v[0]).y - prevr->ht1 - ND_coord(tn).y -
             GD_rank(g)[r].ht2;
  } else {
    vspace = GD_ranksep(g);
  }
  stepx = sp->Multisep / (cnt + 1);
  stepy = vspace / (cnt + 1);
 
  makeFlatEnd(g, sp, P, tn, e, &tend, true);
  makeFlatEnd(g, sp, P, hn, e, &hend, false);
 
  for (unsigned i = 0; i < cnt; i++) {
    boxf b;
    e = edges[ind + i];
    size_t boxn = 0;
 
    boxf boxes[3];
 
    b = tend.boxes[tend.boxn - 1];
    boxes[boxn].LL.x = b.LL.x;
    boxes[boxn].LL.y = b.UR.y;
    boxes[boxn].UR.x = b.UR.x + (i + 1) * stepx;
    boxes[boxn].UR.y = b.UR.y + (i + 1) * stepy;
    boxn++;
    boxes[boxn].LL.x = tend.boxes[tend.boxn - 1].LL.x;
    boxes[boxn].LL.y = boxes[boxn - 1].UR.y;
    boxes[boxn].UR.x = hend.boxes[hend.boxn - 1].UR.x;
    boxes[boxn].UR.y = boxes[boxn].LL.y + stepy;
    boxn++;
    b = hend.boxes[hend.boxn - 1];
    boxes[boxn].UR.x = b.UR.x;
    boxes[boxn].LL.y = b.UR.y;
    boxes[boxn].LL.x = b.LL.x - (i + 1) * stepx;
    boxes[boxn].UR.y = boxes[boxn - 1].LL.y;
    boxn++;
    assert(boxn == sizeof(boxes) / sizeof(boxes[0]));
 
    for (j = 0; j < tend.boxn; j++)
      add_box(P, tend.boxes[j]);
    for (size_t k = 0; k < boxn; k++)
      add_box(P, boxes[k]);
    for (j = hend.boxn - 1; j >= 0; j--)
      add_box(P, hend.boxes[j]);
 
    pointf *ps = NULL;
    size_t pn = 0;
    if (et == EDGETYPE_SPLINE)
      ps = routesplines(P, &pn);
    else
      ps = routepolylines(P, &pn);
    if (pn == 0) {
      free(ps);
      return;
    }
    clip_and_install(e, aghead(e), ps, pn, &sinfo);
    free(ps);
    P->nbox = 0;
  }
}
 
static bool leftOf(pointf p1, pointf p2, pointf p3) {
  return (p1.y - p2.y) * (p3.x - p2.x) - (p3.y - p2.y) * (p1.x - p2.x) > 0;
}
 
/* makeLineEdge:
 * Create an edge as line segment. We guarantee that the points
 * are always drawn downwards. This means that for flipped edges,
 * we draw from the head to the tail. The routine returns the
 * end node of the edge in *hp. The points are stored in the
 * given array of points, and the number of points is returned.
 *
 * If the edge has a label, the edge is draw as two segments, with
 * the bend near the label.
 *
 * If the endpoints are on adjacent ranks, revert to usual code by
 * returning 0.
 * This is done because the usual code handles the interaction of
 * multiple edges better.
 */
static int makeLineEdge(graph_t *g, edge_t *fe, points_t *points, node_t **hp) {
  int delr, pn;
  node_t *hn;
  node_t *tn;
  edge_t *e = fe;
  pointf startp, endp, lp;
  pointf dimen;
  double width, height;
 
  while (ED_edge_type(e) != NORMAL)
    e = ED_to_orig(e);
  hn = aghead(e);
  tn = agtail(e);
  delr = abs(ND_rank(hn) - ND_rank(tn));
  if (delr == 1 || (delr == 2 && (GD_has_labels(g->root) & EDGE_LABEL)))
    return 0;
  if (agtail(fe) == agtail(e)) {
    *hp = hn;
    startp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
    endp = add_pointf(ND_coord(hn), ED_head_port(e).p);
  } else {
    *hp = tn;
    startp = add_pointf(ND_coord(hn), ED_head_port(e).p);
    endp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
  }
 
  if (ED_label(e)) {
    dimen = ED_label(e)->dimen;
    if (GD_flip(agraphof(hn))) {
      width = dimen.y;
      height = dimen.x;
    } else {
      width = dimen.x;
      height = dimen.y;
    }
 
    lp = ED_label(e)->pos;
    if (leftOf(endp, startp, lp)) {
      lp.x += width / 2.0;
      lp.y -= height / 2.0;
    } else {
      lp.x -= width / 2.0;
      lp.y += height / 2.0;
    }
 
    points_append(points, startp);
    points_append(points, startp);
    points_append(points, lp);
    points_append(points, lp);
    points_append(points, lp);
    points_append(points, endp);
    points_append(points, endp);
    pn = 7;
  } else {
    points_append(points, startp);
    points_append(points, startp);
    points_append(points, endp);
    points_append(points, endp);
    pn = 4;
  }
 
  return pn;
}
 
static void make_regular_edge(graph_t *g, spline_info_t *sp, path *P,
                              edge_t **edges, unsigned ind, unsigned cnt,
                              int et) {
  node_t *tn, *hn;
  Agedgeinfo_t fwdedgeai, fwdedgebi, fwdedgei;
  Agedgepair_t fwdedgea, fwdedgeb, fwdedge;
  edge_t *e, *fe, *le, *segfirst;
  pathend_t tend, hend;
  boxf b;
  int sl, si;
  points_t pointfs = {0};
  points_t pointfs2 = {0};
 
  fwdedgea.out.base.data = (Agrec_t *)&fwdedgeai;
  fwdedgeb.out.base.data = (Agrec_t *)&fwdedgebi;
  fwdedge.out.base.data = (Agrec_t *)&fwdedgei;
 
  sl = 0;
  e = edges[ind];
  bool hackflag = false;
  if (abs(ND_rank(agtail(e)) - ND_rank(aghead(e))) > 1) {
    fwdedgeai = *(Agedgeinfo_t *)e->base.data;
    fwdedgea.out = *e;
    fwdedgea.in = *AGOUT2IN(e);
    fwdedgea.out.base.data = (Agrec_t *)&fwdedgeai;
    if (ED_tree_index(e) & BWDEDGE) {
      MAKEFWDEDGE(&fwdedgeb.out, e);
      agtail(&fwdedgea.out) = aghead(e);
      ED_tail_port(&fwdedgea.out) = ED_head_port(e);
    } else {
      fwdedgebi = *(Agedgeinfo_t *)e->base.data;
      fwdedgeb.out = *e;
      fwdedgeb.out.base.data = (Agrec_t *)&fwdedgebi;
      agtail(&fwdedgea.out) = agtail(e);
      fwdedgeb.in = *AGOUT2IN(e);
    }
    le = getmainedge(e);
    while (ED_to_virt(le))
      le = ED_to_virt(le);
    aghead(&fwdedgea.out) = aghead(le);
    ED_head_port(&fwdedgea.out).defined = false;
    ED_edge_type(&fwdedgea.out) = VIRTUAL;
    ED_head_port(&fwdedgea.out).p.x = ED_head_port(&fwdedgea.out).p.y = 0;
    ED_to_orig(&fwdedgea.out) = e;
    e = &fwdedgea.out;
    hackflag = true;
  } else {
    if (ED_tree_index(e) & BWDEDGE) {
      MAKEFWDEDGE(&fwdedgea.out, e);
      e = &fwdedgea.out;
    }
  }
  fe = e;
 
  /* compute the spline points for the edge */
 
  if (et == EDGETYPE_LINE && makeLineEdge(g, fe, &pointfs, &hn)) {
  } else {
    bool is_spline = et == EDGETYPE_SPLINE;
    boxes_t boxes = {0};
    segfirst = e;
    tn = agtail(e);
    hn = aghead(e);
    b = tend.nb = maximal_bbox(g, sp, tn, NULL, e);
    beginpath(P, e, REGULAREDGE, &tend, spline_merge(tn));
    b.UR.y = tend.boxes[tend.boxn - 1].UR.y;
    b.LL.y = tend.boxes[tend.boxn - 1].LL.y;
    b = makeregularend(b, BOTTOM, ND_coord(tn).y - GD_rank(g)[ND_rank(tn)].ht1);
    if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
      tend.boxes[tend.boxn++] = b;
    bool smode = false;
    si = -1;
    while (ND_node_type(hn) == VIRTUAL && !sinfo.splineMerge(hn)) {
      boxes_append(&boxes, rank_box(sp, g, ND_rank(tn)));
      if (!smode && ((sl = straight_len(hn)) >=
                     ((GD_has_labels(g->root) & EDGE_LABEL) ? 4 + 1 : 2 + 1))) {
        smode = true;
        si = 1, sl -= 2;
      }
      if (!smode || si > 0) {
        si--;
        boxes_append(&boxes, maximal_bbox(g, sp, hn, e, ND_out(hn).list[0]));
        e = ND_out(hn).list[0];
        tn = agtail(e);
        hn = aghead(e);
        continue;
      }
      hend.nb = maximal_bbox(g, sp, hn, e, ND_out(hn).list[0]);
      endpath(P, e, REGULAREDGE, &hend, spline_merge(aghead(e)));
      b = makeregularend(hend.boxes[hend.boxn - 1], TOP,
                         ND_coord(hn).y + GD_rank(g)[ND_rank(hn)].ht2);
      if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
        hend.boxes[hend.boxn++] = b;
      P->end.theta = M_PI / 2, P->end.constrained = true;
      completeregularpath(P, segfirst, e, &tend, &hend, &boxes);
      pointf *ps = NULL;
      size_t pn = 0;
      if (is_spline)
        ps = routesplines(P, &pn);
      else {
        ps = routepolylines(P, &pn);
        if (et == EDGETYPE_LINE && pn > 4) {
          ps[1] = ps[0];
          ps[3] = ps[2] = ps[pn - 1];
          pn = 4;
        }
      }
      if (pn == 0) {
        free(ps);
        boxes_free(&boxes);
        points_free(&pointfs);
        points_free(&pointfs2);
        return;
      }
 
      for (size_t i = 0; i < pn; i++) {
        points_append(&pointfs, ps[i]);
      }
      free(ps);
      e = straight_path(ND_out(hn).list[0], sl, &pointfs);
      recover_slack(segfirst, P);
      segfirst = e;
      tn = agtail(e);
      hn = aghead(e);
      boxes_clear(&boxes);
      tend.nb = maximal_bbox(g, sp, tn, ND_in(tn).list[0], e);
      beginpath(P, e, REGULAREDGE, &tend, spline_merge(tn));
      b = makeregularend(tend.boxes[tend.boxn - 1], BOTTOM,
                         ND_coord(tn).y - GD_rank(g)[ND_rank(tn)].ht1);
      if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
        tend.boxes[tend.boxn++] = b;
      P->start.theta = -M_PI / 2, P->start.constrained = true;
      smode = false;
    }
    boxes_append(&boxes, rank_box(sp, g, ND_rank(tn)));
    b = hend.nb = maximal_bbox(g, sp, hn, e, NULL);
    endpath(P, hackflag ? &fwdedgeb.out : e, REGULAREDGE, &hend,
            spline_merge(aghead(e)));
    b.UR.y = hend.boxes[hend.boxn - 1].UR.y;
    b.LL.y = hend.boxes[hend.boxn - 1].LL.y;
    b = makeregularend(b, TOP, ND_coord(hn).y + GD_rank(g)[ND_rank(hn)].ht2);
    if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
      hend.boxes[hend.boxn++] = b;
    completeregularpath(P, segfirst, e, &tend, &hend, &boxes);
    boxes_free(&boxes);
    pointf *ps = NULL;
    size_t pn = 0;
    if (is_spline)
      ps = routesplines(P, &pn);
    else
      ps = routepolylines(P, &pn);
    if (et == EDGETYPE_LINE && pn > 4) {
      /* Here we have used the polyline case to handle
       * an edge between two nodes on adjacent ranks. If the
       * results really is a polyline, straighten it.
       */
      ps[1] = ps[0];
      ps[3] = ps[2] = ps[pn - 1];
      pn = 4;
    }
    if (pn == 0) {
      free(ps);
      points_free(&pointfs);
      points_free(&pointfs2);
      return;
    }
    for (size_t i = 0; i < pn; i++) {
      points_append(&pointfs, ps[i]);
    }
    free(ps);
    recover_slack(segfirst, P);
    hn = hackflag ? aghead(&fwdedgeb.out) : aghead(e);
  }
 
  /* make copies of the spline points, one per multi-edge */
 
  if (cnt == 1) {
    points_sync(&pointfs);
    clip_and_install(fe, hn, points_front(&pointfs), points_size(&pointfs),
                     &sinfo);
    points_free(&pointfs);
    points_free(&pointfs2);
    return;
  }
  const double dx = sp->Multisep * (cnt - 1) / 2;
  for (size_t k = 1; k + 1 < points_size(&pointfs); k++)
    points_at(&pointfs, k)->x -= dx;
 
  for (size_t k = 0; k < points_size(&pointfs); k++)
    points_append(&pointfs2, points_get(&pointfs, k));
  points_sync(&pointfs2);
  clip_and_install(fe, hn, points_front(&pointfs2), points_size(&pointfs2),
                   &sinfo);
  for (unsigned j = 1; j < cnt; j++) {
    e = edges[ind + j];
    if (ED_tree_index(e) & BWDEDGE) {
      MAKEFWDEDGE(&fwdedge.out, e);
      e = &fwdedge.out;
    }
    for (size_t k = 1; k + 1 < points_size(&pointfs); k++)
      points_at(&pointfs, k)->x += sp->Multisep;
    points_clear(&pointfs2);
    for (size_t k = 0; k < points_size(&pointfs); k++)
      points_append(&pointfs2, points_get(&pointfs, k));
    points_sync(&pointfs2);
    clip_and_install(e, aghead(e), points_front(&pointfs2),
                     points_size(&pointfs2), &sinfo);
  }
  points_free(&pointfs);
  points_free(&pointfs2);
}
 
/* regular edges */
 
static void completeregularpath(path *P, edge_t *first, edge_t *last,
                                pathend_t *tendp, pathend_t *hendp,
                                const boxes_t *boxes) {
  edge_t *uleft, *uright, *lleft, *lright;
 
  uleft = uright = NULL;
  uleft = top_bound(first, -1), uright = top_bound(first, 1);
  if (uleft) {
    if (getsplinepoints(uleft) == NULL)
      return;
  }
  if (uright) {
    if (getsplinepoints(uright) == NULL)
      return;
  }
  lleft = lright = NULL;
  lleft = bot_bound(last, -1), lright = bot_bound(last, 1);
  if (lleft) {
    if (getsplinepoints(lleft) == NULL)
      return;
  }
  if (lright) {
    if (getsplinepoints(lright) == NULL)
      return;
  }
  for (int i = 0; i < tendp->boxn; i++)
    add_box(P, tendp->boxes[i]);
  const size_t fb = P->nbox + 1;
  const size_t lb = fb + boxes_size(boxes) - 3;
  for (size_t i = 0; i < boxes_size(boxes); i++)
    add_box(P, boxes_get(boxes, i));
  for (int i = hendp->boxn - 1; i >= 0; i--)
    add_box(P, hendp->boxes[i]);
  adjustregularpath(P, fb, lb);
}
 
/* makeregularend:
 * Add box to fill between node and interrank space. Needed because
 * nodes in a given rank can differ in height.
 * for now, regular edges always go from top to bottom
 */
static boxf makeregularend(boxf b, int side, double y) {
  assert(side == BOTTOM || side == TOP);
  if (side == BOTTOM) {
    return (boxf){{b.LL.x, y}, {b.UR.x, b.LL.y}};
  }
  return (boxf){{b.LL.x, b.UR.y}, {b.UR.x, y}};
}
 
/* adjustregularpath:
 * make sure the path is wide enough.
 * the % 2 was so that in rank boxes would only be grown if
 * they were == 0 while inter-rank boxes could be stretched to a min
 * width.
 * The list of boxes has three parts: tail boxes, path boxes, and head
 * boxes. (Note that because of back edges, the tail boxes might actually
 * belong to the head node, and vice versa.) fb is the index of the
 * first interrank path box and lb is the last interrank path box.
 * If fb > lb, there are none.
 *
 * The second for loop was added by ek long ago, and apparently is intended
 * to guarantee an overlap between adjacent boxes of at least MINW.
 * It doesn't do this.
 */
static void adjustregularpath(path *P, size_t fb, size_t lb) {
  boxf *bp1, *bp2;
 
  for (size_t i = fb - 1; i < lb + 1; i++) {
    bp1 = &P->boxes[i];
    if ((i - fb) % 2 == 0) {
      if (bp1->LL.x >= bp1->UR.x) {
        double x = (bp1->LL.x + bp1->UR.x) / 2;
        bp1->LL.x = x - HALFMINW;
        bp1->UR.x = x + HALFMINW;
      }
    } else {
      if (bp1->LL.x + MINW > bp1->UR.x) {
        double x = (bp1->LL.x + bp1->UR.x) / 2;
        bp1->LL.x = x - HALFMINW;
        bp1->UR.x = x + HALFMINW;
      }
    }
  }
  for (size_t i = 0; i + 1 < P->nbox; i++) {
    bp1 = &P->boxes[i], bp2 = &P->boxes[i + 1];
    if (i >= fb && i <= lb && (i - fb) % 2 == 0) {
      if (bp1->LL.x + MINW > bp2->UR.x)
        bp2->UR.x = bp1->LL.x + MINW;
      if (bp1->UR.x - MINW < bp2->LL.x)
        bp2->LL.x = bp1->UR.x - MINW;
    } else if (i + 1 >= fb && i < lb && (i + 1 - fb) % 2 == 0) {
      if (bp1->LL.x + MINW > bp2->UR.x)
        bp1->LL.x = bp2->UR.x - MINW;
      if (bp1->UR.x - MINW < bp2->LL.x)
        bp1->UR.x = bp2->LL.x + MINW;
    }
  }
}
 
static boxf rank_box(spline_info_t *sp, graph_t *g, int r) {
  boxf b;
  node_t *left0, *left1;
 
  b = sp->Rank_box[r];
  if (b.LL.x == b.UR.x) {
    left0 = GD_rank(g)[r].v[0];
    left1 = GD_rank(g)[r + 1].v[0];
    b.LL.x = sp->LeftBound;
    b.LL.y = ND_coord(left1).y + GD_rank(g)[r + 1].ht2;
    b.UR.x = sp->RightBound;
    b.UR.y = ND_coord(left0).y - GD_rank(g)[r].ht1;
    sp->Rank_box[r] = b;
  }
  return b;
}
 
/* returns count of vertically aligned edges starting at n */
static int straight_len(node_t *n) {
  int cnt = 0;
  node_t *v;
 
  v = n;
  while (1) {
    v = aghead(ND_out(v).list[0]);
    if (ND_node_type(v) != VIRTUAL)
      break;
    if (ND_out(v).size != 1 || ND_in(v).size != 1)
      break;
    if (ND_coord(v).x != ND_coord(n).x)
      break;
    cnt++;
  }
  return cnt;
}
 
static edge_t *straight_path(edge_t *e, int cnt, points_t *plist) {
  edge_t *f = e;
 
  while (cnt--)
    f = ND_out(aghead(f)).list[0];
  assert(!points_is_empty(plist));
  points_append(plist, points_get(plist, points_size(plist) - 1));
  points_append(plist, points_get(plist, points_size(plist) - 1));
 
  return f;
}
 
static void recover_slack(edge_t *e, path *p) {
  node_t *vn;
 
  size_t b = 0; // skip first rank box
  for (vn = aghead(e); ND_node_type(vn) == VIRTUAL && !sinfo.splineMerge(vn);
       vn = aghead(ND_out(vn).list[0])) {
    while (b < p->nbox && p->boxes[b].LL.y > ND_coord(vn).y)
      b++;
    if (b >= p->nbox)
      break;
    if (p->boxes[b].UR.y < ND_coord(vn).y)
      continue;
    if (ND_label(vn))
      resize_vn(vn, p->boxes[b].LL.x, p->boxes[b].UR.x,
                p->boxes[b].UR.x + ND_rw(vn));
    else
      resize_vn(vn, p->boxes[b].LL.x, (p->boxes[b].LL.x + p->boxes[b].UR.x) / 2,
                p->boxes[b].UR.x);
  }
}
 
static void resize_vn(node_t *vn, double lx, double cx, double rx) {
  ND_coord(vn).x = cx;
  ND_lw(vn) = cx - lx, ND_rw(vn) = rx - cx;
}
 
/* side > 0 means right. side < 0 means left */
static edge_t *top_bound(edge_t *e, int side) {
  edge_t *f, *ans = NULL;
  int i;
 
  for (i = 0; (f = ND_out(agtail(e)).list[i]); i++) {
    if (side * (ND_order(aghead(f)) - ND_order(aghead(e))) <= 0)
      continue;
    if (ED_spl(f) == NULL &&
        (ED_to_orig(f) == NULL || ED_spl(ED_to_orig(f)) == NULL))
      continue;
    if (ans == NULL || side * (ND_order(aghead(ans)) - ND_order(aghead(f))) > 0)
      ans = f;
  }
  return ans;
}
 
static edge_t *bot_bound(edge_t *e, int side) {
  edge_t *f, *ans = NULL;
  int i;
 
  for (i = 0; (f = ND_in(aghead(e)).list[i]); i++) {
    if (side * (ND_order(agtail(f)) - ND_order(agtail(e))) <= 0)
      continue;
    if (ED_spl(f) == NULL &&
        (ED_to_orig(f) == NULL || ED_spl(ED_to_orig(f)) == NULL))
      continue;
    if (ans == NULL || side * (ND_order(agtail(ans)) - ND_order(agtail(f))) > 0)
      ans = f;
  }
  return ans;
}
 
/* common routines */
 
static bool cl_vninside(graph_t *cl, node_t *n) {
  return BETWEEN(GD_bb(cl).LL.x, ND_coord(n).x, GD_bb(cl).UR.x) &&
         BETWEEN(GD_bb(cl).LL.y, ND_coord(n).y, GD_bb(cl).UR.y);
}
 
/* All nodes belong to some cluster, which may be the root graph.
 * For the following, we only want a cluster if it is a real cluster
 * It is not clear this will handle all potential problems. It seems one
 * could have hcl and tcl contained in cl, which would also cause problems.
 */
#define REAL_CLUSTER(n) (ND_clust(n) == g ? NULL : ND_clust(n))
 
/* returns the cluster of (adj) that interferes with n,
 */
static Agraph_t *cl_bound(graph_t *g, node_t *n, node_t *adj) {
  graph_t *rv, *cl, *tcl, *hcl;
  edge_t *orig;
 
  rv = NULL;
  if (ND_node_type(n) == NORMAL)
    tcl = hcl = ND_clust(n);
  else {
    orig = ED_to_orig(ND_out(n).list[0]);
    tcl = ND_clust(agtail(orig));
    hcl = ND_clust(aghead(orig));
  }
  if (ND_node_type(adj) == NORMAL) {
    cl = REAL_CLUSTER(adj);
    if (cl && cl != tcl && cl != hcl)
      rv = cl;
  } else {
    orig = ED_to_orig(ND_out(adj).list[0]);
    cl = REAL_CLUSTER(agtail(orig));
    if (cl && cl != tcl && cl != hcl && cl_vninside(cl, adj))
      rv = cl;
    else {
      cl = REAL_CLUSTER(aghead(orig));
      if (cl && cl != tcl && cl != hcl && cl_vninside(cl, adj))
        rv = cl;
    }
  }
  return rv;
}
 
/* maximal_bbox:
 * Return an initial bounding box to be used for building the
 * beginning or ending of the path of boxes.
 * Height reflects height of tallest node on rank.
 * The extra space provided by FUDGE allows begin/endpath to create a box
 * FUDGE-2 away from the node, so the routing can avoid the node and the
 * box is at least 2 wide.
 */
#define FUDGE 4
 
static boxf maximal_bbox(graph_t *g, spline_info_t *sp, node_t *vn, edge_t *ie,
                         edge_t *oe) {
  double b, nb;
  graph_t *left_cl, *right_cl;
  node_t *left, *right;
  boxf rv;
 
  left_cl = right_cl = NULL;
 
  /* give this node all the available space up to its neighbors */
  b = (double)(ND_coord(vn).x - ND_lw(vn) - FUDGE);
  if ((left = neighbor(g, vn, ie, oe, -1))) {
    if ((left_cl = cl_bound(g, vn, left)))
      nb = GD_bb(left_cl).UR.x + sp->Splinesep;
    else {
      nb = (double)(ND_coord(left).x + ND_mval(left));
      if (ND_node_type(left) == NORMAL)
        nb += GD_nodesep(g) / 2.;
      else
        nb += sp->Splinesep;
    }
    if (nb < b)
      b = nb;
    rv.LL.x = round(b);
  } else
    rv.LL.x = fmin(round(b), sp->LeftBound);
 
  /* we have to leave room for our own label! */
  if (ND_node_type(vn) == VIRTUAL && ND_label(vn))
    b = (double)(ND_coord(vn).x + 10);
  else
    b = (double)(ND_coord(vn).x + ND_rw(vn) + FUDGE);
  if ((right = neighbor(g, vn, ie, oe, 1))) {
    if ((right_cl = cl_bound(g, vn, right)))
      nb = GD_bb(right_cl).LL.x - sp->Splinesep;
    else {
      nb = ND_coord(right).x - ND_lw(right);
      if (ND_node_type(right) == NORMAL)
        nb -= GD_nodesep(g) / 2.;
      else
        nb -= sp->Splinesep;
    }
    if (nb > b)
      b = nb;
    rv.UR.x = round(b);
  } else
    rv.UR.x = fmax(round(b), sp->RightBound);
 
  if (ND_node_type(vn) == VIRTUAL && ND_label(vn)) {
    rv.UR.x -= ND_rw(vn);
    if (rv.UR.x < rv.LL.x)
      rv.UR.x = ND_coord(vn).x;
  }
 
  rv.LL.y = ND_coord(vn).y - GD_rank(g)[ND_rank(vn)].ht1;
  rv.UR.y = ND_coord(vn).y + GD_rank(g)[ND_rank(vn)].ht2;
  return rv;
}
 
static node_t *neighbor(graph_t *g, node_t *vn, edge_t *ie, edge_t *oe,
                        int dir) {
  int i;
  node_t *n, *rv = NULL;
  rank_t *rank = &(GD_rank(g)[ND_rank(vn)]);
 
  for (i = ND_order(vn) + dir; i >= 0 && i < rank->n; i += dir) {
    n = rank->v[i];
    if (ND_node_type(n) == VIRTUAL && ND_label(n)) {
      rv = n;
      break;
    }
    if (ND_node_type(n) == NORMAL) {
      rv = n;
      break;
    }
    if (!pathscross(n, vn, ie, oe)) {
      rv = n;
      break;
    }
  }
  return rv;
}
 
static bool pathscross(node_t *n0, node_t *n1, edge_t *ie1, edge_t *oe1) {
  edge_t *e0, *e1;
  node_t *na, *nb;
  int order, cnt;
 
  order = ND_order(n0) > ND_order(n1);
  if (ND_out(n0).size != 1 && ND_out(n1).size != 1)
    return false;
  e1 = oe1;
  if (ND_out(n0).size == 1 && e1) {
    e0 = ND_out(n0).list[0];
    for (cnt = 0; cnt < 2; cnt++) {
      if ((na = aghead(e0)) == (nb = aghead(e1)))
        break;
      if (order != (ND_order(na) > ND_order(nb)))
        return true;
      if (ND_out(na).size != 1 || ND_node_type(na) == NORMAL)
        break;
      e0 = ND_out(na).list[0];
      if (ND_out(nb).size != 1 || ND_node_type(nb) == NORMAL)
        break;
      e1 = ND_out(nb).list[0];
    }
  }
  e1 = ie1;
  if (ND_in(n0).size == 1 && e1) {
    e0 = ND_in(n0).list[0];
    for (cnt = 0; cnt < 2; cnt++) {
      if ((na = agtail(e0)) == (nb = agtail(e1)))
        break;
      if (order != (ND_order(na) > ND_order(nb)))
        return true;
      if (ND_in(na).size != 1 || ND_node_type(na) == NORMAL)
        break;
      e0 = ND_in(na).list[0];
      if (ND_in(nb).size != 1 || ND_node_type(nb) == NORMAL)
        break;
      e1 = ND_in(nb).list[0];
    }
  }
  return false;
}
 
#ifdef DEBUG
void showpath(path *p) {
  pointf LL, UR;
 
  fprintf(stderr, "%%!PS\n");
  for (size_t i = 0; i < p->nbox; i++) {
    LL = p->boxes[i].LL;
    UR = p->boxes[i].UR;
    fprintf(stderr,
            "newpath %.04f %.04f moveto %.04f %.04f lineto %.04f %.04f lineto "
            "%.04f %.04f lineto closepath stroke\n",
            LL.x, LL.y, UR.x, LL.y, UR.x, UR.y, LL.x, UR.y);
  }
  fprintf(stderr, "showpage\n");
}
#endif