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#include "dot.h"
16
17
18static node_t *make_vn_slot(graph_t * g, int r, int pos)
19{
20 int i;
21 node_t **v, *n;
22
23 v = GD_rank(g)[r].v =
24 ALLOC(GD_rank(g)[r].n + 2, GD_rank(g)[r].v, node_t *);
25 for (i = GD_rank(g)[r].n; i > pos; i--) {
26 v[i] = v[i - 1];
27 ND_order(v[i])++;
28 }
29 n = v[pos] = virtual_node(g);
30 ND_order(n) = pos;
31 ND_rank(n) = r;
32 v[++(GD_rank(g)[r].n)] = NULL;
33 return v[pos];
34}
35
36#define HLB 0 /* hard left bound */
37#define HRB 1 /* hard right bound */
38#define SLB 2 /* soft left bound */
39#define SRB 3 /* soft right bound */
40
41static void findlr(node_t * u, node_t * v, int *lp, int *rp)
42{
43 int l, r;
44 l = ND_order(u);
45 r = ND_order(v);
46 if (l > r) {
47 int t = l;
48 l = r;
49 r = t;
50 }
51 *lp = l;
52 *rp = r;
53}
54
55static void setbounds(node_t * v, int *bounds, int lpos, int rpos)
56{
57 int i, l, r, ord;
58 edge_t *f;
59
60 if (ND_node_type(v) == VIRTUAL) {
61 ord = ND_order(v);
62 if (ND_in(v).size == 0) { /* flat */
63 assert(ND_out(v).size == 2);
64 findlr(aghead(ND_out(v).list[0]), aghead(ND_out(v).list[1]), &l,
65 &r);
66 /* the other flat edge could be to the left or right */
67 if (r <= lpos)
68 bounds[SLB] = bounds[HLB] = ord;
69 else if (l >= rpos)
70 bounds[SRB] = bounds[HRB] = ord;
71 /* could be spanning this one */
72 else if ((l < lpos) && (r > rpos)); /* ignore */
73 /* must have intersecting ranges */
74 else {
75 if ((l < lpos) || ((l == lpos) && (r < rpos)))
76 bounds[SLB] = ord;
77 if ((r > rpos) || ((r == rpos) && (l > lpos)))
78 bounds[SRB] = ord;
79 }
80 } else { /* forward */
81 boolean onleft, onright;
82 onleft = onright = FALSE;
83 for (i = 0; (f = ND_out(v).list[i]); i++) {
84 if (ND_order(aghead(f)) <= lpos) {
85 onleft = TRUE;
86 continue;
87 }
88 if (ND_order(aghead(f)) >= rpos) {
89 onright = TRUE;
90 continue;
91 }
92 }
93 if (onleft && (onright == FALSE))
94 bounds[HLB] = ord + 1;
95 if (onright && (onleft == FALSE))
96 bounds[HRB] = ord - 1;
97 }
98 }
99}
100
101static int flat_limits(graph_t * g, edge_t * e)
102{
103 int lnode, rnode, r, bounds[4], lpos, rpos, pos;
104 node_t **rank;
105
106 r = ND_rank(agtail(e)) - 1;
107 rank = GD_rank(g)[r].v;
108 lnode = 0;
109 rnode = GD_rank(g)[r].n - 1;
110 bounds[HLB] = bounds[SLB] = lnode - 1;
111 bounds[HRB] = bounds[SRB] = rnode + 1;
112 findlr(agtail(e), aghead(e), &lpos, &rpos);
113 while (lnode <= rnode) {
114 setbounds(rank[lnode], bounds, lpos, rpos);
115 if (lnode != rnode)
116 setbounds(rank[rnode], bounds, lpos, rpos);
117 lnode++;
118 rnode--;
119 if (bounds[HRB] - bounds[HLB] <= 1)
120 break;
121 }
122 if (bounds[HLB] <= bounds[HRB])
123 pos = (bounds[HLB] + bounds[HRB] + 1) / 2;
124 else
125 pos = (bounds[SLB] + bounds[SRB] + 1) / 2;
126 return pos;
127}
128
129/* flat_node:
130 * Create virtual node representing edge label between
131 * actual ends of edge e.
132 * This node is characterized by being virtual and having a non-NULL
133 * ND_alg pointing to e.
134 */
135static void
136flat_node(edge_t * e)
137{
138 int r, place, ypos, h2;
139 graph_t *g;
140 node_t *n, *vn;
141 edge_t *ve;
142 pointf dimen;
143
144 if (ED_label(e) == NULL)
145 return;
146 g = dot_root(agtail(e));
147 r = ND_rank(agtail(e));
148
149 place = flat_limits(g, e);
150 /* grab ypos = LL.y of label box before make_vn_slot() */
151 if ((n = GD_rank(g)[r - 1].v[0]))
152 ypos = ND_coord(n).y - GD_rank(g)[r - 1].ht1;
153 else {
154 n = GD_rank(g)[r].v[0];
155 ypos = ND_coord(n).y + GD_rank(g)[r].ht2 + GD_ranksep(g);
156 }
157 vn = make_vn_slot(g, r - 1, place);
158 dimen = ED_label(e)->dimen;
159 if (GD_flip(g)) {
160 double f = dimen.x;
161 dimen.x = dimen.y;
162 dimen.y = f;
163 }
164 ND_ht(vn) = dimen.y;
165 h2 = ND_ht(vn) / 2;
166 ND_lw(vn) = ND_rw(vn) = dimen.x / 2;
167 ND_label(vn) = ED_label(e);
168 ND_coord(vn).y = ypos + h2;
169 ve = virtual_edge(vn, agtail(e), e); /* was NULL? */
170 ED_tail_port(ve).p.x = -ND_lw(vn);
171 ED_head_port(ve).p.x = ND_rw(agtail(e));
172 ED_edge_type(ve) = FLATORDER;
173 ve = virtual_edge(vn, aghead(e), e);
174 ED_tail_port(ve).p.x = ND_rw(vn);
175 ED_head_port(ve).p.x = ND_lw(aghead(e));
176 ED_edge_type(ve) = FLATORDER;
177 /* another assumed symmetry of ht1/ht2 of a label node */
178 if (GD_rank(g)[r - 1].ht1 < h2)
179 GD_rank(g)[r - 1].ht1 = h2;
180 if (GD_rank(g)[r - 1].ht2 < h2)
181 GD_rank(g)[r - 1].ht2 = h2;
182 ND_alg(vn) = e;
183}
184
185static void abomination(graph_t * g)
186{
187 int r;
188 rank_t *rptr;
189
190 assert(GD_minrank(g) == 0);
191 /* 3 = one for new rank, one for sentinel, one for off-by-one */
192 r = GD_maxrank(g) + 3;
193 rptr = ALLOC(r, GD_rank(g), rank_t);
194 GD_rank(g) = rptr + 1;
195 for (r = GD_maxrank(g); r >= 0; r--)
196 GD_rank(g)[r] = GD_rank(g)[r - 1];
197 GD_rank(g)[r].n = GD_rank(g)[r].an = 0;
198 GD_rank(g)[r].v = GD_rank(g)[r].av = N_NEW(2, node_t *);
199 GD_rank(g)[r].flat = NULL;
200 GD_rank(g)[r].ht1 = GD_rank(g)[r].ht2 = 1;
201 GD_rank(g)[r].pht1 = GD_rank(g)[r].pht2 = 1;
202 GD_minrank(g)--;
203}
204
205/* checkFlatAdjacent:
206 * Check if tn and hn are adjacent.
207 * If so, set adjacent bit on all related edges.
208 * Assume e is flat.
209 */
210static void
211checkFlatAdjacent (edge_t* e)
212{
213 node_t* tn = agtail(e);
214 node_t* hn = aghead(e);
215 int i, lo, hi;
216 node_t* n;
217 rank_t *rank;
218
219 if (ND_order(tn) < ND_order(hn)) {
220 lo = ND_order(tn);
221 hi = ND_order(hn);
222 }
223 else {
224 lo = ND_order(hn);
225 hi = ND_order(tn);
226 }
227 rank = &(GD_rank(dot_root(tn))[ND_rank(tn)]);
228 for (i = lo + 1; i < hi; i++) {
229 n = rank->v[i];
230 if ((ND_node_type(n) == VIRTUAL && ND_label(n)) ||
231 ND_node_type(n) == NORMAL)
232 break;
233 }
234 if (i == hi) { /* adjacent edge */
235 do {
236 ED_adjacent(e) = 1;
237 e = ED_to_virt(e);
238 } while (e);
239 }
240}
241
242/* flat_edges:
243 * Process flat edges.
244 * First, mark flat edges as having adjacent endpoints or not.
245 *
246 * Second, if there are edge labels, nodes are placed on ranks 0,2,4,...
247 * If we have a labeled flat edge on rank 0, add a rank -1.
248 *
249 * Finally, create label information. Add a virtual label node in the
250 * previous rank for each labeled, non-adjacent flat edge. If this is
251 * done for any edge, return true, so that main code will reset y coords.
252 * For labeled adjacent flat edges, store label width in representative edge.
253 * FIX: We should take into account any extra height needed for the latter
254 * labels.
255 *
256 * We leave equivalent flat edges in ND_other. Their ED_virt field should
257 * still point to the class representative.
258 */
259int
260flat_edges(graph_t * g)
261{
262 int i, j, reset = FALSE;
263 node_t *n;
264 edge_t *e;
265 int found = FALSE;
266
267 for (n = GD_nlist(g); n; n = ND_next(n)) {
268 if (ND_flat_out(n).list) {
269 for (j = 0; (e = ND_flat_out(n).list[j]); j++) {
270 checkFlatAdjacent (e);
271 }
272 }
273 for (j = 0; j < ND_other(n).size; j++) {
274 e = ND_other(n).list[j];
275 if (ND_rank(aghead(e)) == ND_rank(agtail(e)))
276 checkFlatAdjacent (e);
277 }
278 }
279
280 if ((GD_rank(g)[0].flat) || (GD_n_cluster(g) > 0)) {
281 for (i = 0; (n = GD_rank(g)[0].v[i]); i++) {
282 for (j = 0; (e = ND_flat_in(n).list[j]); j++) {
283 if ((ED_label(e)) && !ED_adjacent(e)) {
284 abomination(g);
285 found = TRUE;
286 break;
287 }
288 }
289 if (found)
290 break;
291 }
292 }
293
294 rec_save_vlists(g);
295 for (n = GD_nlist(g); n; n = ND_next(n)) {
296 /* if n is the tail of any flat edge, one will be in flat_out */
297 if (ND_flat_out(n).list) {
298 for (i = 0; (e = ND_flat_out(n).list[i]); i++) {
299 if (ED_label(e)) {
300 if (ED_adjacent(e)) {
301 if (GD_flip(g)) ED_dist(e) = ED_label(e)->dimen.y;
302 else ED_dist(e) = ED_label(e)->dimen.x;
303 }
304 else {
305 reset = TRUE;
306 flat_node(e);
307 }
308 }
309 }
310 /* look for other flat edges with labels */
311 for (j = 0; j < ND_other(n).size; j++) {
312 edge_t* le;
313 e = ND_other(n).list[j];
314 if (ND_rank(agtail(e)) != ND_rank(aghead(e))) continue;
315 if (agtail(e) == aghead(e)) continue; /* skip loops */
316 le = e;
317 while (ED_to_virt(le)) le = ED_to_virt(le);
318 ED_adjacent(e) = ED_adjacent(le);
319 if (ED_label(e)) {
320 if (ED_adjacent(e)) {
321 double lw;
322 if (GD_flip(g)) lw = ED_label(e)->dimen.y;
323 else lw = ED_label(e)->dimen.x;
324 ED_dist(le) = MAX(lw,ED_dist(le));
325 }
326 else {
327 reset = TRUE;
328 flat_node(e);
329 }
330 }
331 }
332 }
333 }
334 if (reset) {
335 checkLabelOrder(g);
336 rec_reset_vlists(g);
337 }
338 return reset;
339}
340