Graphviz  2.41.20170921.2350
fastgr.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 #include "dot.h"
16 
17 
18 /*
19  * operations on the fast internal graph.
20  */
21 
22 static 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 
43 {
44  return ffe(u, ND_out(u), v, ND_in(v));
45 }
46 
47 static node_t*
48 find_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 
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 */
63 static void
64 safe_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 
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 */
100 void 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 */
116 {
117  assert(e != NULL);
118  zapinlist(&(ND_out(agtail(e))), e);
119  zapinlist(&(ND_in(aghead(e))), e);
120 }
121 
122 static void
123 safe_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 
138 {
139  elist_append(e, ND_other(agtail(e)));
140 }
141 
143 {
144  safe_list_append(e, &(ND_other(agtail(e))));
145 }
146 
147 #ifdef OBSOLETE
148 void
149 delete_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  */
163 {
164  edge_t *e;
165 
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 
200 {
201  return fast_edge(new_virtual_edge(u, v, orig));
202 }
203 
204 void 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 
218 void 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 
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 
241 {
242  node_t *n;
243 
244  n = NEW(node_t);
245 // agnameof(n) = "virtual";
246  AGTYPE(n) = AGNODE;
247  n->base.data = (Agrec_t*)NEW(Agnodeinfo_t);
248  n->root = agroot(g);
249  ND_node_type(n) = VIRTUAL;
250  ND_lw(n) = ND_rw(n) = 1;
251  ND_ht(n) = 1;
252  ND_UF_size(n) = 1;
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 
260 void flat_edge(graph_t * g, edge_t * e)
261 {
265 }
266 
268 {
269  assert(e != NULL);
270  if (ED_to_orig(e) && ED_to_virt(ED_to_orig(e)) == e)
271  ED_to_virt(ED_to_orig(e)) = NULL;
272  zapinlist(&(ND_flat_out(agtail(e))), e);
273  zapinlist(&(ND_flat_in(aghead(e))), e);
274 }
275 
276 #ifdef DEBUG
277 static char *NAME(node_t * n)
278 {
279  static char buf[20];
280  if (ND_node_type(n) == NORMAL)
281  return agnameof(n);
282  sprintf(buf, "V%p", n);
283  return buf;
284 }
285 
286 void fastgr(graph_t * g)
287 {
288  int i, j;
289  node_t *n, *w;
290  edge_t *e, *f;
291 
292  for (n = GD_nlist(g); n; n = ND_next(n)) {
293  fprintf(stderr, "%s %d: (", NAME(n), ND_rank(n));
294  for (i = 0; (e = ND_out(n).list[i]); i++) {
295  fprintf(stderr, " %s:%d", NAME(aghead(e)), ED_count(e));
296  w = aghead(e);
297  if (g == agroot(g)) {
298  for (j = 0; (f = ND_in(w).list[j]); j++)
299  if (e == f)
300  break;
301  assert(f != NULL);
302  }
303  }
304  fprintf(stderr, " ) (");
305  for (i = 0; (e = ND_in(n).list[i]); i++) {
306  fprintf(stderr, " %s:%d", NAME(agtail(e)), ED_count(e));
307  w = agtail(e);
308  if (g == agroot(g)) {
309  for (j = 0; (f = ND_out(w).list[j]); j++)
310  if (e == f)
311  break;
312  assert(f != NULL);
313  }
314  }
315  fprintf(stderr, " )\n");
316  }
317 }
318 #endif
319 
320 static void
321 basic_merge(edge_t * e, edge_t * rep)
322 {
323  if (ED_minlen(rep) < ED_minlen(e))
324  ED_minlen(rep) = ED_minlen(e);
325  while (rep) {
326  ED_count(rep) += ED_count(e);
327  ED_xpenalty(rep) += ED_xpenalty(e);
328  ED_weight(rep) += ED_weight(e);
329  rep = ED_to_virt(rep);
330  }
331 }
332 
333 void
335 {
336  if (rep == ED_to_virt(e)) {
337  agerr(AGWARN, "merge_oneway glitch\n");
338  return;
339  }
340  assert(ED_to_virt(e) == NULL);
341  ED_to_virt(e) = rep;
342  basic_merge(e, rep);
343 }
344 
345 static void
346 unrep(edge_t * rep, edge_t * e)
347 {
348  ED_count(rep) -= ED_count(e);
349  ED_xpenalty(rep) -= ED_xpenalty(e);
350  ED_weight(rep) -= ED_weight(e);
351 }
352 
354 {
355  edge_t *rep, *nextrep;
356  for (rep = ED_to_virt(e); rep; rep = nextrep) {
357  unrep(rep, e);
358  nextrep = ED_to_virt(rep);
359  if (ED_count(rep) == 0)
360  safe_delete_fast_edge(rep); /* free(rep)? */
361 
362  /* unmerge from a virtual edge chain */
363  while ((ED_edge_type(rep) == VIRTUAL)
364  && (ND_node_type(aghead(rep)) == VIRTUAL)
365  && (ND_out(aghead(rep)).size == 1)) {
366  rep = ND_out(aghead(rep)).list[0];
367  unrep(rep, e);
368  }
369  }
370  ED_to_virt(e) = NULL;
371 }
372 
373 #ifdef OBSOLETET
374 static int
375 is_fast_node(graph_t * g, node_t * v)
376 {
377  node_t *n;
378 
379  for (n = GD_nlist(g); n; n = ND_next(n))
380  if (v == n)
381  return TRUE;
382  return FALSE;
383 }
384 #endif
#define AGSEQ(obj)
Definition: cgraph.h:115
#define ND_rank(n)
Definition: types.h:529
#define GD_nlist(g)
Definition: types.h:401
void delete_fast_node(Agraph_t *, Agnode_t *)
Definition: fastgr.c:229
#define elist_append(item, L)
Definition: types.h:272
Agedge_t * find_flat_edge(Agnode_t *, Agnode_t *)
Definition: fastgr.c:57
void fast_nodeapp(Agnode_t *, Agnode_t *)
Definition: fastgr.c:218
Agedge_t * find_fast_edge(Agnode_t *, Agnode_t *)
Definition: fastgr.c:42
#define ND_node_type(n)
Definition: types.h:518
#define ED_head_port(e)
Definition: types.h:591
#define ND_flat_in(n)
Definition: types.h:498
#define assert(x)
Definition: cghdr.h:47
Agedge_t in
Definition: cgraph.h:147
Agnode_t * virtual_node(Agraph_t *)
Definition: fastgr.c:240
#define ND_UF_size(n)
Definition: types.h:493
#define ED_to_orig(e)
Definition: types.h:601
#define ED_weight(e)
Definition: types.h:606
#define GD_has_flat_edges(g)
Definition: types.h:374
void unmerge_oneway(Agedge_t *)
Definition: fastgr.c:353
Agobj_t base
Definition: cgraph.h:134
void delete_flat_edge(Agedge_t *)
Definition: fastgr.c:267
#define alloc_elist(n, L)
Definition: types.h:273
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
void delete_fast_edge(Agedge_t *)
Definition: fastgr.c:115
CGRAPH_API Agraph_t * agroot(void *obj)
Definition: obj.c:169
#define AGOUTEDGE
Definition: cgraph.h:102
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition: fastgr.c:199
#define AGTYPE(obj)
Definition: cgraph.h:113
Definition: cgraph.h:388
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
void safe_other_edge(Agedge_t *)
Definition: fastgr.c:142
void fast_node(Agraph_t *, Agnode_t *)
Definition: fastgr.c:204
#define ED_tail_port(e)
Definition: types.h:600
Definition: types.h:261
void other_edge(Agedge_t *)
Definition: fastgr.c:137
#define ND_ht(n)
Definition: types.h:506
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
Agedge_t out
Definition: cgraph.h:147
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define VIRTUAL
Definition: const.h:28
#define ED_count(e)
Definition: types.h:583
void merge_oneway(Agedge_t *, Agedge_t *)
Definition: fastgr.c:334
#define ND_rw(n)
Definition: types.h:531
edge_t ** list
Definition: types.h:262
Definition: cgraph.h:83
#define AGNODE
Definition: cgraph.h:101
Agobj_t base
Definition: cgraph.h:140
Agraph_t * dot_root(void *p)
Definition: dotinit.c:513
void flat_edge(Agraph_t *, Agedge_t *)
Definition: fastgr.c:260
#define GD_n_nodes(g)
Definition: types.h:397
Agedge_t * new_virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition: fastgr.c:162
#define ED_to_virt(e)
Definition: types.h:602
#define ND_lw(n)
Definition: types.h:513
#define NULL
Definition: logic.h:39
#define ND_in(n)
Definition: types.h:507
#define ND_next(n)
Definition: types.h:517
void zapinlist(elist *, Agedge_t *)
Definition: fastgr.c:100
Agrec_t * data
Definition: cgraph.h:109
#define ND_out(n)
Definition: types.h:522
int size
Definition: types.h:263
#define ED_xpenalty(e)
Definition: types.h:604
#define ND_other(n)
Definition: types.h:521
#define AGINEDGE
Definition: cgraph.h:103
#define ND_flat_out(n)
Definition: types.h:499
Agraph_t * root
Definition: cgraph.h:135
#define NORMAL
Definition: const.h:27
#define ND_prev(n)
Definition: types.h:527
#define ED_edge_type(e)
Definition: types.h:585
#define FALSE
Definition: cgraph.h:35
Agedge_t * fast_edge(Agedge_t *)
Definition: fastgr.c:74
#define ED_minlen(e)
Definition: types.h:595
#define NEW(t)
Definition: memory.h:35
#define TRUE
Definition: cgraph.h:38