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