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 /*
16 * build edge_t concentrators for parallel edges with a common endpoint
17 */
18
19 #include "dot.h"
20 #include <setjmp.h>
21
22 #define UP 0
23 #define DOWN 1
24
25 static jmp_buf jbuf;
26
samedir(edge_t * e,edge_t * f)27 static boolean samedir(edge_t * e, edge_t * f)
28 {
29 edge_t *e0, *f0;
30
31 for (e0 = e; ED_edge_type(e0) != NORMAL; e0 = ED_to_orig(e0));
32 for (f0 = f; ED_edge_type(f0) != NORMAL; f0 = ED_to_orig(f0));
33 if (ED_conc_opp_flag(e0))
34 return FALSE;
35 if (ED_conc_opp_flag(f0))
36 return FALSE;
37 return ((ND_rank(agtail(f0)) - ND_rank(aghead(f0)))
38 * (ND_rank(agtail(e0)) - ND_rank(aghead(e0))) > 0);
39 }
40
downcandidate(node_t * v)41 static boolean downcandidate(node_t * v)
42 {
43 return ((ND_node_type(v) == VIRTUAL) && (ND_in(v).size == 1)
44 && (ND_out(v).size == 1) && (ND_label(v) == NULL));
45 }
46
bothdowncandidates(node_t * u,node_t * v)47 static boolean bothdowncandidates(node_t * u, node_t * v)
48 {
49 edge_t *e, *f;
50 e = ND_in(u).list[0];
51 f = ND_in(v).list[0];
52 if (downcandidate(v) && (agtail(e) == agtail(f))) {
53 return samedir(e, f)
54 && (portcmp(ED_tail_port(e), ED_tail_port(f)) == 0);
55 }
56 return FALSE;
57 }
58
upcandidate(node_t * v)59 static boolean upcandidate(node_t * v)
60 {
61 return ((ND_node_type(v) == VIRTUAL) && (ND_out(v).size == 1)
62 && (ND_in(v).size == 1) && (ND_label(v) == NULL));
63 }
64
bothupcandidates(node_t * u,node_t * v)65 static boolean bothupcandidates(node_t * u, node_t * v)
66 {
67 edge_t *e, *f;
68 e = ND_out(u).list[0];
69 f = ND_out(v).list[0];
70 if (upcandidate(v) && (aghead(e) == aghead(f))) {
71 return samedir(e, f)
72 && (portcmp(ED_head_port(e), ED_head_port(f)) == 0);
73 }
74 return FALSE;
75 }
76
mergevirtual(graph_t * g,int r,int lpos,int rpos,int dir)77 static void mergevirtual(graph_t * g, int r, int lpos, int rpos, int dir)
78 {
79 int i, k;
80 node_t *left, *right;
81 edge_t *e, *f, *e0;
82
83 left = GD_rank(g)[r].v[lpos];
84 /* merge all right nodes into the leftmost one */
85 for (i = lpos + 1; i <= rpos; i++) {
86 right = GD_rank(g)[r].v[i];
87 if (dir == DOWN) {
88 while ((e = ND_out(right).list[0])) {
89 for (k = 0; (f = ND_out(left).list[k]); k++)
90 if (aghead(f) == aghead(e))
91 break;
92 if (f == NULL)
93 f = virtual_edge(left, aghead(e), e);
94 while ((e0 = ND_in(right).list[0])) {
95 merge_oneway(e0, f);
96 /*ED_weight(f) += ED_weight(e0); */
97 delete_fast_edge(e0);
98 }
99 delete_fast_edge(e);
100 }
101 } else {
102 while ((e = ND_in(right).list[0])) {
103 for (k = 0; (f = ND_in(left).list[k]); k++)
104 if (agtail(f) == agtail(e))
105 break;
106 if (f == NULL)
107 f = virtual_edge(agtail(e), left, e);
108 while ((e0 = ND_out(right).list[0])) {
109 merge_oneway(e0, f);
110 delete_fast_edge(e0);
111 }
112 delete_fast_edge(e);
113 }
114 }
115 assert(ND_in(right).size + ND_out(right).size == 0);
116 delete_fast_node(g, right);
117 }
118 k = lpos + 1;
119 i = rpos + 1;
120 while (i < GD_rank(g)[r].n) {
121 node_t *n;
122 n = GD_rank(g)[r].v[k] = GD_rank(g)[r].v[i];
123 ND_order(n) = k;
124 k++;
125 i++;
126 }
127 GD_rank(g)[r].n = k;
128 GD_rank(g)[r].v[k] = NULL;
129 }
130
infuse(graph_t * g,node_t * n)131 static void infuse(graph_t * g, node_t * n)
132 {
133 node_t *lead;
134
135 lead = GD_rankleader(g)[ND_rank(n)];
136 if ((lead == NULL) || (ND_order(lead) > ND_order(n)))
137 GD_rankleader(g)[ND_rank(n)] = n;
138 }
139
rebuild_vlists(graph_t * g)140 static void rebuild_vlists(graph_t * g)
141 {
142 int c, i, r, maxi;
143 node_t *n, *lead;
144 edge_t *e, *rep;
145
146 for (r = GD_minrank(g); r <= GD_maxrank(g); r++)
147 GD_rankleader(g)[r] = NULL;
148 dot_scan_ranks(g);
149 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
150 infuse(g, n);
151 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
152 for (rep = e; ED_to_virt(rep); rep = ED_to_virt(rep));
153 while (rep != NULL && ND_rank(aghead(rep)) < ND_rank(aghead(e))) {
154 infuse(g, aghead(rep));
155 rep = ND_out(aghead(rep)).list[0];
156 }
157 }
158 }
159
160 for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
161 lead = GD_rankleader(g)[r];
162 if (lead == NULL) {
163 agerr(AGERR, "rebuiltd_vlists: lead is null for rank %d\n", r);
164 longjmp(jbuf, 1);
165 }
166 else if (GD_rank(dot_root(g))[r].v[ND_order(lead)] != lead) {
167 agerr(AGERR, "rebuiltd_vlists: rank lead %s not in order %d of rank %d\n",
168 agnameof(lead), ND_order(lead), r);
169 longjmp(jbuf, 1);
170 }
171 GD_rank(g)[r].v =
172 GD_rank(dot_root(g))[r].v + ND_order((GD_rankleader(g)[r]));
173 maxi = -1;
174 for (i = 0; i < GD_rank(g)[r].n; i++) {
175 if ((n = GD_rank(g)[r].v[i]) == NULL)
176 break;
177 if (ND_node_type(n) == NORMAL) {
178 if (agcontains(g, n))
179 maxi = i;
180 else
181 break;
182 } else {
183 edge_t *e;
184 for (e = ND_in(n).list[0]; e && ED_to_orig(e);
185 e = ED_to_orig(e));
186 if (e && (agcontains(g, agtail(e)))
187 && agcontains(g, aghead(e)))
188 maxi = i;
189 }
190 }
191 if (maxi == -1)
192 agerr(AGWARN, "degenerate concentrated rank %s,%d\n", agnameof(g),
193 r);
194 GD_rank(g)[r].n = maxi + 1;
195 }
196
197 for (c = 1; c <= GD_n_cluster(g); c++)
198 rebuild_vlists(GD_clust(g)[c]);
199 }
200
dot_concentrate(graph_t * g)201 void dot_concentrate(graph_t * g)
202 {
203 int c, r, leftpos, rightpos;
204 node_t *left, *right;
205
206 if (GD_maxrank(g) - GD_minrank(g) <= 1)
207 return;
208 /* this is the downward looking pass. r is a candidate rank. */
209 for (r = 1; GD_rank(g)[r + 1].n; r++) {
210 for (leftpos = 0; leftpos < GD_rank(g)[r].n; leftpos++) {
211 left = GD_rank(g)[r].v[leftpos];
212 if (downcandidate(left) == FALSE)
213 continue;
214 for (rightpos = leftpos + 1; rightpos < GD_rank(g)[r].n;
215 rightpos++) {
216 right = GD_rank(g)[r].v[rightpos];
217 if (bothdowncandidates(left, right) == FALSE)
218 break;
219 }
220 if (rightpos - leftpos > 1)
221 mergevirtual(g, r, leftpos, rightpos - 1, DOWN);
222 }
223 }
224 /* this is the corresponding upward pass */
225 while (r > 0) {
226 for (leftpos = 0; leftpos < GD_rank(g)[r].n; leftpos++) {
227 left = GD_rank(g)[r].v[leftpos];
228 if (upcandidate(left) == FALSE)
229 continue;
230 for (rightpos = leftpos + 1; rightpos < GD_rank(g)[r].n;
231 rightpos++) {
232 right = GD_rank(g)[r].v[rightpos];
233 if (bothupcandidates(left, right) == FALSE)
234 break;
235 }
236 if (rightpos - leftpos > 1)
237 mergevirtual(g, r, leftpos, rightpos - 1, UP);
238 }
239 r--;
240 }
241 if (setjmp(jbuf)) {
242 agerr(AGPREV, "concentrate=true may not work correctly.\n");
243 return;
244 }
245 for (c = 1; c <= GD_n_cluster(g); c++)
246 rebuild_vlists(GD_clust(g)[c]);
247 }
248