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