Graphviz 13.0.0~dev.20250511.0440
Loading...
Searching...
No Matches
dotsplines.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11/*
12 * set edge splines.
13 */
14
15#include <assert.h>
16#include <common/boxes.h>
17#include <dotgen/dot.h>
18#include <math.h>
19#include <stdatomic.h>
20#include <stdbool.h>
21#include <stdint.h>
22#include <stdlib.h>
23#include <string.h>
24#include <util/agxbuf.h>
25#include <util/alloc.h>
26#include <util/gv_math.h>
27#include <util/list.h>
28
29#ifdef ORTHO
30#include <ortho/ortho.h>
31#endif
32
33#define NSUB 9 /* number of subdivisions, re-aiming splines */
34#define CHUNK 128 /* in building list of edges */
35
36#define MINW 16 /* minimum width of a box in the edge path */
37#define HALFMINW 8
38
39#define FWDEDGE 16
40#define BWDEDGE 32
41
42#define MAINGRAPH 64
43#define AUXGRAPH 128
44#define GRAPHTYPEMASK 192 /* the OR of the above */
45
46#define MAKEFWDEDGE(new, old) \
47 { \
48 edge_t *newp; \
49 Agedgeinfo_t *info; \
50 newp = new; \
51 info = (Agedgeinfo_t *)newp->base.data; \
52 *info = *(Agedgeinfo_t *)old->base.data; \
53 *newp = *old; \
54 newp->base.data = (Agrec_t *)info; \
55 AGTAIL(newp) = AGHEAD(old); \
56 AGHEAD(newp) = AGTAIL(old); \
57 ED_tail_port(newp) = ED_head_port(old); \
58 ED_head_port(newp) = ED_tail_port(old); \
59 ED_edge_type(newp) = VIRTUAL; \
60 ED_to_orig(newp) = old; \
61 }
62
63typedef struct {
64 double LeftBound;
65 double RightBound;
66 double Splinesep;
67 double Multisep;
70
72
73static void adjustregularpath(path *, size_t, size_t);
74static Agedge_t *bot_bound(Agedge_t *, int);
75static bool pathscross(Agnode_t *, Agnode_t *, Agedge_t *, Agedge_t *);
77static bool cl_vninside(Agraph_t *, Agnode_t *);
79 pathend_t *, const boxes_t *);
80static int edgecmp(const void *, const void *);
81static int make_flat_edge(graph_t *, spline_info_t *, path *, Agedge_t **,
82 unsigned, unsigned, int);
83static void make_regular_edge(graph_t *g, spline_info_t *, path *, Agedge_t **,
84 unsigned, unsigned, int);
85static boxf makeregularend(boxf, int, double);
87 Agedge_t *);
88static Agnode_t *neighbor(graph_t *, Agnode_t *, Agedge_t *, Agedge_t *, int);
89static void place_vnlabel(Agnode_t *);
90static boxf rank_box(spline_info_t *sp, Agraph_t *, int);
91static void recover_slack(Agedge_t *, path *);
92static void resize_vn(Agnode_t *, double, double, double);
93static void setflags(Agedge_t *, int, int, int);
94static int straight_len(Agnode_t *);
95static Agedge_t *straight_path(Agedge_t *, int, points_t *);
96static Agedge_t *top_bound(Agedge_t *, int);
97
98#define GROWEDGES \
99 do { \
100 edges = gv_recalloc(edges, n_edges, n_edges + CHUNK, sizeof(edge_t *)); \
101 } while (0)
102
104 edge_t *le = e;
105 while (ED_to_virt(le))
106 le = ED_to_virt(le);
107 while (ED_to_orig(le))
108 le = ED_to_orig(le);
109 return le;
110}
111
112static bool spline_merge(node_t *n) {
113 return ND_node_type(n) == VIRTUAL &&
114 (ND_in(n).size > 1 || ND_out(n).size > 1);
115}
116
117static bool swap_ends_p(edge_t *e) {
118 while (ED_to_orig(e))
119 e = ED_to_orig(e);
120 if (ND_rank(aghead(e)) > ND_rank(agtail(e)))
121 return false;
122 if (ND_rank(aghead(e)) < ND_rank(agtail(e)))
123 return true;
124 if (ND_order(aghead(e)) >= ND_order(agtail(e)))
125 return false;
126 return true;
127}
128
130 .splineMerge = spline_merge};
131
132int portcmp(port p0, port p1) {
133 if (!p1.defined)
134 return p0.defined ? 1 : 0;
135 if (!p0.defined)
136 return -1;
137 if (p0.p.x < p1.p.x)
138 return -1;
139 if (p0.p.x > p1.p.x)
140 return 1;
141 if (p0.p.y < p1.p.y)
142 return -1;
143 if (p0.p.y > p1.p.y)
144 return 1;
145 return 0;
146}
147
148static void swap_bezier(bezier *b) {
149 const size_t sz = b->size;
150 for (size_t i = 0; i < sz / 2; ++i) { // reverse list of points
151 SWAP(&b->list[i], &b->list[sz - 1 - i]);
152 }
153
154 SWAP(&b->sflag, &b->eflag);
155 SWAP(&b->sp, &b->ep);
156}
157
158static void swap_spline(splines *s) {
159 const size_t sz = s->size;
160
161 // reverse list
162 for (size_t i = 0; i < sz / 2; ++i) {
163 SWAP(&s->list[i], &s->list[sz - 1 - i]);
164 }
165
166 // swap beziers
167 for (size_t i = 0; i < sz; ++i) {
168 swap_bezier(&s->list[i]);
169 }
170}
171
172/* edge_normalize:
173 * Some back edges are reversed during layout and the reversed edge
174 * is used to compute the spline. We would like to guarantee that
175 * the order of control points always goes from tail to head, so
176 * we reverse them if necessary.
177 */
178static void edge_normalize(graph_t *g) {
179 edge_t *e;
180 node_t *n;
181
182 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
183 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
184 if (sinfo.swapEnds(e) && ED_spl(e))
186 }
187 }
188}
189
190/* resetRW:
191 * In position, each node has its rw stored in mval and,
192 * if a node is part of a loop, rw may be increased to
193 * reflect the loops and associated labels. We restore
194 * the original value here.
195 */
196static void resetRW(graph_t *g) {
197 node_t *n;
198
199 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
200 if (ND_other(n).list) {
201 SWAP(&ND_rw(n), &ND_mval(n));
202 }
203 }
204}
205
206/* setEdgeLabelPos:
207 * Set edge label position information for regular and non-adjacent flat edges.
208 * Dot has allocated space and position for these labels. This info will be
209 * used when routing orthogonal edges.
210 */
211static void setEdgeLabelPos(graph_t *g) {
212 node_t *n;
213 textlabel_t *l;
214
215 /* place regular edge labels */
216 for (n = GD_nlist(g); n; n = ND_next(n)) {
217 if (ND_node_type(n) == VIRTUAL) {
218 if (ND_alg(n)) { // label of non-adjacent flat edge
219 edge_t *fe = ND_alg(n);
220 l = ED_label(fe);
221 assert(l);
222 l->pos = ND_coord(n);
223 l->set = true;
224 } else if ((l = ND_label(n))) { // label of regular edge
225 place_vnlabel(n);
226 }
227 if (l)
228 updateBB(g, l);
229 }
230 }
231}
232
241static int dot_splines_(graph_t *g, int normalize) {
242 int i, j, k, n_nodes;
243 node_t *n;
244 Agedgeinfo_t fwdedgeai, fwdedgebi;
245 Agedgepair_t fwdedgea, fwdedgeb;
246 edge_t *e, *e0, *e1, *ea, *eb, *le0, *le1, **edges = NULL;
247 path P = {0};
248 int et = EDGE_TYPE(g);
249 fwdedgea.out.base.data = (Agrec_t *)&fwdedgeai;
250 fwdedgeb.out.base.data = (Agrec_t *)&fwdedgebi;
251
252 if (et == EDGETYPE_NONE)
253 return 0;
254 if (et == EDGETYPE_CURVED) {
255 resetRW(g);
256 if (GD_has_labels(g->root) & EDGE_LABEL) {
257 agwarningf("edge labels with splines=curved not supported in dot - use "
258 "xlabels\n");
259 }
260 }
261#ifdef ORTHO
262 if (et == EDGETYPE_ORTHO) {
263 resetRW(g);
264 if (GD_has_labels(g->root) & EDGE_LABEL) {
266 orthoEdges(g, true);
267 } else
268 orthoEdges(g, false);
269 goto finish;
270 }
271#else
272 (void)setEdgeLabelPos;
273#endif
274
276 if (routesplinesinit())
277 return 0;
278 spline_info_t sd = {.Splinesep = GD_nodesep(g) / 4,
279 .Multisep = GD_nodesep(g)};
280 edges = gv_calloc(CHUNK, sizeof(edge_t *));
281
282 /* compute boundaries and list of splines */
283 unsigned n_edges = 0;
284 n_nodes = 0;
285 for (i = GD_minrank(g); i <= GD_maxrank(g); i++) {
286 n_nodes += GD_rank(g)[i].n;
287 if ((n = GD_rank(g)[i].v[0]))
288 sd.LeftBound = MIN(sd.LeftBound, (ND_coord(n).x - ND_lw(n)));
289 if (GD_rank(g)[i].n && (n = GD_rank(g)[i].v[GD_rank(g)[i].n - 1]))
290 sd.RightBound = MAX(sd.RightBound, (ND_coord(n).x + ND_rw(n)));
291 sd.LeftBound -= MINW;
292 sd.RightBound += MINW;
293
294 for (j = 0; j < GD_rank(g)[i].n; j++) {
295 n = GD_rank(g)[i].v[j];
296 /* if n is the label of a flat edge, copy its position to
297 * the label.
298 */
299 if (ND_alg(n)) {
300 edge_t *fe = ND_alg(n);
301 assert(ED_label(fe));
302 ED_label(fe)->pos = ND_coord(n);
303 ED_label(fe)->set = true;
304 }
305 if (ND_node_type(n) != NORMAL && !sinfo.splineMerge(n))
306 continue;
307 for (k = 0; (e = ND_out(n).list[k]); k++) {
308 if (ED_edge_type(e) == FLATORDER || ED_edge_type(e) == IGNORED)
309 continue;
311 edges[n_edges++] = e;
312 if (n_edges % CHUNK == 0)
313 GROWEDGES;
314 }
315 if (ND_flat_out(n).list)
316 for (k = 0; (e = ND_flat_out(n).list[k]); k++) {
317 setflags(e, FLATEDGE, 0, AUXGRAPH);
318 edges[n_edges++] = e;
319 if (n_edges % CHUNK == 0)
320 GROWEDGES;
321 }
322 if (ND_other(n).list) {
323 /* In position, each node has its rw stored in mval and,
324 * if a node is part of a loop, rw may be increased to
325 * reflect the loops and associated labels. We restore
326 * the original value here.
327 */
328 if (ND_node_type(n) == NORMAL) {
329 SWAP(&ND_rw(n), &ND_mval(n));
330 }
331 for (k = 0; (e = ND_other(n).list[k]); k++) {
332 setflags(e, 0, 0, AUXGRAPH);
333 edges[n_edges++] = e;
334 if (n_edges % CHUNK == 0)
335 GROWEDGES;
336 }
337 }
338 }
339 }
340
341 /* Sort so that equivalent edges are contiguous.
342 * Equivalence should basically mean that 2 edges have the
343 * same set {(tailnode,tailport),(headnode,headport)}, or
344 * alternatively, the edges would be routed identically if
345 * routed separately.
346 */
347 qsort(edges, n_edges, sizeof(edges[0]), edgecmp);
348
349 /* FIXME: just how many boxes can there be? */
350 P.boxes = gv_calloc(n_nodes + 20 * 2 * NSUB, sizeof(boxf));
351 sd.Rank_box = gv_calloc(i, sizeof(boxf));
352
353 if (et == EDGETYPE_LINE) {
354 /* place regular edge labels */
355 for (n = GD_nlist(g); n; n = ND_next(n)) {
356 if (ND_node_type(n) == VIRTUAL && ND_label(n)) {
357 place_vnlabel(n);
358 }
359 }
360 }
361
362 for (unsigned l = 0; l < n_edges;) {
363 const unsigned ind = l;
364 le0 = getmainedge((e0 = edges[l++]));
365 if (ED_tail_port(e0).defined || ED_head_port(e0).defined) {
366 ea = e0;
367 } else {
368 ea = le0;
369 }
370 if (ED_tree_index(ea) & BWDEDGE) {
371 MAKEFWDEDGE(&fwdedgea.out, ea);
372 ea = &fwdedgea.out;
373 }
374 unsigned cnt;
375 for (cnt = 1; l < n_edges; cnt++, l++) {
376 if (le0 != (le1 = getmainedge((e1 = edges[l]))))
377 break;
378 if (ED_adjacent(e0))
379 continue; /* all flat adjacent edges at once */
380 if (ED_tail_port(e1).defined || ED_head_port(e1).defined) {
381 eb = e1;
382 } else {
383 eb = le1;
384 }
385 if (ED_tree_index(eb) & BWDEDGE) {
386 MAKEFWDEDGE(&fwdedgeb.out, eb);
387 eb = &fwdedgeb.out;
388 }
389 if (portcmp(ED_tail_port(ea), ED_tail_port(eb)))
390 break;
391 if (portcmp(ED_head_port(ea), ED_head_port(eb)))
392 break;
393 if ((ED_tree_index(e0) & EDGETYPEMASK) == FLATEDGE &&
394 ED_label(e0) != ED_label(e1))
395 break;
396 if (ED_tree_index(edges[l]) & MAINGRAPH) /* Aha! -C is on */
397 break;
398 }
399
400 if (et == EDGETYPE_CURVED) {
401 edge_t **edgelist = gv_calloc(cnt, sizeof(edge_t *));
402 edgelist[0] = getmainedge((edges + ind)[0]);
403 for (unsigned ii = 1; ii < cnt; ii++)
404 edgelist[ii] = (edges + ind)[ii];
406 free(edgelist);
407 } else if (agtail(e0) == aghead(e0)) {
408 int r;
409 double sizey;
410 n = agtail(e0);
411 r = ND_rank(n);
412 if (r == GD_maxrank(g)) {
413 if (r > 0)
414 sizey = ND_coord(GD_rank(g)[r - 1].v[0]).y - ND_coord(n).y;
415 else
416 sizey = ND_ht(n);
417 } else if (r == GD_minrank(g)) {
418 sizey = ND_coord(n).y - ND_coord(GD_rank(g)[r + 1].v[0]).y;
419 } else {
420 double upy = ND_coord(GD_rank(g)[r - 1].v[0]).y - ND_coord(n).y;
421 double dwny = ND_coord(n).y - ND_coord(GD_rank(g)[r + 1].v[0]).y;
422 sizey = MIN(upy, dwny);
423 }
424 makeSelfEdge(edges, ind, cnt, sd.Multisep, sizey / 2, &sinfo);
425 for (unsigned b = 0; b < cnt; b++) {
426 e = edges[ind + b];
427 if (ED_label(e))
428 updateBB(g, ED_label(e));
429 }
430 } else if (ND_rank(agtail(e0)) == ND_rank(aghead(e0))) {
431 const int rc = make_flat_edge(g, &sd, &P, edges, ind, cnt, et);
432 if (rc != 0) {
433 return rc;
434 }
435 } else
436 make_regular_edge(g, &sd, &P, edges, ind, cnt, et);
437 }
438
439 /* place regular edge labels */
440 for (n = GD_nlist(g); n; n = ND_next(n)) {
441 if (ND_node_type(n) == VIRTUAL && ND_label(n)) {
442 place_vnlabel(n);
443 updateBB(g, ND_label(n));
444 }
445 }
446
447 /* normalize splines so they always go from tail to head */
448 /* place_portlabel relies on this being done first */
449 if (normalize)
451
452#ifdef ORTHO
453finish:
454#endif
455 /* place port labels */
456 /* FIX: head and tail labels are not part of cluster bbox */
458 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
459 if (E_headlabel) {
460 for (e = agfstin(g, n); e; e = agnxtin(g, e))
461 if (ED_head_label(AGMKOUT(e))) {
462 place_portlabel(AGMKOUT(e), true);
464 }
465 }
466 if (E_taillabel) {
467 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
468 if (ED_tail_label(e)) {
469 if (place_portlabel(e, false))
470 updateBB(g, ED_tail_label(e));
471 }
472 }
473 }
474 }
475 }
476
477#ifdef ORTHO
478 if (et != EDGETYPE_ORTHO && et != EDGETYPE_CURVED) {
479#else
480 if (et != EDGETYPE_CURVED) {
481#endif
482 free(sd.Rank_box);
484 }
485 free(edges);
486 free(P.boxes);
488 EdgeLabelsDone = 1;
489 return 0;
490}
491
492/* dot_splines:
493 * If the splines attribute is defined but equal to "", skip edge routing.
494 *
495 * @return 0 on success
496 */
497int dot_splines(graph_t *g) { return dot_splines_(g, 1); }
498
499/* place_vnlabel:
500 * assign position of an edge label from its virtual node
501 * This is for regular edges only.
502 */
503static void place_vnlabel(node_t *n) {
504 pointf dimen;
505 double width;
506 edge_t *e;
507 if (ND_in(n).size == 0)
508 return; /* skip flat edge labels here */
509 for (e = ND_out(n).list[0]; ED_edge_type(e) != NORMAL; e = ED_to_orig(e))
510 ;
511 dimen = ED_label(e)->dimen;
512 width = GD_flip(agraphof(n)) ? dimen.y : dimen.x;
513 ED_label(e)->pos.x = ND_coord(n).x + width / 2.0;
514 ED_label(e)->pos.y = ND_coord(n).y;
515 ED_label(e)->set = true;
516}
517
518static void setflags(edge_t *e, int hint1, int hint2, int f3) {
519 int f1, f2;
520 if (hint1 != 0)
521 f1 = hint1;
522 else {
523 if (agtail(e) == aghead(e))
524 if (ED_tail_port(e).defined || ED_head_port(e).defined)
525 f1 = SELFWPEDGE;
526 else
527 f1 = SELFNPEDGE;
528 else if (ND_rank(agtail(e)) == ND_rank(aghead(e)))
529 f1 = FLATEDGE;
530 else
531 f1 = REGULAREDGE;
532 }
533 if (hint2 != 0)
534 f2 = hint2;
535 else {
536 if (f1 == REGULAREDGE)
537 f2 = ND_rank(agtail(e)) < ND_rank(aghead(e)) ? FWDEDGE : BWDEDGE;
538 else if (f1 == FLATEDGE)
539 f2 = ND_order(agtail(e)) < ND_order(aghead(e)) ? FWDEDGE : BWDEDGE;
540 else /* f1 == SELF*EDGE */
541 f2 = FWDEDGE;
542 }
543 ED_tree_index(e) = (f1 | f2 | f3);
544}
545
546/* edgecmp:
547 * lexicographically order edges by
548 * - edge type
549 * - |rank difference of nodes|
550 * - |x difference of nodes|
551 * - id of witness edge for equivalence class
552 * - port comparison
553 * - graph type
554 * - labels if flat edges
555 * - edge id
556 */
557static int edgecmp(const void *x, const void *y) {
558// Suppress Clang/GCC -Wcast-qual warning. Casting away const here is acceptable
559// as the later usage is const. We need the cast because the macros use
560// non-const pointers for genericity.
561#ifdef __GNUC__
562#pragma GCC diagnostic push
563#pragma GCC diagnostic ignored "-Wcast-qual"
564#endif
565 edge_t **ptr0 = (edge_t **)x;
566 edge_t **ptr1 = (edge_t **)y;
567#ifdef __GNUC__
568#pragma GCC diagnostic pop
569#endif
570 Agedgeinfo_t fwdedgeai, fwdedgebi;
571 Agedgepair_t fwdedgea, fwdedgeb;
572 edge_t *e0, *e1, *ea, *eb, *le0, *le1;
573 int et0, et1, v0, v1, rv;
574 double t0, t1;
575
576 fwdedgea.out.base.data = (Agrec_t *)&fwdedgeai;
577 fwdedgeb.out.base.data = (Agrec_t *)&fwdedgebi;
578 e0 = *ptr0;
579 e1 = *ptr1;
580 et0 = ED_tree_index(e0) & EDGETYPEMASK;
581 et1 = ED_tree_index(e1) & EDGETYPEMASK;
582 if (et0 < et1) {
583 return 1;
584 }
585 if (et0 > et1) {
586 return -1;
587 }
588
589 le0 = getmainedge(e0);
590 le1 = getmainedge(e1);
591
592 t0 = ND_rank(agtail(le0)) - ND_rank(aghead(le0));
593 t1 = ND_rank(agtail(le1)) - ND_rank(aghead(le1));
594 v0 = abs((int)t0); /* ugly, but explicit as to how we avoid equality tests on
595 fp numbers */
596 v1 = abs((int)t1);
597 if (v0 < v1) {
598 return -1;
599 }
600 if (v0 > v1) {
601 return 1;
602 }
603
604 t0 = ND_coord(agtail(le0)).x - ND_coord(aghead(le0)).x;
605 t1 = ND_coord(agtail(le1)).x - ND_coord(aghead(le1)).x;
606 v0 = abs((int)t0);
607 v1 = abs((int)t1);
608 if (v0 < v1) {
609 return -1;
610 }
611 if (v0 > v1) {
612 return 1;
613 }
614
615 /* This provides a cheap test for edges having the same set of endpoints. */
616 if (AGSEQ(le0) < AGSEQ(le1)) {
617 return -1;
618 }
619 if (AGSEQ(le0) > AGSEQ(le1)) {
620 return 1;
621 }
622
623 ea = (ED_tail_port(e0).defined || ED_head_port(e0).defined) ? e0 : le0;
624 if (ED_tree_index(ea) & BWDEDGE) {
625 MAKEFWDEDGE(&fwdedgea.out, ea);
626 ea = &fwdedgea.out;
627 }
628 eb = (ED_tail_port(e1).defined || ED_head_port(e1).defined) ? e1 : le1;
629 if (ED_tree_index(eb) & BWDEDGE) {
630 MAKEFWDEDGE(&fwdedgeb.out, eb);
631 eb = &fwdedgeb.out;
632 }
633 if ((rv = portcmp(ED_tail_port(ea), ED_tail_port(eb))))
634 return rv;
635 if ((rv = portcmp(ED_head_port(ea), ED_head_port(eb))))
636 return rv;
637
638 et0 = ED_tree_index(e0) & GRAPHTYPEMASK;
639 et1 = ED_tree_index(e1) & GRAPHTYPEMASK;
640 if (et0 < et1) {
641 return -1;
642 }
643 if (et0 > et1) {
644 return 1;
645 }
646
647 if (et0 == FLATEDGE) {
648 if (ED_label(e0) < ED_label(e1)) {
649 return -1;
650 }
651 if (ED_label(e0) > ED_label(e1)) {
652 return 1;
653 }
654 }
655
656 if (AGSEQ(e0) < AGSEQ(e1)) {
657 return -1;
658 }
659 if (AGSEQ(e0) > AGSEQ(e1)) {
660 return 1;
661 }
662 return 0;
663}
664
709
710static void setState(graph_t *auxg, attr_state_t *attr_state) {
711 /* save state */
712 attr_state->E_constr = E_constr;
713 attr_state->E_dir = E_dir;
714 attr_state->E_samehead = E_samehead;
715 attr_state->E_sametail = E_sametail;
716 attr_state->E_weight = E_weight;
717 attr_state->E_minlen = E_minlen;
718 attr_state->E_fontcolor = E_fontcolor;
719 attr_state->E_fontname = E_fontname;
720 attr_state->E_fontsize = E_fontsize;
721 attr_state->E_headclip = E_headclip;
722 attr_state->E_headlabel = E_headlabel;
723 attr_state->E_label = E_label;
724 attr_state->E_label_float = E_label_float;
726 attr_state->E_labelfontname = E_labelfontname;
727 attr_state->E_labelfontsize = E_labelfontsize;
728 attr_state->E_tailclip = E_tailclip;
729 attr_state->E_taillabel = E_taillabel;
730 attr_state->E_xlabel = E_xlabel;
731 attr_state->N_height = N_height;
732 attr_state->N_width = N_width;
733 attr_state->N_shape = N_shape;
734 attr_state->N_style = N_style;
735 attr_state->N_fontsize = N_fontsize;
736 attr_state->N_fontname = N_fontname;
737 attr_state->N_fontcolor = N_fontcolor;
738 attr_state->N_label = N_label;
739 attr_state->N_xlabel = N_xlabel;
740 attr_state->N_showboxes = N_showboxes;
741 attr_state->N_ordering = N_ordering;
742 attr_state->N_sides = N_sides;
743 attr_state->N_peripheries = N_peripheries;
744 attr_state->N_skew = N_skew;
745 attr_state->N_orientation = N_orientation;
746 attr_state->N_distortion = N_distortion;
747 attr_state->N_fixed = N_fixed;
748 attr_state->N_nojustify = N_nojustify;
749 attr_state->N_group = N_group;
750 attr_state->State = State;
751 attr_state->G_ordering = G_ordering;
752
753 E_constr = NULL;
754 E_dir = agattr_text(auxg, AGEDGE, "dir", NULL);
755 E_samehead = agattr_text(auxg, AGEDGE, "samehead", NULL);
756 E_sametail = agattr_text(auxg, AGEDGE, "sametail", NULL);
757 E_weight = agattr_text(auxg, AGEDGE, "weight", NULL);
758 if (!E_weight)
759 E_weight = agattr_text(auxg, AGEDGE, "weight", "");
760 E_minlen = NULL;
762 E_fontname = agfindedgeattr(auxg, "fontname");
763 E_fontsize = agfindedgeattr(auxg, "fontsize");
764 E_headclip = agfindedgeattr(auxg, "headclip");
766 E_label = agfindedgeattr(auxg, "label");
767 E_label_float = agfindedgeattr(auxg, "label_float");
769 E_labelfontname = agfindedgeattr(auxg, "labelfontname");
770 E_labelfontsize = agfindedgeattr(auxg, "labelfontsize");
771 E_tailclip = agfindedgeattr(auxg, "tailclip");
773 E_xlabel = NULL;
774 N_height = agfindnodeattr(auxg, "height");
775 N_width = agfindnodeattr(auxg, "width");
776 N_shape = agfindnodeattr(auxg, "shape");
777 N_style = NULL;
778 N_fontsize = agfindnodeattr(auxg, "fontsize");
779 N_fontname = agfindnodeattr(auxg, "fontname");
781 N_label = agfindnodeattr(auxg, "label");
782 N_xlabel = NULL;
784 N_ordering = agfindnodeattr(auxg, "ordering");
785 N_sides = agfindnodeattr(auxg, "sides");
786 N_peripheries = agfindnodeattr(auxg, "peripheries");
787 N_skew = agfindnodeattr(auxg, "skew");
788 N_orientation = agfindnodeattr(auxg, "orientation");
789 N_distortion = agfindnodeattr(auxg, "distortion");
790 N_fixed = agfindnodeattr(auxg, "fixed");
792 N_group = NULL;
793 G_ordering = agfindgraphattr(auxg, "ordering");
794}
795
796/* cloneGraph:
797 * Create clone graph. It stores the global Agsyms, to be
798 * restored in cleanupCloneGraph. The graph uses the main
799 * graph's settings for certain geometry parameters, and
800 * declares all node and edge attributes used in the original
801 * graph.
802 */
803static graph_t *cloneGraph(graph_t *g, attr_state_t *attr_state) {
804 Agsym_t *sym;
805 graph_t *auxg;
806 if (agisdirected(g))
807 auxg = agopen("auxg", Agdirected, NULL);
808 else
809 auxg = agopen("auxg", Agundirected, NULL);
810 agbindrec(auxg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
811 agattr_text(auxg, AGRAPH, "rank", "");
812 GD_drawing(auxg) = gv_alloc(sizeof(layout_t));
813 GD_drawing(auxg)->quantum = GD_drawing(g)->quantum;
814 GD_drawing(auxg)->dpi = GD_drawing(g)->dpi;
815
816 GD_charset(auxg) = GD_charset(g);
817 if (GD_flip(g))
818 SET_RANKDIR(auxg, RANKDIR_TB);
819 else
820 SET_RANKDIR(auxg, RANKDIR_LR);
821 GD_nodesep(auxg) = GD_nodesep(g);
822 GD_ranksep(auxg) = GD_ranksep(g);
823
824 // copy node attrs to auxg
825 sym = agnxtattr(agroot(g), AGNODE, NULL); // get the first attr.
826 for (; sym; sym = agnxtattr(agroot(g), AGNODE, sym)) {
827 const bool is_html = aghtmlstr(sym->defval);
828 is_html ? agattr_html(auxg, AGNODE, sym->name, sym->defval)
829 : agattr_text(auxg, AGNODE, sym->name, sym->defval);
830 }
831
832 // copy edge attributes
833 sym = agnxtattr(agroot(g), AGEDGE, NULL); // get the first attr.
834 for (; sym; sym = agnxtattr(agroot(g), AGEDGE, sym)) {
835 const bool is_html = aghtmlstr(sym->defval);
836 is_html ? agattr_html(auxg, AGEDGE, sym->name, sym->defval)
837 : agattr_text(auxg, AGEDGE, sym->name, sym->defval);
838 }
839
840 if (!agattr_text(auxg, AGEDGE, "headport", NULL))
841 agattr_text(auxg, AGEDGE, "headport", "");
842 if (!agattr_text(auxg, AGEDGE, "tailport", NULL))
843 agattr_text(auxg, AGEDGE, "tailport", "");
844
845 setState(auxg, attr_state);
846
847 return auxg;
848}
849
850static void cleanupCloneGraph(graph_t *g, attr_state_t *attr_state) {
851 /* restore main graph syms */
852 E_constr = attr_state->E_constr;
853 E_dir = attr_state->E_dir;
854 E_samehead = attr_state->E_samehead;
855 E_sametail = attr_state->E_sametail;
856 E_weight = attr_state->E_weight;
857 E_minlen = attr_state->E_minlen;
858 E_fontcolor = attr_state->E_fontcolor;
859 E_fontname = attr_state->E_fontname;
860 E_fontsize = attr_state->E_fontsize;
861 E_headclip = attr_state->E_headclip;
862 E_headlabel = attr_state->E_headlabel;
863 E_label = attr_state->E_label;
864 E_label_float = attr_state->E_label_float;
866 E_labelfontname = attr_state->E_labelfontname;
867 E_labelfontsize = attr_state->E_labelfontsize;
868 E_tailclip = attr_state->E_tailclip;
869 E_taillabel = attr_state->E_taillabel;
870 E_xlabel = attr_state->E_xlabel;
871 N_height = attr_state->N_height;
872 N_width = attr_state->N_width;
873 N_shape = attr_state->N_shape;
874 N_style = attr_state->N_style;
875 N_fontsize = attr_state->N_fontsize;
876 N_fontname = attr_state->N_fontname;
877 N_fontcolor = attr_state->N_fontcolor;
878 N_label = attr_state->N_label;
879 N_xlabel = attr_state->N_xlabel;
880 N_showboxes = attr_state->N_showboxes;
881 N_ordering = attr_state->N_ordering;
882 N_sides = attr_state->N_sides;
883 N_peripheries = attr_state->N_peripheries;
884 N_skew = attr_state->N_skew;
885 N_orientation = attr_state->N_orientation;
886 N_distortion = attr_state->N_distortion;
887 N_fixed = attr_state->N_fixed;
888 N_nojustify = attr_state->N_nojustify;
889 N_group = attr_state->N_group;
890 G_ordering = attr_state->G_ordering;
891 State = attr_state->State;
892
893 dot_cleanup(g);
894 agclose(g);
895}
896
897/* cloneNode:
898 * If original graph has rankdir=LR or RL, records change shape,
899 * so we wrap a record node's label in "{...}" to prevent this.
900 */
901static node_t *cloneNode(graph_t *g, node_t *orign) {
902 node_t *n = agnode(g, agnameof(orign), 1);
903 agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), true);
904 agcopyattr(orign, n);
905 if (shapeOf(orign) == SH_RECORD) {
906 agxbuf buf = {0};
907 agxbprint(&buf, "{%s}", ND_label(orign)->text);
908 agset(n, "label", agxbuse(&buf));
909 agxbfree(&buf);
910 }
911
912 return n;
913}
914
915static edge_t *cloneEdge(graph_t *g, node_t *tn, node_t *hn, edge_t *orig) {
916 edge_t *e = agedge(g, tn, hn, NULL, 1);
917 agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), true);
918 agcopyattr(orig, e);
919
920 return e;
921}
922
923/* transformf:
924 * Rotate, if necessary, then translate points.
925 */
926static pointf transformf(pointf p, pointf del, int flip) {
927 if (flip) {
928 double i = p.x;
929 p.x = p.y;
930 p.y = -i;
931 }
932 return add_pointf(p, del);
933}
934
935/* edgelblcmpfn:
936 * lexicographically order edges by
937 * - has label
938 * - label is wider
939 * - label is higher
940 */
941static int edgelblcmpfn(const void *x, const void *y) {
942// Suppress Clang/GCC -Wcast-qual warning. Casting away const here is acceptable
943// as the later usage is const. We need the cast because the macros use
944// non-const pointers for genericity.
945#ifdef __GNUC__
946#pragma GCC diagnostic push
947#pragma GCC diagnostic ignored "-Wcast-qual"
948#endif
949 edge_t **ptr0 = (edge_t **)x;
950 edge_t **ptr1 = (edge_t **)y;
951#ifdef __GNUC__
952#pragma GCC diagnostic pop
953#endif
954 pointf sz0, sz1;
955
956 edge_t *e0 = *ptr0;
957 edge_t *e1 = *ptr1;
958
959 if (ED_label(e0)) {
960 if (ED_label(e1)) {
961 sz0 = ED_label(e0)->dimen;
962 sz1 = ED_label(e1)->dimen;
963 if (sz0.x > sz1.x)
964 return -1;
965 if (sz0.x < sz1.x)
966 return 1;
967 if (sz0.y > sz1.y)
968 return -1;
969 if (sz0.y < sz1.y)
970 return 1;
971 return 0;
972 }
973 return -1;
974 }
975 if (ED_label(e1)) {
976 return 1;
977 }
978 return 0;
979}
980
981#define LBL_SPACE 6 /* space between labels, in points */
982
983/* makeSimpleFlatLabels:
984 * This handles the second simplest case for flat edges between
985 * two adjacent nodes. We still invoke a dot on a rotated problem
986 * to handle edges with ports. This usually works, but fails for
987 * records because of their weird nature.
988 */
989static void makeSimpleFlatLabels(node_t *tn, node_t *hn, edge_t **edges,
990 unsigned ind, unsigned cnt, int et,
991 unsigned n_lbls) {
993 edge_t *e = edges[ind];
994 pointf points[10], tp, hp;
995 double leftend, rightend, ctrx, ctry, miny, maxy;
996 double uminx, umaxx;
997 double lminx = 0.0, lmaxx = 0.0;
998
999 edge_t **earray = gv_calloc(cnt, sizeof(edge_t *));
1000
1001 for (unsigned i = 0; i < cnt; i++) {
1002 earray[i] = edges[ind + i];
1003 }
1004
1005 qsort(earray, cnt, sizeof(edge_t *), edgelblcmpfn);
1006
1007 tp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
1008 hp = add_pointf(ND_coord(hn), ED_head_port(e).p);
1009
1010 leftend = tp.x + ND_rw(tn);
1011 rightend = hp.x - ND_lw(hn);
1012 ctrx = (leftend + rightend) / 2.0;
1013
1014 /* do first edge */
1015 e = earray[0];
1016 size_t pointn = 0;
1017 points[pointn++] = tp;
1018 points[pointn++] = tp;
1019 points[pointn++] = hp;
1020 points[pointn++] = hp;
1021 clip_and_install(e, aghead(e), points, pointn, &sinfo);
1022 ED_label(e)->pos.x = ctrx;
1023 ED_label(e)->pos.y = tp.y + (ED_label(e)->dimen.y + LBL_SPACE) / 2.0;
1024 ED_label(e)->set = true;
1025
1026 miny = tp.y + LBL_SPACE / 2.0;
1027 maxy = miny + ED_label(e)->dimen.y;
1028 uminx = ctrx - ED_label(e)->dimen.x / 2.0;
1029 umaxx = ctrx + ED_label(e)->dimen.x / 2.0;
1030
1031 unsigned i;
1032 for (i = 1; i < n_lbls; i++) {
1033 e = earray[i];
1034 if (i % 2) { /* down */
1035 if (i == 1) {
1036 lminx = ctrx - ED_label(e)->dimen.x / 2.0;
1037 lmaxx = ctrx + ED_label(e)->dimen.x / 2.0;
1038 }
1039 miny -= LBL_SPACE + ED_label(e)->dimen.y;
1040 points[0] = tp;
1041 points[1].x = tp.x;
1042 points[1].y = miny - LBL_SPACE;
1043 points[2].x = hp.x;
1044 points[2].y = points[1].y;
1045 points[3] = hp;
1046 points[4].x = lmaxx;
1047 points[4].y = hp.y;
1048 points[5].x = lmaxx;
1049 points[5].y = miny;
1050 points[6].x = lminx;
1051 points[6].y = miny;
1052 points[7].x = lminx;
1053 points[7].y = tp.y;
1054 ctry = miny + ED_label(e)->dimen.y / 2.0;
1055 } else { /* up */
1056 points[0] = tp;
1057 points[1].x = uminx;
1058 points[1].y = tp.y;
1059 points[2].x = uminx;
1060 points[2].y = maxy;
1061 points[3].x = umaxx;
1062 points[3].y = maxy;
1063 points[4].x = umaxx;
1064 points[4].y = hp.y;
1065 points[5].x = hp.x;
1066 points[5].y = hp.y;
1067 points[6].x = hp.x;
1068 points[6].y = maxy + LBL_SPACE;
1069 points[7].x = tp.x;
1070 points[7].y = maxy + LBL_SPACE;
1071 ctry = maxy + ED_label(e)->dimen.y / 2.0 + LBL_SPACE;
1072 maxy += ED_label(e)->dimen.y + LBL_SPACE;
1073 }
1074 poly.pn = 8;
1075 poly.ps = (Ppoint_t *)points;
1076 size_t pn;
1077 pointf *ps = simpleSplineRoute(tp, hp, poly, &pn, et == EDGETYPE_PLINE);
1078 if (ps == NULL || pn == 0) {
1079 free(ps);
1080 free(earray);
1081 return;
1082 }
1083 ED_label(e)->pos.x = ctrx;
1084 ED_label(e)->pos.y = ctry;
1085 ED_label(e)->set = true;
1086 clip_and_install(e, aghead(e), ps, pn, &sinfo);
1087 free(ps);
1088 }
1089
1090 /* edges with no labels */
1091 for (; i < cnt; i++) {
1092 e = earray[i];
1093 if (i % 2) { /* down */
1094 if (i == 1) {
1095 lminx = (2 * leftend + rightend) / 3.0;
1096 lmaxx = (leftend + 2 * rightend) / 3.0;
1097 }
1098 miny -= LBL_SPACE;
1099 points[0] = tp;
1100 points[1].x = tp.x;
1101 points[1].y = miny - LBL_SPACE;
1102 points[2].x = hp.x;
1103 points[2].y = points[1].y;
1104 points[3] = hp;
1105 points[4].x = lmaxx;
1106 points[4].y = hp.y;
1107 points[5].x = lmaxx;
1108 points[5].y = miny;
1109 points[6].x = lminx;
1110 points[6].y = miny;
1111 points[7].x = lminx;
1112 points[7].y = tp.y;
1113 } else { /* up */
1114 points[0] = tp;
1115 points[1].x = uminx;
1116 points[1].y = tp.y;
1117 points[2].x = uminx;
1118 points[2].y = maxy;
1119 points[3].x = umaxx;
1120 points[3].y = maxy;
1121 points[4].x = umaxx;
1122 points[4].y = hp.y;
1123 points[5].x = hp.x;
1124 points[5].y = hp.y;
1125 points[6].x = hp.x;
1126 points[6].y = maxy + LBL_SPACE;
1127 points[7].x = tp.x;
1128 points[7].y = maxy + LBL_SPACE;
1129 maxy += +LBL_SPACE;
1130 }
1131 poly.pn = 8;
1132 poly.ps = (Ppoint_t *)points;
1133 size_t pn;
1134 pointf *ps = simpleSplineRoute(tp, hp, poly, &pn, et == EDGETYPE_PLINE);
1135 if (ps == NULL || pn == 0) {
1136 free(ps);
1137 free(earray);
1138 return;
1139 }
1140 clip_and_install(e, aghead(e), ps, pn, &sinfo);
1141 free(ps);
1142 }
1143
1144 free(earray);
1145}
1146
1147static void makeSimpleFlat(node_t *tn, node_t *hn, edge_t **edges, unsigned ind,
1148 unsigned cnt, int et) {
1149 edge_t *e = edges[ind];
1150 pointf points[10], tp, hp;
1151 double stepy, dy;
1152
1153 tp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
1154 hp = add_pointf(ND_coord(hn), ED_head_port(e).p);
1155
1156 stepy = cnt > 1 ? ND_ht(tn) / (double)(cnt - 1) : 0.;
1157 dy = tp.y - (cnt > 1 ? ND_ht(tn) / 2. : 0.);
1158
1159 for (unsigned i = 0; i < cnt; i++) {
1160 e = edges[ind + i];
1161 size_t pointn = 0;
1162 if (et == EDGETYPE_SPLINE || et == EDGETYPE_LINE) {
1163 points[pointn++] = tp;
1164 points[pointn++] = (pointf){(2 * tp.x + hp.x) / 3, dy};
1165 points[pointn++] = (pointf){(2 * hp.x + tp.x) / 3, dy};
1166 points[pointn++] = hp;
1167 } else { /* EDGETYPE_PLINE */
1168 points[pointn++] = tp;
1169 points[pointn++] = tp;
1170 points[pointn++] = (pointf){(2 * tp.x + hp.x) / 3, dy};
1171 points[pointn++] = (pointf){(2 * tp.x + hp.x) / 3, dy};
1172 points[pointn++] = (pointf){(2 * tp.x + hp.x) / 3, dy};
1173 points[pointn++] = (pointf){(2 * hp.x + tp.x) / 3, dy};
1174 points[pointn++] = (pointf){(2 * hp.x + tp.x) / 3, dy};
1175 points[pointn++] = (pointf){(2 * hp.x + tp.x) / 3, dy};
1176 points[pointn++] = hp;
1177 points[pointn++] = hp;
1178 }
1179 dy += stepy;
1180 clip_and_install(e, aghead(e), points, pointn, &sinfo);
1181 }
1182}
1183
1184/* make_flat_adj_edges:
1185 * In the simple case, with no labels or ports, this creates a simple
1186 * spindle of splines.
1187 * If there are only labels, cobble something together.
1188 * Otherwise, we run dot recursively on the 2 nodes and the edges,
1189 * essentially using rankdir=LR, to get the needed spline info.
1190 * This is probably to cute and fragile, and should be rewritten in a
1191 * more straightforward and laborious fashion.
1192 *
1193 * @return 0 on success
1194 */
1195static int make_flat_adj_edges(graph_t *g, edge_t **edges, unsigned ind,
1196 unsigned cnt, edge_t *e0, int et) {
1197 node_t *n;
1198 node_t *tn, *hn;
1199 edge_t *e;
1200 graph_t *auxg;
1201 graph_t *subg;
1202 node_t *auxt, *auxh;
1203 edge_t *auxe;
1204 double midx, midy, leftx, rightx;
1205 pointf del;
1206 edge_t *hvye = NULL;
1207 static atomic_flag warned;
1208
1209 tn = agtail(e0), hn = aghead(e0);
1210 if (shapeOf(tn) == SH_RECORD || shapeOf(hn) == SH_RECORD) {
1211 if (!atomic_flag_test_and_set(&warned)) {
1212 agwarningf("flat edge between adjacent nodes one of which has a record "
1213 "shape - replace records with HTML-like labels\n");
1214 agerr(AGPREV, " Edge %s %s %s\n", agnameof(tn),
1215 agisdirected(g) ? "->" : "--", agnameof(hn));
1216 }
1217 return 0;
1218 }
1219 unsigned labels = 0;
1220 bool ports = false;
1221 for (unsigned i = 0; i < cnt; i++) {
1222 e = edges[ind + i];
1223 if (ED_label(e))
1224 labels++;
1225 if (ED_tail_port(e).defined || ED_head_port(e).defined)
1226 ports = true;
1227 }
1228
1229 if (!ports) {
1230 /* flat edges without ports and labels can go straight left to right */
1231 if (labels == 0) {
1232 makeSimpleFlat(tn, hn, edges, ind, cnt, et);
1233 }
1234 /* flat edges without ports but with labels take more work */
1235 else {
1236 makeSimpleFlatLabels(tn, hn, edges, ind, cnt, et, labels);
1237 }
1238 return 0;
1239 }
1240
1241 attr_state_t attrs = {0};
1242 auxg = cloneGraph(g, &attrs);
1243 subg = agsubg(auxg, "xxx", 1);
1244 agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), true);
1245 agset(subg, "rank", "source");
1246 rightx = ND_coord(hn).x;
1247 leftx = ND_coord(tn).x;
1248 if (GD_flip(g)) {
1249 SWAP(&tn, &hn);
1250 }
1251 auxt = cloneNode(subg, tn);
1252 auxh = cloneNode(auxg, hn);
1253 for (unsigned i = 0; i < cnt; i++) {
1254 e = edges[ind + i];
1255 for (; ED_edge_type(e) != NORMAL; e = ED_to_orig(e))
1256 ;
1257 if (agtail(e) == tn)
1258 auxe = cloneEdge(auxg, auxt, auxh, e);
1259 else
1260 auxe = cloneEdge(auxg, auxh, auxt, e);
1261 ED_alg(e) = auxe;
1262 if (!hvye && !ED_tail_port(e).defined && !ED_head_port(e).defined) {
1263 hvye = auxe;
1264 ED_alg(hvye) = e;
1265 }
1266 }
1267 if (!hvye) {
1268 hvye = agedge(auxg, auxt, auxh, NULL, 1);
1269 }
1270 agxset(hvye, E_weight, "10000");
1271 GD_gvc(auxg) = GD_gvc(g);
1272 GD_dotroot(auxg) = auxg;
1273 setEdgeType(auxg, et);
1274 dot_init_node_edge(auxg);
1275
1276 dot_rank(auxg);
1277 const int r = dot_mincross(auxg);
1278 if (r != 0) {
1279 return r;
1280 }
1281 dot_position(auxg);
1282
1283 /* reposition */
1284 midx = (ND_coord(tn).x - ND_rw(tn) + ND_coord(hn).x + ND_lw(hn)) / 2;
1285 midy = (ND_coord(auxt).x + ND_coord(auxh).x) / 2;
1286 for (n = GD_nlist(auxg); n; n = ND_next(n)) {
1287 if (n == auxt) {
1288 ND_coord(n).y = rightx;
1289 ND_coord(n).x = midy;
1290 } else if (n == auxh) {
1291 ND_coord(n).y = leftx;
1292 ND_coord(n).x = midy;
1293 } else
1294 ND_coord(n).y = midx;
1295 }
1296 dot_sameports(auxg);
1297 const int rc = dot_splines_(auxg, 0);
1298 if (rc != 0) {
1299 return rc;
1300 }
1302
1303 /* copy splines */
1304 if (GD_flip(g)) {
1305 del.x = ND_coord(tn).x - ND_coord(auxt).y;
1306 del.y = ND_coord(tn).y + ND_coord(auxt).x;
1307 } else {
1308 del.x = ND_coord(tn).x - ND_coord(auxt).x;
1309 del.y = ND_coord(tn).y - ND_coord(auxt).y;
1310 }
1311 for (unsigned i = 0; i < cnt; i++) {
1312 bezier *auxbz;
1313 bezier *bz;
1314
1315 e = edges[ind + i];
1316 for (; ED_edge_type(e) != NORMAL; e = ED_to_orig(e))
1317 ;
1318 auxe = ED_alg(e);
1319 if ((auxe == hvye) & !ED_alg(auxe))
1320 continue; /* pseudo-edge */
1321 auxbz = ED_spl(auxe)->list;
1322 bz = new_spline(e, auxbz->size);
1323 bz->sflag = auxbz->sflag;
1324 bz->sp = transformf(auxbz->sp, del, GD_flip(g));
1325 bz->eflag = auxbz->eflag;
1326 bz->ep = transformf(auxbz->ep, del, GD_flip(g));
1327 for (size_t j = 0; j < auxbz->size;) {
1328 pointf cp[4];
1329 cp[0] = bz->list[j] = transformf(auxbz->list[j], del, GD_flip(g));
1330 j++;
1331 if (j >= auxbz->size)
1332 break;
1333 cp[1] = bz->list[j] = transformf(auxbz->list[j], del, GD_flip(g));
1334 j++;
1335 cp[2] = bz->list[j] = transformf(auxbz->list[j], del, GD_flip(g));
1336 j++;
1337 cp[3] = transformf(auxbz->list[j], del, GD_flip(g));
1338 update_bb_bz(&GD_bb(g), cp);
1339 }
1340 if (ED_label(e)) {
1341 ED_label(e)->pos = transformf(ED_label(auxe)->pos, del, GD_flip(g));
1342 ED_label(e)->set = true;
1343 updateBB(g, ED_label(e));
1344 }
1345 }
1346
1347 cleanupCloneGraph(auxg, &attrs);
1348 return 0;
1349}
1350
1351static void makeFlatEnd(graph_t *g, spline_info_t *sp, path *P, node_t *n,
1352 edge_t *e, pathend_t *endp, bool isBegin) {
1353 boxf b;
1354
1355 b = endp->nb = maximal_bbox(g, sp, n, NULL, e);
1356 endp->sidemask = TOP;
1357 if (isBegin)
1358 beginpath(P, e, FLATEDGE, endp, false);
1359 else
1360 endpath(P, e, FLATEDGE, endp, false);
1361 b.UR.y = endp->boxes[endp->boxn - 1].UR.y;
1362 b.LL.y = endp->boxes[endp->boxn - 1].LL.y;
1363 b = makeregularend(b, TOP, ND_coord(n).y + GD_rank(g)[ND_rank(n)].ht2);
1364 if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
1365 endp->boxes[endp->boxn++] = b;
1366}
1367
1369 edge_t *e, pathend_t *endp, bool isBegin) {
1370 boxf b;
1371
1372 b = endp->nb = maximal_bbox(g, sp, n, NULL, e);
1373 endp->sidemask = BOTTOM;
1374 if (isBegin)
1375 beginpath(P, e, FLATEDGE, endp, false);
1376 else
1377 endpath(P, e, FLATEDGE, endp, false);
1378 b.UR.y = endp->boxes[endp->boxn - 1].UR.y;
1379 b.LL.y = endp->boxes[endp->boxn - 1].LL.y;
1380 b = makeregularend(b, BOTTOM, ND_coord(n).y - GD_rank(g)[ND_rank(n)].ht2);
1381 if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
1382 endp->boxes[endp->boxn++] = b;
1383}
1384
1386 edge_t *e, int et) {
1387 node_t *tn, *hn, *ln;
1388 pointf *ps;
1389 bool ps_needs_free = false;
1390 pathend_t tend, hend;
1391 boxf lb;
1392 int i;
1393 edge_t *f;
1394 pointf points[7];
1395
1396 tn = agtail(e);
1397 hn = aghead(e);
1398
1399 for (f = ED_to_virt(e); ED_to_virt(f); f = ED_to_virt(f))
1400 ;
1401 ln = agtail(f);
1402 ED_label(e)->pos = ND_coord(ln);
1403 ED_label(e)->set = true;
1404
1405 size_t pn;
1406 if (et == EDGETYPE_LINE) {
1407 pointf startp, endp, lp;
1408
1409 startp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
1410 endp = add_pointf(ND_coord(hn), ED_head_port(e).p);
1411
1412 lp = ED_label(e)->pos;
1413 lp.y -= ED_label(e)->dimen.y / 2.0;
1414 points[1] = points[0] = startp;
1415 points[2] = points[3] = points[4] = lp;
1416 points[5] = points[6] = endp;
1417 ps = points;
1418 pn = 7;
1419 } else {
1420 lb.LL.x = ND_coord(ln).x - ND_lw(ln);
1421 lb.UR.x = ND_coord(ln).x + ND_rw(ln);
1422 lb.UR.y = ND_coord(ln).y + ND_ht(ln) / 2;
1423 double ydelta = ND_coord(ln).y - GD_rank(g)[ND_rank(tn)].ht1 -
1424 ND_coord(tn).y + GD_rank(g)[ND_rank(tn)].ht2;
1425 ydelta /= 6;
1426 lb.LL.y = lb.UR.y - MAX(5, ydelta);
1427
1428 makeFlatEnd(g, sp, P, tn, e, &tend, true);
1429 makeFlatEnd(g, sp, P, hn, e, &hend, false);
1430
1431 boxf boxes[] = {
1432 {
1433 .LL =
1434 {
1435 .x = tend.boxes[tend.boxn - 1].LL.x,
1436 .y = tend.boxes[tend.boxn - 1].UR.y,
1437 },
1438 .UR = lb.LL,
1439 },
1440 {
1441 .LL =
1442 {
1443 .x = tend.boxes[tend.boxn - 1].LL.x,
1444 .y = lb.LL.y,
1445 },
1446 .UR =
1447 {
1448 .x = hend.boxes[hend.boxn - 1].UR.x,
1449 .y = lb.UR.y,
1450 },
1451 },
1452 {
1453 .LL =
1454 {
1455 .x = lb.UR.x,
1456 .y = hend.boxes[hend.boxn - 1].UR.y,
1457 },
1458 .UR =
1459 {
1460 .x = hend.boxes[hend.boxn - 1].UR.x,
1461 .y = lb.LL.y,
1462 },
1463 },
1464 };
1465 const size_t boxn = sizeof(boxes) / sizeof(boxes[0]);
1466
1467 for (i = 0; i < tend.boxn; i++)
1468 add_box(P, tend.boxes[i]);
1469 for (size_t j = 0; j < boxn; j++)
1470 add_box(P, boxes[j]);
1471 for (i = hend.boxn - 1; i >= 0; i--)
1472 add_box(P, hend.boxes[i]);
1473
1474 ps_needs_free = true;
1475 if (et == EDGETYPE_SPLINE)
1476 ps = routesplines(P, &pn);
1477 else
1478 ps = routepolylines(P, &pn);
1479 if (pn == 0) {
1480 free(ps);
1481 return;
1482 }
1483 }
1484 clip_and_install(e, aghead(e), ps, pn, &sinfo);
1485 if (ps_needs_free)
1486 free(ps);
1487}
1488
1490 edge_t **edges, unsigned ind, unsigned cnt,
1491 edge_t *e, bool use_splines) {
1492 node_t *tn, *hn;
1493 int j, r;
1494 double stepx, stepy, vspace;
1495 rank_t *nextr;
1496 pathend_t tend, hend;
1497
1498 tn = agtail(e);
1499 hn = aghead(e);
1500 r = ND_rank(tn);
1501 if (r < GD_maxrank(g)) {
1502 nextr = GD_rank(g) + (r + 1);
1503 vspace = ND_coord(tn).y - GD_rank(g)[r].pht1 -
1504 (ND_coord(nextr->v[0]).y + nextr->pht2);
1505 } else {
1506 vspace = GD_ranksep(g);
1507 }
1508 stepx = sp->Multisep / (cnt + 1);
1509 stepy = vspace / (cnt + 1);
1510
1511 makeBottomFlatEnd(g, sp, P, tn, e, &tend, true);
1512 makeBottomFlatEnd(g, sp, P, hn, e, &hend, false);
1513
1514 for (unsigned i = 0; i < cnt; i++) {
1515 boxf b;
1516 e = edges[ind + i];
1517 size_t boxn = 0;
1518
1519 boxf boxes[3];
1520
1521 b = tend.boxes[tend.boxn - 1];
1522 boxes[boxn].LL.x = b.LL.x;
1523 boxes[boxn].UR.y = b.LL.y;
1524 boxes[boxn].UR.x = b.UR.x + (i + 1) * stepx;
1525 boxes[boxn].LL.y = b.LL.y - (i + 1) * stepy;
1526 boxn++;
1527 boxes[boxn].LL.x = tend.boxes[tend.boxn - 1].LL.x;
1528 boxes[boxn].UR.y = boxes[boxn - 1].LL.y;
1529 boxes[boxn].UR.x = hend.boxes[hend.boxn - 1].UR.x;
1530 boxes[boxn].LL.y = boxes[boxn].UR.y - stepy;
1531 boxn++;
1532 b = hend.boxes[hend.boxn - 1];
1533 boxes[boxn].UR.x = b.UR.x;
1534 boxes[boxn].UR.y = b.LL.y;
1535 boxes[boxn].LL.x = b.LL.x - (i + 1) * stepx;
1536 boxes[boxn].LL.y = boxes[boxn - 1].UR.y;
1537 boxn++;
1538 assert(boxn == sizeof(boxes) / sizeof(boxes[0]));
1539
1540 for (j = 0; j < tend.boxn; j++)
1541 add_box(P, tend.boxes[j]);
1542 for (size_t k = 0; k < boxn; k++)
1543 add_box(P, boxes[k]);
1544 for (j = hend.boxn - 1; j >= 0; j--)
1545 add_box(P, hend.boxes[j]);
1546
1547 pointf *ps = NULL;
1548 size_t pn = 0;
1549 if (use_splines)
1550 ps = routesplines(P, &pn);
1551 else
1552 ps = routepolylines(P, &pn);
1553 if (pn == 0) {
1554 free(ps);
1555 return;
1556 }
1557 clip_and_install(e, aghead(e), ps, pn, &sinfo);
1558 free(ps);
1559 P->nbox = 0;
1560 }
1561}
1562
1563/* make_flat_edge:
1564 * Construct flat edges edges[ind...ind+cnt-1]
1565 * There are 4 main cases:
1566 * - all edges between a and b where a and b are adjacent
1567 * - one labeled edge
1568 * - all non-labeled edges with identical ports between non-adjacent a and b
1569 * = connecting bottom to bottom/left/right - route along bottom
1570 * = the rest - route along top
1571 *
1572 * @return 0 on success
1573 */
1575 edge_t **edges, unsigned ind, unsigned cnt, int et) {
1576 node_t *tn, *hn;
1577 Agedgeinfo_t fwdedgei;
1578 Agedgepair_t fwdedge;
1579 edge_t *e;
1580 int j, r;
1581 double stepx, stepy, vspace;
1582 int tside, hside;
1583 pathend_t tend, hend;
1584
1585 fwdedge.out.base.data = (Agrec_t *)&fwdedgei;
1586
1587 /* Get sample edge; normalize to go from left to right */
1588 e = edges[ind];
1589 bool isAdjacent = ED_adjacent(e) != 0;
1590 if (ED_tree_index(e) & BWDEDGE) {
1591 MAKEFWDEDGE(&fwdedge.out, e);
1592 e = &fwdedge.out;
1593 }
1594 for (unsigned i = 1; i < cnt; i++) {
1595 if (ED_adjacent(edges[ind + i])) {
1596 isAdjacent = true;
1597 break;
1598 }
1599 }
1600 /* The lead edge edges[ind] might not have been marked earlier as adjacent,
1601 * so check them all.
1602 */
1603 if (isAdjacent) {
1604 return make_flat_adj_edges(g, edges, ind, cnt, e, et);
1605 }
1606 if (ED_label(e)) { /* edges with labels aren't multi-edges */
1607 make_flat_labeled_edge(g, sp, P, e, et);
1608 return 0;
1609 }
1610
1611 if (et == EDGETYPE_LINE) {
1612 makeSimpleFlat(agtail(e), aghead(e), edges, ind, cnt, et);
1613 return 0;
1614 }
1615
1616 tside = ED_tail_port(e).side;
1617 hside = ED_head_port(e).side;
1618 if ((tside == BOTTOM && hside != TOP) || (hside == BOTTOM && tside != TOP)) {
1619 make_flat_bottom_edges(g, sp, P, edges, ind, cnt, e, et == EDGETYPE_SPLINE);
1620 return 0;
1621 }
1622
1623 tn = agtail(e);
1624 hn = aghead(e);
1625 r = ND_rank(tn);
1626 if (r > 0) {
1627 rank_t *prevr;
1628 if (GD_has_labels(g->root) & EDGE_LABEL)
1629 prevr = GD_rank(g) + (r - 2);
1630 else
1631 prevr = GD_rank(g) + (r - 1);
1632 vspace = ND_coord(prevr->v[0]).y - prevr->ht1 - ND_coord(tn).y -
1633 GD_rank(g)[r].ht2;
1634 } else {
1635 vspace = GD_ranksep(g);
1636 }
1637 stepx = sp->Multisep / (cnt + 1);
1638 stepy = vspace / (cnt + 1);
1639
1640 makeFlatEnd(g, sp, P, tn, e, &tend, true);
1641 makeFlatEnd(g, sp, P, hn, e, &hend, false);
1642
1643 for (unsigned i = 0; i < cnt; i++) {
1644 boxf b;
1645 e = edges[ind + i];
1646 size_t boxn = 0;
1647
1648 boxf boxes[3];
1649
1650 b = tend.boxes[tend.boxn - 1];
1651 boxes[boxn].LL.x = b.LL.x;
1652 boxes[boxn].LL.y = b.UR.y;
1653 boxes[boxn].UR.x = b.UR.x + (i + 1) * stepx;
1654 boxes[boxn].UR.y = b.UR.y + (i + 1) * stepy;
1655 boxn++;
1656 boxes[boxn].LL.x = tend.boxes[tend.boxn - 1].LL.x;
1657 boxes[boxn].LL.y = boxes[boxn - 1].UR.y;
1658 boxes[boxn].UR.x = hend.boxes[hend.boxn - 1].UR.x;
1659 boxes[boxn].UR.y = boxes[boxn].LL.y + stepy;
1660 boxn++;
1661 b = hend.boxes[hend.boxn - 1];
1662 boxes[boxn].UR.x = b.UR.x;
1663 boxes[boxn].LL.y = b.UR.y;
1664 boxes[boxn].LL.x = b.LL.x - (i + 1) * stepx;
1665 boxes[boxn].UR.y = boxes[boxn - 1].LL.y;
1666 boxn++;
1667 assert(boxn == sizeof(boxes) / sizeof(boxes[0]));
1668
1669 for (j = 0; j < tend.boxn; j++)
1670 add_box(P, tend.boxes[j]);
1671 for (size_t k = 0; k < boxn; k++)
1672 add_box(P, boxes[k]);
1673 for (j = hend.boxn - 1; j >= 0; j--)
1674 add_box(P, hend.boxes[j]);
1675
1676 pointf *ps = NULL;
1677 size_t pn = 0;
1678 if (et == EDGETYPE_SPLINE)
1679 ps = routesplines(P, &pn);
1680 else
1681 ps = routepolylines(P, &pn);
1682 if (pn == 0) {
1683 free(ps);
1684 return 0;
1685 }
1686 clip_and_install(e, aghead(e), ps, pn, &sinfo);
1687 free(ps);
1688 P->nbox = 0;
1689 }
1690 return 0;
1691}
1692
1694static bool leftOf(pointf p1, pointf p2, pointf p3) {
1695 return (p1.y - p2.y) * (p3.x - p2.x) - (p3.y - p2.y) * (p1.x - p2.x) > 0;
1696}
1697
1698/* makeLineEdge:
1699 * Create an edge as line segment. We guarantee that the points
1700 * are always drawn downwards. This means that for flipped edges,
1701 * we draw from the head to the tail. The routine returns the
1702 * end node of the edge in *hp. The points are stored in the
1703 * given array of points, and the number of points is returned.
1704 *
1705 * If the edge has a label, the edge is draw as two segments, with
1706 * the bend near the label.
1707 *
1708 * If the endpoints are on adjacent ranks, revert to usual code by
1709 * returning 0.
1710 * This is done because the usual code handles the interaction of
1711 * multiple edges better.
1712 */
1713static int makeLineEdge(graph_t *g, edge_t *fe, points_t *points, node_t **hp) {
1714 int delr, pn;
1715 node_t *hn;
1716 node_t *tn;
1717 edge_t *e = fe;
1718 pointf startp, endp, lp;
1719 pointf dimen;
1720 double width, height;
1721
1722 while (ED_edge_type(e) != NORMAL)
1723 e = ED_to_orig(e);
1724 hn = aghead(e);
1725 tn = agtail(e);
1726 delr = abs(ND_rank(hn) - ND_rank(tn));
1727 if (delr == 1 || (delr == 2 && (GD_has_labels(g->root) & EDGE_LABEL)))
1728 return 0;
1729 if (agtail(fe) == agtail(e)) {
1730 *hp = hn;
1731 startp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
1732 endp = add_pointf(ND_coord(hn), ED_head_port(e).p);
1733 } else {
1734 *hp = tn;
1735 startp = add_pointf(ND_coord(hn), ED_head_port(e).p);
1736 endp = add_pointf(ND_coord(tn), ED_tail_port(e).p);
1737 }
1738
1739 if (ED_label(e)) {
1740 dimen = ED_label(e)->dimen;
1741 if (GD_flip(agraphof(hn))) {
1742 width = dimen.y;
1743 height = dimen.x;
1744 } else {
1745 width = dimen.x;
1746 height = dimen.y;
1747 }
1748
1749 lp = ED_label(e)->pos;
1750 if (leftOf(endp, startp, lp)) {
1751 lp.x += width / 2.0;
1752 lp.y -= height / 2.0;
1753 } else {
1754 lp.x -= width / 2.0;
1755 lp.y += height / 2.0;
1756 }
1757
1758 points_append(points, startp);
1759 points_append(points, startp);
1760 points_append(points, lp);
1761 points_append(points, lp);
1762 points_append(points, lp);
1763 points_append(points, endp);
1764 points_append(points, endp);
1765 pn = 7;
1766 } else {
1767 points_append(points, startp);
1768 points_append(points, startp);
1769 points_append(points, endp);
1770 points_append(points, endp);
1771 pn = 4;
1772 }
1773
1774 return pn;
1775}
1776
1778 edge_t **edges, unsigned ind, unsigned cnt,
1779 int et) {
1780 node_t *tn, *hn;
1781 Agedgeinfo_t fwdedgeai, fwdedgebi, fwdedgei;
1782 Agedgepair_t fwdedgea, fwdedgeb, fwdedge;
1783 edge_t *e, *fe, *le, *segfirst;
1784 pathend_t tend, hend;
1785 boxf b;
1786 int sl, si;
1787 points_t pointfs = {0};
1788 points_t pointfs2 = {0};
1789
1790 fwdedgea.out.base.data = (Agrec_t *)&fwdedgeai;
1791 fwdedgeb.out.base.data = (Agrec_t *)&fwdedgebi;
1792 fwdedge.out.base.data = (Agrec_t *)&fwdedgei;
1793
1794 sl = 0;
1795 e = edges[ind];
1796 bool hackflag = false;
1797 if (abs(ND_rank(agtail(e)) - ND_rank(aghead(e))) > 1) {
1798 fwdedgeai = *(Agedgeinfo_t *)e->base.data;
1799 fwdedgea.out = *e;
1800 fwdedgea.in = *AGOUT2IN(e);
1801 fwdedgea.out.base.data = (Agrec_t *)&fwdedgeai;
1802 if (ED_tree_index(e) & BWDEDGE) {
1803 MAKEFWDEDGE(&fwdedgeb.out, e);
1804 agtail(&fwdedgea.out) = aghead(e);
1805 ED_tail_port(&fwdedgea.out) = ED_head_port(e);
1806 } else {
1807 fwdedgebi = *(Agedgeinfo_t *)e->base.data;
1808 fwdedgeb.out = *e;
1809 fwdedgeb.out.base.data = (Agrec_t *)&fwdedgebi;
1810 agtail(&fwdedgea.out) = agtail(e);
1811 fwdedgeb.in = *AGOUT2IN(e);
1812 }
1813 le = getmainedge(e);
1814 while (ED_to_virt(le))
1815 le = ED_to_virt(le);
1816 aghead(&fwdedgea.out) = aghead(le);
1817 ED_head_port(&fwdedgea.out).defined = false;
1818 ED_edge_type(&fwdedgea.out) = VIRTUAL;
1819 ED_head_port(&fwdedgea.out).p.x = ED_head_port(&fwdedgea.out).p.y = 0;
1820 ED_to_orig(&fwdedgea.out) = e;
1821 e = &fwdedgea.out;
1822 hackflag = true;
1823 } else {
1824 if (ED_tree_index(e) & BWDEDGE) {
1825 MAKEFWDEDGE(&fwdedgea.out, e);
1826 e = &fwdedgea.out;
1827 }
1828 }
1829 fe = e;
1830
1831 /* compute the spline points for the edge */
1832
1833 if (et == EDGETYPE_LINE && makeLineEdge(g, fe, &pointfs, &hn)) {
1834 } else {
1835 bool is_spline = et == EDGETYPE_SPLINE;
1836 boxes_t boxes = {0};
1837 segfirst = e;
1838 tn = agtail(e);
1839 hn = aghead(e);
1840 b = tend.nb = maximal_bbox(g, sp, tn, NULL, e);
1841 beginpath(P, e, REGULAREDGE, &tend, spline_merge(tn));
1842 b.UR.y = tend.boxes[tend.boxn - 1].UR.y;
1843 b.LL.y = tend.boxes[tend.boxn - 1].LL.y;
1844 b = makeregularend(b, BOTTOM, ND_coord(tn).y - GD_rank(g)[ND_rank(tn)].ht1);
1845 if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
1846 tend.boxes[tend.boxn++] = b;
1847 bool smode = false;
1848 si = -1;
1849 while (ND_node_type(hn) == VIRTUAL && !sinfo.splineMerge(hn)) {
1850 boxes_append(&boxes, rank_box(sp, g, ND_rank(tn)));
1851 if (!smode && ((sl = straight_len(hn)) >=
1852 ((GD_has_labels(g->root) & EDGE_LABEL) ? 4 + 1 : 2 + 1))) {
1853 smode = true;
1854 si = 1, sl -= 2;
1855 }
1856 if (!smode || si > 0) {
1857 si--;
1858 boxes_append(&boxes, maximal_bbox(g, sp, hn, e, ND_out(hn).list[0]));
1859 e = ND_out(hn).list[0];
1860 tn = agtail(e);
1861 hn = aghead(e);
1862 continue;
1863 }
1864 hend.nb = maximal_bbox(g, sp, hn, e, ND_out(hn).list[0]);
1865 endpath(P, e, REGULAREDGE, &hend, spline_merge(aghead(e)));
1866 b = makeregularend(hend.boxes[hend.boxn - 1], TOP,
1867 ND_coord(hn).y + GD_rank(g)[ND_rank(hn)].ht2);
1868 if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
1869 hend.boxes[hend.boxn++] = b;
1870 P->end.theta = M_PI / 2, P->end.constrained = true;
1871 completeregularpath(P, segfirst, e, &tend, &hend, &boxes);
1872 pointf *ps = NULL;
1873 size_t pn = 0;
1874 if (is_spline)
1875 ps = routesplines(P, &pn);
1876 else {
1877 ps = routepolylines(P, &pn);
1878 if (et == EDGETYPE_LINE && pn > 4) {
1879 ps[1] = ps[0];
1880 ps[3] = ps[2] = ps[pn - 1];
1881 pn = 4;
1882 }
1883 }
1884 if (pn == 0) {
1885 free(ps);
1886 boxes_free(&boxes);
1887 points_free(&pointfs);
1888 points_free(&pointfs2);
1889 return;
1890 }
1891
1892 for (size_t i = 0; i < pn; i++) {
1893 points_append(&pointfs, ps[i]);
1894 }
1895 free(ps);
1896 e = straight_path(ND_out(hn).list[0], sl, &pointfs);
1897 recover_slack(segfirst, P);
1898 segfirst = e;
1899 tn = agtail(e);
1900 hn = aghead(e);
1901 boxes_clear(&boxes);
1902 tend.nb = maximal_bbox(g, sp, tn, ND_in(tn).list[0], e);
1903 beginpath(P, e, REGULAREDGE, &tend, spline_merge(tn));
1904 b = makeregularend(tend.boxes[tend.boxn - 1], BOTTOM,
1905 ND_coord(tn).y - GD_rank(g)[ND_rank(tn)].ht1);
1906 if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
1907 tend.boxes[tend.boxn++] = b;
1908 P->start.theta = -M_PI / 2, P->start.constrained = true;
1909 smode = false;
1910 }
1911 boxes_append(&boxes, rank_box(sp, g, ND_rank(tn)));
1912 b = hend.nb = maximal_bbox(g, sp, hn, e, NULL);
1913 endpath(P, hackflag ? &fwdedgeb.out : e, REGULAREDGE, &hend,
1914 spline_merge(aghead(e)));
1915 b.UR.y = hend.boxes[hend.boxn - 1].UR.y;
1916 b.LL.y = hend.boxes[hend.boxn - 1].LL.y;
1917 b = makeregularend(b, TOP, ND_coord(hn).y + GD_rank(g)[ND_rank(hn)].ht2);
1918 if (b.LL.x < b.UR.x && b.LL.y < b.UR.y)
1919 hend.boxes[hend.boxn++] = b;
1920 completeregularpath(P, segfirst, e, &tend, &hend, &boxes);
1921 boxes_free(&boxes);
1922 pointf *ps = NULL;
1923 size_t pn = 0;
1924 if (is_spline)
1925 ps = routesplines(P, &pn);
1926 else
1927 ps = routepolylines(P, &pn);
1928 if (et == EDGETYPE_LINE && pn > 4) {
1929 /* Here we have used the polyline case to handle
1930 * an edge between two nodes on adjacent ranks. If the
1931 * results really is a polyline, straighten it.
1932 */
1933 ps[1] = ps[0];
1934 ps[3] = ps[2] = ps[pn - 1];
1935 pn = 4;
1936 }
1937 if (pn == 0) {
1938 free(ps);
1939 points_free(&pointfs);
1940 points_free(&pointfs2);
1941 return;
1942 }
1943 for (size_t i = 0; i < pn; i++) {
1944 points_append(&pointfs, ps[i]);
1945 }
1946 free(ps);
1947 recover_slack(segfirst, P);
1948 hn = hackflag ? aghead(&fwdedgeb.out) : aghead(e);
1949 }
1950
1951 /* make copies of the spline points, one per multi-edge */
1952
1953 if (cnt == 1) {
1954 points_sync(&pointfs);
1955 clip_and_install(fe, hn, points_front(&pointfs), points_size(&pointfs),
1956 &sinfo);
1957 points_free(&pointfs);
1958 points_free(&pointfs2);
1959 return;
1960 }
1961 const double dx = sp->Multisep * (cnt - 1) / 2;
1962 for (size_t k = 1; k + 1 < points_size(&pointfs); k++)
1963 points_at(&pointfs, k)->x -= dx;
1964
1965 for (size_t k = 0; k < points_size(&pointfs); k++)
1966 points_append(&pointfs2, points_get(&pointfs, k));
1967 points_sync(&pointfs2);
1968 clip_and_install(fe, hn, points_front(&pointfs2), points_size(&pointfs2),
1969 &sinfo);
1970 for (unsigned j = 1; j < cnt; j++) {
1971 e = edges[ind + j];
1972 if (ED_tree_index(e) & BWDEDGE) {
1973 MAKEFWDEDGE(&fwdedge.out, e);
1974 e = &fwdedge.out;
1975 }
1976 for (size_t k = 1; k + 1 < points_size(&pointfs); k++)
1977 points_at(&pointfs, k)->x += sp->Multisep;
1978 points_clear(&pointfs2);
1979 for (size_t k = 0; k < points_size(&pointfs); k++)
1980 points_append(&pointfs2, points_get(&pointfs, k));
1981 points_sync(&pointfs2);
1982 clip_and_install(e, aghead(e), points_front(&pointfs2),
1983 points_size(&pointfs2), &sinfo);
1984 }
1985 points_free(&pointfs);
1986 points_free(&pointfs2);
1987}
1988
1989/* regular edges */
1990
1991static void completeregularpath(path *P, edge_t *first, edge_t *last,
1992 pathend_t *tendp, pathend_t *hendp,
1993 const boxes_t *boxes) {
1994 edge_t *uleft, *uright, *lleft, *lright;
1995
1996 uleft = uright = NULL;
1997 uleft = top_bound(first, -1), uright = top_bound(first, 1);
1998 if (uleft) {
1999 if (getsplinepoints(uleft) == NULL)
2000 return;
2001 }
2002 if (uright) {
2003 if (getsplinepoints(uright) == NULL)
2004 return;
2005 }
2006 lleft = lright = NULL;
2007 lleft = bot_bound(last, -1), lright = bot_bound(last, 1);
2008 if (lleft) {
2009 if (getsplinepoints(lleft) == NULL)
2010 return;
2011 }
2012 if (lright) {
2013 if (getsplinepoints(lright) == NULL)
2014 return;
2015 }
2016 for (int i = 0; i < tendp->boxn; i++)
2017 add_box(P, tendp->boxes[i]);
2018 const size_t fb = P->nbox + 1;
2019 const size_t lb = fb + boxes_size(boxes) - 3;
2020 for (size_t i = 0; i < boxes_size(boxes); i++)
2021 add_box(P, boxes_get(boxes, i));
2022 for (int i = hendp->boxn - 1; i >= 0; i--)
2023 add_box(P, hendp->boxes[i]);
2024 adjustregularpath(P, fb, lb);
2025}
2026
2027/* makeregularend:
2028 * Add box to fill between node and interrank space. Needed because
2029 * nodes in a given rank can differ in height.
2030 * for now, regular edges always go from top to bottom
2031 */
2032static boxf makeregularend(boxf b, int side, double y) {
2033 assert(side == BOTTOM || side == TOP);
2034 if (side == BOTTOM) {
2035 return (boxf){{b.LL.x, y}, {b.UR.x, b.LL.y}};
2036 }
2037 return (boxf){{b.LL.x, b.UR.y}, {b.UR.x, y}};
2038}
2039
2040/* adjustregularpath:
2041 * make sure the path is wide enough.
2042 * the % 2 was so that in rank boxes would only be grown if
2043 * they were == 0 while inter-rank boxes could be stretched to a min
2044 * width.
2045 * The list of boxes has three parts: tail boxes, path boxes, and head
2046 * boxes. (Note that because of back edges, the tail boxes might actually
2047 * belong to the head node, and vice versa.) fb is the index of the
2048 * first interrank path box and lb is the last interrank path box.
2049 * If fb > lb, there are none.
2050 *
2051 * The second for loop was added by ek long ago, and apparently is intended
2052 * to guarantee an overlap between adjacent boxes of at least MINW.
2053 * It doesn't do this.
2054 */
2055static void adjustregularpath(path *P, size_t fb, size_t lb) {
2056 boxf *bp1, *bp2;
2057
2058 for (size_t i = fb - 1; i < lb + 1; i++) {
2059 bp1 = &P->boxes[i];
2060 if ((i - fb) % 2 == 0) {
2061 if (bp1->LL.x >= bp1->UR.x) {
2062 double x = (bp1->LL.x + bp1->UR.x) / 2;
2063 bp1->LL.x = x - HALFMINW;
2064 bp1->UR.x = x + HALFMINW;
2065 }
2066 } else {
2067 if (bp1->LL.x + MINW > bp1->UR.x) {
2068 double x = (bp1->LL.x + bp1->UR.x) / 2;
2069 bp1->LL.x = x - HALFMINW;
2070 bp1->UR.x = x + HALFMINW;
2071 }
2072 }
2073 }
2074 for (size_t i = 0; i + 1 < P->nbox; i++) {
2075 bp1 = &P->boxes[i], bp2 = &P->boxes[i + 1];
2076 if (i >= fb && i <= lb && (i - fb) % 2 == 0) {
2077 if (bp1->LL.x + MINW > bp2->UR.x)
2078 bp2->UR.x = bp1->LL.x + MINW;
2079 if (bp1->UR.x - MINW < bp2->LL.x)
2080 bp2->LL.x = bp1->UR.x - MINW;
2081 } else if (i + 1 >= fb && i < lb && (i + 1 - fb) % 2 == 0) {
2082 if (bp1->LL.x + MINW > bp2->UR.x)
2083 bp1->LL.x = bp2->UR.x - MINW;
2084 if (bp1->UR.x - MINW < bp2->LL.x)
2085 bp1->UR.x = bp2->LL.x + MINW;
2086 }
2087 }
2088}
2089
2090static boxf rank_box(spline_info_t *sp, graph_t *g, int r) {
2091 boxf b;
2092 node_t *left0, *left1;
2093
2094 b = sp->Rank_box[r];
2095 if (b.LL.x == b.UR.x) {
2096 left0 = GD_rank(g)[r].v[0];
2097 left1 = GD_rank(g)[r + 1].v[0];
2098 b.LL.x = sp->LeftBound;
2099 b.LL.y = ND_coord(left1).y + GD_rank(g)[r + 1].ht2;
2100 b.UR.x = sp->RightBound;
2101 b.UR.y = ND_coord(left0).y - GD_rank(g)[r].ht1;
2102 sp->Rank_box[r] = b;
2103 }
2104 return b;
2105}
2106
2107/* returns count of vertically aligned edges starting at n */
2108static int straight_len(node_t *n) {
2109 int cnt = 0;
2110 node_t *v;
2111
2112 v = n;
2113 while (1) {
2114 v = aghead(ND_out(v).list[0]);
2115 if (ND_node_type(v) != VIRTUAL)
2116 break;
2117 if (ND_out(v).size != 1 || ND_in(v).size != 1)
2118 break;
2119 if (ND_coord(v).x != ND_coord(n).x)
2120 break;
2121 cnt++;
2122 }
2123 return cnt;
2124}
2125
2126static edge_t *straight_path(edge_t *e, int cnt, points_t *plist) {
2127 edge_t *f = e;
2128
2129 while (cnt--)
2130 f = ND_out(aghead(f)).list[0];
2131 assert(!points_is_empty(plist));
2132 points_append(plist, points_get(plist, points_size(plist) - 1));
2133 points_append(plist, points_get(plist, points_size(plist) - 1));
2134
2135 return f;
2136}
2137
2138static void recover_slack(edge_t *e, path *p) {
2139 node_t *vn;
2140
2141 size_t b = 0; // skip first rank box
2142 for (vn = aghead(e); ND_node_type(vn) == VIRTUAL && !sinfo.splineMerge(vn);
2143 vn = aghead(ND_out(vn).list[0])) {
2144 while (b < p->nbox && p->boxes[b].LL.y > ND_coord(vn).y)
2145 b++;
2146 if (b >= p->nbox)
2147 break;
2148 if (p->boxes[b].UR.y < ND_coord(vn).y)
2149 continue;
2150 if (ND_label(vn))
2151 resize_vn(vn, p->boxes[b].LL.x, p->boxes[b].UR.x,
2152 p->boxes[b].UR.x + ND_rw(vn));
2153 else
2154 resize_vn(vn, p->boxes[b].LL.x, (p->boxes[b].LL.x + p->boxes[b].UR.x) / 2,
2155 p->boxes[b].UR.x);
2156 }
2157}
2158
2159static void resize_vn(node_t *vn, double lx, double cx, double rx) {
2160 ND_coord(vn).x = cx;
2161 ND_lw(vn) = cx - lx, ND_rw(vn) = rx - cx;
2162}
2163
2164/* side > 0 means right. side < 0 means left */
2165static edge_t *top_bound(edge_t *e, int side) {
2166 edge_t *f, *ans = NULL;
2167 int i;
2168
2169 for (i = 0; (f = ND_out(agtail(e)).list[i]); i++) {
2170 if (side * (ND_order(aghead(f)) - ND_order(aghead(e))) <= 0)
2171 continue;
2172 if (ED_spl(f) == NULL &&
2173 (ED_to_orig(f) == NULL || ED_spl(ED_to_orig(f)) == NULL))
2174 continue;
2175 if (ans == NULL || side * (ND_order(aghead(ans)) - ND_order(aghead(f))) > 0)
2176 ans = f;
2177 }
2178 return ans;
2179}
2180
2181static edge_t *bot_bound(edge_t *e, int side) {
2182 edge_t *f, *ans = NULL;
2183 int i;
2184
2185 for (i = 0; (f = ND_in(aghead(e)).list[i]); i++) {
2186 if (side * (ND_order(agtail(f)) - ND_order(agtail(e))) <= 0)
2187 continue;
2188 if (ED_spl(f) == NULL &&
2189 (ED_to_orig(f) == NULL || ED_spl(ED_to_orig(f)) == NULL))
2190 continue;
2191 if (ans == NULL || side * (ND_order(agtail(ans)) - ND_order(agtail(f))) > 0)
2192 ans = f;
2193 }
2194 return ans;
2195}
2196
2197/* common routines */
2198
2199static bool cl_vninside(graph_t *cl, node_t *n) {
2200 return BETWEEN(GD_bb(cl).LL.x, ND_coord(n).x, GD_bb(cl).UR.x) &&
2201 BETWEEN(GD_bb(cl).LL.y, ND_coord(n).y, GD_bb(cl).UR.y);
2202}
2203
2204/* All nodes belong to some cluster, which may be the root graph.
2205 * For the following, we only want a cluster if it is a real cluster
2206 * It is not clear this will handle all potential problems. It seems one
2207 * could have hcl and tcl contained in cl, which would also cause problems.
2208 */
2209#define REAL_CLUSTER(n) (ND_clust(n) == g ? NULL : ND_clust(n))
2210
2211/* returns the cluster of (adj) that interferes with n,
2212 */
2213static Agraph_t *cl_bound(graph_t *g, node_t *n, node_t *adj) {
2214 graph_t *rv, *cl, *tcl, *hcl;
2215 edge_t *orig;
2216
2217 rv = NULL;
2218 if (ND_node_type(n) == NORMAL)
2219 tcl = hcl = ND_clust(n);
2220 else {
2221 orig = ED_to_orig(ND_out(n).list[0]);
2222 tcl = ND_clust(agtail(orig));
2223 hcl = ND_clust(aghead(orig));
2224 }
2225 if (ND_node_type(adj) == NORMAL) {
2226 cl = REAL_CLUSTER(adj);
2227 if (cl && cl != tcl && cl != hcl)
2228 rv = cl;
2229 } else {
2230 orig = ED_to_orig(ND_out(adj).list[0]);
2231 cl = REAL_CLUSTER(agtail(orig));
2232 if (cl && cl != tcl && cl != hcl && cl_vninside(cl, adj))
2233 rv = cl;
2234 else {
2235 cl = REAL_CLUSTER(aghead(orig));
2236 if (cl && cl != tcl && cl != hcl && cl_vninside(cl, adj))
2237 rv = cl;
2238 }
2239 }
2240 return rv;
2241}
2242
2243/* maximal_bbox:
2244 * Return an initial bounding box to be used for building the
2245 * beginning or ending of the path of boxes.
2246 * Height reflects height of tallest node on rank.
2247 * The extra space provided by FUDGE allows begin/endpath to create a box
2248 * FUDGE-2 away from the node, so the routing can avoid the node and the
2249 * box is at least 2 wide.
2250 */
2251#define FUDGE 4
2252
2254 edge_t *oe) {
2255 double b, nb;
2256 graph_t *left_cl, *right_cl;
2257 node_t *left, *right;
2258 boxf rv;
2259
2260 left_cl = right_cl = NULL;
2261
2262 /* give this node all the available space up to its neighbors */
2263 b = (double)(ND_coord(vn).x - ND_lw(vn) - FUDGE);
2264 if ((left = neighbor(g, vn, ie, oe, -1))) {
2265 if ((left_cl = cl_bound(g, vn, left)))
2266 nb = GD_bb(left_cl).UR.x + sp->Splinesep;
2267 else {
2268 nb = (double)(ND_coord(left).x + ND_mval(left));
2269 if (ND_node_type(left) == NORMAL)
2270 nb += GD_nodesep(g) / 2.;
2271 else
2272 nb += sp->Splinesep;
2273 }
2274 if (nb < b)
2275 b = nb;
2276 rv.LL.x = round(b);
2277 } else
2278 rv.LL.x = fmin(round(b), sp->LeftBound);
2279
2280 /* we have to leave room for our own label! */
2281 if (ND_node_type(vn) == VIRTUAL && ND_label(vn))
2282 b = (double)(ND_coord(vn).x + 10);
2283 else
2284 b = (double)(ND_coord(vn).x + ND_rw(vn) + FUDGE);
2285 if ((right = neighbor(g, vn, ie, oe, 1))) {
2286 if ((right_cl = cl_bound(g, vn, right)))
2287 nb = GD_bb(right_cl).LL.x - sp->Splinesep;
2288 else {
2289 nb = ND_coord(right).x - ND_lw(right);
2290 if (ND_node_type(right) == NORMAL)
2291 nb -= GD_nodesep(g) / 2.;
2292 else
2293 nb -= sp->Splinesep;
2294 }
2295 if (nb > b)
2296 b = nb;
2297 rv.UR.x = round(b);
2298 } else
2299 rv.UR.x = fmax(round(b), sp->RightBound);
2300
2301 if (ND_node_type(vn) == VIRTUAL && ND_label(vn)) {
2302 rv.UR.x -= ND_rw(vn);
2303 if (rv.UR.x < rv.LL.x)
2304 rv.UR.x = ND_coord(vn).x;
2305 }
2306
2307 rv.LL.y = ND_coord(vn).y - GD_rank(g)[ND_rank(vn)].ht1;
2308 rv.UR.y = ND_coord(vn).y + GD_rank(g)[ND_rank(vn)].ht2;
2309 return rv;
2310}
2311
2312static node_t *neighbor(graph_t *g, node_t *vn, edge_t *ie, edge_t *oe,
2313 int dir) {
2314 int i;
2315 node_t *n, *rv = NULL;
2316 rank_t *rank = &(GD_rank(g)[ND_rank(vn)]);
2317
2318 for (i = ND_order(vn) + dir; i >= 0 && i < rank->n; i += dir) {
2319 n = rank->v[i];
2320 if (ND_node_type(n) == VIRTUAL && ND_label(n)) {
2321 rv = n;
2322 break;
2323 }
2324 if (ND_node_type(n) == NORMAL) {
2325 rv = n;
2326 break;
2327 }
2328 if (!pathscross(n, vn, ie, oe)) {
2329 rv = n;
2330 break;
2331 }
2332 }
2333 return rv;
2334}
2335
2336static bool pathscross(node_t *n0, node_t *n1, edge_t *ie1, edge_t *oe1) {
2337 edge_t *e0, *e1;
2338 node_t *na, *nb;
2339 int order, cnt;
2340
2341 order = ND_order(n0) > ND_order(n1);
2342 if (ND_out(n0).size != 1 && ND_out(n1).size != 1)
2343 return false;
2344 e1 = oe1;
2345 if (ND_out(n0).size == 1 && e1) {
2346 e0 = ND_out(n0).list[0];
2347 for (cnt = 0; cnt < 2; cnt++) {
2348 if ((na = aghead(e0)) == (nb = aghead(e1)))
2349 break;
2350 if (order != (ND_order(na) > ND_order(nb)))
2351 return true;
2352 if (ND_out(na).size != 1 || ND_node_type(na) == NORMAL)
2353 break;
2354 e0 = ND_out(na).list[0];
2355 if (ND_out(nb).size != 1 || ND_node_type(nb) == NORMAL)
2356 break;
2357 e1 = ND_out(nb).list[0];
2358 }
2359 }
2360 e1 = ie1;
2361 if (ND_in(n0).size == 1 && e1) {
2362 e0 = ND_in(n0).list[0];
2363 for (cnt = 0; cnt < 2; cnt++) {
2364 if ((na = agtail(e0)) == (nb = agtail(e1)))
2365 break;
2366 if (order != (ND_order(na) > ND_order(nb)))
2367 return true;
2368 if (ND_in(na).size != 1 || ND_node_type(na) == NORMAL)
2369 break;
2370 e0 = ND_in(na).list[0];
2371 if (ND_in(nb).size != 1 || ND_node_type(nb) == NORMAL)
2372 break;
2373 e1 = ND_in(nb).list[0];
2374 }
2375 }
2376 return false;
2377}
2378
2379#ifdef DEBUG
2380void showpath(path *p) {
2381 pointf LL, UR;
2382
2383 fprintf(stderr, "%%!PS\n");
2384 for (size_t i = 0; i < p->nbox; i++) {
2385 LL = p->boxes[i].LL;
2386 UR = p->boxes[i].UR;
2387 fprintf(stderr,
2388 "newpath %.04f %.04f moveto %.04f %.04f lineto %.04f %.04f lineto "
2389 "%.04f %.04f lineto closepath stroke\n",
2390 LL.x, LL.y, UR.x, LL.y, UR.x, UR.y, LL.x, UR.y);
2391 }
2392 fprintf(stderr, "showpage\n");
2393}
2394#endif
int normalize(graph_t *g)
Definition adjust.c:738
static agxbuf last
last message
Definition agerror.c:29
static void agxbfree(agxbuf *xb)
free any malloced resources
Definition agxbuf.h:78
static int agxbprint(agxbuf *xb, const char *fmt,...)
Printf-style output to an agxbuf.
Definition agxbuf.h:234
static WUR char * agxbuse(agxbuf *xb)
Definition agxbuf.h:307
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define BETWEEN(a, b, c)
Definition arith.h:38
#define MIN(a, b)
Definition arith.h:28
#define M_PI
Definition arith.h:41
#define right(i)
Definition closest.c:79
void setEdgeType(graph_t *g, int defaultValue)
Definition utils.c:1419
void updateBB(graph_t *g, textlabel_t *lp)
Definition utils.c:621
#define SELFWPEDGE
Definition const.h:161
#define NORMAL
Definition const.h:24
#define EDGETYPE_SPLINE
Definition const.h:253
#define FLATORDER
Definition const.h:28
#define REGULAREDGE
Definition const.h:159
#define EDGE_LABEL
Definition const.h:176
#define IGNORED
Definition const.h:30
#define RANKDIR_TB
Definition const.h:190
#define EDGETYPE_CURVED
Definition const.h:250
#define VIRTUAL
Definition const.h:25
#define RANKDIR_LR
Definition const.h:191
#define EDGETYPE_ORTHO
Definition const.h:252
#define EDGETYPE_PLINE
Definition const.h:251
#define EDGETYPE_LINE
Definition const.h:249
#define EDGETYPEMASK
Definition const.h:164
#define EDGETYPE_NONE
Definition const.h:248
#define GVSPLINES
Definition const.h:173
#define BOTTOM
Definition const.h:117
#define FLATEDGE
Definition const.h:160
#define TOP
Definition const.h:119
#define SELFNPEDGE
Definition const.h:162
void dot_init_node_edge(graph_t *g)
Definition dotinit.c:86
void dot_cleanup(graph_t *g)
Definition dotinit.c:178
int dot_mincross(Agraph_t *)
Definition mincross.c:350
void dot_sameports(Agraph_t *)
Definition sameport.c:39
void dot_rank(Agraph_t *)
Definition rank.c:449
void dot_position(Agraph_t *)
Definition position.c:125
static bool leftOf(pointf p1, pointf p2, pointf p3)
Return true if p3 is to left of ray p1->p2.
static boxf maximal_bbox(graph_t *g, spline_info_t *, Agnode_t *, Agedge_t *, Agedge_t *)
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)
#define HALFMINW
Definition dotsplines.c:37
static void swap_bezier(bezier *b)
Definition dotsplines.c:148
#define GROWEDGES
Definition dotsplines.c:98
static int make_flat_adj_edges(graph_t *g, edge_t **edges, unsigned ind, unsigned cnt, edge_t *e0, int et)
#define CHUNK
Definition dotsplines.c:34
#define MINW
Definition dotsplines.c:36
int dot_splines(graph_t *g)
Definition dotsplines.c:497
#define FWDEDGE
Definition dotsplines.c:39
static int straight_len(Agnode_t *)
#define NSUB
Definition dotsplines.c:33
static bool pathscross(Agnode_t *, Agnode_t *, Agedge_t *, Agedge_t *)
static edge_t * cloneEdge(graph_t *g, node_t *tn, node_t *hn, edge_t *orig)
Definition dotsplines.c:915
static int make_flat_edge(graph_t *, spline_info_t *, path *, Agedge_t **, unsigned, unsigned, int)
static void setState(graph_t *auxg, attr_state_t *attr_state)
Definition dotsplines.c:710
static void edge_normalize(graph_t *g)
Definition dotsplines.c:178
static void makeSimpleFlatLabels(node_t *tn, node_t *hn, edge_t **edges, unsigned ind, unsigned cnt, int et, unsigned n_lbls)
Definition dotsplines.c:989
static int makeLineEdge(graph_t *g, edge_t *fe, points_t *points, node_t **hp)
#define BWDEDGE
Definition dotsplines.c:40
static Agedge_t * top_bound(Agedge_t *, int)
static bool swap_ends_p(edge_t *e)
Definition dotsplines.c:117
int portcmp(port p0, port p1)
Definition dotsplines.c:132
static void make_flat_labeled_edge(graph_t *g, spline_info_t *sp, path *P, edge_t *e, int et)
static bool spline_merge(node_t *n)
Definition dotsplines.c:112
#define AUXGRAPH
Definition dotsplines.c:43
static void setEdgeLabelPos(graph_t *g)
Definition dotsplines.c:211
#define MAINGRAPH
Definition dotsplines.c:42
static bool cl_vninside(Agraph_t *, Agnode_t *)
static void place_vnlabel(Agnode_t *)
Definition dotsplines.c:503
static Agraph_t * cl_bound(graph_t *, Agnode_t *, Agnode_t *)
static void make_regular_edge(graph_t *g, spline_info_t *, path *, Agedge_t **, unsigned, unsigned, int)
static void adjustregularpath(path *, size_t, size_t)
static graph_t * cloneGraph(graph_t *g, attr_state_t *attr_state)
Definition dotsplines.c:803
#define LBL_SPACE
Definition dotsplines.c:981
#define MAKEFWDEDGE(new, old)
Definition dotsplines.c:46
static boxf makeregularend(boxf, int, double)
static edge_t * getmainedge(edge_t *e)
Definition dotsplines.c:103
static boxf rank_box(spline_info_t *sp, Agraph_t *, int)
static void cleanupCloneGraph(graph_t *g, attr_state_t *attr_state)
Definition dotsplines.c:850
static void makeBottomFlatEnd(graph_t *g, spline_info_t *sp, path *P, node_t *n, edge_t *e, pathend_t *endp, bool isBegin)
static void recover_slack(Agedge_t *, path *)
static void makeFlatEnd(graph_t *g, spline_info_t *sp, path *P, node_t *n, edge_t *e, pathend_t *endp, bool isBegin)
static Agedge_t * straight_path(Agedge_t *, int, points_t *)
static int edgecmp(const void *, const void *)
Definition dotsplines.c:557
#define FUDGE
#define GRAPHTYPEMASK
Definition dotsplines.c:44
#define REAL_CLUSTER(n)
static splineInfo sinfo
Definition dotsplines.c:129
static int edgelblcmpfn(const void *x, const void *y)
Definition dotsplines.c:941
static void resize_vn(Agnode_t *, double, double, double)
static void resetRW(graph_t *g)
Definition dotsplines.c:196
static void makeSimpleFlat(node_t *tn, node_t *hn, edge_t **edges, unsigned ind, unsigned cnt, int et)
static void completeregularpath(path *, Agedge_t *, Agedge_t *, pathend_t *, pathend_t *, const boxes_t *)
static void setflags(Agedge_t *, int, int, int)
Definition dotsplines.c:518
static pointf transformf(pointf p, pointf del, int flip)
Definition dotsplines.c:926
static int dot_splines_(graph_t *g, int normalize)
Definition dotsplines.c:241
static void swap_spline(splines *s)
Definition dotsplines.c:158
static Agedge_t * bot_bound(Agedge_t *, int)
static node_t * cloneNode(graph_t *g, node_t *orign)
Definition dotsplines.c:901
static float dy
Definition draw.c:37
static float dx
Definition draw.c:36
#define left
Definition dthdr.h:12
static void del(Dict_t *d, Dtlink_t **set, Agedge_t *e)
Definition edge.c:157
#define le
Definition edges.h:25
void update_bb_bz(boxf *bb, pointf *cp)
Definition emit.c:748
struct pointf_s pointf
static pointf add_pointf(pointf p, pointf q)
Definition geomprocs.h:88
Agsym_t * E_sametail
Definition globals.h:87
Agsym_t * N_fontsize
Definition globals.h:75
Agsym_t * E_labelfontsize
Definition globals.h:89
Agsym_t * E_fontcolor
Definition globals.h:83
Agsym_t * N_group
Definition globals.h:79
Agsym_t * N_width
Definition globals.h:74
Agsym_t * E_weight
Definition globals.h:82
int State
Definition globals.h:63
Agsym_t * N_orientation
Definition globals.h:77
Agsym_t * N_sides
Definition globals.h:77
Agsym_t * E_headclip
Definition globals.h:91
Agsym_t * G_ordering
Definition globals.h:71
Agsym_t * E_headlabel
Definition globals.h:88
Agsym_t * N_showboxes
Definition globals.h:76
Agsym_t * N_fontname
Definition globals.h:75
Agsym_t * E_fontname
Definition globals.h:83
Agsym_t * N_style
Definition globals.h:76
int EdgeLabelsDone
Definition globals.h:64
Agsym_t * E_dir
Definition globals.h:84
Agsym_t * E_label
Definition globals.h:84
Agsym_t * N_skew
Definition globals.h:78
Agsym_t * E_minlen
Definition globals.h:82
Agsym_t * N_shape
Definition globals.h:74
Agsym_t * N_xlabel
Definition globals.h:76
Agsym_t * E_label_float
Definition globals.h:86
Agsym_t * E_samehead
Definition globals.h:87
Agsym_t * N_nojustify
Definition globals.h:76
Agsym_t * E_taillabel
Definition globals.h:88
Agsym_t * N_label
Definition globals.h:76
Agsym_t * E_labelangle
Definition globals.h:90
Agsym_t * E_fontsize
Definition globals.h:83
Agsym_t * N_fixed
Definition globals.h:78
Agsym_t * N_peripheries
Definition globals.h:77
Agsym_t * E_labelfontname
Definition globals.h:89
Agsym_t * N_distortion
Definition globals.h:78
Agsym_t * E_xlabel
Definition globals.h:84
Agsym_t * E_constr
Definition globals.h:85
Agsym_t * N_fontcolor
Definition globals.h:75
Agsym_t * E_labelfontcolor
Definition globals.h:89
Agsym_t * E_tailclip
Definition globals.h:91
Agsym_t * E_labeldistance
Definition globals.h:90
Agsym_t * N_ordering
Definition globals.h:77
Agsym_t * N_height
Definition globals.h:74
void free(void *)
node NULL
Definition grammar.y:163
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:200
Agsym_t * agattr_text(Agraph_t *g, int kind, char *name, const char *value)
creates or looks up text attributes of a graph
Definition attr.c:357
int agset(void *obj, char *name, const char *value)
Definition attr.c:499
Agsym_t * agnxtattr(Agraph_t *g, int kind, Agsym_t *attr)
permits traversing the list of attributes of a given type
Definition attr.c:386
int agxset(void *obj, Agsym_t *sym, const char *value)
Definition attr.c:546
int agcopyattr(void *oldobj, void *newobj)
copies all of the attributes from one object to another
Definition attr.c:659
Agsym_t * agattr_html(Agraph_t *g, int kind, char *name, const char *value)
agattr_text, but creates HTML-like values
Definition attr.c:361
#define ED_to_orig(e)
Definition types.h:598
#define ED_tree_index(e)
Definition types.h:600
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int createflag)
Definition edge.c:256
#define AGMKOUT(e)
Definition cgraph.h:980
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition edge.c:69
#define ED_head_label(e)
Definition types.h:587
#define agfindedgeattr(g, a)
Definition types.h:617
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:24
#define ED_spl(e)
Definition types.h:595
#define agtail(e)
Definition cgraph.h:986
#define ED_edge_type(e)
Definition types.h:582
#define ED_alg(e)
Definition types.h:578
#define ED_tail_label(e)
Definition types.h:596
#define ED_adjacent(e)
Definition types.h:584
#define aghead(e)
Definition cgraph.h:987
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:39
#define ED_head_port(e)
Definition types.h:588
Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition edge.c:55
#define ED_label(e)
Definition types.h:589
#define ED_tail_port(e)
Definition types.h:597
#define ED_to_virt(e)
Definition types.h:599
#define AGOUT2IN(outedge)
Agedgepair_s.out -> Agedgepair_s.in/*#end#*‍/.
Definition cgraph.h:976
void agwarningf(const char *fmt,...)
Definition agerror.c:173
int agerr(agerrlevel_t level, const char *fmt,...)
Definition agerror.c:155
@ AGPREV
Definition cgraph.h:955
#define GD_minrank(g)
Definition types.h:384
#define agfindgraphattr(g, a)
Definition types.h:613
#define GD_maxrank(g)
Definition types.h:382
#define GD_drawing(g)
Definition types.h:353
Agdesc_t Agundirected
undirected
Definition graph.c:276
#define GD_has_labels(g)
Definition types.h:368
int agisdirected(Agraph_t *g)
Definition graph.c:180
int agclose(Agraph_t *g)
deletes a graph, freeing its associated storage
Definition graph.c:97
#define GD_rank(g)
Definition types.h:395
#define GD_bb(g)
Definition types.h:354
#define GD_nlist(g)
Definition types.h:393
Agraph_t * agopen(char *name, Agdesc_t desc, Agdisc_t *disc)
creates a new graph with the given name and kind
Definition graph.c:44
#define GD_dotroot(g)
Definition types.h:361
#define GD_nodesep(g)
Definition types.h:394
#define GD_charset(g)
Definition types.h:367
#define GD_gvc(g)
Definition types.h:355
#define GD_flip(g)
Definition types.h:378
#define GD_ranksep(g)
Definition types.h:397
Agdesc_t Agdirected
directed
Definition graph.c:274
Agnode_t * agnode(Agraph_t *g, char *name, int createflag)
Definition node.c:140
#define ND_rank(n)
Definition types.h:523
#define ND_ht(n)
Definition types.h:500
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:47
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:40
#define ND_next(n)
Definition types.h:510
#define ND_clust(n)
Definition types.h:489
#define ND_other(n)
Definition types.h:514
#define agfindnodeattr(g, a)
Definition types.h:615
#define ND_label(n)
Definition types.h:502
#define ND_alg(n)
Definition types.h:484
#define ND_flat_out(n)
Definition types.h:493
#define ND_rw(n)
Definition types.h:525
#define ND_node_type(n)
Definition types.h:511
#define ND_lw(n)
Definition types.h:506
#define ND_mval(n)
Definition types.h:508
#define ND_order(n)
Definition types.h:513
#define ND_coord(n)
Definition types.h:490
#define ND_in(n)
Definition types.h:501
#define ND_out(n)
Definition types.h:515
Agraph_t * agraphof(void *obj)
Definition obj.c:185
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
Agraph_t * agroot(void *obj)
Definition obj.c:168
#define AGSEQ(obj)
Definition cgraph.h:225
@ AGEDGE
Definition cgraph.h:207
@ AGNODE
Definition cgraph.h:207
@ AGRAPH
Definition cgraph.h:207
void * agbindrec(void *obj, const char *name, unsigned int recsize, int move_to_front)
attaches a new record of the given size to the object
Definition rec.c:89
int aghtmlstr(const char *)
Definition refstr.c:438
Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition subg.c:55
Arithmetic helper functions.
#define SWAP(a, b)
Definition gv_math.h:130
static gdPoint * points
void mark_lowclusters(Agraph_t *root)
Definition cluster.c:412
#define DEFINE_LIST(name, type)
Definition list.h:22
static int * ps
Definition lu.c:51
#define EDGE_TYPE(g)
Definition macros.h:25
#define neighbor(t, i, edim, elist)
Definition make_map.h:41
int rank(graph_t *g, int balance, int maxiter)
Definition ns.c:1061
void orthoEdges(Agraph_t *g, bool useLbls)
Definition ortho.c:1236
void dotneato_postprocess(Agraph_t *g)
Definition postproc.c:690
bezier * new_spline(edge_t *e, size_t sz)
Definition splines.c:216
splines * getsplinepoints(edge_t *e)
Definition splines.c:1390
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, size_t pn, splineInfo *info)
Definition splines.c:239
pointf * simpleSplineRoute(pointf, pointf, Ppoly_t, size_t *, int)
Given a simple (ccw) polygon, route an edge from tp to hp.
Definition routespl.c:173
int routesplinesinit(void)
Definition routespl.c:220
shape_kind shapeOf(node_t *)
Definition shapes.c:1906
void add_box(path *, boxf)
Definition splines.c:346
void beginpath(path *, Agedge_t *, int, pathend_t *, bool)
Definition splines.c:387
pointf * routesplines(path *, size_t *)
Definition routespl.c:566
void routesplinesterm(void)
Definition routespl.c:233
void makeSelfEdge(edge_t *edges[], size_t ind, size_t cnt, double sizex, double sizey, splineInfo *sinfo)
Definition splines.c:1172
void endpath(path *, Agedge_t *, int, pathend_t *, bool)
Definition splines.c:584
pointf * routepolylines(path *pp, size_t *npoints)
Definition routespl.c:570
int place_portlabel(edge_t *e, bool head_p)
Definition splines.c:1338
void makeStraightEdges(graph_t *g, edge_t **edges, size_t e_cnt, int et, splineInfo *sinfo)
Definition routespl.c:945
Agobj_t base
Definition cgraph.h:269
Agedge_t in
Definition cgraph.h:276
Agedge_t out
Definition cgraph.h:276
Agrec_t * data
stores programmer-defined data, access with AGDATA
Definition cgraph.h:212
graph or subgraph
Definition cgraph.h:424
Agraph_t * root
subgraphs - ancestors
Definition cgraph.h:433
implementation of Agrec_t
Definition cgraph.h:172
string attribute descriptor symbol in Agattr_s.dict
Definition cgraph.h:651
char * name
Definition cgraph.h:653
char * defval
Definition cgraph.h:654
attrsym_t * N_style
Definition dotsplines.c:689
attrsym_t * E_sametail
Definition dotsplines.c:669
attrsym_t * E_fontsize
Definition dotsplines.c:674
attrsym_t * N_shape
Definition dotsplines.c:688
attrsym_t * E_minlen
Definition dotsplines.c:671
attrsym_t * E_tailclip
Definition dotsplines.c:682
attrsym_t * E_taillabel
Definition dotsplines.c:683
attrsym_t * E_label
Definition dotsplines.c:677
attrsym_t * E_weight
Definition dotsplines.c:670
attrsym_t * N_nojustify
Definition dotsplines.c:703
attrsym_t * N_fontcolor
Definition dotsplines.c:692
attrsym_t * N_peripheries
Definition dotsplines.c:698
attrsym_t * E_xlabel
Definition dotsplines.c:684
attrsym_t * E_samehead
Definition dotsplines.c:668
attrsym_t * N_xlabel
Definition dotsplines.c:694
attrsym_t * E_label_float
Definition dotsplines.c:678
attrsym_t * N_fontname
Definition dotsplines.c:691
attrsym_t * E_headclip
Definition dotsplines.c:675
attrsym_t * N_sides
Definition dotsplines.c:697
attrsym_t * N_group
Definition dotsplines.c:704
attrsym_t * N_ordering
Definition dotsplines.c:696
attrsym_t * N_width
Definition dotsplines.c:687
attrsym_t * N_fixed
Definition dotsplines.c:702
attrsym_t * E_labelfontname
Definition dotsplines.c:680
attrsym_t * E_dir
Definition dotsplines.c:667
attrsym_t * E_labelfontcolor
Definition dotsplines.c:679
attrsym_t * N_height
Definition dotsplines.c:686
attrsym_t * G_ordering
Definition dotsplines.c:706
attrsym_t * E_constr
Definition dotsplines.c:666
attrsym_t * N_label
Definition dotsplines.c:693
attrsym_t * E_fontname
Definition dotsplines.c:673
attrsym_t * N_skew
Definition dotsplines.c:699
attrsym_t * N_distortion
Definition dotsplines.c:701
attrsym_t * E_fontcolor
Definition dotsplines.c:672
attrsym_t * E_headlabel
Definition dotsplines.c:676
attrsym_t * N_showboxes
Definition dotsplines.c:695
attrsym_t * N_orientation
Definition dotsplines.c:700
attrsym_t * N_fontsize
Definition dotsplines.c:690
attrsym_t * E_labelfontsize
Definition dotsplines.c:681
Definition types.h:89
size_t size
Definition types.h:91
pointf sp
Definition types.h:94
pointf * list
Definition types.h:90
uint32_t eflag
Definition types.h:93
pointf ep
Definition types.h:95
uint32_t sflag
Definition types.h:92
Definition geom.h:41
pointf UR
Definition geom.h:41
pointf LL
Definition geom.h:41
Definition cdt.h:100
Definition types.h:81
port start
Definition types.h:82
boxf * boxes
Definition types.h:85
port end
Definition types.h:83
size_t nbox
number of subdivisions
Definition types.h:84
boxf nb
Definition types.h:74
int boxn
Definition types.h:77
int sidemask
Definition types.h:76
boxf boxes[20]
Definition types.h:78
double x
Definition geom.h:29
double y
Definition geom.h:29
Definition types.h:48
pointf p
Definition types.h:49
double theta
Definition types.h:50
bool constrained
Definition types.h:55
bool defined
Definition types.h:54
double pht1
Definition types.h:207
node_t ** v
Definition types.h:202
double ht1
Definition types.h:205
double pht2
Definition types.h:208
bool(* swapEnds)(edge_t *e)
Definition types.h:67
bool(* splineMerge)(node_t *n)
Definition types.h:68
boxf * Rank_box
Definition dotsplines.c:68
double RightBound
Definition dotsplines.c:65
double LeftBound
Definition dotsplines.c:64
double Multisep
Definition dotsplines.c:67
double Splinesep
Definition dotsplines.c:66
pointf pos
Definition types.h:114
bool set
Definition types.h:123
struct poly_s poly
@ SH_RECORD
Definition types.h:187
#define SET_RANKDIR(g, rd)
Definition types.h:607
Definition grammar.c:93
struct item_s * list
Definition grammar.c:99
#define MAX(a, b)
Definition write.c:31