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
21static Agtag_t Tag; /* to silence warnings about initialization */
22
23
24/* return first outedge of <n> */
25Agedge_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> */
40Agedge_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
56Agedge_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
70Agedge_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
86Agedge_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
95Agedge_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 */
116static 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
146static 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
157Agsubnode_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
169static 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
176static 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
185static 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
207static void subedge(Agraph_t * g, Agedge_t * e)
208{
209 installedge(g, e);
210 /* might an init method call be needed here? */
211}
212
213static 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 */
243static 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
259Agedge_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
281Agedge_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
327void 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
357int 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
378Agedge_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. */
405int 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. */
425int 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 */
447Dtdisc_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
459Dtdisc_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 */
472Dtdisc_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
484Dtdisc_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
497and to expose them to foreign languages without C preprocessor. */
498#ifdef ageqedge
499#undef ageqedge
500#endif
501CGRAPH_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
509CGRAPH_API Agedge_t *agmkout(Agedge_t * e)
510{
511 return AGMKOUT(e);
512}
513
514#ifdef agmkin
515#undef agmkin
516#endif
517CGRAPH_API Agedge_t *agmkin(Agedge_t * e)
518{
519 return AGMKIN(e);
520}
521
522#ifdef agtail
523#undef agtail
524#endif
525CGRAPH_API Agnode_t *agtail(Agedge_t * e)
526{
527 return AGTAIL(e);
528}
529
530#ifdef aghead
531#undef aghead
532#endif
533CGRAPH_API Agnode_t *aghead(Agedge_t * e)
534{
535 return AGHEAD(e);
536}
537
538#ifdef agopp
539#undef agopp
540#endif
541CGRAPH_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 */
548static 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