Graphviz  2.39.20141219.0545
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  * If isOrtho is true, we have to use the bounding box of each node.
265  *
266  * The polygon has its vertices in CW order.
267  *
268  */
269 Ppoly_t *makeObstacle(node_t * n, expand_t* pmargin, boolean isOrtho)
270 {
271  Ppoly_t *obs;
272  polygon_t *poly;
273  double adj = 0.0;
274  int j, sides;
275  pointf polyp;
276  boxf b;
277  pointf pt;
278  field_t *fld;
279  epsf_t *desc;
280  int isPoly;
281  pointf* verts;
282  pointf vs[4];
283  pointf p;
284  pointf margin;
285 
286  switch (shapeOf(n)) {
287  case SH_POLY:
288  case SH_POINT:
289  obs = NEW(Ppoly_t);
290  poly = (polygon_t *) ND_shape_info(n);
291  if (isOrtho) {
292  isPoly = 1;
293  sides = 4;
294  verts = vs;
295  margin.x = margin.y = 0;
296  /* For fixedshape, we can't use the width and height, as this includes
297  * the label. We only want to use the actual node shape.
298  */
299  if (poly->option & FIXEDSHAPE) {
300  b = polyBB (poly);
301  vs[0] = b.LL;
302  vs[1].x = b.UR.x;
303  vs[1].y = b.LL.y;
304  vs[2] = b.UR;
305  vs[3].x = b.LL.x;
306  vs[3].y = b.UR.y;
307  } else {
308  p.x = -ND_lw(n);
309  p.y = -ND_ht(n)/2.0;
310  vs[0] = p;
311  p.x = ND_lw(n);
312  vs[1] = p;
313  p.y = ND_ht(n)/2.0;
314  vs[2] = p;
315  p.x = -ND_lw(n);
316  vs[3] = p;
317  }
318  }
319  else if (poly->sides >= 3) {
320  isPoly = 1;
321  sides = poly->sides;
322  verts = poly->vertices;
323  margin.x = pmargin->x;
324  margin.y = pmargin->y;
325  } else { /* ellipse */
326  isPoly = 0;
327  sides = 8;
328  adj = drand48() * .01;
329  }
330  obs->pn = sides;
331  obs->ps = N_NEW(sides, Ppoint_t);
332  /* assuming polys are in CCW order, and pathplan needs CW */
333  for (j = 0; j < sides; j++) {
334  double xmargin = 0.0, ymargin = 0.0;
335  if (isPoly) {
336  if (pmargin->doAdd) {
337  if (sides == 4) {
338  switch (j) {
339  case 0 :
340  xmargin = margin.x;
341  ymargin = margin.y;
342  break;
343  case 1 :
344  xmargin = -margin.x;
345  ymargin = margin.y;
346  break;
347  case 2 :
348  xmargin = -margin.x;
349  ymargin = -margin.y;
350  break;
351  case 3 :
352  xmargin = margin.x;
353  ymargin = -margin.y;
354  break;
355  }
356  polyp.x = verts[j].x + xmargin;
357  polyp.y = verts[j].y + ymargin;
358  }
359  else {
360  double h = LEN(verts[j].x,verts[j].y);
361  polyp.x = verts[j].x * (1.0 + margin.x/h);
362  polyp.y = verts[j].y * (1.0 + margin.y/h);
363  }
364  }
365  else {
366  polyp.x = verts[j].x * margin.x;
367  polyp.y = verts[j].y * margin.y;
368  }
369  } else {
370  double c, s;
371  c = cos(2.0 * M_PI * j / sides + adj);
372  s = sin(2.0 * M_PI * j / sides + adj);
373  if (pmargin->doAdd) {
374  polyp.x = c*(ND_lw(n)+ND_rw(n)+pmargin->x) / 2.0;
375  polyp.y = s*(ND_ht(n)+pmargin->y) / 2.0;
376  }
377  else {
378  polyp.x = pmargin->x * c * (ND_lw(n) + ND_rw(n)) / 2.0;
379  polyp.y = pmargin->y * s * ND_ht(n) / 2.0;
380  }
381  }
382  obs->ps[sides - j - 1].x = polyp.x + ND_coord(n).x;
383  obs->ps[sides - j - 1].y = polyp.y + ND_coord(n).y;
384  }
385  break;
386  case SH_RECORD:
387  fld = (field_t *) ND_shape_info(n);
388  b = fld->b;
389  obs = NEW(Ppoly_t);
390  obs->pn = 4;
391  obs->ps = N_NEW(4, Ppoint_t);
392  /* CW order */
393  pt = ND_coord(n);
394  if (pmargin->doAdd) {
395  obs->ps[0] = genPt(b.LL.x-pmargin->x, b.LL.y-pmargin->y, pt);
396  obs->ps[1] = genPt(b.LL.x-pmargin->x, b.UR.y+pmargin->y, pt);
397  obs->ps[2] = genPt(b.UR.x+pmargin->x, b.UR.y+pmargin->y, pt);
398  obs->ps[3] = genPt(b.UR.x+pmargin->x, b.LL.y-pmargin->y, pt);
399  }
400  else {
401  obs->ps[0] = recPt(b.LL.x, b.LL.y, pt, pmargin);
402  obs->ps[1] = recPt(b.LL.x, b.UR.y, pt, pmargin);
403  obs->ps[2] = recPt(b.UR.x, b.UR.y, pt, pmargin);
404  obs->ps[3] = recPt(b.UR.x, b.LL.y, pt, pmargin);
405  }
406  break;
407  case SH_EPSF:
408  desc = (epsf_t *) (ND_shape_info(n));
409  obs = NEW(Ppoly_t);
410  obs->pn = 4;
411  obs->ps = N_NEW(4, Ppoint_t);
412  /* CW order */
413  pt = ND_coord(n);
414  if (pmargin->doAdd) {
415  obs->ps[0] = genPt(-ND_lw(n)-pmargin->x, -ND_ht(n)-pmargin->y,pt);
416  obs->ps[1] = genPt(-ND_lw(n)-pmargin->x, ND_ht(n)+pmargin->y,pt);
417  obs->ps[2] = genPt(ND_rw(n)+pmargin->x, ND_ht(n)+pmargin->y,pt);
418  obs->ps[3] = genPt(ND_rw(n)+pmargin->x, -ND_ht(n)-pmargin->y,pt);
419  }
420  else {
421  obs->ps[0] = recPt(-ND_lw(n), -ND_ht(n), pt, pmargin);
422  obs->ps[1] = recPt(-ND_lw(n), ND_ht(n), pt, pmargin);
423  obs->ps[2] = recPt(ND_rw(n), ND_ht(n), pt, pmargin);
424  obs->ps[3] = recPt(ND_rw(n), -ND_ht(n), pt, pmargin);
425  }
426  break;
427  default:
428  obs = NULL;
429  break;
430  }
431  return obs;
432 }
433 
434 /* getPath
435  * Construct the shortest path from one endpoint of e to the other.
436  * The obstacles and their number are given by obs and npoly.
437  * vconfig is a precomputed data structure to help in the computation.
438  * If chkPts is true, the function finds the polygons, if any, containing
439  * the endpoints and tells the shortest path computation to ignore them.
440  * Assumes this info is set in ND_lim, usually from _spline_edges.
441  * Returns the shortest path.
442  */
444 getPath(edge_t * e, vconfig_t * vconfig, int chkPts, Ppoly_t ** obs,
445  int npoly)
446 {
447  Ppolyline_t line;
448  int pp, qp;
449  Ppoint_t p, q;
450 
451  p = add_pointf(ND_coord(agtail(e)), ED_tail_port(e).p);
452  q = add_pointf(ND_coord(aghead(e)), ED_head_port(e).p);
453 
454  /* determine the polygons (if any) that contain the endpoints */
455  pp = qp = POLYID_NONE;
456  if (chkPts) {
457  pp = ND_lim(agtail(e));
458  qp = ND_lim(aghead(e));
459 /*
460  for (i = 0; i < npoly; i++) {
461  if ((pp == POLYID_NONE) && in_poly(*obs[i], p))
462  pp = i;
463  if ((qp == POLYID_NONE) && in_poly(*obs[i], q))
464  qp = i;
465  }
466 */
467  }
468  Pobspath(vconfig, p, pp, q, qp, &line);
469  return line;
470 }
471 
472 /* makePolyline:
473  */
474 static void
475 makePolyline(graph_t* g, edge_t * e)
476 {
477  Ppolyline_t spl, line = ED_path(e);
478  Ppoint_t p0, q0;
479 
480  p0 = line.ps[0];
481  q0 = line.ps[line.pn - 1];
482  make_polyline (line, &spl);
483  if (Verbose > 1)
484  fprintf(stderr, "polyline %s %s\n", agnameof(agtail(e)), agnameof(aghead(e)));
485  clip_and_install(e, aghead(e), spl.ps, spl.pn, &sinfo);
486  addEdgeLabels(g, e, p0, q0);
487 }
488 
489 /* makeSpline:
490  * Construct a spline connecting the endpoints of e, avoiding the npoly
491  * obstacles obs.
492  * The resultant spline is attached to the edge, the positions of any
493  * edge labels are computed, and the graph's bounding box is recomputed.
494  *
495  * If chkPts is true, the function checks if one or both of the endpoints
496  * is on or inside one of the obstacles and, if so, tells the shortest path
497  * computation to ignore them.
498  */
499 void makeSpline(graph_t* g, edge_t * e, Ppoly_t ** obs, int npoly, boolean chkPts)
500 {
501  Ppolyline_t line, spline;
502  Pvector_t slopes[2];
503  int i, n_barriers;
504  int pp, qp;
505  Ppoint_t p, q;
506  Pedge_t *barriers;
507 
508  line = ED_path(e);
509  p = line.ps[0];
510  q = line.ps[line.pn - 1];
511  /* determine the polygons (if any) that contain the endpoints */
512  pp = qp = POLYID_NONE;
513  if (chkPts)
514  for (i = 0; i < npoly; i++) {
515  if ((pp == POLYID_NONE) && in_poly(*obs[i], p))
516  pp = i;
517  if ((qp == POLYID_NONE) && in_poly(*obs[i], q))
518  qp = i;
519  }
520 
521  make_barriers(obs, npoly, pp, qp, &barriers, &n_barriers);
522  slopes[0].x = slopes[0].y = 0.0;
523  slopes[1].x = slopes[1].y = 0.0;
524  if (Proutespline(barriers, n_barriers, line, slopes, &spline) < 0) {
525  agerr (AGERR, "makeSpline: failed to make spline edge (%s,%s)\n", agnameof(agtail(e)), agnameof(aghead(e)));
526  return;
527  }
528 
529  /* north why did you ever use int coords */
530  if (Verbose > 1)
531  fprintf(stderr, "spline %s %s\n", agnameof(agtail(e)), agnameof(aghead(e)));
532  clip_and_install(e, aghead(e), spline.ps, spline.pn, &sinfo);
533  free(barriers);
534  addEdgeLabels(g, e, p, q);
535 }
536 
537  /* True if either head or tail has a port on its boundary */
538 #define BOUNDARY_PORT(e) ((ED_tail_port(e).side)||(ED_head_port(e).side))
539 
540 /* _spline_edges:
541  * Basic default routine for creating edges.
542  * If splines are requested, we construct the obstacles.
543  * If not, or nodes overlap, the function reverts to line segments.
544  * NOTE: intra-cluster edges are not constrained to
545  * remain in the cluster's bounding box and, conversely, a cluster's box
546  * is not altered to reflect intra-cluster edges.
547  * If Nop > 1 and the spline exists, it is just copied.
548  * NOTE: if edgetype = ET_NONE, we shouldn't be here.
549  */
550 static int _spline_edges(graph_t * g, expand_t* pmargin, int edgetype)
551 {
552  node_t *n;
553  edge_t *e;
554  edge_t *e0;
555  Ppoly_t **obs = 0;
556  Ppoly_t *obp;
557  int cnt, i = 0, npoly;
558  vconfig_t *vconfig = 0;
559  path *P = NULL;
560  int useEdges = (Nop > 1);
561  router_t* rtr = 0;
562  int legal = 0;
563 
564  /* build configuration */
565  if (edgetype >= ET_PLINE) {
566  obs = N_NEW(agnnodes(g), Ppoly_t *);
567  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
568  obp = makeObstacle(n, pmargin, edgetype == ET_ORTHO);
569  if (obp) {
570  ND_lim(n) = i;
571  obs[i++] = obp;
572  }
573  else
574  ND_lim(n) = POLYID_NONE;
575  }
576  } else {
577  obs = 0;
578  }
579  npoly = i;
580  if (obs) {
581  if ((legal = Plegal_arrangement(obs, npoly))) {
582  if (edgetype != ET_ORTHO) vconfig = Pobsopen(obs, npoly);
583  }
584  else {
585  if (edgetype == ET_ORTHO)
586  agerr(AGWARN, "the bounding boxes of some nodes touch - falling back to straight line edges\n");
587  else
588  agerr(AGWARN, "some nodes with margin (%.02f,%.02f) touch - falling back to straight line edges\n", pmargin->x, pmargin->y);
589  }
590  }
591 
592  /* route edges */
593  if (Verbose)
594  fprintf(stderr, "Creating edges using %s\n",
595  (legal && (edgetype == ET_ORTHO)) ? "orthogonal lines" :
596  (vconfig ? (edgetype == ET_SPLINE ? "splines" : "polylines") :
597  "line segments"));
598  if (vconfig) {
599  /* path-finding pass */
600  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
601  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
602  ED_path(e) = getPath(e, vconfig, TRUE, obs, npoly);
603  }
604  }
605  }
606 #ifdef ORTHO
607  else if (legal && (edgetype == ET_ORTHO)) {
608  orthoEdges (g, 0);
609  useEdges = 1;
610  }
611 #endif
612 
613  /* spline-drawing pass */
614  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
615  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
616 /* fprintf (stderr, "%s -- %s %d\n", agnameof(agtail(e)), agnameof(aghead(e)), ED_count(e)); */
617  node_t *head = aghead(e);
618  if (useEdges && ED_spl(e)) {
619  addEdgeLabels(g, e,
620  add_pointf(ND_coord(n), ED_tail_port(e).p),
621  add_pointf(ND_coord(head), ED_head_port(e).p));
622  }
623  else if (ED_count(e) == 0) continue; /* only do representative */
624  else if (n == head) { /* self arc */
625  if (!P) {
626  P = NEW(path);
627  P->boxes = N_NEW(agnnodes(g) + 20 * 2 * 9, boxf);
628  }
629  makeSelfArcs(P, e, GD_nodesep(g->root));
630  } else if (vconfig) { /* ET_SPLINE or ET_PLINE */
631 #ifdef HAVE_GTS
632  if ((ED_count(e) > 1) || BOUNDARY_PORT(e)) {
633  int fail = 0;
634  if ((ED_path(e).pn == 2) && !BOUNDARY_PORT(e))
635  /* if a straight line can connect the ends */
636  makeStraightEdge(g, e, edgetype, &sinfo);
637  else {
638  if (!rtr) rtr = mkRouter (obs, npoly);
639  fail = makeMultiSpline(g, e, rtr, edgetype == ET_PLINE);
640  }
641  if (!fail) continue;
642  }
643  /* We can probably remove this branch and just use
644  * makeMultiSpline. It can also catch the makeStraightEdge
645  * case. We could then eliminate all of the vconfig stuff.
646  */
647 #endif
648  cnt = ED_count(e);
649  if (Concentrate) cnt = 1; /* only do representative */
650  e0 = e;
651  for (i = 0; i < cnt; i++) {
652  if (edgetype == ET_SPLINE)
653  makeSpline(g, e0, obs, npoly, TRUE);
654  else
655  makePolyline(g, e0);
656  e0 = ED_to_virt(e0);
657  }
658  } else {
659  makeStraightEdge(g, e, edgetype, &sinfo);
660  }
661  }
662  }
663 
664 #ifdef HAVE_GTS
665  if (rtr)
666  freeRouter (rtr);
667 #endif
668 
669  if (vconfig)
670  Pobsclose (vconfig);
671  if (P) {
672  free(P->boxes);
673  free(P);
674  }
675  if (obs) {
676  for (i=0; i < npoly; i++)
677  free (obs[i]);
678  free (obs);
679  }
680  return 0;
681 }
682 
683 /* splineEdges:
684  * Main wrapper code for generating edges.
685  * Sets desired separation.
686  * Coalesces equivalent edges (edges * with the same endpoints).
687  * It then calls the edge generating function, and marks the
688  * spline phase complete.
689  * Returns 0 on success.
690  *
691  * The edge function is given the graph, the separation to be added
692  * around obstacles, and the type of edge. It must guarantee
693  * that all bounding boxes are current; in particular, the bounding box of
694  * g must reflect the addition of the edges.
695  */
696 int
697 splineEdges(graph_t * g, int (*edgefn) (graph_t *, expand_t*, int),
698  int edgetype)
699 {
700  node_t *n;
701  edge_t *e;
702  expand_t margin;
703  Dt_t *map;
704 
705  margin = esepFactor (g);
706 
707  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
708  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
709  resolvePorts (e);
710  }
711  }
712 
713  /* find equivalent edges */
714  map = dtopen(&edgeItemDisc, Dtoset);
715  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
716  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
717  if ((Nop > 1 && ED_spl(e))) {
718  /* If Nop > 1 (use given edges) and e has a spline, it
719  * should have its own equivalence class.
720  */
721  ED_count(e)++;
722  } else {
723  edge_t *leader = equivEdge(map, e);
724  if (leader != e) {
725  ED_count(leader)++;
726  ED_to_virt(e) = ED_to_virt(leader);
727  ED_to_virt(leader) = e;
728  }
729  }
730  }
731  }
732  dtclose(map);
733 
734  if (edgefn(g, &margin, edgetype))
735  return 1;
736 
737  State = GVSPLINES;
738  return 0;
739 }
740 
741 /* spline_edges1:
742  * Construct edges using default algorithm and given splines value.
743  * Return 0 on success.
744  */
745 int spline_edges1(graph_t * g, int edgetype)
746 {
747  return splineEdges(g, _spline_edges, edgetype);
748 }
749 
750 /* spline_edges0:
751  * Sets the graph's aspect ratio.
752  * Check splines attribute and construct edges using default algorithm.
753  * If the splines attribute is defined but equal to "", skip edge routing.
754  *
755  * Assumes u.bb for has been computed for g and all clusters
756  * (not just top-level clusters), and that GD_bb(g).LL is at the origin.
757  *
758  * This last criterion is, I believe, mainly to simplify the code
759  * in neato_set_aspect. It would be good to remove this constraint,
760  * as this would allow nodes pinned on input to have the same coordinates
761  * when output in dot or plain format.
762  *
763  */
764 void spline_edges0(graph_t * g, boolean set_aspect)
765 {
766  int et = EDGE_TYPE (g);
767  if (set_aspect) neato_set_aspect(g);
768  if (et == ET_NONE) return;
769 #ifndef ORTHO
770  if (et == ET_ORTHO) {
771  agerr (AGWARN, "Orthogonal edges not yet supported\n");
772  et = ET_PLINE;
773  GD_flags(g->root) &= ~ET_ORTHO;
774  GD_flags(g->root) |= ET_PLINE;
775  }
776 #endif
777  spline_edges1(g, et);
778 }
779 
780 /* shiftClusters:
781  */
782 static void
783 shiftClusters (graph_t * g, pointf offset)
784 {
785  int i;
786 
787  for (i = 1; i <= GD_n_cluster(g); i++) {
788  shiftClusters (GD_clust(g)[i], offset);
789  }
790 
791  GD_bb(g).UR.x -= offset.x;
792  GD_bb(g).UR.y -= offset.y;
793  GD_bb(g).LL.x -= offset.x;
794  GD_bb(g).LL.y -= offset.y;
795 }
796 
797 /* spline_edges:
798  * Compute bounding box, translate graph to origin,
799  * then construct all edges.
800  */
802 {
803  node_t *n;
804  pointf offset;
805 
806  compute_bb(g);
807  offset.x = PS2INCH(GD_bb(g).LL.x);
808  offset.y = PS2INCH(GD_bb(g).LL.y);
809  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
810  ND_pos(n)[0] -= offset.x;
811  ND_pos(n)[1] -= offset.y;
812  }
813 
814  shiftClusters (g, GD_bb(g).LL);
815  spline_edges0(g, TRUE);
816 }
817 
818 /* scaleEdge:
819  * Scale edge by given factor.
820  * Assume ED_spl != NULL.
821  */
822 static void scaleEdge(edge_t * e, double xf, double yf)
823 {
824  int i, j;
825  pointf *pt;
826  bezier *bez;
827  pointf delh, delt;
828 
829  delh.x = POINTS_PER_INCH * (ND_pos(aghead(e))[0] * (xf - 1.0));
830  delh.y = POINTS_PER_INCH * (ND_pos(aghead(e))[1] * (yf - 1.0));
831  delt.x = POINTS_PER_INCH * (ND_pos(agtail(e))[0] * (xf - 1.0));
832  delt.y = POINTS_PER_INCH * (ND_pos(agtail(e))[1] * (yf - 1.0));
833 
834  bez = ED_spl(e)->list;
835  for (i = 0; i < ED_spl(e)->size; i++) {
836  pt = bez->list;
837  for (j = 0; j < bez->size; j++) {
838  if ((i == 0) && (j == 0)) {
839  pt->x += delt.x;
840  pt->y += delt.y;
841  }
842  else if ((i == ED_spl(e)->size-1) && (j == bez->size-1)) {
843  pt->x += delh.x;
844  pt->y += delh.y;
845  }
846  else {
847  pt->x *= xf;
848  pt->y *= yf;
849  }
850  pt++;
851  }
852  if (bez->sflag) {
853  bez->sp.x += delt.x;
854  bez->sp.y += delt.y;
855  }
856  if (bez->eflag) {
857  bez->ep.x += delh.x;
858  bez->ep.y += delh.y;
859  }
860  bez++;
861  }
862 
863  if (ED_label(e) && ED_label(e)->set) {
864  ED_label(e)->pos.x *= xf;
865  ED_label(e)->pos.y *= yf;
866  }
867  if (ED_head_label(e) && ED_head_label(e)->set) {
868  ED_head_label(e)->pos.x += delh.x;
869  ED_head_label(e)->pos.y += delh.y;
870  }
871  if (ED_tail_label(e) && ED_tail_label(e)->set) {
872  ED_tail_label(e)->pos.x += delt.x;
873  ED_tail_label(e)->pos.y += delt.y;
874  }
875 }
876 
877 /* scaleBB:
878  * Scale bounding box of clusters of g by given factors.
879  */
880 static void scaleBB(graph_t * g, double xf, double yf)
881 {
882  int i;
883 
884  GD_bb(g).UR.x *= xf;
885  GD_bb(g).UR.y *= yf;
886  GD_bb(g).LL.x *= xf;
887  GD_bb(g).LL.y *= yf;
888 
889  if (GD_label(g) && GD_label(g)->set) {
890  GD_label(g)->pos.x *= xf;
891  GD_label(g)->pos.y *= yf;
892  }
893 
894  for (i = 1; i <= GD_n_cluster(g); i++)
895  scaleBB(GD_clust(g)[i], xf, yf);
896 }
897 
898 /* translateE:
899  * Translate edge by offset.
900  * Assume ED_spl(e) != NULL
901  */
902 static void translateE(edge_t * e, pointf offset)
903 {
904  int i, j;
905  pointf *pt;
906  bezier *bez;
907 
908  bez = ED_spl(e)->list;
909  for (i = 0; i < ED_spl(e)->size; i++) {
910  pt = bez->list;
911  for (j = 0; j < bez->size; j++) {
912  pt->x -= offset.x;
913  pt->y -= offset.y;
914  pt++;
915  }
916  if (bez->sflag) {
917  bez->sp.x -= offset.x;
918  bez->sp.y -= offset.y;
919  }
920  if (bez->eflag) {
921  bez->ep.x -= offset.x;
922  bez->ep.y -= offset.y;
923  }
924  bez++;
925  }
926 
927  if (ED_label(e) && ED_label(e)->set) {
928  ED_label(e)->pos.x -= offset.x;
929  ED_label(e)->pos.y -= offset.y;
930  }
931  if (ED_xlabel(e) && ED_xlabel(e)->set) {
932  ED_xlabel(e)->pos.x -= offset.x;
933  ED_xlabel(e)->pos.y -= offset.y;
934  }
935  if (ED_head_label(e) && ED_head_label(e)->set) {
936  ED_head_label(e)->pos.x -= offset.x;
937  ED_head_label(e)->pos.y -= offset.y;
938  }
939  if (ED_tail_label(e) && ED_tail_label(e)->set) {
940  ED_tail_label(e)->pos.x -= offset.x;
941  ED_tail_label(e)->pos.y -= offset.y;
942  }
943 }
944 
945 /* translateG:
946  */
947 static void translateG(Agraph_t * g, pointf offset)
948 {
949  int i;
950 
951  GD_bb(g).UR.x -= offset.x;
952  GD_bb(g).UR.y -= offset.y;
953  GD_bb(g).LL.x -= offset.x;
954  GD_bb(g).LL.y -= offset.y;
955 
956  if (GD_label(g) && GD_label(g)->set) {
957  GD_label(g)->pos.x -= offset.x;
958  GD_label(g)->pos.y -= offset.y;
959  }
960 
961  for (i = 1; i <= GD_n_cluster(g); i++)
962  translateG(GD_clust(g)[i], offset);
963 }
964 
965 /* neato_translate:
966  */
968 {
969  node_t *n;
970  edge_t *e;
971  pointf offset;
972  pointf ll;
973 
974  ll = GD_bb(g).LL;
975 
976  offset.x = PS2INCH(ll.x);
977  offset.y = PS2INCH(ll.y);
978  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
979  ND_pos(n)[0] -= offset.x;
980  ND_pos(n)[1] -= offset.y;
981  if (ND_xlabel(n) && ND_xlabel(n)->set) {
982  ND_xlabel(n)->pos.x -= ll.x;
983  ND_xlabel(n)->pos.y -= ll.y;
984  }
985  }
986  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
987  for (e = agfstout(g, n); e; e = agnxtout(g, e))
988  if (ED_spl(e))
989  translateE(e, ll);
990  }
991  translateG(g, ll);
992 }
993 
994 /* _neato_set_aspect;
995  * Assume all bounding boxes are correct.
996  * Return false if no transform is performed. This includes
997  * the possiblity that a translation was done.
998  */
999 static boolean _neato_set_aspect(graph_t * g)
1000 {
1001  double xf, yf, actual, desired;
1002  node_t *n;
1003  boolean translated = FALSE;
1004 
1005  if (g->root != g)
1006  return FALSE;
1007 
1008  /* compute_bb(g); */
1009  if (GD_drawing(g)->ratio_kind) {
1010  if (GD_bb(g).LL.x || GD_bb(g).LL.y) {
1011  translated = TRUE;
1012  neato_translate (g);
1013  }
1014  /* normalize */
1015  if (GD_flip(g)) {
1016  double t = GD_bb(g).UR.x;
1017  GD_bb(g).UR.x = GD_bb(g).UR.y;
1018  GD_bb(g).UR.y = t;
1019  }
1020  if (GD_drawing(g)->ratio_kind == R_FILL) {
1021  /* fill is weird because both X and Y can stretch */
1022  if (GD_drawing(g)->size.x <= 0)
1023  return (translated || FALSE);
1024  xf = (double) GD_drawing(g)->size.x / GD_bb(g).UR.x;
1025  yf = (double) GD_drawing(g)->size.y / GD_bb(g).UR.y;
1026  /* handle case where one or more dimensions is too big */
1027  if ((xf < 1.0) || (yf < 1.0)) {
1028  if (xf < yf) {
1029  yf = yf / xf;
1030  xf = 1.0;
1031  } else {
1032  xf = xf / yf;
1033  yf = 1.0;
1034  }
1035  }
1036  } else if (GD_drawing(g)->ratio_kind == R_EXPAND) {
1037  if (GD_drawing(g)->size.x <= 0)
1038  return (translated || FALSE);
1039  xf = (double) GD_drawing(g)->size.x / GD_bb(g).UR.x;
1040  yf = (double) GD_drawing(g)->size.y / GD_bb(g).UR.y;
1041  if ((xf > 1.0) && (yf > 1.0)) {
1042  double scale = MIN(xf, yf);
1043  xf = yf = scale;
1044  } else
1045  return (translated || FALSE);
1046  } else if (GD_drawing(g)->ratio_kind == R_VALUE) {
1047  desired = GD_drawing(g)->ratio;
1048  actual = (GD_bb(g).UR.y) / (GD_bb(g).UR.x);
1049  if (actual < desired) {
1050  yf = desired / actual;
1051  xf = 1.0;
1052  } else {
1053  xf = actual / desired;
1054  yf = 1.0;
1055  }
1056  } else
1057  return (translated || FALSE);
1058  if (GD_flip(g)) {
1059  double t = xf;
1060  xf = yf;
1061  yf = t;
1062  }
1063 
1064  if (Nop > 1) {
1065  edge_t *e;
1066  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1067  for (e = agfstout(g, n); e; e = agnxtout(g, e))
1068  if (ED_spl(e))
1069  scaleEdge(e, xf, yf);
1070  }
1071  }
1072  /* Not relying on neato_nlist here allows us not to have to
1073  * allocate it in the root graph and the connected components.
1074  */
1075  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1076  ND_pos(n)[0] = ND_pos(n)[0] * xf;
1077  ND_pos(n)[1] = ND_pos(n)[1] * yf;
1078  }
1079  scaleBB(g, xf, yf);
1080  return TRUE;
1081  }
1082  else
1083  return FALSE;
1084 }
1085 
1086 /* neato_set_aspect:
1087  * Sets aspect ratio if necessary; real work done in _neato_set_aspect;
1088  * This also copies the internal layout coordinates (ND_pos) to the
1089  * external ones (ND_coord).
1090  *
1091  * Return true if some node moved.
1092  */
1094 {
1095  node_t *n;
1096  boolean moved = FALSE;
1097 
1098  /* setting aspect ratio only makes sense on root graph */
1099  moved = _neato_set_aspect(g);
1100  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1101  ND_coord(n).x = POINTS_PER_INCH * (ND_pos(n)[0]);
1102  ND_coord(n).y = POINTS_PER_INCH * (ND_pos(n)[1]);
1103  }
1104  return moved;
1105 }
1106 
boolean doAdd
Definition: adjust.h:45
#define GD_label(g)
Definition: types.h:361
Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:494
Definition: cgraph.h:389
int eflag
Definition: types.h:111
#define ET_SPLINE
Definition: const.h:274
Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:502
#define N_NEW(n, t)
Definition: memory.h:36
edge_t * e
Definition: neatosplines.c:116
pointf p2
Definition: neatosplines.c:111
int pn
Definition: pathgeom.h:36
#define ND_xlabel(n)
Definition: types.h:471
int size
Definition: types.h:110
int option
Definition: types.h:149
#define head
Definition: dthdr.h:26
#define MIN(a, b)
Definition: arith.h:38
#define GD_n_cluster(g)
Definition: types.h:376
EXTERN int State
Definition: globals.h:89
node_t * n1
Definition: neatosplines.c:108
Definition: types.h:235
shape_kind shapeOf(node_t *)
Definition: shapes.c:1797
EXTERN int Nop
Definition: globals.h:79
void neato_translate(Agraph_t *g)
Definition: neatosplines.c:967
#define ED_head_port(e)
Definition: types.h:545
pointf p1
Definition: neatosplines.c:109
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
void spline_edges(graph_t *g)
Definition: neatosplines.c:801
double x
Definition: pathgeom.h:27
int Proutespline(Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route)
#define assert(x)
Definition: cghdr.h:48
Definition: render.h:54
Definition: geom.h:30
#define NOTUSED(var)
Definition: cghdr.h:68
Definition: cdt.h:95
#define ED_label(e)
Definition: types.h:546
#define GD_flags(g)
Definition: types.h:349
Ppoly_t * makeObstacle(node_t *n, expand_t *pmargin, boolean isOrtho)
Definition: neatosplines.c:269
#define offsetof(typ, fld)
Definition: cghdr.h:66
void make_polyline(Ppolyline_t line, Ppolyline_t *sline)
Definition: util.c:82
void clip_and_install(edge_t *fe, node_t *hn, pointf *ps, int pn, splineInfo *info)
Definition: splines.c:241
int agnnodes(Agraph_t *g)
#define EDGE_TYPE(g)
Definition: macros.h:33
Definition: types.h:216
#define GVSPLINES
Definition: const.h:181
#define ND_pos(n)
Definition: types.h:487
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:142
#define FIXEDSHAPE
Definition: const.h:220
router_t * mkRouter(Ppoly_t **obsp, int npoly)
Definition: multispline.c:694
Ppoint_t b
Definition: pathgeom.h:42
boxf b
Definition: types.h:237
#define ND_shape_info(n)
Definition: types.h:496
#define ED_tail_label(e)
Definition: types.h:553
boxf * boxes
Definition: types.h:104
int makeMultiSpline(graph_t *g, edge_t *e, router_t *rtr, int doPolyline)
Definition: multispline.c:1341
Definition: cgraph.h:389
void addEdgeLabels(graph_t *g, edge_t *e, pointf rp, pointf rq)
Definition: splines.c:1355
Dtdisc_t edgeItemDisc
Definition: neatosplines.c:160
#define ED_tail_port(e)
Definition: types.h:554
#define ED_spl(e)
Definition: types.h:552
#define ND_ht(n)
Definition: types.h:467
void free()
int i
Definition: gvdevice.c:448
int in_poly(Ppoly_t argpoly, Ppoint_t q)
Definition: inpoly.c:29
double y
Definition: geom.h:30
int sflag
Definition: types.h:111
int spline_edges1(graph_t *g, int edgetype)
Definition: neatosplines.c:745
#define ET_PLINE
Definition: const.h:272
Definition: types.h:182
vconfig_t * Pobsopen(Ppoly_t **obs, int n_obs)
Definition: cvt.c:62
#define ET_NONE
Definition: const.h:269
#define ED_count(e)
Definition: types.h:538
void makeSpline(graph_t *g, edge_t *e, Ppoly_t **obs, int npoly, boolean chkPts)
Definition: neatosplines.c:499
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
float y
Definition: adjust.h:44
pointf sp
Definition: types.h:112
void Pobsclose(vconfig_t *config)
Definition: cvt.c:104
#define ND_rw(n)
Definition: types.h:492
Dtmethod_t * Dtoset
void makePortLabels(edge_t *e)
Definition: splines.c:1237
void compute_bb(graph_t *g)
Definition: utils.c:849
Ppolyline_t getPath(edge_t *e, vconfig_t *vconfig, int chkPts, Ppoly_t **obs, int npoly)
Definition: neatosplines.c:444
int sides
Definition: types.h:145
pointf * list
Definition: types.h:109
boolean neato_set_aspect(graph_t *g)
expand_t esepFactor(graph_t *g)
Definition: adjust.c:1297
Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
Definition: grammar.c:79
#define GD_clust(g)
Definition: types.h:344
#define ND_lim(n)
Definition: types.h:472
#define GD_flip(g)
Definition: types.h:365
double drand48(void)
Definition: utils.c:1965
Ppoint_t * ps
Definition: pathgeom.h:35
#define POLYID_NONE
Definition: vispath.h:47
#define dtinsert(d, o)
Definition: cdt.h:311
pointf ep
Definition: types.h:112
Definition: types.h:216
#define ED_to_virt(e)
Definition: types.h:556
#define ND_lw(n)
Definition: types.h:474
int splineEdges(graph_t *g, int(*edgefn)(graph_t *, expand_t *, int), int edgetype)
Definition: neatosplines.c:697
EXTERN unsigned char Concentrate
Definition: globals.h:85
Agraph_t * agraphof(void *obj)
Definition: obj.c:185
#define NULL
Definition: logic.h:50
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define ED_head_label(e)
Definition: types.h:544
double x
Definition: geom.h:30
#define ED_xlabel(e)
Definition: types.h:547
#define ND_coord(n)
Definition: types.h:457
Definition: types.h:182
EXTERN unsigned char Verbose
Definition: globals.h:73
void makeSelfEdge(path *P, edge_t *edges[], int ind, int cnt, double sizex, double sizey, splineInfo *sinfo)
Definition: splines.c:1191
Definition: types.h:108
char * agnameof(void *)
Definition: id.c:143
Ppoint_t a
Definition: pathgeom.h:42
pointf LL
Definition: geom.h:37
Definition: types.h:101
void makeStraightEdge(graph_t *g, edge_t *e, int edgetype, splineInfo *info)
Definition: routespl.c:936
void updateBB(graph_t *g, textlabel_t *lp)
Definition: utils.c:839
#define ED_path(e)
Definition: types.h:550
Dt_t * dtopen(Dtdisc_t *disc, Dtmethod_t *meth)
Definition: dtopen.c:12
void makeSelfArcs(path *P, edge_t *e, int stepx)
Definition: neatosplines.c:228
int Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route)
Definition: cvt.c:117
node_t * n2
Definition: neatosplines.c:110
Dtlink_t link
Definition: neatosplines.c:114
Definition: cdt.h:120
pointf * vertices
Definition: types.h:150
#define GD_bb(g)
Definition: types.h:337
Definition: pathgeom.h:26
#define M_PI
Definition: arith.h:80
#define GD_nodesep(g)
Definition: types.h:382
boxf polyBB(polygon_t *poly)
Definition: utils.c:818
void resolvePorts(edge_t *e)
Definition: shapes.c:4079
double y
Definition: pathgeom.h:27
int dtclose(reg Dt_t *dt)
Definition: dtclose.c:8
Agraph_t * root
Definition: cgraph.h:241
#define GD_drawing(g)
Definition: types.h:336
edgeinfo id
Definition: neatosplines.c:115
float x
Definition: adjust.h:44
void freeRouter(router_t *rtr)
Definition: multispline.c:638
Definition: vis.h:38
pointf UR
Definition: geom.h:37
void printvis(vconfig_t *cp)
Definition: printvis.c:19
#define BOUNDARY_PORT(e)
Definition: neatosplines.c:538
Definition: geom.h:37
#define N_GNEW(n, t)
Definition: agxbuf.c:20
#define FALSE
Definition: cgraph.h:24
void spline_edges0(graph_t *g, boolean set_aspect)
Definition: neatosplines.c:764
#define ET_ORTHO
Definition: const.h:273
#define NEW(t)
Definition: memory.h:35
#define TRUE
Definition: cgraph.h:27