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/*
19 * operations on the fast internal graph.
20 */
21
22static edge_t *ffe(node_t * u, elist uL, node_t * v, elist vL)
23{
24 int i;
25 edge_t *e;
26
27 if ((uL.size > 0) && (vL.size > 0)) {
28 if (uL.size < vL.size) {
29 for (i = 0; (e = uL.list[i]); i++)
30 if (aghead(e) == v)
31 break;
32 } else {
33 for (i = 0; (e = vL.list[i]); i++)
34 if (agtail(e) == u)
35 break;
36 }
37 } else
38 e = 0;
39 return e;
40}
41
42edge_t *find_fast_edge(node_t * u, node_t * v)
43{
44 return ffe(u, ND_out(u), v, ND_in(v));
45}
46
47static node_t*
48find_fast_node(graph_t * g, node_t * n)
49{
50 node_t *v;
51 for (v = GD_nlist(g); v; v = ND_next(v))
52 if (v == n)
53 break;
54 return v;
55}
56
57edge_t *find_flat_edge(node_t * u, node_t * v)
58{
59 return ffe(u, ND_flat_out(u), v, ND_flat_in(v));
60}
61
62/* safe_list_append - append e to list L only if e not already a member */
63static void
64safe_list_append(edge_t * e, elist * L)
65{
66 int i;
67
68 for (i = 0; i < L->size; i++)
69 if (e == L->list[i])
70 return;
71 elist_append(e, (*L));
72}
73
74edge_t *fast_edge(edge_t * e)
75{
76#ifdef DEBUG
77 int i;
78 edge_t *f;
79 for (i = 0; (f = ND_out(agtail(e)).list[i]); i++) {
80 if (e == f) {
81 fprintf(stderr, "duplicate fast edge\n");
82 return 0;
83 }
84 assert(aghead(e) != aghead(f));
85 }
86 for (i = 0; (f = ND_in(aghead(e)).list[i]); i++) {
87 if (e == f) {
88 fprintf(stderr, "duplicate fast edge\n");
89 return 0;
90 }
91 assert(agtail(e) != agtail(f));
92 }
93#endif
94 elist_append(e, ND_out(agtail(e)));
95 elist_append(e, ND_in(aghead(e)));
96 return e;
97}
98
99/* zapinlist - remove e from list and fill hole with last member of list */
100void zapinlist(elist * L, edge_t * e)
101{
102 int i;
103
104 for (i = 0; i < L->size; i++) {
105 if (L->list[i] == e) {
106 L->size--;
107 L->list[i] = L->list[L->size];
108 L->list[L->size] = NULL;
109 break;
110 }
111 }
112}
113
114/* disconnects e from graph */
115void delete_fast_edge(edge_t * e)
116{
117 assert(e != NULL);
118 zapinlist(&(ND_out(agtail(e))), e);
119 zapinlist(&(ND_in(aghead(e))), e);
120}
121
122static void
123safe_delete_fast_edge(edge_t * e)
124{
125 int i;
126 edge_t *f;
127
128 assert(e != NULL);
129 for (i = 0; (f = ND_out(agtail(e)).list[i]); i++)
130 if (f == e)
131 zapinlist(&(ND_out(agtail(e))), e);
132 for (i = 0; (f = ND_in(aghead(e)).list[i]); i++)
133 if (f == e)
134 zapinlist(&(ND_in(aghead(e))), e);
135}
136
137void other_edge(edge_t * e)
138{
139 elist_append(e, ND_other(agtail(e)));
140}
141
142void safe_other_edge(edge_t * e)
143{
144 safe_list_append(e, &(ND_other(agtail(e))));
145}
146
147#ifdef OBSOLETE
148void
149delete_other_edge(edge_t * e)
150{
151 assert(e != NULL);
152 zapinlist(&(ND_other(agtail(e))), e);
153}
154#endif
155
156/* new_virtual_edge:
157 * Create and return a new virtual edge e attached to orig.
158 * ED_to_orig(e) = orig
159 * ED_to_virt(orig) = e if e is the first virtual edge attached.
160 * orig might be an input edge, reverse of an input edge, or virtual edge
161 */
162edge_t *new_virtual_edge(node_t * u, node_t * v, edge_t * orig)
163{
164 edge_t *e;
165
166 Agedgepair_t* e2 = NEW(Agedgepair_t);
167 AGTYPE(&(e2->in)) = AGINEDGE;
168 AGTYPE(&(e2->out)) = AGOUTEDGE;
169 e2->out.base.data = (Agrec_t*)NEW(Agedgeinfo_t);
170 e = &(e2->out);
171 agtail(e) = u;
172 aghead(e) = v;
173 ED_edge_type(e) = VIRTUAL;
174
175 if (orig) {
176 AGSEQ(e) = AGSEQ(orig);
177 AGSEQ(&(e2->in)) = AGSEQ(orig);
178 ED_count(e) = ED_count(orig);
179 ED_xpenalty(e) = ED_xpenalty(orig);
180 ED_weight(e) = ED_weight(orig);
181 ED_minlen(e) = ED_minlen(orig);
182 if (agtail(e) == agtail(orig))
183 ED_tail_port(e) = ED_tail_port(orig);
184 else if (agtail(e) == aghead(orig))
185 ED_tail_port(e) = ED_head_port(orig);
186 if (aghead(e) == aghead(orig))
187 ED_head_port(e) = ED_head_port(orig);
188 else if (aghead(e) == agtail(orig))
189 ED_head_port(e) = ED_tail_port(orig);
190
191 if (ED_to_virt(orig) == NULL)
192 ED_to_virt(orig) = e;
193 ED_to_orig(e) = orig;
194 } else
195 ED_minlen(e) = ED_count(e) = ED_xpenalty(e) = ED_weight(e) = 1;
196 return e;
197}
198
199edge_t *virtual_edge(node_t * u, node_t * v, edge_t * orig)
200{
201 return fast_edge(new_virtual_edge(u, v, orig));
202}
203
204void fast_node(graph_t * g, Agnode_t * n)
205{
206
207#ifdef DEBUG
208 assert(find_fast_node(g, n) == NULL);
209#endif
210 ND_next(n) = GD_nlist(g);
211 if (ND_next(n))
212 ND_prev(ND_next(n)) = n;
213 GD_nlist(g) = n;
214 ND_prev(n) = NULL;
215 assert(n != ND_next(n));
216}
217
218void fast_nodeapp(node_t * u, node_t * v)
219{
220 assert(u != v);
221 assert(ND_next(v) == NULL);
222 ND_next(v) = ND_next(u);
223 if (ND_next(u))
224 ND_prev(ND_next(u)) = v;
225 ND_prev(v) = u;
226 ND_next(u) = v;
227}
228
229void delete_fast_node(graph_t * g, node_t * n)
230{
231 assert(find_fast_node(g, n));
232 if (ND_next(n))
233 ND_prev(ND_next(n)) = ND_prev(n);
234 if (ND_prev(n))
235 ND_next(ND_prev(n)) = ND_next(n);
236 else
237 GD_nlist(g) = ND_next(n);
238}
239
240node_t *named_virtual_node(graph_t * g, char *s)
241{
242 node_t *n;
243
244 n = NEW(node_t);
245 AGTYPE(n) = AGNODE;
246 n->base.data = (Agrec_t*)NEW(Agnodeinfo_t);
247 n->root = agroot(g);
248 ND_node_type(n) = VIRTUAL;
249 ND_lw(n) = ND_rw(n) = 1;
250 ND_ht(n) = 1;
251 ND_UF_size(n) = 1;
252 if (s) ND_alg(n) = s;
253 alloc_elist(4, ND_in(n));
254 alloc_elist(4, ND_out(n));
255 fast_node(g, n);
256 GD_n_nodes(g)++;
257 return n;
258}
259
260node_t *virtual_node(graph_t * g)
261{
262 return named_virtual_node(g,0);
263}
264
265void flat_edge(graph_t * g, edge_t * e)
266{
267 elist_append(e, ND_flat_out(agtail(e)));
268 elist_append(e, ND_flat_in(aghead(e)));
269 GD_has_flat_edges(dot_root(g)) = GD_has_flat_edges(g) = TRUE;
270}
271
272void delete_flat_edge(edge_t * e)
273{
274 assert(e != NULL);
275 if (ED_to_orig(e) && ED_to_virt(ED_to_orig(e)) == e)
276 ED_to_virt(ED_to_orig(e)) = NULL;
277 zapinlist(&(ND_flat_out(agtail(e))), e);
278 zapinlist(&(ND_flat_in(aghead(e))), e);
279}
280
281#ifdef DEBUG
282static char *NAME(node_t * n)
283{
284 static char buf[20];
285 if (ND_node_type(n) == NORMAL)
286 return agnameof(n);
287 sprintf(buf, "V%p", n);
288 return buf;
289}
290
291void fastgr(graph_t * g)
292{
293 int i, j;
294 node_t *n, *w;
295 edge_t *e, *f;
296
297 for (n = GD_nlist(g); n; n = ND_next(n)) {
298 fprintf(stderr, "%s %d: (", NAME(n), ND_rank(n));
299 for (i = 0; (e = ND_out(n).list[i]); i++) {
300 fprintf(stderr, " %s:%d", NAME(aghead(e)), ED_count(e));
301 w = aghead(e);
302 if (g == agroot(g)) {
303 for (j = 0; (f = ND_in(w).list[j]); j++)
304 if (e == f)
305 break;
306 assert(f != NULL);
307 }
308 }
309 fprintf(stderr, " ) (");
310 for (i = 0; (e = ND_in(n).list[i]); i++) {
311 fprintf(stderr, " %s:%d", NAME(agtail(e)), ED_count(e));
312 w = agtail(e);
313 if (g == agroot(g)) {
314 for (j = 0; (f = ND_out(w).list[j]); j++)
315 if (e == f)
316 break;
317 assert(f != NULL);
318 }
319 }
320 fprintf(stderr, " )\n");
321 }
322}
323#endif
324
325static void
326basic_merge(edge_t * e, edge_t * rep)
327{
328 if (ED_minlen(rep) < ED_minlen(e))
329 ED_minlen(rep) = ED_minlen(e);
330 while (rep) {
331 ED_count(rep) += ED_count(e);
332 ED_xpenalty(rep) += ED_xpenalty(e);
333 ED_weight(rep) += ED_weight(e);
334 rep = ED_to_virt(rep);
335 }
336}
337
338void
339merge_oneway(edge_t * e, edge_t * rep)
340{
341 if (rep == ED_to_virt(e)) {
342 agerr(AGWARN, "merge_oneway glitch\n");
343 return;
344 }
345 assert(ED_to_virt(e) == NULL);
346 ED_to_virt(e) = rep;
347 basic_merge(e, rep);
348}
349
350static void
351unrep(edge_t * rep, edge_t * e)
352{
353 ED_count(rep) -= ED_count(e);
354 ED_xpenalty(rep) -= ED_xpenalty(e);
355 ED_weight(rep) -= ED_weight(e);
356}
357
358void unmerge_oneway(edge_t * e)
359{
360 edge_t *rep, *nextrep;
361 for (rep = ED_to_virt(e); rep; rep = nextrep) {
362 unrep(rep, e);
363 nextrep = ED_to_virt(rep);
364 if (ED_count(rep) == 0)
365 safe_delete_fast_edge(rep); /* free(rep)? */
366
367 /* unmerge from a virtual edge chain */
368 while ((ED_edge_type(rep) == VIRTUAL)
369 && (ND_node_type(aghead(rep)) == VIRTUAL)
370 && (ND_out(aghead(rep)).size == 1)) {
371 rep = ND_out(aghead(rep)).list[0];
372 unrep(rep, e);
373 }
374 }
375 ED_to_virt(e) = NULL;
376}
377
378#ifdef OBSOLETET
379static int
380is_fast_node(graph_t * g, node_t * v)
381{
382 node_t *n;
383
384 for (n = GD_nlist(g); n; n = ND_next(n))
385 if (v == n)
386 return TRUE;
387 return FALSE;
388}
389#endif
390