Graphviz  2.39.20141221.0545
flat.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 
15 #include "dot.h"
16 
17 
18 static 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 
41 static 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 
55 static 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 
101 static 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  */
135 static void
136 flat_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 
185 static 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  */
210 static void
211 checkFlatAdjacent (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  */
259 int
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 }
#define MAX(a, b)
Definition: agerror.c:17
#define ND_rank(n)
Definition: types.h:490
Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:494
#define GD_nlist(g)
Definition: types.h:381
Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:502
#define N_NEW(n, t)
Definition: memory.h:36
#define FLATORDER
Definition: const.h:31
#define GD_n_cluster(g)
Definition: types.h:376
#define ND_node_type(n)
Definition: types.h:479
#define ALLOC(size, ptr, type)
Definition: memory.h:41
#define ED_head_port(e)
Definition: types.h:545
#define ND_flat_in(n)
Definition: types.h:459
#define assert(x)
Definition: cghdr.h:48
void rec_reset_vlists(Agraph_t *)
Definition: mincross.c:1089
Agnode_t * virtual_node(Agraph_t *)
Definition: fastgr.c:240
Definition: geom.h:30
void checkLabelOrder(graph_t *g)
Definition: mincross.c:286
#define ED_label(e)
Definition: types.h:546
#define ND_label(n)
Definition: types.h:470
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition: fastgr.c:199
#define GD_ranksep(g)
Definition: types.h:386
#define ED_adjacent(e)
Definition: types.h:541
int flat_edges(graph_t *g)
Definition: flat.c:260
#define ED_tail_port(e)
Definition: types.h:554
int rank(graph_t *g, int balance, int maxiter)
Definition: ns.c:681
#define le
Definition: edges.h:32
#define ND_ht(n)
Definition: types.h:467
int i
Definition: gvdevice.c:448
double y
Definition: geom.h:30
#define ND_order(n)
Definition: types.h:481
#define VIRTUAL
Definition: const.h:28
#define GD_maxrank(g)
Definition: types.h:369
#define ND_rw(n)
Definition: types.h:492
#define SLB
Definition: flat.c:38
#define HRB
Definition: flat.c:37
#define GD_flip(g)
Definition: types.h:365
Agraph_t * dot_root(void *p)
Definition: dotinit.c:510
void rec_save_vlists(Agraph_t *)
Definition: mincross.c:1079
#define ED_to_virt(e)
Definition: types.h:556
#define ND_lw(n)
Definition: types.h:474
#define ND_alg(n)
Definition: types.h:451
#define NULL
Definition: logic.h:50
node_t ** v
Definition: types.h:204
double x
Definition: geom.h:30
#define ND_in(n)
Definition: types.h:468
#define ND_coord(n)
Definition: types.h:457
#define ND_next(n)
Definition: types.h:478
#define ND_out(n)
Definition: types.h:483
#define SRB
Definition: flat.c:39
#define HLB
Definition: flat.c:36
#define ND_other(n)
Definition: types.h:482
#define GD_minrank(g)
Definition: types.h:371
#define ND_flat_out(n)
Definition: types.h:460
#define GD_rank(g)
Definition: types.h:384
Definition: types.h:202
#define NORMAL
Definition: const.h:27
#define ED_edge_type(e)
Definition: types.h:540
#define ED_dist(e)
Definition: types.h:559
#define FALSE
Definition: cgraph.h:24
#define TRUE
Definition: cgraph.h:27