Graphviz 13.0.0~dev.20241225.0935
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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
59/* safe_list_append - append e to list L only if e not already a member */
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 int i;
73 edge_t *f;
74 for (i = 0; (f = ND_out(agtail(e)).list[i]); i++) {
75 if (e == f) {
76 fprintf(stderr, "duplicate fast edge\n");
77 return 0;
78 }
79 assert(aghead(e) != aghead(f));
80 }
81 for (i = 0; (f = ND_in(aghead(e)).list[i]); i++) {
82 if (e == f) {
83 fprintf(stderr, "duplicate fast edge\n");
84 return 0;
85 }
86 assert(agtail(e) != agtail(f));
87 }
88#endif
91 return e;
92}
93
94/* zapinlist - remove e from list and fill hole with last member of list */
95void zapinlist(elist * L, edge_t * e)
96{
97 for (size_t i = 0; i < L->size; i++) {
98 if (L->list[i] == e) {
99 L->size--;
100 L->list[i] = L->list[L->size];
101 L->list[L->size] = NULL;
102 break;
103 }
104 }
105}
106
107/* disconnects e from graph */
109{
110 assert(e != NULL);
111 zapinlist(&(ND_out(agtail(e))), e);
112 zapinlist(&(ND_in(aghead(e))), e);
113}
114
116{
118}
119
121{
123}
124
125/* new_virtual_edge:
126 * Create and return a new virtual edge e attached to orig.
127 * ED_to_orig(e) = orig
128 * ED_to_virt(orig) = e if e is the first virtual edge attached.
129 * orig might be an input edge, reverse of an input edge, or virtual edge
130 */
132{
133 edge_t *e;
134
135 Agedgepair_t* e2 = gv_alloc(sizeof(Agedgepair_t));
136 AGTYPE(&(e2->in)) = AGINEDGE;
137 AGTYPE(&(e2->out)) = AGOUTEDGE;
138 e2->out.base.data = gv_alloc(sizeof(Agedgeinfo_t));
139 e = &(e2->out);
140 agtail(e) = u;
141 aghead(e) = v;
143
144 if (orig) {
145 AGSEQ(e) = AGSEQ(orig);
146 AGSEQ(&(e2->in)) = AGSEQ(orig);
147 ED_count(e) = ED_count(orig);
148 ED_xpenalty(e) = ED_xpenalty(orig);
149 ED_weight(e) = ED_weight(orig);
150 ED_minlen(e) = ED_minlen(orig);
151 if (agtail(e) == agtail(orig))
152 ED_tail_port(e) = ED_tail_port(orig);
153 else if (agtail(e) == aghead(orig))
154 ED_tail_port(e) = ED_head_port(orig);
155 if (aghead(e) == aghead(orig))
156 ED_head_port(e) = ED_head_port(orig);
157 else if (aghead(e) == agtail(orig))
158 ED_head_port(e) = ED_tail_port(orig);
159
160 if (ED_to_virt(orig) == NULL)
161 ED_to_virt(orig) = e;
162 ED_to_orig(e) = orig;
163 } else {
164 ED_weight(e) = 1;
165 ED_xpenalty(e) = 1;
166 ED_count(e) = 1;
167 ED_minlen(e) = 1;
168 }
169 return e;
170}
171
173{
174 return fast_edge(new_virtual_edge(u, v, orig));
175}
176
178{
179
180#ifdef DEBUG
181 assert(find_fast_node(g, n) == NULL);
182#endif
183 ND_next(n) = GD_nlist(g);
184 if (ND_next(n))
185 ND_prev(ND_next(n)) = n;
186 GD_nlist(g) = n;
187 ND_prev(n) = NULL;
188 assert(n != ND_next(n));
189}
190
192{
193 assert(find_fast_node(g, n));
194 if (ND_next(n))
195 ND_prev(ND_next(n)) = ND_prev(n);
196 if (ND_prev(n))
197 ND_next(ND_prev(n)) = ND_next(n);
198 else
199 GD_nlist(g) = ND_next(n);
200}
201
203 node_t *n = gv_alloc(sizeof(node_t));
204 AGTYPE(n) = AGNODE;
205 n->base.data = gv_alloc(sizeof(Agnodeinfo_t));
206 n->root = agroot(g);
208 ND_lw(n) = ND_rw(n) = 1;
209 ND_ht(n) = 1;
210 ND_UF_size(n) = 1;
211 alloc_elist(4, ND_in(n));
212 alloc_elist(4, ND_out(n));
213 fast_node(g, n);
214 return n;
215}
216
218{
222}
223
225{
226 assert(e != NULL);
227 if (ED_to_orig(e) && ED_to_virt(ED_to_orig(e)) == e)
229 zapinlist(&(ND_flat_out(agtail(e))), e);
230 zapinlist(&(ND_flat_in(aghead(e))), e);
231}
232
233#ifdef DEBUG
234static char *NAME(node_t * n)
235{
236 static char buf[20];
237 if (ND_node_type(n) == NORMAL)
238 return agnameof(n);
239 snprintf(buf, sizeof(buf), "V%p", n);
240 return buf;
241}
242
243void fastgr(graph_t * g)
244{
245 int i, j;
246 node_t *n, *w;
247 edge_t *e, *f;
248
249 for (n = GD_nlist(g); n; n = ND_next(n)) {
250 fprintf(stderr, "%s %d: (", NAME(n), ND_rank(n));
251 for (i = 0; (e = ND_out(n).list[i]); i++) {
252 fprintf(stderr, " %s:%d", NAME(aghead(e)), ED_count(e));
253 w = aghead(e);
254 if (g == agroot(g)) {
255 for (j = 0; (f = ND_in(w).list[j]); j++)
256 if (e == f)
257 break;
258 assert(f != NULL);
259 }
260 }
261 fprintf(stderr, " ) (");
262 for (i = 0; (e = ND_in(n).list[i]); i++) {
263 fprintf(stderr, " %s:%d", NAME(agtail(e)), ED_count(e));
264 w = agtail(e);
265 if (g == agroot(g)) {
266 for (j = 0; (f = ND_out(w).list[j]); j++)
267 if (e == f)
268 break;
269 assert(f != NULL);
270 }
271 }
272 fprintf(stderr, " )\n");
273 }
274}
275#endif
276
277static void
279{
280 if (ED_minlen(rep) < ED_minlen(e))
281 ED_minlen(rep) = ED_minlen(e);
282 while (rep) {
283 ED_count(rep) += ED_count(e);
284 ED_xpenalty(rep) += ED_xpenalty(e);
285 ED_weight(rep) += ED_weight(e);
286 rep = ED_to_virt(rep);
287 }
288}
289
290void
292{
293 if (rep == ED_to_virt(e) || e == ED_to_virt(rep)) {
294 agwarningf("merge_oneway glitch\n");
295 return;
296 }
297 assert(ED_to_virt(e) == NULL);
298 ED_to_virt(e) = rep;
299 basic_merge(e, rep);
300}
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:496
static void safe_list_append(edge_t *e, elist *L)
Definition fastgr.c:61
void zapinlist(elist *L, edge_t *e)
Definition fastgr.c:95
void delete_fast_edge(edge_t *e)
Definition fastgr.c:108
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:131
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:177
node_t * virtual_node(graph_t *g)
Definition fastgr.c:202
void flat_edge(graph_t *g, edge_t *e)
Definition fastgr.c:217
edge_t * find_fast_edge(node_t *u, node_t *v)
Definition fastgr.c:41
void other_edge(edge_t *e)
Definition fastgr.c:115
void delete_flat_edge(edge_t *e)
Definition fastgr.c:224
edge_t * fast_edge(edge_t *e)
Definition fastgr.c:69
static void basic_merge(edge_t *e, edge_t *rep)
Definition fastgr.c:278
void merge_oneway(edge_t *e, edge_t *rep)
Definition fastgr.c:291
void delete_fast_node(graph_t *g, node_t *n)
Definition fastgr.c:191
void safe_other_edge(edge_t *e)
Definition fastgr.c:120
edge_t * virtual_edge(node_t *u, node_t *v, edge_t *orig)
Definition fastgr.c:172
#define NAME
Definition gmlparse.c:377
static attrs_t * L
Definition gmlparse.c:93
node NULL
Definition grammar.y:163
#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:880
#define ED_edge_type(e)
Definition types.h:582
#define ED_weight(e)
Definition types.h:603
#define aghead(e)
Definition cgraph.h:881
#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:158
#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:425
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