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