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