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/* vladimir@cs.ualberta.ca, 9-Dec-1997
16 * merge edges with specified samehead/sametail onto the same port
17 */
18
19#include "dot.h"
20
21
22#define MAXSAME 5 /* max no of same{head,tail} groups on a node */
23
24typedef struct same_t {
25 char *id; /* group id */
26 elist l; /* edges in the group */
27 int n_arr; /* number of edges with arrows */
28 double arr_len; /* arrow length of an edge in the group */
29} same_t;
30
31static int sameedge(same_t * same, int n_same, node_t * n, edge_t * e, char *id);
32static void sameport(node_t * u, elist * l, double arr_len);
33
34void dot_sameports(graph_t * g)
35/* merge edge ports in G */
36{
37 node_t *n;
38 edge_t *e;
39 char *id;
40 same_t samehead[MAXSAME];
41 same_t sametail[MAXSAME];
42 int n_samehead; /* number of same_t groups on current node */
43 int n_sametail; /* number of same_t groups on current node */
44 int i;
45
46 E_samehead = agattr(g, AGEDGE, "samehead",(char*)0);
47 E_sametail = agattr(g, AGEDGE, "sametail",(char*)0);
48 if (!(E_samehead || E_sametail))
49 return;
50 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
51 n_samehead = n_sametail = 0;
52 for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
53 if (aghead(e) == agtail(e)) continue; /* Don't support same* for loops */
54 if (aghead(e) == n && E_samehead &&
55 (id = agxget(e, E_samehead))[0])
56 n_samehead = sameedge(samehead, n_samehead, n, e, id);
57 else if (agtail(e) == n && E_sametail &&
58 (id = agxget(e, E_sametail))[0])
59 n_sametail = sameedge(sametail, n_sametail, n, e, id);
60 }
61 for (i = 0; i < n_samehead; i++) {
62 if (samehead[i].l.size > 1)
63 sameport(n, &samehead[i].l, samehead[i].arr_len);
64 free_list(samehead[i].l);
65 /* I sure hope I don't need to free the char* id */
66 }
67 for (i = 0; i < n_sametail; i++) {
68 if (sametail[i].l.size > 1)
69 sameport(n, &sametail[i].l, sametail[i].arr_len);
70 free_list(sametail[i].l);
71 /* I sure hope I don't need to free the char* id */
72 }
73 }
74}
75
76static int sameedge(same_t * same, int n_same, node_t * n, edge_t * e, char *id)
77/* register E in the SAME structure of N under ID. Uses static int N_SAME */
78{
79 int i, sflag, eflag, flag;
80
81 for (i = 0; i < n_same; i++)
82 if (streq(same[i].id, id)) {
83 elist_append(e, same[i].l);
84 goto set_arrow;
85 }
86 if (++n_same > MAXSAME) {
87 n_same--;
88 agerr(AGERR, "too many (> %d) same{head,tail} groups for node %s\n",
89 MAXSAME, agnameof(n));
90 return n_same;
91 }
92 alloc_elist(1, same[i].l);
93 elist_fastapp(e, same[i].l);
94 same[i].id = id;
95 same[i].n_arr = 0;
96 same[i].arr_len = 0;
97 set_arrow:
98 arrow_flags(e, &sflag, &eflag);
99 if ((flag = aghead(e) == n ? eflag : sflag))
100 same[i].arr_len =
101 /* only consider arrows if there's exactly one arrow */
102 (++same[i].n_arr == 1) ? arrow_length(e, flag) : 0;
103 return n_same;
104}
105
106static void sameport(node_t * u, elist * l, double arr_len)
107/* make all edges in L share the same port on U. The port is placed on the
108 node boundary and the average angle between the edges. FIXME: this assumes
109 naively that the edges are straight lines, which is wrong if they are long.
110 In that case something like concentration could be done.
111
112 An arr_port is also computed that's ARR_LEN away from the node boundary.
113 It's used for edges that don't themselves have an arrow.
114*/
115{
116 node_t *v;
117 edge_t *e, *f;
118 int i;
119 double x = 0, y = 0, x1, y1, x2, y2, r;
120 port prt;
121 int sflag, eflag;
122#ifdef OLD
123 int ht;
124 port arr_prt;
125#endif
126
127 /* Compute the direction vector (x,y) of the average direction. We compute
128 with direction vectors instead of angles because else we have to first
129 bring the angles within PI of each other. av(a,b)!=av(a,b+2*PI) */
130 for (i = 0; i < l->size; i++) {
131 e = l->list[i];
132 if (aghead(e) == u)
133 v = agtail(e);
134 else
135 v = aghead(e);
136 x1 = ND_coord(v).x - ND_coord(u).x;
137 y1 = ND_coord(v).y - ND_coord(u).y;
138 r = hypot(x1, y1);
139 x += x1 / r;
140 y += y1 / r;
141 }
142 r = hypot(x, y);
143 x /= r;
144 y /= r;
145
146 /* (x1,y1),(x2,y2) is a segment that must cross the node boundary */
147 x1 = ND_coord(u).x;
148 y1 = ND_coord(u).y; /* center of node */
149 r = MAX(ND_lw(u) + ND_rw(u), ND_ht(u) + GD_ranksep(agraphof(u))); /* far away */
150 x2 = x * r + ND_coord(u).x;
151 y2 = y * r + ND_coord(u).y;
152 { /* now move (x1,y1) to the node boundary */
153 pointf curve[4]; /* bezier control points for a straight line */
154 curve[0].x = x1;
155 curve[0].y = y1;
156 curve[1].x = (2 * x1 + x2) / 3;
157 curve[1].y = (2 * y1 + y2) / 3;
158 curve[2].x = (2 * x2 + x1) / 3;
159 curve[2].y = (2 * y2 + y1) / 3;
160 curve[3].x = x2;
161 curve[3].y = y2;
162
163 shape_clip(u, curve);
164 x1 = curve[0].x - ND_coord(u).x;
165 y1 = curve[0].y - ND_coord(u).y;
166 }
167
168 /* compute PORT on the boundary */
169 prt.p.x = ROUND(x1);
170 prt.p.y = ROUND(y1);
171 prt.bp = 0;
172 prt.order =
173 (MC_SCALE * (ND_lw(u) + prt.p.x)) / (ND_lw(u) + ND_rw(u));
174 prt.constrained = FALSE;
175 prt.defined = TRUE;
176 prt.clip = FALSE;
177 prt.dyna = FALSE;
178 prt.theta = 0;
179 prt.side = 0;
180 prt.name = NULL;
181
182#ifdef OBSOLETE
183/* This is commented because a version of gcc cannot handle it otherwise.
184This code appears obsolete and wrong. First, we don't use arr_prt
185anymore, as we have previously ifdef'ed out the code below where it
186is used. In addition, it resets the rank height. But we've already
187positioned the nodes, so it can cause the new ht2, when added to a
188node's y coordinate to give a value in the middle of the rank above.
189This causes havoc when constructing box for spline routing.
190See bug 419.
191If we really want to make room for arrowheads, this should be done in
192the general case that the user sets a small ranksep, and requires repositioning
193nodes and maintaining equal separation when specified
194*/
195 /* compute ARR_PORT at a distance ARR_LEN away from the boundary */
196 if ((arr_prt.defined = arr_len && TRUE)) {
197 arr_prt.p.x = ROUND(x1 + x * arr_len);
198 arr_prt.p.y = ROUND(y1 + y * arr_len);
199 arr_prt.bp = 0;
200 arr_prt.side = 0;
201 arr_prt.constrained = FALSE;
202 arr_prt.order =
203 (MC_SCALE * (ND_lw_i(u) + arr_prt.p.x)) / (ND_lw_i(u) +
204 ND_rw_i(u));
205 /* adjust ht so that splines.c uses feasible boxes.
206 FIXME: I guess this adds an extra box for all edges in the rank */
207 if (u == l->list[0]->head) {
208 if (GD_rank(u->graph)[ND_rank(u)].ht2 <
209 (ht = ABS(arr_prt.p.y)))
210 GD_rank(u->graph)[ND_rank(u)].ht2 = ht;
211 } else {
212 if (GD_rank(u->graph)[ND_rank(u)].ht1 <
213 (ht = ABS(arr_prt.p.y)))
214 GD_rank(u->graph)[ND_rank(u)].ht1 = ht;
215 }
216 }
217#endif
218
219 /* assign one of the ports to every edge */
220 for (i = 0; i < l->size; i++) {
221 e = l->list[i];
222 arrow_flags(e, &sflag, &eflag);
223#ifndef OBSOLETE
224 for (; e; e = ED_to_virt(e)) { /* assign to all virt edges of e */
225 for (f = e; f;
226 f = ED_edge_type(f) == VIRTUAL &&
227 ND_node_type(aghead(f)) == VIRTUAL &&
228 ND_out(aghead(f)).size == 1 ?
229 ND_out(aghead(f)).list[0] : NULL) {
230 if (aghead(f) == u)
231 ED_head_port(f) = prt;
232 if (agtail(f) == u)
233 ED_tail_port(f) = prt;
234 }
235 for (f = e; f;
236 f = ED_edge_type(f) == VIRTUAL &&
237 ND_node_type(agtail(f)) == VIRTUAL &&
238 ND_in(agtail(f)).size == 1 ?
239 ND_in(agtail(f)).list[0] : NULL) {
240 if (aghead(f) == u)
241 ED_head_port(f) = prt;
242 if (agtail(f) == u)
243 ED_tail_port(f) = prt;
244 }
245 }
246#else
247 for (; e; e = ED_to_virt(e)) { /* assign to all virt edges of e */
248 if (aghead(e) == u)
249 ED_head_port(e) =
250 arr_port.defined && !eflag ? arr_prt : prt;
251 if (agtail(e) == u)
252 ED_tail_port(e) =
253 arr_port.defined && !sflag ? arr_prt : prt;
254 }
255#endif
256 }
257
258 ND_has_port(u) = TRUE; /* kinda pointless, because mincross is already done */
259}
260