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
19static node_t*
20label_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
41static void
42incr_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
49static node_t*
50plain_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
58static node_t*
59leader_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 */
77static void
78make_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
106static void
107interclrep(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])
131 ED_edge_type(ve) = CLUSTER_EDGE;
132 }
133 /* else ignore intra-cluster edges at this point */
134}
135
136static int
137is_cluster_edge(edge_t * e)
138{
139 return ((ND_ranktype(agtail(e)) == CLUSTER)
140 || (ND_ranktype(aghead(e)) == CLUSTER));
141}
142
143void 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
164int 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
172void 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
308