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