Graphviz 13.1.1~dev.20250704.1433
Loading...
Searching...
No Matches
fastgr.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <dotgen/dot.h>
12#include <stdbool.h>
13#include <stddef.h>
14#include <util/alloc.h>
15#include <util/unused.h>
16
17/*
18 * operations on the fast internal graph.
19 */
20
21static edge_t *ffe(node_t * u, elist uL, node_t * v, elist vL)
22{
23 int i;
24 edge_t *e;
25
26 if (uL.size > 0 && vL.size > 0) {
27 if (uL.size < vL.size) {
28 for (i = 0; (e = uL.list[i]); i++)
29 if (aghead(e) == v)
30 break;
31 } else {
32 for (i = 0; (e = vL.list[i]); i++)
33 if (agtail(e) == u)
34 break;
35 }
36 } else
37 e = 0;
38 return e;
39}
40
42{
43 return ffe(u, ND_out(u), v, ND_in(v));
44}
45
47 node_t *v;
48 for (v = GD_nlist(g); v; v = ND_next(v))
49 if (v == n)
50 break;
51 return v;
52}
53
55{
56 return ffe(u, ND_flat_out(u), v, ND_flat_in(v));
57}
58
60static void
62{
63 for (size_t i = 0; i < L->size; i++)
64 if (e == L->list[i])
65 return;
66 elist_append(e, (*L));
67}
68
70{
71#ifdef DEBUG
72 edge_t *f;
73 for (int i = 0; (f = ND_out(agtail(e)).list[i]); i++) {
74 if (e == f) {
75 fprintf(stderr, "duplicate fast edge\n");
76 return 0;
77 }
78 assert(aghead(e) != aghead(f));
79 }
80 for (int i = 0; (f = ND_in(aghead(e)).list[i]); i++) {
81 if (e == f) {
82 fprintf(stderr, "duplicate fast edge\n");
83 return 0;
84 }
85 assert(agtail(e) != agtail(f));
86 }
87#endif
90 return e;
91}
92
94void zapinlist(elist * L, edge_t * e)
95{
96 for (size_t i = 0; i < L->size; i++) {
97 if (L->list[i] == e) {
98 L->size--;
99 L->list[i] = L->list[L->size];
100 L->list[L->size] = NULL;
101 break;
102 }
103 }
104}
105
106/* disconnects e from graph */
108{
109 assert(e != NULL);
110 zapinlist(&(ND_out(agtail(e))), e);
111 zapinlist(&(ND_in(aghead(e))), e);
112}
113
115{
117}
118
120{
122}
123
124/* Create and return a new virtual edge e attached to orig.
125 * ED_to_orig(e) = orig
126 * ED_to_virt(orig) = e if e is the first virtual edge attached.
127 * orig might be an input edge, reverse of an input edge, or virtual edge
128 */
130{
131 Agedgepair_t* e2 = gv_alloc(sizeof(Agedgepair_t));
132 AGTYPE(&e2->in) = AGINEDGE;
133 AGTYPE(&e2->out) = AGOUTEDGE;
134 e2->out.base.data = gv_alloc(sizeof(Agedgeinfo_t));
135 edge_t *e = &e2->out;
136 agtail(e) = u;
137 aghead(e) = v;
139
140 if (orig) {
141 AGSEQ(e) = AGSEQ(orig);
142 AGSEQ(&(e2->in)) = AGSEQ(orig);
143 ED_count(e) = ED_count(orig);
144 ED_xpenalty(e) = ED_xpenalty(orig);
145 ED_weight(e) = ED_weight(orig);
146 ED_minlen(e) = ED_minlen(orig);
147 if (agtail(e) == agtail(orig))
148 ED_tail_port(e) = ED_tail_port(orig);
149 else if (agtail(e) == aghead(orig))
150 ED_tail_port(e) = ED_head_port(orig);
151 if (aghead(e) == aghead(orig))
152 ED_head_port(e) = ED_head_port(orig);
153 else if (aghead(e) == agtail(orig))
154 ED_head_port(e) = ED_tail_port(orig);
155
156 if (ED_to_virt(orig) == NULL)
157 ED_to_virt(orig) = e;
158 ED_to_orig(e) = orig;
159 } else {
160 ED_weight(e) = 1;
161 ED_xpenalty(e) = 1;
162 ED_count(e) = 1;
163 ED_minlen(e) = 1;
164 }
165 return e;
166}
167
169{
170 return fast_edge(new_virtual_edge(u, v, orig));
171}
172
174{
175
176#ifdef DEBUG
177 assert(find_fast_node(g, n) == NULL);
178#endif
179 ND_next(n) = GD_nlist(g);
180 if (ND_next(n))
181 ND_prev(ND_next(n)) = n;
182 GD_nlist(g) = n;
183 ND_prev(n) = NULL;
184 assert(n != ND_next(n));
185}
186
188{
189 assert(find_fast_node(g, n));
190 if (ND_next(n))
191 ND_prev(ND_next(n)) = ND_prev(n);
192 if (ND_prev(n))
193 ND_next(ND_prev(n)) = ND_next(n);
194 else
195 GD_nlist(g) = ND_next(n);
196}
197
199 node_t *n = gv_alloc(sizeof(node_t));
200 AGTYPE(n) = AGNODE;
201 n->base.data = gv_alloc(sizeof(Agnodeinfo_t));
202 n->root = agroot(g);
204 ND_lw(n) = ND_rw(n) = 1;
205 ND_ht(n) = 1;
206 ND_UF_size(n) = 1;
207 alloc_elist(4, ND_in(n));
208 alloc_elist(4, ND_out(n));
209 fast_node(g, n);
210 return n;
211}
212
214{
218}
219
221{
222 assert(e != NULL);
223 if (ED_to_orig(e) && ED_to_virt(ED_to_orig(e)) == e)
226 zapinlist(&ND_flat_in(aghead(e)), e);
227}
228
229#ifdef DEBUG
230static char *NAME(node_t * n)
231{
232 static char buf[20];
233 if (ND_node_type(n) == NORMAL)
234 return agnameof(n);
235 snprintf(buf, sizeof(buf), "V%p", n);
236 return buf;
237}
238
239void fastgr(graph_t * g)
240{
241 int i, j;
242 node_t *n, *w;
243 edge_t *e, *f;
244
245 for (n = GD_nlist(g); n; n = ND_next(n)) {
246 fprintf(stderr, "%s %d: (", NAME(n), ND_rank(n));
247 for (i = 0; (e = ND_out(n).list[i]); i++) {
248 fprintf(stderr, " %s:%d", NAME(aghead(e)), ED_count(e));
249 w = aghead(e);
250 if (g == agroot(g)) {
251 for (j = 0; (f = ND_in(w).list[j]); j++)
252 if (e == f)
253 break;
254 assert(f != NULL);
255 }
256 }
257 fprintf(stderr, " ) (");
258 for (i = 0; (e = ND_in(n).list[i]); i++) {
259 fprintf(stderr, " %s:%d", NAME(agtail(e)), ED_count(e));
260 w = agtail(e);
261 if (g == agroot(g)) {
262 for (j = 0; (f = ND_out(w).list[j]); j++)
263 if (e == f)
264 break;
265 assert(f != NULL);
266 }
267 }
268 fprintf(stderr, " )\n");
269 }
270}
271#endif
272
273static void
275{
276 if (ED_minlen(rep) < ED_minlen(e))
277 ED_minlen(rep) = ED_minlen(e);
278 while (rep) {
279 ED_count(rep) += ED_count(e);
280 ED_xpenalty(rep) += ED_xpenalty(e);
281 ED_weight(rep) += ED_weight(e);
282 rep = ED_to_virt(rep);
283 }
284}
285
286void
288{
289 if (rep == ED_to_virt(e) || e == ED_to_virt(rep)) {
290 agwarningf("merge_oneway glitch\n");
291 return;
292 }
293 assert(ED_to_virt(e) == NULL);
294 ED_to_virt(e) = rep;
295 basic_merge(e, rep);
296}
Memory allocation wrappers that exit on failure.
static void * gv_alloc(size_t size)
Definition alloc.h:47
#define NORMAL
Definition const.h:24
#define VIRTUAL
Definition const.h:25
Agraph_t * dot_root(void *p)
Definition dotinit.c:525
static void safe_list_append(edge_t *e, elist *L)
append e to list L only if e not already a member
Definition fastgr.c:61
void zapinlist(elist *L, edge_t *e)
remove e from list and fill hole with last member of list
Definition fastgr.c:94
void delete_fast_edge(edge_t *e)
Definition fastgr.c:107
edge_t * find_flat_edge(node_t *u, node_t *v)
Definition fastgr.c:54
edge_t * new_virtual_edge(node_t *u, node_t *v, edge_t *orig)
Definition fastgr.c:129
static UNUSED node_t * find_fast_node(graph_t *g, node_t *n)
Definition fastgr.c:46
static edge_t * ffe(node_t *u, elist uL, node_t *v, elist vL)
Definition fastgr.c:21
void fast_node(graph_t *g, Agnode_t *n)
Definition fastgr.c:173
node_t * virtual_node(graph_t *g)
Definition fastgr.c:198
void flat_edge(graph_t *g, edge_t *e)
Definition fastgr.c:213
edge_t * find_fast_edge(node_t *u, node_t *v)
Definition fastgr.c:41
void other_edge(edge_t *e)
Definition fastgr.c:114
void delete_flat_edge(edge_t *e)
Definition fastgr.c:220
edge_t * fast_edge(edge_t *e)
Definition fastgr.c:69
static void basic_merge(edge_t *e, edge_t *rep)
Definition fastgr.c:274
void merge_oneway(edge_t *e, edge_t *rep)
Definition fastgr.c:287
void delete_fast_node(graph_t *g, node_t *n)
Definition fastgr.c:187
void safe_other_edge(edge_t *e)
Definition fastgr.c:119
edge_t * virtual_edge(node_t *u, node_t *v, edge_t *orig)
Definition fastgr.c:168
static attrs_t * L
Definition gmlparse.c:94
#define NAME
Definition gmlparse.h:135
node NULL
Definition grammar.y:181
#define ED_to_orig(e)
Definition types.h:598
#define ED_minlen(e)
Definition types.h:592
#define ED_xpenalty(e)
Definition types.h:601
#define ED_count(e)
Definition types.h:580
#define agtail(e)
Definition cgraph.h:988
#define ED_edge_type(e)
Definition types.h:582
#define ED_weight(e)
Definition types.h:603
#define aghead(e)
Definition cgraph.h:989
#define ED_head_port(e)
Definition types.h:588
#define ED_tail_port(e)
Definition types.h:597
#define ED_to_virt(e)
Definition types.h:599
void agwarningf(const char *fmt,...)
Definition agerror.c:173
#define GD_has_flat_edges(g)
Definition types.h:370
#define GD_nlist(g)
Definition types.h:393
#define ND_rank(n)
Definition types.h:523
#define ND_prev(n)
Definition types.h:521
#define ND_ht(n)
Definition types.h:500
#define ND_next(n)
Definition types.h:510
#define ND_other(n)
Definition types.h:514
#define ND_flat_out(n)
Definition types.h:493
#define ND_rw(n)
Definition types.h:525
#define ND_node_type(n)
Definition types.h:511
#define ND_lw(n)
Definition types.h:506
#define ND_UF_size(n)
Definition types.h:487
#define ND_flat_in(n)
Definition types.h:492
#define ND_in(n)
Definition types.h:501
#define ND_out(n)
Definition types.h:515
char * agnameof(void *)
returns a string descriptor for the object.
Definition id.c:143
#define AGTYPE(obj)
returns AGRAPH, AGNODE, or AGEDGE depending on the type of the object
Definition cgraph.h:216
Agraph_t * agroot(void *obj)
Definition obj.c:168
#define AGSEQ(obj)
Definition cgraph.h:225
@ AGOUTEDGE
Definition cgraph.h:207
@ AGNODE
Definition cgraph.h:207
@ AGINEDGE
Definition cgraph.h:207
Agobj_t base
Definition cgraph.h:269
Agedge_t in
Definition cgraph.h:276
Agedge_t out
Definition cgraph.h:276
Agraph_t * root
Definition cgraph.h:261
Agobj_t base
Definition cgraph.h:260
Agrec_t * data
stores programmer-defined data, access with AGDATA
Definition cgraph.h:212
graph or subgraph
Definition cgraph.h:424
Definition types.h:251
edge_t ** list
Definition types.h:252
size_t size
Definition types.h:253
#define elist_append(item, L)
Definition types.h:261
#define alloc_elist(n, L)
Definition types.h:267
abstraction for squashing compiler warnings for unused symbols
#define UNUSED
Definition unused.h:25