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