1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3
4 /*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14 #include <cghdr.h>
15
16 #define IN_SET FALSE
17 #define OUT_SET TRUE
18 #define ID_ORDER TRUE
19 #define SEQ_ORDER FALSE
20
21 static Agtag_t Tag; /* to silence warnings about initialization */
22
23
24 /* return first outedge of <n> */
agfstout(Agraph_t * g,Agnode_t * n)25 Agedge_t *agfstout(Agraph_t * g, Agnode_t * n)
26 {
27 Agsubnode_t *sn;
28 Agedge_t *e = NILedge;
29
30 sn = agsubrep(g, n);
31 if (sn) {
32 dtrestore(g->e_seq, sn->out_seq);
33 e = (Agedge_t *) dtfirst(g->e_seq);
34 sn->out_seq = dtextract(g->e_seq);
35 }
36 return e;
37 }
38
39 /* return outedge that follows <e> of <n> */
agnxtout(Agraph_t * g,Agedge_t * e)40 Agedge_t *agnxtout(Agraph_t * g, Agedge_t * e)
41 {
42 Agnode_t *n;
43 Agsubnode_t *sn;
44 Agedge_t *f = NILedge;
45
46 n = AGTAIL(e);
47 sn = agsubrep(g, n);
48 if (sn) {
49 dtrestore(g->e_seq, sn->out_seq);
50 f = (Agedge_t *) dtnext(g->e_seq, e);
51 sn->out_seq = dtextract(g->e_seq);
52 }
53 return f;
54 }
55
agfstin(Agraph_t * g,Agnode_t * n)56 Agedge_t *agfstin(Agraph_t * g, Agnode_t * n)
57 {
58 Agsubnode_t *sn;
59 Agedge_t *e = NILedge;
60
61 sn = agsubrep(g, n);
62 if (sn) {
63 dtrestore(g->e_seq, sn->in_seq);
64 e = (Agedge_t *) dtfirst(g->e_seq);
65 sn->in_seq = dtextract(g->e_seq);
66 }
67 return e;
68 }
69
agnxtin(Agraph_t * g,Agedge_t * e)70 Agedge_t *agnxtin(Agraph_t * g, Agedge_t * e)
71 {
72 Agnode_t *n;
73 Agsubnode_t *sn;
74 Agedge_t *f = NILedge;
75
76 n = AGHEAD(e);
77 sn = agsubrep(g, n);
78 if (sn) {
79 dtrestore(g->e_seq, sn->in_seq);
80 f = (Agedge_t *) dtnext(g->e_seq, e);
81 sn->in_seq = dtextract(g->e_seq);
82 }
83 return f;
84 }
85
agfstedge(Agraph_t * g,Agnode_t * n)86 Agedge_t *agfstedge(Agraph_t * g, Agnode_t * n)
87 {
88 Agedge_t *rv;
89 rv = agfstout(g, n);
90 if (rv == NILedge)
91 rv = agfstin(g, n);
92 return rv;
93 }
94
agnxtedge(Agraph_t * g,Agedge_t * e,Agnode_t * n)95 Agedge_t *agnxtedge(Agraph_t * g, Agedge_t * e, Agnode_t * n)
96 {
97 Agedge_t *rv;
98
99 if (AGTYPE(e) == AGOUTEDGE) {
100 rv = agnxtout(g, e);
101 if (rv == NILedge) {
102 do {
103 rv = !rv ? agfstin(g, n) : agnxtin(g,rv);
104 } while (rv && (rv->node == n));
105 }
106 } else {
107 do {
108 rv = agnxtin(g, e); /* so that we only see each edge once, */
109 e = rv;
110 } while (rv && (rv->node == n)); /* ignore loops as in-edges */
111 }
112 return rv;
113 }
114
115 /* internal edge set lookup */
agfindedge_by_key(Agraph_t * g,Agnode_t * t,Agnode_t * h,Agtag_t key)116 static Agedge_t *agfindedge_by_key(Agraph_t * g, Agnode_t * t, Agnode_t * h,
117 Agtag_t key)
118 {
119 Agedge_t *e, template;
120 Agsubnode_t *sn;
121
122 if ((t == NILnode) || (h == NILnode))
123 return NILedge;
124 template.base.tag = key;
125 template.node = t; /* guess that fan-in < fan-out */
126 sn = agsubrep(g, h);
127 if (!sn) e = 0;
128 else {
129 #if 0
130 if (t != h) {
131 #endif
132 dtrestore(g->e_id, sn->in_id);
133 e = (Agedge_t *) dtsearch(g->e_id, &template);
134 sn->in_id = dtextract(g->e_id);
135 #if 0
136 } else { /* self edge */
137 dtrestore(g->e_id, sn->out_id);
138 e = (Agedge_t *) dtsearch(g->e_id, &template);
139 sn->out_id = dtextract(g->e_id);
140 }
141 #endif
142 }
143 return e;
144 }
145
agfindedge_by_id(Agraph_t * g,Agnode_t * t,Agnode_t * h,IDTYPE id)146 static Agedge_t *agfindedge_by_id(Agraph_t * g, Agnode_t * t, Agnode_t * h,
147 IDTYPE id)
148 {
149 Agtag_t tag;
150
151 tag = Tag;
152 tag.objtype = AGEDGE;
153 tag.id = id;
154 return agfindedge_by_key(g, t, h, tag);
155 }
156
agsubrep(Agraph_t * g,Agnode_t * n)157 Agsubnode_t *agsubrep(Agraph_t * g, Agnode_t * n)
158 {
159 Agsubnode_t *sn, template;
160
161 if (g == n->root) sn = &(n->mainsub);
162 else {
163 template.node = n;
164 sn = dtsearch(g->n_id, &template);
165 }
166 return sn;
167 }
168
ins(Dict_t * d,Dtlink_t ** set,Agedge_t * e)169 static void ins(Dict_t * d, Dtlink_t ** set, Agedge_t * e)
170 {
171 dtrestore(d, *set);
172 dtinsert(d, e);
173 *set = dtextract(d);
174 }
175
del(Dict_t * d,Dtlink_t ** set,Agedge_t * e)176 static void del(Dict_t * d, Dtlink_t ** set, Agedge_t * e)
177 {
178 void *x;
179 dtrestore(d, *set);
180 x = dtdelete(d, e);
181 assert(x);
182 *set = dtextract(d);
183 }
184
installedge(Agraph_t * g,Agedge_t * e)185 static void installedge(Agraph_t * g, Agedge_t * e)
186 {
187 Agnode_t *t, *h;
188 Agedge_t *out, *in;
189 Agsubnode_t *sn;
190
191 out = AGMKOUT(e);
192 in = AGMKIN(e);
193 t = agtail(e);
194 h = aghead(e);
195 while (g) {
196 if (agfindedge_by_key(g, t, h, AGTAG(e))) break;
197 sn = agsubrep(g, t);
198 ins(g->e_seq, &sn->out_seq, out);
199 ins(g->e_id, &sn->out_id, out);
200 sn = agsubrep(g, h);
201 ins(g->e_seq, &sn->in_seq, in);
202 ins(g->e_id, &sn->in_id, in);
203 g = agparent(g);
204 }
205 }
206
subedge(Agraph_t * g,Agedge_t * e)207 static void subedge(Agraph_t * g, Agedge_t * e)
208 {
209 installedge(g, e);
210 /* might an init method call be needed here? */
211 }
212
newedge(Agraph_t * g,Agnode_t * t,Agnode_t * h,IDTYPE id)213 static Agedge_t *newedge(Agraph_t * g, Agnode_t * t, Agnode_t * h,
214 IDTYPE id)
215 {
216 Agedgepair_t *e2;
217 Agedge_t *in, *out;
218 int seq;
219
220 (void)agsubnode(g,t,TRUE);
221 (void)agsubnode(g,h,TRUE);
222 e2 = (Agedgepair_t *) agalloc(g, sizeof(Agedgepair_t));
223 in = &(e2->in);
224 out = &(e2->out);
225 seq = agnextseq(g, AGEDGE);
226 AGTYPE(in) = AGINEDGE;
227 AGTYPE(out) = AGOUTEDGE;
228 AGID(in) = AGID(out) = id;
229 AGSEQ(in) = AGSEQ(out) = seq;
230 in->node = t;
231 out->node = h;
232
233 installedge(g, out);
234 if (g->desc.has_attrs) {
235 (void) agbindrec(out, AgDataRecName, sizeof(Agattr_t), FALSE);
236 agedgeattr_init(g, out);
237 }
238 agmethod_init(g, out);
239 return out;
240 }
241
242 /* edge creation predicate */
ok_to_make_edge(Agraph_t * g,Agnode_t * t,Agnode_t * h)243 static int ok_to_make_edge(Agraph_t * g, Agnode_t * t, Agnode_t * h)
244 {
245 Agtag_t key;
246
247 /* protect against self, multi-edges in strict graphs */
248 if (agisstrict(g)) {
249 key = Tag;
250 key.objtype = 0; /* wild card */
251 if (agfindedge_by_key(g, t, h, key))
252 return FALSE;
253 }
254 if (g->desc.no_loop && (t == h)) /* simple graphs */
255 return FALSE;
256 return TRUE;
257 }
258
agidedge(Agraph_t * g,Agnode_t * t,Agnode_t * h,IDTYPE id,int cflag)259 Agedge_t *agidedge(Agraph_t * g, Agnode_t * t, Agnode_t * h,
260 IDTYPE id, int cflag)
261 {
262 Agraph_t *root;
263 Agedge_t *e;
264
265 e = agfindedge_by_id(g, t, h, id);
266 if ((e == NILedge) && agisundirected(g))
267 e = agfindedge_by_id(g, h, t, id);
268 if ((e == NILedge) && cflag && ok_to_make_edge(g, t, h)) {
269 root = agroot(g);
270 if ((g != root) && ((e = agfindedge_by_id(root, t, h, id)))) {
271 subedge(g, e); /* old */
272 } else {
273 if (agallocid(g, AGEDGE, id)) {
274 e = newedge(g, t, h, id); /* new */
275 }
276 }
277 }
278 return e;
279 }
280
agedge(Agraph_t * g,Agnode_t * t,Agnode_t * h,char * name,int cflag)281 Agedge_t *agedge(Agraph_t * g, Agnode_t * t, Agnode_t * h, char *name,
282 int cflag)
283 {
284 Agedge_t *e;
285 IDTYPE my_id;
286 int have_id;
287
288 have_id = agmapnametoid(g, AGEDGE, name, &my_id, FALSE);
289 if (have_id || ((name == NILstr) && (NOT(cflag) || agisstrict(g)))) {
290 /* probe for pre-existing edge */
291 Agtag_t key;
292 key = Tag;
293 if (have_id) {
294 key.id = my_id;
295 key.objtype = AGEDGE;
296 } else {
297 key.id = key.objtype = 0;
298 }
299
300 /* might already exist locally */
301 e = agfindedge_by_key(g, t, h, key);
302 if ((e == NILedge) && agisundirected(g))
303 e = agfindedge_by_key(g, h, t, key);
304 if (e)
305 return e;
306 if (cflag) {
307 e = agfindedge_by_key(agroot(g), t, h, key);
308 if ((e == NILedge) && agisundirected(g))
309 e = agfindedge_by_key(agroot(g), h, t, key);
310 if (e) {
311 subedge(g,e);
312 return e;
313 }
314 }
315 }
316
317 if (cflag && ok_to_make_edge(g, t, h)
318 && agmapnametoid(g, AGEDGE, name, &my_id, TRUE)) { /* reserve id */
319 e = newedge(g, t, h, my_id);
320 agregister(g, AGEDGE, e); /* register new object in external namespace */
321 }
322 else
323 e = NILedge;
324 return e;
325 }
326
agdeledgeimage(Agraph_t * g,Agedge_t * e,void * ignored)327 void agdeledgeimage(Agraph_t * g, Agedge_t * e, void *ignored)
328 {
329 Agedge_t *in, *out;
330 Agnode_t *t, *h;
331 Agsubnode_t *sn;
332
333 NOTUSED(ignored);
334 if (AGTYPE(e) == AGINEDGE) {
335 in = e;
336 out = AGIN2OUT(e);
337 } else {
338 out = e;
339 in = AGOUT2IN(e);
340 }
341 t = in->node;
342 h = out->node;
343 sn = agsubrep(g, t);
344 del(g->e_seq, &sn->out_seq, out);
345 del(g->e_id, &sn->out_id, out);
346 sn = agsubrep(g, h);
347 del(g->e_seq, &sn->in_seq, in);
348 del(g->e_id, &sn->in_id, in);
349 #ifdef DEBUG
350 for (e = agfstin(g,h); e; e = agnxtin(g,e))
351 assert(e != in);
352 for (e = agfstout(g,t); e; e = agnxtout(g,e))
353 assert(e != out);
354 #endif
355 }
356
agdeledge(Agraph_t * g,Agedge_t * e)357 int agdeledge(Agraph_t * g, Agedge_t * e)
358 {
359 e = AGMKOUT(e);
360 if (agfindedge_by_key(g, agtail(e), aghead(e), AGTAG(e)) == NILedge)
361 return FAILURE;
362
363 if (g == agroot(g)) {
364 if (g->desc.has_attrs)
365 agedgeattr_delete(e);
366 agmethod_delete(g, e);
367 agrecclose((Agobj_t *) e);
368 agfreeid(g, AGEDGE, AGID(e));
369 }
370 if (agapply (g, (Agobj_t *) e, (agobjfn_t) agdeledgeimage, NILedge, FALSE) == SUCCESS) {
371 if (g == agroot(g))
372 agfree(g, e);
373 return SUCCESS;
374 } else
375 return FAILURE;
376 }
377
agsubedge(Agraph_t * g,Agedge_t * e,int cflag)378 Agedge_t *agsubedge(Agraph_t * g, Agedge_t * e, int cflag)
379 {
380 Agnode_t *t, *h;
381 Agedge_t *rv;
382
383 rv = NILedge;
384 t = agsubnode(g, AGTAIL(e), cflag);
385 h = agsubnode(g, AGHEAD(e), cflag);
386 if (t && h) {
387 rv = agfindedge_by_key(g, t, h, AGTAG(e));
388 if (cflag && (rv == NILedge)) {
389 #ifdef OLD_OBSOLETE
390 rv = agfindedge_by_id(g, t, h, AGID(e));
391 if (!rv)
392 rv = newedge(g, t, h, AGID(e));
393 #else
394 installedge(g, e);
395 rv = e;
396 #endif
397 }
398 if (rv && (AGTYPE(rv) != AGTYPE(e)))
399 rv = AGOPP(rv);
400 }
401 return rv;
402 }
403
404 /* edge comparison. AGTYPE(e) == 0 means ID is a wildcard. */
agedgeidcmpf(Dict_t * d,void * arg_e0,void * arg_e1,Dtdisc_t * disc)405 static int agedgeidcmpf(Dict_t * d, void *arg_e0, void *arg_e1, Dtdisc_t * disc)
406 {
407 Agedge_t *e0, *e1;
408
409 NOTUSED(d);
410 e0 = arg_e0;
411 e1 = arg_e1;
412 NOTUSED(disc);
413
414 if (AGID(e0->node) < AGID(e1->node)) return -1;
415 if (AGID(e0->node) > AGID(e1->node)) return 1;
416 /* same node */
417 if ((AGTYPE(e0) != 0) && (AGTYPE(e1) != 0)) {
418 if (AGID(e0) < AGID(e1)) return -1;
419 if (AGID(e0) > AGID(e1)) return 1;
420 }
421 return 0;
422 }
423
424 /* edge comparison. for ordered traversal. */
agedgeseqcmpf(Dict_t * d,void * arg_e0,void * arg_e1,Dtdisc_t * disc)425 static int agedgeseqcmpf(Dict_t * d, void *arg_e0, void *arg_e1, Dtdisc_t * disc)
426 {
427 Agedge_t *e0, *e1;
428
429 NOTUSED(d);
430 e0 = arg_e0;
431 e1 = arg_e1;
432 NOTUSED(disc);
433 assert(arg_e0 && arg_e1);
434
435 if (e0->node != e1->node) {
436 if (AGSEQ(e0->node) < AGSEQ(e1->node)) return -1;
437 if (AGSEQ(e0->node) > AGSEQ(e1->node)) return 1;
438 }
439 else {
440 if (AGSEQ(e0) < AGSEQ(e1)) return -1;
441 if (AGSEQ(e0) > AGSEQ(e1)) return 1;
442 }
443 return 0;
444 }
445
446 /* indexing for ordered traversal */
447 Dtdisc_t Ag_mainedge_seq_disc = {
448 0, /* pass object ptr */
449 0, /* size (ignored) */
450 offsetof(Agedge_t,seq_link),/* use internal links */
451 NIL(Dtmake_f),
452 NIL(Dtfree_f),
453 agedgeseqcmpf,
454 NIL(Dthash_f),
455 agdictobjmem,
456 NIL(Dtevent_f)
457 };
458
459 Dtdisc_t Ag_subedge_seq_disc = {
460 0, /* pass object ptr */
461 0, /* size (ignored) */
462 -1, /* use external holder objects */
463 NIL(Dtmake_f),
464 NIL(Dtfree_f),
465 agedgeseqcmpf,
466 NIL(Dthash_f),
467 agdictobjmem,
468 NIL(Dtevent_f)
469 };
470
471 /* indexing for random search */
472 Dtdisc_t Ag_mainedge_id_disc = {
473 0, /* pass object ptr */
474 0, /* size (ignored) */
475 offsetof(Agedge_t,id_link), /* use internal links */
476 NIL(Dtmake_f),
477 NIL(Dtfree_f),
478 agedgeidcmpf,
479 NIL(Dthash_f),
480 agdictobjmem,
481 NIL(Dtevent_f)
482 };
483
484 Dtdisc_t Ag_subedge_id_disc = {
485 0, /* pass object ptr */
486 0, /* size (ignored) */
487 -1, /* use external holder objects */
488 NIL(Dtmake_f),
489 NIL(Dtfree_f),
490 agedgeidcmpf,
491 NIL(Dthash_f),
492 agdictobjmem,
493 NIL(Dtevent_f)
494 };
495
496 /* expose macros as functions for ease of debugging
497 and to expose them to foreign languages without C preprocessor. */
498 #ifdef ageqedge
499 #undef ageqedge
500 #endif
ageqedge(Agedge_t * e,Agedge_t * f)501 CGRAPH_API int ageqedge(Agedge_t * e, Agedge_t * f)
502 {
503 return AGEQEDGE(e, f);
504 }
505
506 #ifdef agmkout
507 #undef agmkout
508 #endif
agmkout(Agedge_t * e)509 CGRAPH_API Agedge_t *agmkout(Agedge_t * e)
510 {
511 return AGMKOUT(e);
512 }
513
514 #ifdef agmkin
515 #undef agmkin
516 #endif
agmkin(Agedge_t * e)517 CGRAPH_API Agedge_t *agmkin(Agedge_t * e)
518 {
519 return AGMKIN(e);
520 }
521
522 #ifdef agtail
523 #undef agtail
524 #endif
agtail(Agedge_t * e)525 CGRAPH_API Agnode_t *agtail(Agedge_t * e)
526 {
527 return AGTAIL(e);
528 }
529
530 #ifdef aghead
531 #undef aghead
532 #endif
aghead(Agedge_t * e)533 CGRAPH_API Agnode_t *aghead(Agedge_t * e)
534 {
535 return AGHEAD(e);
536 }
537
538 #ifdef agopp
539 #undef agopp
540 #endif
agopp(Agedge_t * e)541 CGRAPH_API Agedge_t *agopp(Agedge_t * e)
542 {
543 return AGOPP(e);
544 }
545
546 #ifdef NOTDEF
547 /* could be useful if we write relabel_edge */
agfindedge_by_name(Agraph_t * g,Agnode_t * t,Agnode_t * h,char * name)548 static Agedge_t *agfindedge_by_name(Agraph_t * g, Agnode_t * t,
549 Agnode_t * h, char *name)
550 {
551 uint64_t id;
552
553 if (agmapnametoid(agraphof(t), AGEDGE, name, &id, FALSE))
554 return agfindedge_by_id(g, t, h, id);
555 else
556 return NILedge;
557 }
558 #endif
559