Graphviz  2.35.20130930.0449
class2.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 /* classify edges for mincross/nodepos/splines, using given ranks */
16 
17 #include "dot.h"
18 
19 static node_t*
20 label_vnode(graph_t * g, edge_t * orig)
21 {
22  node_t *v;
23  pointf dimen;
24 
25  dimen = ED_label(orig)->dimen;
26  v = virtual_node(g);
27  ND_label(v) = ED_label(orig);
28  ND_lw(v) = GD_nodesep(agroot(agraphof(v)));
29  if (!ED_label_ontop(orig)) {
30  if (GD_flip(agroot(g))) {
31  ND_ht(v) = dimen.x;
32  ND_rw(v) = dimen.y;
33  } else {
34  ND_ht(v) = dimen.y;
35  ND_rw(v) = dimen.x;
36  }
37  }
38  return v;
39 }
40 
41 static void
42 incr_width(graph_t * g, node_t * v)
43 {
44  int width = GD_nodesep(g) / 2;
45  ND_lw(v) += width;
46  ND_rw(v) += width;
47 }
48 
49 static node_t*
50 plain_vnode(graph_t * g, edge_t * orig)
51 {
52  node_t *v;
53  orig = orig;
54  v = virtual_node(g);
55  incr_width(g, v);
56  return v;
57 }
58 
59 static node_t*
60 leader_of(graph_t * g, node_t * v)
61 {
62  graph_t *clust;
63  node_t *rv;
64 
65  if (ND_ranktype(v) != CLUSTER) {
66  /*assert(v == UF_find(v)); could be leaf, so comment out */
67  rv = UF_find(v);
68  } else {
69  clust = ND_clust(v);
70  rv = GD_rankleader(clust)[ND_rank(v)];
71  }
72  return rv;
73 }
74 
75 /* make_chain:
76  * Create chain of dummy nodes for edge orig.
77  */
78 static void
79 make_chain(graph_t * g, node_t * from, node_t * to, edge_t * orig)
80 {
81  int r, label_rank;
82  node_t *u, *v;
83  edge_t *e;
84 
85  u = from;
86  if (ED_label(orig))
87  label_rank = (ND_rank(from) + ND_rank(to)) / 2;
88  else
89  label_rank = -1;
90  assert(ED_to_virt(orig) == NULL);
91  for (r = ND_rank(from) + 1; r <= ND_rank(to); r++) {
92  if (r < ND_rank(to)) {
93  if (r == label_rank)
94  v = label_vnode(g, orig);
95  else
96  v = plain_vnode(g, orig);
97  ND_rank(v) = r;
98  } else
99  v = to;
100  e = virtual_edge(u, v, orig);
101  virtual_weight(e);
102  u = v;
103  }
104  assert(ED_to_virt(orig) != NULL);
105 }
106 
107 static void
108 interclrep(graph_t * g, edge_t * e)
109 {
110  node_t *t, *h;
111  edge_t *ve;
112 
113  t = leader_of(g, agtail(e));
114  h = leader_of(g, aghead(e));
115  if (ND_rank(t) > ND_rank(h)) {
116  node_t *t0 = t;
117  t = h;
118  h = t0;
119  }
120  if (ND_clust(t) != ND_clust(h)) {
121  if ((ve = find_fast_edge(t, h))) {
122  merge_chain(g, e, ve, TRUE);
123  return;
124  }
125  if (ND_rank(t) == ND_rank(h))
126  return;
127  make_chain(g, t, h, e);
128 
129  /* mark as cluster edge */
130  for (ve = ED_to_virt(e); ve && (ND_rank(aghead(ve)) <= ND_rank(h));
131  ve = ND_out(aghead(ve)).list[0])
133  }
134  /* else ignore intra-cluster edges at this point */
135 }
136 
137 static int
138 is_cluster_edge(edge_t * e)
139 {
140  return ((ND_ranktype(agtail(e)) == CLUSTER)
141  || (ND_ranktype(aghead(e)) == CLUSTER));
142 }
143 
144 void merge_chain(graph_t * g, edge_t * e, edge_t * f, int flag)
145 {
146  edge_t *rep;
147  int lastrank = MAX(ND_rank(agtail(e)), ND_rank(aghead(e)));
148 
149  assert(ED_to_virt(e) == NULL);
150  ED_to_virt(e) = f;
151  rep = f;
152  do {
153  /* interclust multi-edges are not counted now */
154  if (flag)
155  ED_count(rep) += ED_count(e);
156  ED_xpenalty(rep) += ED_xpenalty(e);
157  ED_weight(rep) += ED_weight(e);
158  if (ND_rank(aghead(rep)) == lastrank)
159  break;
160  incr_width(g, aghead(rep));
161  rep = ND_out(aghead(rep)).list[0];
162  } while (rep);
163 }
164 
165 int mergeable(edge_t * e, edge_t * f)
166 {
167  if (e && f && (agtail(e) == agtail(f)) && (aghead(e) == aghead(f)) &&
168  (ED_label(e) == ED_label(f)) && ports_eq(e, f))
169  return TRUE;
170  return FALSE;
171 }
172 
173 void class2(graph_t * g)
174 {
175  int c;
176  node_t *n, *t, *h;
177  edge_t *e, *prev, *opp;
178 
179  GD_nlist(g) = NULL;
180 
181  GD_n_nodes(g) = 0; /* new */
182 
183  mark_clusters(g);
184  for (c = 1; c <= GD_n_cluster(g); c++)
185  build_skeleton(g, GD_clust(g)[c]);
186  for (n = agfstnode(g); n; n = agnxtnode(g, n))
187  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
188  if (ND_weight_class(aghead(e)) <= 2)
189  ND_weight_class(aghead(e))++;
190  if (ND_weight_class(agtail(e)) <= 2)
191  ND_weight_class(agtail(e))++;
192  }
193 
194  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
195  if ((ND_clust(n) == NULL) && (n == UF_find(n))) {
196  fast_node(g, n);
197  GD_n_nodes(g)++;
198  }
199  prev = NULL;
200  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
201 
202  /* already processed */
203  if (ED_to_virt(e)) {
204  prev = e;
205  continue;
206  }
207 
208  /* edges involving sub-clusters of g */
209  if (is_cluster_edge(e)) {
210  /* following is new cluster multi-edge code */
211  if (mergeable(prev, e)) {
212  if (ED_to_virt(prev)) {
213  merge_chain(g, e, ED_to_virt(prev), FALSE);
214  other_edge(e);
215  } else if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
216  merge_oneway(e, prev);
217  other_edge(e);
218  }
219  /* else is an intra-cluster edge */
220  continue;
221  }
222  interclrep(g, e);
223  prev = e;
224  continue;
225  }
226  /* merge multi-edges */
227  if (prev && (agtail(e) == agtail(prev)) && (aghead(e) == aghead(prev))) {
228  if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
229  merge_oneway(e, prev);
230  other_edge(e);
231  continue;
232  }
233  if ((ED_label(e) == NULL) && (ED_label(prev) == NULL)
234  && ports_eq(e, prev)) {
235  if (Concentrate)
236  ED_edge_type(e) = IGNORED;
237  else {
238  merge_chain(g, e, ED_to_virt(prev), TRUE);
239  other_edge(e);
240  }
241  continue;
242  }
243  /* parallel edges with different labels fall through here */
244  }
245 
246  /* self edges */
247  if (agtail(e) == aghead(e)) {
248  other_edge(e);
249  prev = e;
250  continue;
251  }
252 
253  t = UF_find(agtail(e));
254  h = UF_find(aghead(e));
255 
256  /* non-leader leaf nodes */
257  if ((agtail(e) != t) || (aghead(e) != h)) {
258  /* FIX need to merge stuff */
259  continue;
260  }
261 
262 
263  /* flat edges */
264  if (ND_rank(agtail(e)) == ND_rank(aghead(e))) {
265  flat_edge(g, e);
266  prev = e;
267  continue;
268  }
269 
270  /* forward edges */
271  if (ND_rank(aghead(e)) > ND_rank(agtail(e))) {
272  make_chain(g, agtail(e), aghead(e), e);
273  prev = e;
274  continue;
275  }
276 
277  /* backward edges */
278  else {
279  /*other_edge(e); */
280  /* avoid when opp==e in undirected graph */
281 #ifndef WITH_CGRAPH
282  if ((opp = agfindedge(g, aghead(e), agtail(e))) && (opp != e)) {
283 #else
284  if ((opp = agfindedge(g, aghead(e), agtail(e))) && (aghead(opp) != aghead(e))) {
285 #endif /* WITH_CGRAPH */
286  /* shadows a forward edge */
287  if (ED_to_virt(opp) == NULL)
288  make_chain(g, agtail(opp), aghead(opp), opp);
289  if ((ED_label(e) == NULL) && (ED_label(opp) == NULL)
290  && ports_eq(e, opp)) {
291  if (Concentrate) {
292  ED_edge_type(e) = IGNORED;
293  ED_conc_opp_flag(opp) = TRUE;
294  } else { /* see above. this is getting out of hand */
295  other_edge(e);
296  merge_chain(g, e, ED_to_virt(opp), TRUE);
297  }
298  continue;
299  }
300  }
301  make_chain(g, aghead(e), agtail(e), e);
302  prev = e;
303  }
304  }
305  }
306  /* since decompose() is not called on subgraphs */
307  if (g != agroot(g)) {
308  GD_comp(g).list = ALLOC(1, GD_comp(g).list, node_t *);
309  GD_comp(g).list[0] = GD_nlist(g);
310  }
311 }
312