Graphviz 13.1.0~dev.20250626.0830
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 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
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/* Create and return a new virtual edge e attached to orig.
126 * ED_to_orig(e) = orig
127 * ED_to_virt(orig) = e if e is the first virtual edge attached.
128 * orig might be an input edge, reverse of an input edge, or virtual edge
129 */
131{
132 Agedgepair_t* e2 = gv_alloc(sizeof(Agedgepair_t));
133 AGTYPE(&e2->in) = AGINEDGE;
134 AGTYPE(&e2->out) = AGOUTEDGE;
135 e2->out.base.data = gv_alloc(sizeof(Agedgeinfo_t));
136 edge_t *e = &e2->out;
137 agtail(e) = u;
138 aghead(e) = v;
140
141 if (orig) {
142 AGSEQ(e) = AGSEQ(orig);
143 AGSEQ(&(e2->in)) = AGSEQ(orig);
144 ED_count(e) = ED_count(orig);
145 ED_xpenalty(e) = ED_xpenalty(orig);
146 ED_weight(e) = ED_weight(orig);
147 ED_minlen(e) = ED_minlen(orig);
148 if (agtail(e) == agtail(orig))
149 ED_tail_port(e) = ED_tail_port(orig);
150 else if (agtail(e) == aghead(orig))
151 ED_tail_port(e) = ED_head_port(orig);
152 if (aghead(e) == aghead(orig))
153 ED_head_port(e) = ED_head_port(orig);
154 else if (aghead(e) == agtail(orig))
155 ED_head_port(e) = ED_tail_port(orig);
156
157 if (ED_to_virt(orig) == NULL)
158 ED_to_virt(orig) = e;
159 ED_to_orig(e) = orig;
160 } else {
161 ED_weight(e) = 1;
162 ED_xpenalty(e) = 1;
163 ED_count(e) = 1;
164 ED_minlen(e) = 1;
165 }
166 return e;
167}
168
170{
171 return fast_edge(new_virtual_edge(u, v, orig));
172}
173
175{
176
177#ifdef DEBUG
178 assert(find_fast_node(g, n) == NULL);
179#endif
180 ND_next(n) = GD_nlist(g);
181 if (ND_next(n))
182 ND_prev(ND_next(n)) = n;
183 GD_nlist(g) = n;
184 ND_prev(n) = NULL;
185 assert(n != ND_next(n));
186}
187
189{
190 assert(find_fast_node(g, n));
191 if (ND_next(n))
192 ND_prev(ND_next(n)) = ND_prev(n);
193 if (ND_prev(n))
194 ND_next(ND_prev(n)) = ND_next(n);
195 else
196 GD_nlist(g) = ND_next(n);
197}
198
200 node_t *n = gv_alloc(sizeof(node_t));
201 AGTYPE(n) = AGNODE;
202 n->base.data = gv_alloc(sizeof(Agnodeinfo_t));
203 n->root = agroot(g);
205 ND_lw(n) = ND_rw(n) = 1;
206 ND_ht(n) = 1;
207 ND_UF_size(n) = 1;
208 alloc_elist(4, ND_in(n));
209 alloc_elist(4, ND_out(n));
210 fast_node(g, n);
211 return n;
212}
213
215{
219}
220
222{
223 assert(e != NULL);
224 if (ED_to_orig(e) && ED_to_virt(ED_to_orig(e)) == e)
227 zapinlist(&ND_flat_in(aghead(e)), e);
228}
229
230#ifdef DEBUG
231static char *NAME(node_t * n)
232{
233 static char buf[20];
234 if (ND_node_type(n) == NORMAL)
235 return agnameof(n);
236 snprintf(buf, sizeof(buf), "V%p", n);
237 return buf;
238}
239
240void fastgr(graph_t * g)
241{
242 int i, j;
243 node_t *n, *w;
244 edge_t *e, *f;
245
246 for (n = GD_nlist(g); n; n = ND_next(n)) {
247 fprintf(stderr, "%s %d: (", NAME(n), ND_rank(n));
248 for (i = 0; (e = ND_out(n).list[i]); i++) {
249 fprintf(stderr, " %s:%d", NAME(aghead(e)), ED_count(e));
250 w = aghead(e);
251 if (g == agroot(g)) {
252 for (j = 0; (f = ND_in(w).list[j]); j++)
253 if (e == f)
254 break;
255 assert(f != NULL);
256 }
257 }
258 fprintf(stderr, " ) (");
259 for (i = 0; (e = ND_in(n).list[i]); i++) {
260 fprintf(stderr, " %s:%d", NAME(agtail(e)), ED_count(e));
261 w = agtail(e);
262 if (g == agroot(g)) {
263 for (j = 0; (f = ND_out(w).list[j]); j++)
264 if (e == f)
265 break;
266 assert(f != NULL);
267 }
268 }
269 fprintf(stderr, " )\n");
270 }
271}
272#endif
273
274static void
276{
277 if (ED_minlen(rep) < ED_minlen(e))
278 ED_minlen(rep) = ED_minlen(e);
279 while (rep) {
280 ED_count(rep) += ED_count(e);
281 ED_xpenalty(rep) += ED_xpenalty(e);
282 ED_weight(rep) += ED_weight(e);
283 rep = ED_to_virt(rep);
284 }
285}
286
287void
289{
290 if (rep == ED_to_virt(e) || e == ED_to_virt(rep)) {
291 agwarningf("merge_oneway glitch\n");
292 return;
293 }
294 assert(ED_to_virt(e) == NULL);
295 ED_to_virt(e) = rep;
296 basic_merge(e, rep);
297}
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: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:130
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:174
node_t * virtual_node(graph_t *g)
Definition fastgr.c:199
void flat_edge(graph_t *g, edge_t *e)
Definition fastgr.c:214
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:221
edge_t * fast_edge(edge_t *e)
Definition fastgr.c:69
static void basic_merge(edge_t *e, edge_t *rep)
Definition fastgr.c:275
void merge_oneway(edge_t *e, edge_t *rep)
Definition fastgr.c:288
void delete_fast_node(graph_t *g, node_t *n)
Definition fastgr.c:188
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:169
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