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