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