Graphviz 14.0.2~dev.20251008.0253
Loading...
Searching...
No Matches
neatosplines.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#include <assert.h>
12#include "config.h"
13#include <limits.h>
14#include <math.h>
15#include <neatogen/neato.h>
16#include <neatogen/adjust.h>
17#include <pathplan/pathplan.h>
18#include <pathplan/vispath.h>
20#include <stdbool.h>
21#include <stddef.h>
22#include <util/alloc.h>
23#include <util/gv_math.h>
24#include <util/unreachable.h>
25
26#ifdef ORTHO
27#include <ortho/ortho.h>
28#endif
29
30
31static bool spline_merge(node_t * n)
32{
33 (void)n;
34 return false;
35}
36
37static bool swap_ends_p(edge_t * e)
38{
39 (void)e;
40 return false;
41}
42
44 .splineMerge = spline_merge};
45
46static void make_barriers(Ppoly_t **poly, int npoly, int pp, int qp,
47 Pedge_t **barriers, size_t *n_barriers) {
48 int i, j, k;
49
50 size_t n = 0;
51 for (i = 0; i < npoly; i++) {
52 if (i == pp)
53 continue;
54 if (i == qp)
55 continue;
56 n += poly[i]->pn;
57 }
58 Pedge_t *bar = gv_calloc(n, sizeof(Pedge_t));
59 size_t b = 0;
60 for (i = 0; i < npoly; i++) {
61 if (i == pp)
62 continue;
63 if (i == qp)
64 continue;
65 for (j = 0; j < (int)poly[i]->pn; j++) {
66 k = j + 1;
67 if (k >= (int)poly[i]->pn)
68 k = 0;
69 bar[b].a = poly[i]->ps[j];
70 bar[b].b = poly[i]->ps[k];
71 b++;
72 }
73 }
74 assert(b == n);
75 *barriers = bar;
76 *n_barriers = n;
77}
78
79static Ppoint_t genPt(double x, double y, pointf c)
80{
81 Ppoint_t p;
82
83 p.x = x + c.x;
84 p.y = y + c.y;
85 return p;
86}
87
88static Ppoint_t recPt(double x, double y, pointf c, expand_t* m)
89{
90 Ppoint_t p;
91
92 p.x = x * m->x + c.x;
93 p.y = y * m->y + c.y;
94 return p;
95}
96
97typedef struct {
102} edgeinfo;
108
109static void *newitem(void *p, Dtdisc_t *disc) {
110 edgeitem *obj = p;
111 edgeitem *newp;
112
113 (void)disc;
114 newp = gv_alloc(sizeof(edgeitem));
115 newp->id = obj->id;
116 newp->e = obj->e;
117 ED_count(newp->e) = 1;
118
119 return newp;
120}
121
122static int cmpitems(void *k1, void *k2) {
123 const edgeinfo *key1 = k1;
124 const edgeinfo *key2 = k2;
125 if (key1->n1 > key2->n1)
126 return 1;
127 if (key1->n1 < key2->n1)
128 return -1;
129 if (key1->n2 > key2->n2)
130 return 1;
131 if (key1->n2 < key2->n2)
132 return -1;
133
134 if (key1->p1.x > key2->p1.x)
135 return 1;
136 if (key1->p1.x < key2->p1.x)
137 return -1;
138 if (key1->p1.y > key2->p1.y)
139 return 1;
140 if (key1->p1.y < key2->p1.y)
141 return -1;
142 if (key1->p2.x > key2->p2.x)
143 return 1;
144 if (key1->p2.x < key2->p2.x)
145 return -1;
146 if (key1->p2.y > key2->p2.y)
147 return 1;
148 if (key1->p2.y < key2->p2.y)
149 return -1;
150 return 0;
151}
152
154 offsetof(edgeitem, id),
155 sizeof(edgeinfo),
156 offsetof(edgeitem, link),
157 newitem,
158 free,
159 cmpitems,
160};
161
162/* equivEdge:
163 * See if we have already encountered an edge between the same
164 * node:port pairs. If so, return the earlier edge. If not,
165 * this edge is added to map and returned.
166 * We first have to canonicalize the key fields using a lexicographic
167 * ordering.
168 */
169static edge_t *equivEdge(Dt_t * map, edge_t * e)
170{
171 edgeinfo test;
172 edgeitem dummy;
173 edgeitem *ip;
174
175 if (agtail(e) < aghead(e)) {
176 test.n1 = agtail(e);
177 test.p1 = ED_tail_port(e).p;
178 test.n2 = aghead(e);
179 test.p2 = ED_head_port(e).p;
180 } else if (agtail(e) > aghead(e)) {
181 test.n2 = agtail(e);
182 test.p2 = ED_tail_port(e).p;
183 test.n1 = aghead(e);
184 test.p1 = ED_head_port(e).p;
185 } else {
186 pointf hp = ED_head_port(e).p;
187 pointf tp = ED_tail_port(e).p;
188 if (tp.x < hp.x) {
189 test.p1 = tp;
190 test.p2 = hp;
191 } else if (tp.x > hp.x) {
192 test.p1 = hp;
193 test.p2 = tp;
194 } else if (tp.y < hp.y) {
195 test.p1 = tp;
196 test.p2 = hp;
197 } else if (tp.y > hp.y) {
198 test.p1 = hp;
199 test.p2 = tp;
200 } else {
201 test.p1 = test.p2 = tp;
202 }
203 test.n2 = test.n1 = agtail(e);
204 }
205 dummy.id = test;
206 dummy.e = e;
207 ip = dtinsert(map, &dummy);
208 return ip->e;
209}
210
211
212/* makeSelfArcs:
213 * Generate loops. We use the library routine makeSelfEdge
214 * which also places the labels.
215 * We have to handle port labels here.
216 * as well as update the bbox from edge labels.
217 */
218void makeSelfArcs(edge_t * e, int stepx)
219{
220 assert(ED_count(e) >= 0);
221 const size_t cnt = (size_t)ED_count(e);
222
223 if (cnt == 1 || Concentrate) {
224 edge_t *edges1[1];
225 edges1[0] = e;
226 makeSelfEdge(edges1, 0, 1, stepx, stepx, &sinfo);
227 if (ED_label(e))
230 } else if (cnt > 1) {
231 edge_t **edges = gv_calloc(cnt, sizeof(edge_t*));
232 for (size_t i = 0; i < cnt; i++) {
233 edges[i] = e;
234 e = ED_to_virt(e);
235 }
236 makeSelfEdge(edges, 0, cnt, stepx, stepx, &sinfo);
237 for (size_t i = 0; i < cnt; i++) {
238 e = edges[i];
239 if (ED_label(e))
242 }
243 free(edges);
244 }
245}
246
271static double ellipse_tangent_slope(double a, double b, pointf p) {
272 assert(p.x != a &&
273 "cannot handle ellipse tangent slope in horizontal extreme point");
274 const double sign_y = p.y >= 0 ? 1 : -1;
275 const double m = -sign_y * (b * p.x) / (a * sqrt(a * a - p.x * p.x));
276 assert(isfinite(m) && "ellipse tangent slope is infinite");
277 return m;
278}
279
287 const double x =
288 (l0.m * l0.p.x - l0.p.y - l1.m * l1.p.x + l1.p.y) / (l0.m - l1.m);
289 const double y = l0.p.y + l0.m * (x - l0.p.x);
290 return (pointf){x, y};
291}
292
302 size_t i,
303 size_t nsides) {
304 const double angle0 = 2.0 * M_PI * ((double)i - 0.5) / (double)nsides;
305 const double angle1 = 2.0 * M_PI * ((double)i + 0.5) / (double)nsides;
306 const pointf p0 = {a * cos(angle0), b * sin(angle0)};
307 const pointf p1 = {a * cos(angle1), b * sin(angle1)};
308 const double m0 = ellipse_tangent_slope(a, b, p0);
309 const double m1 = ellipse_tangent_slope(a, b, p1);
310 const linef line0 = {{p0.x, p0.y}, m0};
311 const linef line1 = {{p1.x, p1.y}, m1};
312 return line_intersection(line0, line1);
313}
314
315/* makeObstacle:
316 * Given a node, return an obstacle reflecting the
317 * node's geometry. pmargin specifies how much space to allow
318 * around the polygon.
319 * Returns the constructed polygon on success, NULL on failure.
320 * Failure means the node shape is not supported.
321 *
322 * If isOrtho is true, we have to use the bounding box of each node.
323 *
324 * The polygon has its vertices in CW order.
325 *
326 */
327Ppoly_t *makeObstacle(node_t * n, expand_t* pmargin, bool isOrtho)
328{
329 Ppoly_t *obs;
331 size_t sides;
332 pointf polyp;
333 boxf b;
334 pointf pt;
335 field_t *fld;
336 bool isPoly;
337 pointf* verts = NULL;
338 pointf vs[4];
339 pointf p;
340 pointf margin = {0};
341
342 switch (shapeOf(n)) {
343 case SH_POLY:
344 case SH_POINT:
345 obs = gv_alloc(sizeof(Ppoly_t));
346 poly = ND_shape_info(n);
347 if (isOrtho) {
348 isPoly = true;
349 sides = 4;
350 verts = vs;
351 /* For fixedshape, we can't use the width and height, as this includes
352 * the label. We only want to use the actual node shape.
353 */
354 if (poly->option.fixedshape) {
355 b = polyBB (poly);
356 vs[0] = b.LL;
357 vs[1].x = b.UR.x;
358 vs[1].y = b.LL.y;
359 vs[2] = b.UR;
360 vs[3].x = b.LL.x;
361 vs[3].y = b.UR.y;
362 } else {
363 const double width = ND_lw(n) + ND_rw(n);
364 const double outline_width = INCH2PS(ND_outline_width(n));
365 // scale lw and rw proportionally to sum to outline width
366 const double outline_lw = ND_lw(n) * outline_width / width;
367 const double outline_ht = INCH2PS(ND_outline_height(n));
368 p.x = -outline_lw;
369 p.y = -outline_ht / 2.0;
370 vs[0] = p;
371 p.x = outline_lw;
372 vs[1] = p;
373 p.y = outline_ht / 2.0;
374 vs[2] = p;
375 p.x = -outline_lw;
376 vs[3] = p;
377 }
378 }
379 else if (poly->sides >= 3) {
380 isPoly = true;
381 sides = poly->sides;
382 const double penwidth = late_double(n, N_penwidth, 1.0, 0.0);
383 // possibly use extra vertices representing the outline, i.e., the
384 // outermost periphery with penwidth taken into account
385 const size_t extra_peripheries = poly->peripheries >= 1 && penwidth > 0.0 ? 1 : 0;
386 const size_t outline_periphery = poly->peripheries + extra_peripheries;
387 const size_t vertices_offset = outline_periphery >= 1 ? (outline_periphery - 1) * sides : 0;
388 verts = poly->vertices + vertices_offset;
389 margin.x = pmargin->x;
390 margin.y = pmargin->y;
391 } else { /* ellipse */
392 isPoly = false;
393 sides = 8;
394 }
395 obs->pn = sides;
396 obs->ps = gv_calloc(sides, sizeof(Ppoint_t));
397 /* assuming polys are in CCW order, and pathplan needs CW */
398 for (size_t j = 0; j < sides; j++) {
399 double xmargin = 0, ymargin = 0;
400 if (isPoly) {
401 if (pmargin->doAdd) {
402 if (sides == 4) {
403 switch (j) {
404 case 0 :
405 xmargin = margin.x;
406 ymargin = margin.y;
407 break;
408 case 1 :
409 xmargin = -margin.x;
410 ymargin = margin.y;
411 break;
412 case 2 :
413 xmargin = -margin.x;
414 ymargin = -margin.y;
415 break;
416 case 3 :
417 xmargin = margin.x;
418 ymargin = -margin.y;
419 break;
420 default:
421 UNREACHABLE();
422 }
423 polyp.x = verts[j].x + xmargin;
424 polyp.y = verts[j].y + ymargin;
425 }
426 else {
427 const double h = hypot(verts[j].x, verts[j].y);
428 polyp.x = verts[j].x * (1.0 + margin.x/h);
429 polyp.y = verts[j].y * (1.0 + margin.y/h);
430 }
431 }
432 else {
433 polyp.x = verts[j].x * margin.x;
434 polyp.y = verts[j].y * margin.y;
435 }
436 } else {
437 const double width = INCH2PS(ND_outline_width(n));
438 const double height = INCH2PS(ND_outline_height(n));
439 margin = pmargin->doAdd ? (pointf){pmargin->x, pmargin->y} : (pointf){0};
440 const double ellipse_a = (width + margin.x) / 2.0;
441 const double ellipse_b = (height + margin.y) / 2.0;
442 polyp = circumscribed_polygon_corner_about_ellipse(ellipse_a, ellipse_b, j, sides);
443 }
444 obs->ps[sides - j - 1].x = polyp.x + ND_coord(n).x;
445 obs->ps[sides - j - 1].y = polyp.y + ND_coord(n).y;
446 }
447 break;
448 case SH_RECORD:
449 fld = ND_shape_info(n);
450 b = fld->b;
451 obs = gv_alloc(sizeof(Ppoly_t));
452 obs->pn = 4;
453 obs->ps = gv_calloc(4, sizeof(Ppoint_t));
454 /* CW order */
455 pt = ND_coord(n);
456 if (pmargin->doAdd) {
457 obs->ps[0] = genPt(b.LL.x-pmargin->x, b.LL.y-pmargin->y, pt);
458 obs->ps[1] = genPt(b.LL.x-pmargin->x, b.UR.y+pmargin->y, pt);
459 obs->ps[2] = genPt(b.UR.x+pmargin->x, b.UR.y+pmargin->y, pt);
460 obs->ps[3] = genPt(b.UR.x+pmargin->x, b.LL.y-pmargin->y, pt);
461 }
462 else {
463 obs->ps[0] = recPt(b.LL.x, b.LL.y, pt, pmargin);
464 obs->ps[1] = recPt(b.LL.x, b.UR.y, pt, pmargin);
465 obs->ps[2] = recPt(b.UR.x, b.UR.y, pt, pmargin);
466 obs->ps[3] = recPt(b.UR.x, b.LL.y, pt, pmargin);
467 }
468 break;
469 case SH_EPSF:
470 obs = gv_alloc(sizeof(Ppoly_t));
471 obs->pn = 4;
472 obs->ps = gv_calloc(4, sizeof(Ppoint_t));
473 /* CW order */
474 pt = ND_coord(n);
475 if (pmargin->doAdd) {
476 obs->ps[0] = genPt(-ND_lw(n)-pmargin->x, -ND_ht(n)-pmargin->y,pt);
477 obs->ps[1] = genPt(-ND_lw(n)-pmargin->x, ND_ht(n)+pmargin->y,pt);
478 obs->ps[2] = genPt(ND_rw(n)+pmargin->x, ND_ht(n)+pmargin->y,pt);
479 obs->ps[3] = genPt(ND_rw(n)+pmargin->x, -ND_ht(n)-pmargin->y,pt);
480 }
481 else {
482 obs->ps[0] = recPt(-ND_lw(n), -ND_ht(n), pt, pmargin);
483 obs->ps[1] = recPt(-ND_lw(n), ND_ht(n), pt, pmargin);
484 obs->ps[2] = recPt(ND_rw(n), ND_ht(n), pt, pmargin);
485 obs->ps[3] = recPt(ND_rw(n), -ND_ht(n), pt, pmargin);
486 }
487 break;
488 default:
489 obs = NULL;
490 break;
491 }
492 return obs;
493}
494
495/* getPath
496 * Construct the shortest path from one endpoint of e to the other.
497 * vconfig is a precomputed data structure to help in the computation.
498 * If chkPts is true, the function finds the polygons, if any, containing
499 * the endpoints and tells the shortest path computation to ignore them.
500 * Assumes this info is set in ND_lim, usually from _spline_edges.
501 * Returns the shortest path.
502 */
503Ppolyline_t getPath(edge_t *e, vconfig_t *vconfig, bool chkPts) {
504 Ppolyline_t line;
505 int pp, qp;
506 Ppoint_t p, q;
507
508 p = add_pointf(ND_coord(agtail(e)), ED_tail_port(e).p);
509 q = add_pointf(ND_coord(aghead(e)), ED_head_port(e).p);
510
511 /* determine the polygons (if any) that contain the endpoints */
512 pp = qp = POLYID_NONE;
513 if (chkPts) {
514 pp = ND_lim(agtail(e));
515 qp = ND_lim(aghead(e));
516 }
517 Pobspath(vconfig, p, pp, q, qp, &line);
518 return line;
519}
520
521static void makePolyline(edge_t * e) {
522 Ppolyline_t spl, line = ED_path(e);
523
524 make_polyline (line, &spl);
525 if (Verbose > 1)
526 fprintf(stderr, "polyline %s %s\n", agnameof(agtail(e)), agnameof(aghead(e)));
527 clip_and_install(e, aghead(e), spl.ps, spl.pn, &sinfo);
528 addEdgeLabels(e);
529}
530
531/* makeSpline:
532 * Construct a spline connecting the endpoints of e, avoiding the npoly
533 * obstacles obs.
534 * The resultant spline is attached to the edge, the positions of any
535 * edge labels are computed, and the graph's bounding box is recomputed.
536 *
537 * If chkPts is true, the function checks if one or both of the endpoints
538 * is on or inside one of the obstacles and, if so, tells the shortest path
539 * computation to ignore them.
540 */
541void makeSpline(edge_t *e, Ppoly_t **obs, int npoly, bool chkPts) {
542 Ppolyline_t line, spline;
543 Pvector_t slopes[2];
544 int i;
545 int pp, qp;
546 Ppoint_t p, q;
547 Pedge_t *barriers;
548
549 line = ED_path(e);
550 p = line.ps[0];
551 q = line.ps[line.pn - 1];
552 /* determine the polygons (if any) that contain the endpoints */
553 pp = qp = POLYID_NONE;
554 if (chkPts)
555 for (i = 0; i < npoly; i++) {
556 if (pp == POLYID_NONE && in_poly(*obs[i], p))
557 pp = i;
558 if (qp == POLYID_NONE && in_poly(*obs[i], q))
559 qp = i;
560 }
561
562 size_t n_barriers;
563 make_barriers(obs, npoly, pp, qp, &barriers, &n_barriers);
564 slopes[0].x = slopes[0].y = 0.0;
565 slopes[1].x = slopes[1].y = 0.0;
566 if (Proutespline(barriers, n_barriers, line, slopes, &spline) < 0) {
567 agerrorf("makeSpline: failed to make spline edge (%s,%s)\n", agnameof(agtail(e)), agnameof(aghead(e)));
568 return;
569 }
570
571 /* north why did you ever use int coords */
572 if (Verbose > 1)
573 fprintf(stderr, "spline %s %s\n", agnameof(agtail(e)), agnameof(aghead(e)));
574 clip_and_install(e, aghead(e), spline.ps, spline.pn, &sinfo);
575 free(barriers);
576 addEdgeLabels(e);
577}
578
579 /* True if either head or tail has a port on its boundary */
580#define BOUNDARY_PORT(e) ((ED_tail_port(e).side)||(ED_head_port(e).side))
581
582/* Basic default routine for creating edges.
583 * If splines are requested, we construct the obstacles.
584 * If not, or nodes overlap, the function reverts to line segments.
585 * NOTE: intra-cluster edges are not constrained to
586 * remain in the cluster's bounding box and, conversely, a cluster's box
587 * is not altered to reflect intra-cluster edges.
588 * If Nop > 1 and the spline exists, it is just copied.
589 * NOTE: if edgetype = EDGETYPE_NONE, we shouldn't be here.
590 */
591static int spline_edges_(graph_t *g, expand_t *pmargin, int edgetype) {
592 node_t *n;
593 edge_t *e;
594 edge_t *e0;
595 Ppoly_t **obs = 0;
596 Ppoly_t *obp;
597 int cnt, i = 0, npoly;
598 vconfig_t *vconfig = 0;
599 int useEdges = Nop > 1;
600 int legal = 0;
601
602#ifdef HAVE_GTS
603 router_t* rtr = 0;
604#endif
605
606 /* build configuration */
607 if (edgetype >= EDGETYPE_PLINE) {
608 obs = gv_calloc(agnnodes(g), sizeof(Ppoly_t*));
609 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
610 obp = makeObstacle(n, pmargin, edgetype == EDGETYPE_ORTHO);
611 if (obp) {
612 ND_lim(n) = i;
613 obs[i++] = obp;
614 }
615 else
616 ND_lim(n) = POLYID_NONE;
617 }
618 } else {
619 obs = 0;
620 }
621 npoly = i;
622 if (obs) {
623 if ((legal = Plegal_arrangement(obs, npoly))) {
624 if (edgetype != EDGETYPE_ORTHO) vconfig = Pobsopen(obs, npoly);
625 }
626 else {
627 if (edgetype == EDGETYPE_ORTHO)
628 agwarningf("the bounding boxes of some nodes touch - falling back to straight line edges\n");
629 else
630 agwarningf("some nodes with margin (%.02f,%.02f) touch - falling back to straight line edges\n", pmargin->x, pmargin->y);
631 }
632 }
633
634 /* route edges */
635 if (Verbose)
636 fprintf(stderr, "Creating edges using %s\n",
637 (legal && edgetype == EDGETYPE_ORTHO) ? "orthogonal lines" :
638 (vconfig ? (edgetype == EDGETYPE_SPLINE ? "splines" : "polylines") :
639 "line segments"));
640 if (vconfig) {
641 /* path-finding pass */
642 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
643 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
644 ED_path(e) = getPath(e, vconfig, true);
645 }
646 }
647 }
648#ifdef ORTHO
649 else if (legal && edgetype == EDGETYPE_ORTHO) {
650 orthoEdges(g, false);
651 useEdges = 1;
652 }
653#endif
654
655 /* spline-drawing pass */
656 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
657 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
658 node_t *head = aghead(e);
659 if (useEdges && ED_spl(e)) {
660 addEdgeLabels(e);
661 }
662 else if (ED_count(e) == 0) continue; /* only do representative */
663 else if (n == head) { /* self arc */
665 } else if (vconfig) { /* EDGETYPE_SPLINE or EDGETYPE_PLINE */
666#ifdef HAVE_GTS
667 if (ED_count(e) > 1 || BOUNDARY_PORT(e)) {
668 int fail = 0;
669 if (ED_path(e).pn == 2 && !BOUNDARY_PORT(e))
670 /* if a straight line can connect the ends */
671 makeStraightEdge(g, e, edgetype, &sinfo);
672 else {
673 if (!rtr) rtr = mkRouter (obs, npoly);
674 fail = makeMultiSpline(e, rtr, edgetype == EDGETYPE_PLINE);
675 }
676 if (!fail) continue;
677 }
678 /* We can probably remove this branch and just use
679 * makeMultiSpline. It can also catch the makeStraightEdge
680 * case. We could then eliminate all of the vconfig stuff.
681 */
682#endif
683 cnt = ED_count(e);
684 if (Concentrate) cnt = 1; /* only do representative */
685 e0 = e;
686 for (i = 0; i < cnt; i++) {
687 if (edgetype == EDGETYPE_SPLINE)
688 makeSpline(e0, obs, npoly, true);
689 else
690 makePolyline(e0);
691 e0 = ED_to_virt(e0);
692 }
693 } else {
694 makeStraightEdge(g, e, edgetype, &sinfo);
695 }
696 }
697 }
698
699#ifdef HAVE_GTS
700 if (rtr)
701 freeRouter (rtr);
702#endif
703
704 if (vconfig)
705 Pobsclose (vconfig);
706 if (obs) {
707 for (i=0; i < npoly; i++) {
708 free (obs[i]->ps);
709 free (obs[i]);
710 }
711 free (obs);
712 }
713 return 0;
714}
715
716/* splineEdges:
717 * Main wrapper code for generating edges.
718 * Sets desired separation.
719 * Coalesces equivalent edges (edges * with the same endpoints).
720 * It then calls the edge generating function, and marks the
721 * spline phase complete.
722 * Returns 0 on success.
723 *
724 * The edge function is given the graph, the separation to be added
725 * around obstacles, and the type of edge. It must guarantee
726 * that all bounding boxes are current; in particular, the bounding box of
727 * g must reflect the addition of the edges.
728 */
729int
731 int edgetype)
732{
733 node_t *n;
734 edge_t *e;
735 expand_t margin;
736 Dt_t *map;
737
738 margin = esepFactor (g);
739
740 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
741 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
742 resolvePorts (e);
743 }
744 }
745
746 /* find equivalent edges */
747 map = dtopen(&edgeItemDisc, Dtoset);
748 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
749 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
750 if (Nop > 1 && ED_spl(e)) {
751 /* If Nop > 1 (use given edges) and e has a spline, it
752 * should have its own equivalence class.
753 */
754 ED_count(e)++;
755 } else {
756 edge_t *leader = equivEdge(map, e);
757 if (leader != e) {
758 ED_count(leader)++;
759 ED_to_virt(e) = ED_to_virt(leader);
760 ED_to_virt(leader) = e;
761 }
762 }
763 }
764 }
765 dtclose(map);
766
767 if (edgefn(g, &margin, edgetype))
768 return 1;
769
771 return 0;
772}
773
774/* spline_edges1:
775 * Construct edges using default algorithm and given splines value.
776 * Return 0 on success.
777 */
778int spline_edges1(graph_t * g, int edgetype)
779{
780 return splineEdges(g, spline_edges_, edgetype);
781}
782
783/* spline_edges0:
784 * Sets the graph's aspect ratio.
785 * Check splines attribute and construct edges using default algorithm.
786 * If the splines attribute is defined but equal to "", skip edge routing.
787 *
788 * Assumes u.bb for has been computed for g and all clusters
789 * (not just top-level clusters), and that GD_bb(g).LL is at the origin.
790 *
791 * This last criterion is, I believe, mainly to simplify the code
792 * in neato_set_aspect. It would be good to remove this constraint,
793 * as this would allow nodes pinned on input to have the same coordinates
794 * when output in dot or plain format.
795 *
796 */
798 int et = EDGE_TYPE (g);
800 if (et == EDGETYPE_NONE) return;
801#ifndef ORTHO
802 if (et == EDGETYPE_ORTHO) {
803 agwarningf("Orthogonal edges not yet supported\n");
804 et = EDGETYPE_PLINE;
805 GD_flags(g->root) &= ~EDGETYPE_ORTHO;
807 }
808#endif
809 spline_edges1(g, et);
810}
811
812static void
814{
815 int i;
816
817 for (i = 1; i <= GD_n_cluster(g); i++) {
818 shiftClusters (GD_clust(g)[i], offset);
819 }
820
821 GD_bb(g).UR.x -= offset.x;
822 GD_bb(g).UR.y -= offset.y;
823 GD_bb(g).LL.x -= offset.x;
824 GD_bb(g).LL.y -= offset.y;
825}
826
827/* spline_edges:
828 * Compute bounding box, translate graph to origin,
829 * then construct all edges.
830 */
832{
833 node_t *n;
834 pointf offset;
835
836 compute_bb(g);
837 offset.x = PS2INCH(GD_bb(g).LL.x);
838 offset.y = PS2INCH(GD_bb(g).LL.y);
839 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
840 ND_pos(n)[0] -= offset.x;
841 ND_pos(n)[1] -= offset.y;
842 }
843
844 shiftClusters (g, GD_bb(g).LL);
845 spline_edges0(g, true);
846}
847
848/* scaleEdge:
849 * Scale edge by given factor.
850 * Assume ED_spl != NULL.
851 */
852static void scaleEdge(edge_t * e, double xf, double yf)
853{
854 pointf *pt;
855 bezier *bez;
856 pointf delh, delt;
857
858 delh.x = POINTS_PER_INCH * (ND_pos(aghead(e))[0] * (xf - 1.0));
859 delh.y = POINTS_PER_INCH * (ND_pos(aghead(e))[1] * (yf - 1.0));
860 delt.x = POINTS_PER_INCH * (ND_pos(agtail(e))[0] * (xf - 1.0));
861 delt.y = POINTS_PER_INCH * (ND_pos(agtail(e))[1] * (yf - 1.0));
862
863 bez = ED_spl(e)->list;
864 for (size_t i = 0; i < ED_spl(e)->size; i++) {
865 pt = bez->list;
866 for (size_t j = 0; j < bez->size; j++) {
867 if (i == 0 && j == 0) {
868 pt->x += delt.x;
869 pt->y += delt.y;
870 }
871 else if (i == ED_spl(e)->size-1 && j == bez->size-1) {
872 pt->x += delh.x;
873 pt->y += delh.y;
874 }
875 else {
876 pt->x *= xf;
877 pt->y *= yf;
878 }
879 pt++;
880 }
881 if (bez->sflag) {
882 bez->sp.x += delt.x;
883 bez->sp.y += delt.y;
884 }
885 if (bez->eflag) {
886 bez->ep.x += delh.x;
887 bez->ep.y += delh.y;
888 }
889 bez++;
890 }
891
892 if (ED_label(e) && ED_label(e)->set) {
893 ED_label(e)->pos.x *= xf;
894 ED_label(e)->pos.y *= yf;
895 }
896 if (ED_head_label(e) && ED_head_label(e)->set) {
897 ED_head_label(e)->pos.x += delh.x;
898 ED_head_label(e)->pos.y += delh.y;
899 }
900 if (ED_tail_label(e) && ED_tail_label(e)->set) {
901 ED_tail_label(e)->pos.x += delt.x;
902 ED_tail_label(e)->pos.y += delt.y;
903 }
904}
905
906/* scaleBB:
907 * Scale bounding box of clusters of g by given factors.
908 */
909static void scaleBB(graph_t * g, double xf, double yf)
910{
911 int i;
912
913 GD_bb(g).UR.x *= xf;
914 GD_bb(g).UR.y *= yf;
915 GD_bb(g).LL.x *= xf;
916 GD_bb(g).LL.y *= yf;
917
918 if (GD_label(g) && GD_label(g)->set) {
919 GD_label(g)->pos.x *= xf;
920 GD_label(g)->pos.y *= yf;
921 }
922
923 for (i = 1; i <= GD_n_cluster(g); i++)
924 scaleBB(GD_clust(g)[i], xf, yf);
925}
926
927/* translateE:
928 * Translate edge by offset.
929 * Assume ED_spl(e) != NULL
930 */
931static void translateE(edge_t * e, pointf offset)
932{
933 pointf *pt;
934 bezier *bez;
935
936 bez = ED_spl(e)->list;
937 for (size_t i = 0; i < ED_spl(e)->size; i++) {
938 pt = bez->list;
939 for (size_t j = 0; j < bez->size; j++) {
940 pt->x -= offset.x;
941 pt->y -= offset.y;
942 pt++;
943 }
944 if (bez->sflag) {
945 bez->sp.x -= offset.x;
946 bez->sp.y -= offset.y;
947 }
948 if (bez->eflag) {
949 bez->ep.x -= offset.x;
950 bez->ep.y -= offset.y;
951 }
952 bez++;
953 }
954
955 if (ED_label(e) && ED_label(e)->set) {
956 ED_label(e)->pos.x -= offset.x;
957 ED_label(e)->pos.y -= offset.y;
958 }
959 if (ED_xlabel(e) && ED_xlabel(e)->set) {
960 ED_xlabel(e)->pos.x -= offset.x;
961 ED_xlabel(e)->pos.y -= offset.y;
962 }
963 if (ED_head_label(e) && ED_head_label(e)->set) {
964 ED_head_label(e)->pos.x -= offset.x;
965 ED_head_label(e)->pos.y -= offset.y;
966 }
967 if (ED_tail_label(e) && ED_tail_label(e)->set) {
968 ED_tail_label(e)->pos.x -= offset.x;
969 ED_tail_label(e)->pos.y -= offset.y;
970 }
971}
972
973static void translateG(Agraph_t * g, pointf offset)
974{
975 int i;
976
977 GD_bb(g).UR.x -= offset.x;
978 GD_bb(g).UR.y -= offset.y;
979 GD_bb(g).LL.x -= offset.x;
980 GD_bb(g).LL.y -= offset.y;
981
982 if (GD_label(g) && GD_label(g)->set) {
983 GD_label(g)->pos.x -= offset.x;
984 GD_label(g)->pos.y -= offset.y;
985 }
986
987 for (i = 1; i <= GD_n_cluster(g); i++)
988 translateG(GD_clust(g)[i], offset);
989}
990
992{
993 node_t *n;
994 edge_t *e;
995 pointf offset;
996 pointf ll;
997
998 ll = GD_bb(g).LL;
999
1000 offset.x = PS2INCH(ll.x);
1001 offset.y = PS2INCH(ll.y);
1002 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1003 ND_pos(n)[0] -= offset.x;
1004 ND_pos(n)[1] -= offset.y;
1005 if (ND_xlabel(n) && ND_xlabel(n)->set) {
1006 ND_xlabel(n)->pos.x -= ll.x;
1007 ND_xlabel(n)->pos.y -= ll.y;
1008 }
1009 }
1010 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1011 for (e = agfstout(g, n); e; e = agnxtout(g, e))
1012 if (ED_spl(e))
1013 translateE(e, ll);
1014 }
1015 translateG(g, ll);
1016}
1017
1018/* _neato_set_aspect;
1019 * Assume all bounding boxes are correct.
1020 * Return false if no transform is performed. This includes
1021 * the possibility that a translation was done.
1022 */
1024{
1025 double xf, yf, actual, desired;
1026 node_t *n;
1027 bool translated = false;
1028
1029 if (g->root != g)
1030 return false;
1031
1032 if (GD_drawing(g)->ratio_kind) {
1033 if (GD_bb(g).LL.x || GD_bb(g).LL.y) {
1034 translated = true;
1035 neato_translate (g);
1036 }
1037 /* normalize */
1038 if (GD_flip(g)) {
1039 GD_bb(g).UR = exch_xyf(GD_bb(g).UR);
1040 }
1041 if (GD_drawing(g)->ratio_kind == R_FILL) {
1042 /* fill is weird because both X and Y can stretch */
1043 if (GD_drawing(g)->size.x <= 0)
1044 return translated;
1045 xf = GD_drawing(g)->size.x / GD_bb(g).UR.x;
1046 yf = GD_drawing(g)->size.y / GD_bb(g).UR.y;
1047 /* handle case where one or more dimensions is too big */
1048 if (xf < 1.0 || yf < 1.0) {
1049 if (xf < yf) {
1050 yf /= xf;
1051 xf = 1.0;
1052 } else {
1053 xf /= yf;
1054 yf = 1.0;
1055 }
1056 }
1057 } else if (GD_drawing(g)->ratio_kind == R_EXPAND) {
1058 if (GD_drawing(g)->size.x <= 0)
1059 return translated;
1060 xf = GD_drawing(g)->size.x / GD_bb(g).UR.x;
1061 yf = GD_drawing(g)->size.y / GD_bb(g).UR.y;
1062 if (xf > 1.0 && yf > 1.0) {
1063 double scale = fmin(xf, yf);
1064 xf = yf = scale;
1065 } else
1066 return translated;
1067 } else if (GD_drawing(g)->ratio_kind == R_VALUE) {
1068 desired = GD_drawing(g)->ratio;
1069 actual = GD_bb(g).UR.y / GD_bb(g).UR.x;
1070 if (actual < desired) {
1071 yf = desired / actual;
1072 xf = 1.0;
1073 } else {
1074 xf = actual / desired;
1075 yf = 1.0;
1076 }
1077 } else
1078 return translated;
1079 if (GD_flip(g)) {
1080 SWAP(&xf, &yf);
1081 }
1082
1083 if (Nop > 1) {
1084 edge_t *e;
1085 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1086 for (e = agfstout(g, n); e; e = agnxtout(g, e))
1087 if (ED_spl(e))
1088 scaleEdge(e, xf, yf);
1089 }
1090 }
1091 /* Not relying on neato_nlist here allows us not to have to
1092 * allocate it in the root graph and the connected components.
1093 */
1094 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1095 ND_pos(n)[0] *= xf;
1096 ND_pos(n)[1] *= yf;
1097 }
1098 scaleBB(g, xf, yf);
1099 return true;
1100 }
1101 else
1102 return false;
1103}
1104
1105/* neato_set_aspect:
1106 * Sets aspect ratio if necessary; real work done in _neato_set_aspect;
1107 * This also copies the internal layout coordinates (ND_pos) to the
1108 * external ones (ND_coord).
1109 *
1110 * Return true if some node moved.
1111 */
1113{
1114 node_t *n;
1115 bool moved = false;
1116
1117 /* setting aspect ratio only makes sense on root graph */
1118 moved = _neato_set_aspect(g);
1119 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1120 ND_coord(n).x = POINTS_PER_INCH * ND_pos(n)[0];
1121 ND_coord(n).y = POINTS_PER_INCH * ND_pos(n)[1];
1122 }
1123 return moved;
1124}
1125
expand_t esepFactor(graph_t *g)
Definition adjust.c:1070
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 M_PI
Definition arith.h:41
#define dtinsert(d, o)
Definition cdt.h:186
CDT_API int dtclose(Dt_t *)
Definition dtclose.c:8
CDT_API Dtmethod_t * Dtoset
ordered set (self-adjusting tree)
Definition dttree.c:304
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition dtopen.c:9
boxf polyBB(polygon_t *poly)
Definition utils.c:602
double late_double(void *obj, attrsym_t *attr, double defaultValue, double minimum)
Definition utils.c:51
void updateBB(graph_t *g, textlabel_t *lp)
Definition utils.c:622
void compute_bb(graph_t *g)
Definition utils.c:631
#define EDGETYPE_SPLINE
Definition const.h:248
#define EDGETYPE_ORTHO
Definition const.h:247
#define EDGETYPE_PLINE
Definition const.h:246
#define EDGETYPE_NONE
Definition const.h:243
#define GVSPLINES
Definition const.h:173
vconfig_t * Pobsopen(Ppoly_t **obs, int n_obs)
Definition cvt.c:26
void Pobsclose(vconfig_t *config)
Definition cvt.c:87
void Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route)
Definition cvt.c:100
#define head
Definition dthdr.h:15
static Dtdisc_t disc
Definition exparse.y:209
#define PS2INCH(a_points)
Definition geom.h:64
struct pointf_s pointf
#define POINTS_PER_INCH
Definition geom.h:58
#define INCH2PS(a_inches)
Definition geom.h:63
static WUR pointf add_pointf(pointf p, pointf q)
Definition geomprocs.h:88
static WUR pointf exch_xyf(pointf p)
Definition geomprocs.h:128
static WUR pointf scale(double c, pointf p)
Definition geomprocs.h:148
int State
Definition globals.h:63
bool Concentrate
Definition globals.h:59
int Nop
Definition globals.h:55
Agsym_t * N_penwidth
Definition globals.h:80
static bool Verbose
Definition gml2gv.c:24
void free(void *)
node NULL
Definition grammar.y:181
static int cnt(Dict_t *d, Dtlink_t **set)
Definition graph.c:196
int agnnodes(Agraph_t *g)
Definition graph.c:155
#define ED_xlabel(e)
Definition types.h:590
#define ED_head_label(e)
Definition types.h:587
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define ED_spl(e)
Definition types.h:595
#define ED_count(e)
Definition types.h:580
#define agtail(e)
Definition cgraph.h:977
#define ED_path(e)
Definition types.h:593
#define ED_tail_label(e)
Definition types.h:596
#define aghead(e)
Definition cgraph.h:978
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
#define ED_head_port(e)
Definition types.h:588
#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
void agwarningf(const char *fmt,...)
Definition agerror.c:173
void agerrorf(const char *fmt,...)
Definition agerror.c:165
#define GD_drawing(g)
Definition types.h:353
#define GD_clust(g)
Definition types.h:360
#define GD_flags(g)
Definition types.h:365
#define GD_bb(g)
Definition types.h:354
#define GD_n_cluster(g)
Definition types.h:389
#define GD_label(g)
Definition types.h:374
#define GD_nodesep(g)
Definition types.h:394
#define GD_flip(g)
Definition types.h:378
#define ND_outline_width(n)
Definition types.h:516
#define ND_outline_height(n)
Definition types.h:517
#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_lim(n)
Definition types.h:504
#define ND_rw(n)
Definition types.h:525
#define ND_lw(n)
Definition types.h:506
#define ND_xlabel(n)
Definition types.h:503
#define ND_shape_info(n)
Definition types.h:529
#define ND_pos(n)
Definition types.h:520
#define ND_coord(n)
Definition types.h:490
Agraph_t * agraphof(void *obj)
Definition obj.c:185
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
Arithmetic helper functions.
#define SWAP(a, b)
Definition gv_math.h:134
static double penwidth[]
bool in_poly(const Ppoly_t poly, Ppoint_t q)
Definition inpoly.c:24
int Plegal_arrangement(Ppoly_t **polys, int n_polys)
Definition legal.c:361
static int * ps
Definition lu.c:51
#define EDGE_TYPE(g)
Definition macros.h:25
router_t * mkRouter(Ppoly_t **obsp, int npoly)
void freeRouter(router_t *rtr)
int makeMultiSpline(edge_t *e, router_t *rtr, int doPolyline)
static bool _neato_set_aspect(graph_t *g)
static int cmpitems(void *k1, void *k2)
static pointf line_intersection(linef l0, linef l1)
static void * newitem(void *p, Dtdisc_t *disc)
static void make_barriers(Ppoly_t **poly, int npoly, int pp, int qp, Pedge_t **barriers, size_t *n_barriers)
static int spline_edges_(graph_t *g, expand_t *pmargin, int edgetype)
static void translateE(edge_t *e, pointf offset)
static Ppoint_t recPt(double x, double y, pointf c, expand_t *m)
static bool swap_ends_p(edge_t *e)
int spline_edges1(graph_t *g, int edgetype)
static bool spline_merge(node_t *n)
Ppoly_t * makeObstacle(node_t *n, expand_t *pmargin, bool isOrtho)
Ppolyline_t getPath(edge_t *e, vconfig_t *vconfig, bool chkPts)
Dtdisc_t edgeItemDisc
void makeSpline(edge_t *e, Ppoly_t **obs, int npoly, bool chkPts)
void spline_edges0(graph_t *g, bool set_aspect)
static pointf circumscribed_polygon_corner_about_ellipse(double a, double b, size_t i, size_t nsides)
static double ellipse_tangent_slope(double a, double b, pointf p)
static void shiftClusters(graph_t *g, pointf offset)
static void scaleEdge(edge_t *e, double xf, double yf)
static void translateG(Agraph_t *g, pointf offset)
static void makePolyline(edge_t *e)
static void scaleBB(graph_t *g, double xf, double yf)
static splineInfo sinfo
int splineEdges(graph_t *g, int(*edgefn)(graph_t *, expand_t *, int), int edgetype)
void makeSelfArcs(edge_t *e, int stepx)
void neato_translate(Agraph_t *g)
static edge_t * equivEdge(Dt_t *map, edge_t *e)
static Ppoint_t genPt(double x, double y, pointf c)
void spline_edges(graph_t *g)
#define BOUNDARY_PORT(e)
bool neato_set_aspect(graph_t *g)
void orthoEdges(Agraph_t *g, bool useLbls)
Definition ortho.c:1186
finds and smooths shortest paths
void make_polyline(Ppolyline_t line, Ppolyline_t *sline)
Definition util.c:59
int Proutespline(Pedge_t *barriers, size_t n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route)
Definition route.c:69
static void set_aspect(graph_t *g)
Definition position.c:903
void makePortLabels(edge_t *e)
Definition splines.c:1213
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, size_t pn, splineInfo *info)
Definition splines.c:239
void resolvePorts(edge_t *e)
Definition shapes.c:4356
shape_kind shapeOf(node_t *)
Definition shapes.c:1906
void makeStraightEdge(graph_t *g, edge_t *e, int edgetype, splineInfo *info)
Definition routespl.c:961
void addEdgeLabels(edge_t *e)
Definition splines.c:1324
void makeSelfEdge(edge_t *edges[], size_t ind, size_t cnt, double sizex, double sizey, splineInfo *sinfo)
Definition splines.c:1170
graph or subgraph
Definition cgraph.h:424
Agraph_t * root
subgraphs - ancestors
Definition cgraph.h:433
Ppoint_t b
Definition pathgeom.h:53
Ppoint_t a
Definition pathgeom.h:53
size_t pn
Definition pathgeom.h:47
Ppoint_t * ps
Definition pathgeom.h:46
double x
Definition pathgeom.h:38
double y
Definition pathgeom.h:38
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:98
node_t * n2
pointf p1
pointf p2
node_t * n1
edge_t * e
edgeinfo id
Dtlink_t link
double x
Definition adjust.h:41
double y
Definition adjust.h:41
bool doAdd
Definition adjust.h:42
boxf b
Definition types.h:237
Definition geom.h:31
pointf p
Definition geom.h:32
double m
Definition geom.h:33
double x
Definition geom.h:29
double y
Definition geom.h:29
bool(* swapEnds)(edge_t *e)
Definition types.h:67
struct poly_s poly
void(* edgefn)(Agraph_t *, Agedge_t *, glCompColor)
@ SH_EPSF
Definition types.h:187
@ SH_RECORD
Definition types.h:187
@ SH_POINT
Definition types.h:187
@ SH_POLY
Definition types.h:187
@ R_VALUE
Definition types.h:216
@ R_FILL
Definition types.h:216
@ R_EXPAND
Definition types.h:216
#define UNREACHABLE()
Definition unreachable.h:30
#define POLYID_NONE
Definition vispath.h:50