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