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