/************************************************************************* * 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 #include #include #include #include #include #include #include #include #include #include #ifdef ORTHO #include #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 pointf tmp = b->list[i]; b->list[i] = b->list[sz - 1 - i]; b->list[sz - 1 - i] = tmp; } { uint32_t tmp = b->sflag; b->sflag = b->eflag; b->eflag = tmp; } { pointf tmp = b->sp; b->sp = b->ep; b->ep = tmp; } } static void swap_spline(splines * s) { const size_t sz = s->size; // reverse list for (size_t i = 0; i < sz / 2; ++i) { bezier tmp = s->list[i]; s->list[i] = s->list[sz - 1 - i]; s->list[sz - 1 - i] = tmp; } // 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) { double tmp = ND_rw(n); ND_rw(n) = ND_mval(n); ND_mval(n) = tmp; } } } /* 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); } } } /** Main spline routing code. * The normalize parameter allows this function to be called by the * recursive call in make_flat_edge without normalization occurring, * so that the edge will only be normalized once in the top level call * of dot_splines. */ 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) { double tmp = ND_rw(n); ND_rw(n) = ND_mval(n); ND_mval(n) = tmp; } 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_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_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_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)) 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)) 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_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; int ports = 0; 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 int warned; tn = agtail(e0), hn = aghead(e0); if (shapeOf(tn) == SH_RECORD || shapeOf(hn) == SH_RECORD) { if (!warned) { warned = 1; 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; 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 = 1; } if (ports == 0) { /* 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)) { node_t *tmp = tn; tn = hn; hn = tmp; } 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; } } /// Return true if p3 is to left of ray p1->p2 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