Graphviz 16.1.3~dev.20261121.1645
Loading...
Searching...
No Matches
edge.c
Go to the documentation of this file.
1
6/*************************************************************************
7 * Copyright (c) 2011 AT&T Intellectual Property
8 * All rights reserved. This program and the accompanying materials
9 * are made available under the terms of the Eclipse Public License v2.0
10 * which accompanies this distribution, and is available at
11 * https://www.eclipse.org/org/documents/epl-2.0/EPL-2.0.html
12 *
13 * Contributors: Details at https://graphviz.org
14 *************************************************************************/
15
16#include "config.h"
17
18#include <assert.h>
19#include <cgraph/cghdr.h>
20#include <cgraph/node_set.h>
21#include <stdbool.h>
22#include <stddef.h>
23#include <stdlib.h>
24#include <util/alloc.h>
25#include <util/unused.h>
26
27/* return first outedge of <n> */
29 Agsubnode_t *sn;
30 Agedge_t *e = NULL;
31
32 sn = agsubrep(g, n);
33 if (sn) {
34 dtrestore(g->e_seq, sn->out_seq);
35 e = dtfirst(g->e_seq);
36 sn->out_seq = dtextract(g->e_seq);
37 }
38 return e;
39}
40
41/* return outedge that follows <e> of <n> */
43 Agnode_t *n;
44 Agsubnode_t *sn;
45 Agedge_t *f = NULL;
46
47 n = AGTAIL(e);
48 sn = agsubrep(g, n);
49 if (sn) {
50 dtrestore(g->e_seq, sn->out_seq);
51 f = dtnext(g->e_seq, e);
52 sn->out_seq = dtextract(g->e_seq);
53 }
54 return f;
55}
56
58 Agsubnode_t *sn;
59 Agedge_t *e = NULL;
60
61 sn = agsubrep(g, n);
62 if (sn) {
63 dtrestore(g->e_seq, sn->in_seq);
64 e = dtfirst(g->e_seq);
65 sn->in_seq = dtextract(g->e_seq);
66 }
67 return e;
68}
69
71 Agnode_t *n;
72 Agsubnode_t *sn;
73 Agedge_t *f = NULL;
74
75 n = AGHEAD(e);
76 sn = agsubrep(g, n);
77 if (sn) {
78 dtrestore(g->e_seq, sn->in_seq);
79 f = dtnext(g->e_seq, e);
80 sn->in_seq = dtextract(g->e_seq);
81 }
82 return f;
83}
84
86 Agedge_t *rv;
87 rv = agfstout(g, n);
88 if (rv == NULL)
89 rv = agfstin(g, n);
90 return rv;
91}
92
94 Agedge_t *rv;
95
96 if (AGTYPE(e) == AGOUTEDGE) {
97 rv = agnxtout(g, e);
98 if (rv == NULL) {
99 do {
100 rv = !rv ? agfstin(g, n) : agnxtin(g, rv);
101 } while (rv && rv->node == n);
102 }
103 } else {
104 do {
105 rv = agnxtin(g, e); /* so that we only see each edge once, */
106 e = rv;
107 } while (rv && rv->node == n); /* ignore loops as in-edges */
108 }
109 return rv;
110}
111
112/* internal edge set lookup */
114 Agtag_t key) {
115 Agedge_t *e;
116 Agsubnode_t *sn;
117
118 if (t == NULL || h == NULL)
119 return NULL;
120 // guess that fan-in < fan-out, and thus searching `h`’s edges for `t` is
121 // cheaper than searching `t`’s edges for `h`
122 sn = agsubrep(g, h);
123 if (!sn)
124 e = 0;
125 else {
126 dtrestore(g->e_id, sn->in_id);
127 e = dtsearch(g->e_id, &((Agedge_t){.base = {.tag = key}, .node = t}));
128 sn->in_id = dtextract(g->e_id);
129 }
130 return e;
131}
132
134 IDTYPE id) {
135 Agtag_t tag = {.objtype = AGEDGE, .id = id};
136 return agfindedge_by_key(g, t, h, tag);
137}
138
140 return g == n->root ? &n->mainsub : node_set_find(g->n_id, n->base.tag.id);
141}
142
143static void ins(Dict_t *d, Dtlink_t **set, Agedge_t *e) {
144 dtrestore(d, *set);
145 dtinsert(d, e);
146 *set = dtextract(d);
147}
148
149static void del(Dict_t *d, Dtlink_t **set, Agedge_t *e) {
150 dtrestore(d, *set);
151 void *x UNUSED = dtdelete(d, e);
152 assert(x);
153 *set = dtextract(d);
154}
155
156static void installedge(Agraph_t *g, Agedge_t *e) {
157 Agedge_t *const out = AGMKOUT(e);
158 Agedge_t *const in = AGMKIN(e);
159 Agnode_t *const t = agtail(e);
160 Agnode_t *const h = aghead(e);
161 while (g) {
162 if (agfindedge_by_key(g, t, h, AGTAG(e)))
163 break;
164 Agsubnode_t *sn = agsubrep(g, t);
165 ins(g->e_seq, &sn->out_seq, out);
166 ins(g->e_id, &sn->out_id, out);
167 sn = agsubrep(g, h);
168 ins(g->e_seq, &sn->in_seq, in);
169 ins(g->e_id, &sn->in_id, in);
170 g = agparent(g);
171 }
172}
173
174static void subedge(Agraph_t *g, Agedge_t *e) {
175 installedge(g, e);
176 /* might an init method call be needed here? */
177}
178
180 Agedge_t *in, *out;
181
182 (void)agsubnode(g, t, 1);
183 (void)agsubnode(g, h, 1);
184 Agedgepair_t *e2 = gv_alloc(sizeof(Agedgepair_t));
185 in = &e2->in;
186 out = &e2->out;
187 uint64_t seq = agnextseq(g, AGEDGE);
188 assert((seq & SEQ_MASK) == seq && "sequence ID overflow");
189 AGTYPE(in) = AGINEDGE;
191 AGID(in) = AGID(out) = id;
192 AGSEQ(in) = AGSEQ(out) = seq & SEQ_MASK;
193 in->node = t;
194 out->node = h;
195
196 installedge(g, out);
197 if (g->desc.has_attrs) {
198 (void)agbindrec(out, AgDataRecName, sizeof(Agattr_t), false);
200 }
201 agmethod_init(g, out);
202 return out;
203}
204
205/* edge creation predicate */
206static bool ok_to_make_edge(Agraph_t *g, Agnode_t *t, Agnode_t *h) {
207 /* protect against self, multi-edges in strict graphs */
208 if (agisstrict(g)) {
209 if (agfindedge_by_key(g, t, h, (Agtag_t){0} /* wild card */))
210 return false;
211 }
212 if (g->desc.no_loop && (t == h)) /* simple graphs */
213 return false;
214 return true;
215}
216
218 int cflag) {
219 Agraph_t *root;
220 Agedge_t *e;
221
222 e = agfindedge_by_id(g, t, h, id);
223 if (e == NULL && agisundirected(g))
224 e = agfindedge_by_id(g, h, t, id);
225 if (e == NULL && cflag && ok_to_make_edge(g, t, h)) {
226 root = agroot(g);
227 if (g != root && (e = agfindedge_by_id(root, t, h, id))) {
228 subedge(g, e); /* old */
229 }
230 }
231 return e;
232}
233
234Agedge_t *agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int cflag) {
235 Agedge_t *e;
236 IDTYPE my_id;
237
238 int have_id = agmapnametoid(g, AGEDGE, name, &my_id, false);
239 if (have_id || (name == NULL && (!cflag || agisstrict(g)))) {
240 /* probe for pre-existing edge */
241 Agtag_t key = {0};
242 if (have_id) {
243 key.id = my_id;
244 key.objtype = AGEDGE;
245 }
246
247 /* might already exist locally */
248 e = agfindedge_by_key(g, t, h, key);
249 if (e == NULL && agisundirected(g))
250 e = agfindedge_by_key(g, h, t, key);
251 if (e)
252 return e;
253 if (cflag) {
254 e = agfindedge_by_key(agroot(g), t, h, key);
255 if (e == NULL && agisundirected(g))
256 e = agfindedge_by_key(agroot(g), h, t, key);
257 if (e) {
258 subedge(g, e);
259 return e;
260 }
261 }
262 }
263
264 if (cflag && ok_to_make_edge(g, t, h) &&
265 agmapnametoid(g, AGEDGE, name, &my_id, true)) { /* reserve id */
266 e = newedge(g, t, h, my_id);
267 agregister(g, AGEDGE, e); /* register new object in external namespace */
268 } else
269 e = NULL;
270 return e;
271}
272
273void agdeledgeimage(Agraph_t *g, Agobj_t *edge, void *ignored) {
274 Agedge_t *e = (Agedge_t *)((char *)edge - offsetof(Agedge_t, base));
275 Agedge_t *in, *out;
276 Agnode_t *t, *h;
277 Agsubnode_t *sn;
278
279 (void)ignored;
280 if (AGTYPE(e) == AGINEDGE) {
281 in = e;
282 out = AGIN2OUT(e);
283 } else {
284 out = e;
285 in = AGOUT2IN(e);
286 }
287 t = in->node;
288 h = out->node;
289 sn = agsubrep(g, t);
290 del(g->e_seq, &sn->out_seq, out);
291 del(g->e_id, &sn->out_id, out);
292 sn = agsubrep(g, h);
293 del(g->e_seq, &sn->in_seq, in);
294 del(g->e_id, &sn->in_id, in);
295#ifdef DEBUG
296 for (e = agfstin(g, h); e; e = agnxtin(g, e))
297 assert(e != in);
298 for (e = agfstout(g, t); e; e = agnxtout(g, e))
299 assert(e != out);
300#endif
301}
302
304 e = AGMKOUT(e);
305 if (agfindedge_by_key(g, agtail(e), aghead(e), AGTAG(e)) == NULL)
306 return FAILURE;
307
308 if (g == agroot(g)) {
309 if (g->desc.has_attrs)
311 agmethod_delete(g, e);
312 agrecclose(&e->base);
313 agfreeid(g, AGEDGE, AGID(e));
314 }
315 if (agapply(g, &e->base, agdeledgeimage, NULL, false) == SUCCESS) {
316 if (g == agroot(g))
317 free(e);
318 return SUCCESS;
319 } else
320 return FAILURE;
321}
322
323Agedge_t *agsubedge(Agraph_t *g, Agedge_t *e, int cflag) {
324 Agnode_t *t;
325 Agedge_t *rv;
326
327 rv = NULL;
328 t = agsubnode(g, AGTAIL(e), cflag);
329 if (t != NULL || cflag) {
330 Agnode_t *const h = agsubnode(g, AGHEAD(e), cflag);
331 if (t != NULL && h != NULL) {
332 rv = agfindedge_by_key(g, t, h, AGTAG(e));
333 if (cflag && rv == NULL) {
334 installedge(g, e);
335 rv = e;
336 }
337 if (rv && AGTYPE(rv) != AGTYPE(e))
338 rv = AGOPP(rv);
339 }
340 }
341 return rv;
342}
343
344/* edge comparison. AGTYPE(e) == 0 means ID is a wildcard. */
345static int agedgeidcmpf(void *arg_e0, void *arg_e1) {
346 Agedge_t *e0 = arg_e0;
347 Agedge_t *e1 = arg_e1;
348
349 if (AGID(e0->node) < AGID(e1->node))
350 return -1;
351 if (AGID(e0->node) > AGID(e1->node))
352 return 1;
353 /* same node */
354 if (AGTYPE(e0) != 0 && AGTYPE(e1) != 0) {
355 if (AGID(e0) < AGID(e1))
356 return -1;
357 if (AGID(e0) > AGID(e1))
358 return 1;
359 }
360 return 0;
361}
362
363/* edge comparison. for ordered traversal. */
364static int agedgeseqcmpf(void *arg_e0, void *arg_e1) {
365 Agedge_t *e0 = arg_e0;
366 Agedge_t *e1 = arg_e1;
367 assert(arg_e0 && arg_e1);
368
369 if (e0->node != e1->node) {
370 if (AGSEQ(e0->node) < AGSEQ(e1->node))
371 return -1;
372 if (AGSEQ(e0->node) > AGSEQ(e1->node))
373 return 1;
374 } else {
375 if (AGSEQ(e0) < AGSEQ(e1))
376 return -1;
377 if (AGSEQ(e0) > AGSEQ(e1))
378 return 1;
379 }
380 return 0;
381}
382
383/* indexing for ordered traversal */
385 .link = offsetof(Agedge_t, seq_link), // use internal links
386 .comparf = agedgeseqcmpf,
387};
388
390 .link = -1, // use external holder objects
391 .comparf = agedgeseqcmpf,
392};
393
394/* indexing for random search */
396 .link = offsetof(Agedge_t, id_link), // use internal links
397 .comparf = agedgeidcmpf,
398};
399
401 .link = -1, // use external holder objects
402 .comparf = agedgeidcmpf,
403};
404
405/* expose macros as functions for ease of debugging
406and to expose them to foreign languages without C preprocessor. */
407#ifdef ageqedge
408#undef ageqedge
409#endif
410CGRAPH_API int ageqedge(Agedge_t *e, Agedge_t *f);
411CGRAPH_API int ageqedge(Agedge_t *e, Agedge_t *f) { return AGEQEDGE(e, f); }
412
413#ifdef agmkout
414#undef agmkout
415#endif
416CGRAPH_API Agedge_t *agmkout(Agedge_t *e);
417CGRAPH_API Agedge_t *agmkout(Agedge_t *e) { return AGMKOUT(e); }
418
419#ifdef agmkin
420#undef agmkin
421#endif
422CGRAPH_API Agedge_t *agmkin(Agedge_t *e);
423CGRAPH_API Agedge_t *agmkin(Agedge_t *e) { return AGMKIN(e); }
424
425#ifdef agtail
426#undef agtail
427#endif
428CGRAPH_API Agnode_t *agtail(Agedge_t *e);
429CGRAPH_API Agnode_t *agtail(Agedge_t *e) { return AGTAIL(e); }
430
431#ifdef aghead
432#undef aghead
433#endif
434CGRAPH_API Agnode_t *aghead(Agedge_t *e);
435CGRAPH_API Agnode_t *aghead(Agedge_t *e) { return AGHEAD(e); }
436
437#ifdef agopp
438#undef agopp
439#endif
440CGRAPH_API Agedge_t *agopp(Agedge_t *e);
441CGRAPH_API Agedge_t *agopp(Agedge_t *e) { return AGOPP(e); }
static void out(agerrlevel_t level, const char *fmt, va_list args)
Report messages using a user-supplied or default write function.
Definition agerror.c:86
Memory allocation wrappers that exit on failure.
static void * gv_alloc(size_t size)
Definition alloc.h:47
int agapply(Agraph_t *g, Agobj_t *obj, agobjfn_t fn, void *arg, int preorder)
Definition apply.c:62
const char AgDataRecName[]
Definition attr.c:156
CDT_API Dtlink_t * dtextract(Dt_t *)
Definition dtextract.c:11
#define dtsearch(d, o)
Definition cdt.h:184
#define dtinsert(d, o)
Definition cdt.h:186
#define dtdelete(d, o)
Definition cdt.h:187
CDT_API int dtrestore(Dt_t *, Dtlink_t *)
Definition dtrestore.c:13
#define dtnext(d, o)
Definition cdt.h:181
#define dtfirst(d)
Definition cdt.h:180
cgraph.h additions
void agfreeid(Agraph_t *g, int objtype, IDTYPE id)
Definition id.c:133
void agrecclose(Agobj_t *obj)
Definition rec.c:229
int agmapnametoid(Agraph_t *g, int objtype, char *str, IDTYPE *result, bool createflag)
Definition id.c:104
uint64_t agnextseq(Agraph_t *g, int objtype)
Definition graph.c:156
#define FAILURE
Definition cghdr.h:45
void agregister(Agraph_t *g, int objtype, void *obj)
Definition id.c:172
#define SUCCESS
Definition cghdr.h:44
@ SEQ_MASK
Definition cghdr.h:73
Agsubnode_t * node_set_find(node_set_t *self, IDTYPE key)
Definition node.c:483
static int in(Extype_t lhs, Exid_t *rhs, Exdisc_t *disc)
Definition compile.c:1645
static bool ok_to_make_edge(Agraph_t *g, Agnode_t *t, Agnode_t *h)
Definition edge.c:206
static int agedgeseqcmpf(void *arg_e0, void *arg_e1)
Definition edge.c:364
static Agedge_t * agfindedge_by_id(Agraph_t *g, Agnode_t *t, Agnode_t *h, IDTYPE id)
Definition edge.c:133
static Agedge_t * newedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, IDTYPE id)
Definition edge.c:179
Agedge_t * agmkout(Agedge_t *e)
Definition edge.c:417
Agedge_t * agmkin(Agedge_t *e)
Definition edge.c:423
static void subedge(Agraph_t *g, Agedge_t *e)
Definition edge.c:174
Dtdisc_t Ag_subedge_seq_disc
Definition edge.c:389
static Agedge_t * agfindedge_by_key(Agraph_t *g, Agnode_t *t, Agnode_t *h, Agtag_t key)
Definition edge.c:113
static int agedgeidcmpf(void *arg_e0, void *arg_e1)
Definition edge.c:345
static void ins(Dict_t *d, Dtlink_t **set, Agedge_t *e)
Definition edge.c:143
Dtdisc_t Ag_mainedge_seq_disc
Definition edge.c:384
static void del(Dict_t *d, Dtlink_t **set, Agedge_t *e)
Definition edge.c:149
Dtdisc_t Ag_subedge_id_disc
Definition edge.c:400
void agdeledgeimage(Agraph_t *g, Agobj_t *edge, void *ignored)
Definition edge.c:273
Dtdisc_t Ag_mainedge_id_disc
Definition edge.c:395
static void installedge(Agraph_t *g, Agedge_t *e)
Definition edge.c:156
void free(void *)
edge
Definition gmlparse.y:246
node NULL
Definition grammar.y:181
void agedgeattr_init(Agraph_t *g, Agedge_t *e)
Definition attr.c:428
void agedgeattr_delete(Agedge_t *e)
Definition attr.c:437
void agmethod_delete(Agraph_t *g, void *obj)
Definition obj.c:140
void agmethod_init(Agraph_t *g, void *obj)
Definition obj.c:80
Agedge_t * agedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, char *name, int cflag)
Definition edge.c:234
Agedge_t * agidedge(Agraph_t *g, Agnode_t *t, Agnode_t *h, IDTYPE id, int cflag)
Definition edge.c:217
#define agopp(e)
opposite edge: flip Agedgepair_s.out ⇄ Agedgepair_s.in/*#end#*‍/
Definition cgraph.h:984
#define AGMKOUT(e)
Definition cgraph.h:976
Agedge_t * agsubedge(Agraph_t *g, Agedge_t *e, int cflag)
Definition edge.c:323
#define AGIN2OUT(inedge)
Agedgepair_s.in -> Agedgepair_s.out.
Definition cgraph.h:971
int agdeledge(Agraph_t *g, Agedge_t *e)
Definition edge.c:303
Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition edge.c:70
#define AGEQEDGE(e, f)
Definition cgraph.h:980
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:28
#define ageqedge(e, f)
edges are equal
Definition cgraph.h:987
#define AGMKIN(e)
Definition cgraph.h:977
#define agtail(e)
Definition cgraph.h:982
Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition edge.c:93
#define aghead(e)
Definition cgraph.h:983
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:42
Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition edge.c:85
#define AGTAIL(e)
Definition cgraph.h:978
Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition edge.c:57
#define AGOPP(e)
Definition cgraph.h:975
#define AGHEAD(e)
Definition cgraph.h:979
#define AGOUT2IN(outedge)
Agedgepair_s.out -> Agedgepair_s.in/*#end#*‍/.
Definition cgraph.h:972
int agisstrict(Agraph_t *g)
Definition graph.c:194
int agisundirected(Agraph_t *g)
Definition graph.c:189
Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition node.c:254
Agsubnode_t * agsubrep(Agraph_t *g, Agnode_t *n)
Definition edge.c:139
#define AGID(obj)
returns the unique integer ID associated with the object
Definition cgraph.h:221
uint64_t IDTYPE
unique per main graph ID
Definition cgraph.h:73
#define AGTYPE(obj)
returns AGRAPH, AGNODE, or AGEDGE depending on the type of the object
Definition cgraph.h:216
#define AGTAG(obj)
Definition cgraph.h:215
Agraph_t * agroot(void *obj)
Definition obj.c:170
#define AGSEQ(obj)
Definition cgraph.h:225
@ AGOUTEDGE
Definition cgraph.h:207
@ AGEDGE
Definition cgraph.h:207
@ AGINEDGE
Definition cgraph.h:207
void * agbindrec(void *obj, const char *name, unsigned int recsize, int move_to_front)
attaches a new record of the given size to the object
Definition rec.c:91
Agraph_t * agparent(Agraph_t *g)
Definition subg.c:85
static uint64_t id
Definition gv2gml.c:42
unordered set of Agsubnode_t *
string attribute container
Definition cgraph.h:633
unsigned has_attrs
Definition cgraph.h:290
unsigned no_loop
Definition cgraph.h:287
Agnode_t * node
Definition cgraph.h:272
Agobj_t base
Definition cgraph.h:269
Agedge_t in
Definition cgraph.h:276
Agedge_t out
Definition cgraph.h:276
Agsubnode_t mainsub
Definition cgraph.h:262
Agraph_t * root
Definition cgraph.h:261
Agobj_t base
Definition cgraph.h:260
a generic header of Agraph_s, Agnode_s and Agedge_s
Definition cgraph.h:210
Agtag_t tag
access with AGTAG
Definition cgraph.h:211
graph or subgraph
Definition cgraph.h:424
struct graphviz_node_set * n_id
the node set indexed by ID
Definition cgraph.h:430
Dict_t * e_seq
Definition cgraph.h:431
Agdesc_t desc
Definition cgraph.h:426
Dict_t * e_id
holders for edge sets
Definition cgraph.h:431
This is the node struct allocated per graph (or subgraph).
Definition cgraph.h:251
Dtlink_t * out_seq
Definition cgraph.h:256
Dtlink_t * out_id
Definition cgraph.h:255
Dtlink_t * in_id
Definition cgraph.h:255
Dtlink_t * in_seq
Definition cgraph.h:256
tag in Agobj_s for graphs, nodes, and edges.
Definition cgraph.h:197
unsigned objtype
access with AGTYPE
Definition cgraph.h:199
IDTYPE id
Definition cgraph.h:203
Definition cdt.h:98
int link
Definition cdt.h:87
abstraction for squashing compiler warnings for unused symbols
#define UNUSED
Definition unused.h:25