From 5eedc859046c58e8649bb32b040d192e28daac51 Mon Sep 17 00:00:00 2001 From: erg Date: Sat, 20 Dec 2008 21:20:31 +0000 Subject: [PATCH] Fix cgraph to have the same semantics as libgraph concerning strict graphs. That is, strict means no multiedges; it does not preclude loops. Added a bit to allow a graph to also disallow loops, though this is unsed at present. --- lib/cgraph/cgraph.h | 4 +++- lib/cgraph/edge.c | 22 +++++++++++----------- lib/cgraph/graph.c | 5 +++++ 3 files changed, 19 insertions(+), 12 deletions(-) diff --git a/lib/cgraph/cgraph.h b/lib/cgraph/cgraph.h index 3249dd32c..d91f56261 100644 --- a/lib/cgraph/cgraph.h +++ b/lib/cgraph/cgraph.h @@ -139,7 +139,8 @@ struct Agedgepair_s { struct Agdesc_s { /* graph descriptor */ unsigned directed:1; /* if edges are asymmetric */ - unsigned strict:1; /* if and self, multi-edges forbidden */ + unsigned strict:1; /* if multi-edges forbidden */ + unsigned no_loop:1; /* if no loops */ unsigned maingraph:1; /* if this is the top level graph */ unsigned flatlock:1; /* if sets are flattened into lists in cdt */ unsigned no_write:1; /* if a temporary subgraph */ @@ -266,6 +267,7 @@ extern int agwrite(Agraph_t * g, void *chan); extern int agisdirected(Agraph_t * g); extern int agisundirected(Agraph_t * g); extern int agisstrict(Agraph_t * g); +extern int agissimple(Agraph_t * g); /* nodes */ extern Agnode_t *agnode(Agraph_t * g, char *name, int createflag); diff --git a/lib/cgraph/edge.c b/lib/cgraph/edge.c index ece00f71b..0b716198d 100644 --- a/lib/cgraph/edge.c +++ b/lib/cgraph/edge.c @@ -113,15 +113,19 @@ static Agedge_t *agfindedge_by_key(Agraph_t * g, Agnode_t * t, Agnode_t * h, sn = agsubrep(g, h); if (!sn) e = 0; else { +#if 0 if (t != h) { +#endif dtrestore(g->e_id, sn->in_id); e = (Agedge_t *) dtsearch(g->e_id, &template); sn->in_id = dtextract(g->e_id); +#if 0 } else { /* self edge */ dtrestore(g->e_id, sn->out_id); e = (Agedge_t *) dtsearch(g->e_id, &template); sn->out_id = dtextract(g->e_id); } +#endif } return e; } @@ -175,11 +179,9 @@ static void installedge(Agraph_t * g, Agedge_t * e) sn = agsubrep(g, t); ins(g->e_seq, &sn->out_seq, out); ins(g->e_id, &sn->out_id, out); - if (t != h) { - sn = agsubrep(g, h); - ins(g->e_seq, &sn->in_seq, in); - ins(g->e_id, &sn->in_id, in); - } + sn = agsubrep(g, h); + ins(g->e_seq, &sn->in_seq, in); + ins(g->e_id, &sn->in_id, in); g = agparent(g); } } @@ -224,7 +226,7 @@ static int ok_to_make_edge(Agraph_t * g, Agnode_t * t, Agnode_t * h) /* protect against self, multi-edges in strict graphs */ if (agisstrict(g)) { - if (t == h) + if (g->desc.no_loop && (t == h)) /* simple graphs */ return FALSE; key = Tag; key.objtype = 0; /* wild card */ @@ -319,11 +321,9 @@ void agdeledgeimage(Agraph_t * g, Agedge_t * e, void *ignored) sn = agsubrep(g, t); del(g->e_seq, &sn->out_seq, out); del(g->e_id, &sn->out_id, out); - if (t != h) { - sn = agsubrep(g, h); - del(g->e_seq, &sn->in_seq, in); - del(g->e_id, &sn->in_id, in); - } + sn = agsubrep(g, h); + del(g->e_seq, &sn->in_seq, in); + del(g->e_id, &sn->in_id, in); #ifdef DEBUG for (e = agfstin(g,h); e; e = agnxtin(g,e)) assert(e != in); diff --git a/lib/cgraph/graph.c b/lib/cgraph/graph.c index bd4e6d17a..966abae49 100644 --- a/lib/cgraph/graph.c +++ b/lib/cgraph/graph.c @@ -191,6 +191,11 @@ int agisstrict(Agraph_t * g) return g->desc.strict; } +int agissimple(Agraph_t * g) +{ + return (g->desc.strict && g->desc.no_loop); +} + int agdegree(Agraph_t * g, Agnode_t * n, int want_in, int want_out) { Agedge_t *e; -- 2.40.0