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