From 21a0c83ee8e3badf5b0af73f3977530c28d347e7 Mon Sep 17 00:00:00 2001 From: erg Date: Wed, 9 Jan 2008 20:50:35 +0000 Subject: [PATCH] Commit versions of tools using the cgraph library. The new code is wrapped in #ifdef USE_CGRAPH --- cmd/tools/acyclic.c | 80 +++++++++++++++++++++++++++++++++------- cmd/tools/bcomps.c | 89 ++++++++++++++++++++++++++++++++++++++++++--- cmd/tools/dot2gxl.c | 18 +++++++++ cmd/tools/gxl2dot.c | 6 +++ 4 files changed, 175 insertions(+), 18 deletions(-) diff --git a/cmd/tools/acyclic.c b/cmd/tools/acyclic.c index 84d45b2ad..3f138f963 100644 --- a/cmd/tools/acyclic.c +++ b/cmd/tools/acyclic.c @@ -20,6 +20,27 @@ * Updated by Emden Gansner */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#ifdef HAVE_UNISTD_H +#include +#endif +#include +#ifdef USE_CGRAPH +#include +#include +typedef struct { + Agrec_t h; + int mark; + int onstack; +} Agnodeinfo_t; + +#define ND_mark(n) (((Agnodeinfo_t*)((n)->base.data))->mark) +#define ND_onstack(n) (((Agnodeinfo_t*)((n)->base.data))->onstack) +#define graphName(g) (agnameof(g)) +#else typedef char Agraphinfo_t; typedef char Agedgeinfo_t; typedef struct { @@ -29,16 +50,12 @@ typedef struct { #define ND_mark(n) (n)->u.mark #define ND_onstack(n) (n)->u.onstack +#define aghead(e) ((e)->head) +#define agtail(e) ((e)->tail) +#define graphName(g) ((g)->name) -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#ifdef HAVE_UNISTD_H -#include -#endif -#include #include +#endif #ifdef HAVE_GETOPT_H #include @@ -52,8 +69,25 @@ static int doWrite = 1; static int Verbose; static char *cmd; +/* addRevEdge: + * Add a reversed version of e. The new edge has the same key. + * We also copy the attributes, reversing the roles of head and + * tail ports. + * This assumes we've already checked that such an edge does not exist. + */ static void addRevEdge(Agraph_t * g, Agedge_t * e) { +#ifdef USE_CGRAPH + Agsym_t* sym; + Agedge_t* f = agedge (g, aghead(e), agtail(e), agnameof(e), 1); + + agcopyattr (e, f); + + sym = agattr (g, AGEDGE, TAILPORT_ID, 0); + if (sym) agsafeset (f, HEADPORT_ID, agxget (e, sym), ""); + sym = agattr (g, AGEDGE, HEADPORT_ID, 0); + if (sym) agsafeset (f, TAILPORT_ID, agxget (e, sym), ""); +#else Agedge_t *reve; char *tmps; char **attrs; @@ -72,6 +106,7 @@ static void addRevEdge(Agraph_t * g, Agedge_t * e) tmps = reve->attr[1]; reve->attr[1] = reve->attr[2]; reve->attr[2] = tmps; +#endif } static int dfs(Agraph_t * g, Agnode_t * t, int hasCycle) @@ -84,15 +119,26 @@ static int dfs(Agraph_t * g, Agnode_t * t, int hasCycle) ND_onstack(t) = 1; for (e = agfstout(g, t); e; e = f) { f = agnxtout(g, e); - if (e->tail == e->head) + if (agtail(e) == aghead(e)) continue; - h = e->head; + h = aghead(e); if (ND_onstack(h)) { +#ifdef USE_CGRAPH + if (agisstrict(g)) { + if (agedge(g, h, t, 0, 0) == 0) + addRevEdge(g, e); + } else { + char* key = agnameof (e); + if (!key || (agedge(g, h, t, key, 0) == 0)) + addRevEdge(g, e); + } +#else if (AG_IS_STRICT(g)) { if (agfindedge(g, h, t) == 0) addRevEdge(g, e); } else addRevEdge(g, e); +#endif agdelete(g, e); hasCycle = 1; } else if (ND_mark(h) == 0) @@ -137,7 +183,9 @@ static void init(int argc, char *argv[]) int c; cmd = argv[0]; +#ifndef USE_CGRAPH aginit(); +#endif while ((c = getopt(argc, argv, ":vno:?")) != -1) switch (c) { @@ -182,8 +230,14 @@ int main(int argc, char *argv[]) init(argc, argv); +#ifdef USE_CGRAPH + if ((g = agread(inFile, (Agdisc_t *) 0)) != 0) { + if (agisdirected (g)) { + aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), TRUE); +#else if ((g = agread(inFile)) != 0) { if (AG_IS_DIRECTED(g)) { +#endif for (n = agfstnode(g); n; n = agnxtnode(g, n)) { if (ND_mark(n) == 0) rv |= dfs(g, n, 0); @@ -194,14 +248,14 @@ int main(int argc, char *argv[]) } if (Verbose) { if (rv) - fprintf(stderr, "Graph %s has cycles\n", g->name); + fprintf(stderr, "Graph %s has cycles\n", graphName(g)); else - fprintf(stderr, "Graph %s is acyclic\n", g->name); + fprintf(stderr, "Graph %s is acyclic\n", graphName(g)); } } else { rv = 2; if (Verbose) - fprintf(stderr, "Graph %s is undirected\n", g->name); + fprintf(stderr, "Graph %s is undirected\n", graphName(g)); } exit(rv); } else diff --git a/cmd/tools/bcomps.c b/cmd/tools/bcomps.c index 4d16d3d29..a92e6944d 100644 --- a/cmd/tools/bcomps.c +++ b/cmd/tools/bcomps.c @@ -33,6 +33,33 @@ #include "compat_getopt.h" #endif +#ifdef USE_CGRAPH +#include +#include + +typedef struct { + Agrec_t h; + Agraph_t *next; +} Agraphinfo_t; + +typedef struct { + Agrec_t h; + Agedge_t *next; +} Agedgeinfo_t; + +typedef struct { + Agrec_t h; + int low; + int val; + int isCut; +} Agnodeinfo_t; + +#define Low(n) (((Agnodeinfo_t*)(n->base.data))->low) +#define Cut(n) (((Agnodeinfo_t*)(n->base.data))->isCut) +#define N(n) (((Agnodeinfo_t*)(n->base.data))->val) +#define NEXT(e) (((Agedgeinfo_t*)(e->base.data))->next) +#define NEXTBLK(g) (((Agraphinfo_t*)(g->base.data))->next) +#else typedef struct { struct Agraph_t *next; } Agraphinfo_t; @@ -48,7 +75,6 @@ typedef struct { } Agnodeinfo_t; #include -#include #define Low(n) ((n)->u.low) #define Cut(n) ((n)->u.isCut) @@ -56,6 +82,12 @@ typedef struct { #define NEXT(e) ((e)->u.next) #define NEXTBLK(g) ((g)->u.next) +#define aghead(e) ((e)->head) +#define agtail(e) ((e)->tail) +#define agnameof(g) ((g)->name) +#endif +#include + #define min(a,b) ((a) < (b) ? (a) : (b)) char **Files; @@ -171,7 +203,12 @@ static Agraph_t *mkBlock(Agraph_t * g, bcstate * stp) Agraph_t *sg; stp->nComp++; +#ifdef USE_CGRAPH + sg = agsubg(g, blockName(agnameof(g), stp->nComp), 1); + agbindrec(sg, "info", sizeof(Agraphinfo_t), TRUE); +#else sg = agsubg(g, blockName(g->name, stp->nComp)); +#endif NEXTBLK(sg) = stp->blks; stp->blks = sg; return sg; @@ -188,8 +225,8 @@ dfs(Agraph_t * g, Agnode_t * u, bcstate * stp, Agnode_t * parent) stp->count++; Low(u) = N(u) = stp->count; for (e = agfstedge(g, u); e; e = agnxtedge(g, e, u)) { - if ((v = e->head) == u) - v = e->tail; + if ((v = aghead(e)) == u) + v = agtail(e); if (v == u) continue; if (N(v) == 0) { @@ -201,8 +238,13 @@ dfs(Agraph_t * g, Agnode_t * u, bcstate * stp, Agnode_t * parent) sg = mkBlock(g, stp); do { ep = pop(&stp->stk); +#ifdef USE_CGRAPH + agsubnode(sg, aghead(ep), 1); + agsubnode(sg, agtail(ep), 1); +#else aginsert(sg, ep->head); aginsert(sg, ep->tail); +#endif } while (ep != e); } } else if (parent != v) { @@ -220,8 +262,13 @@ static void nodeInduce(Agraph_t * g, Agraph_t * eg) for (n = agfstnode(g); n; n = agnxtnode(g, n)) { for (e = agfstout(eg, n); e; e = agnxtout(eg, e)) { +#ifdef USE_CGRAPH + if (agsubnode(g, aghead(e), 0)) { + agsubedge(g, e, 1); +#else if (agcontains(g, e->head)) { aginsert(g, e); +#endif } } } @@ -233,11 +280,20 @@ static void addCutPts(Agraph_t * tree, Agraph_t * blk) Agnode_t *bn; Agnode_t *cn; - bn = agnode(tree, blk->name); +#ifdef USE_CGRAPH + bn = agnode(tree, agnameof(blk), 1); +#else + bn = agnode(tree, agnameof(blk)); +#endif for (n = agfstnode(blk); n; n = agnxtnode(blk, n)) { if (Cut(n)) { +#ifdef USE_CGRAPH + cn = agnode(tree, agnameof(n), 1); + agedge(tree, bn, cn, 0, 1); +#else cn = agnode(tree, n->name); agedge(tree, bn, cn); +#endif } } } @@ -250,6 +306,12 @@ static int process(Agraph_t * g, int gcnt) Agraph_t *tree; int bcnt; +#ifdef USE_CGRAPH + aginit(g, AGNODE, "info", sizeof(Agnodeinfo_t), TRUE); + aginit(g, AGEDGE, "info", sizeof(Agedgeinfo_t), TRUE); + aginit(g, AGRAPH, "info", sizeof(Agraphinfo_t), TRUE); +#endif + state.count = 0; state.nComp = 0; state.stk = 0; @@ -270,7 +332,11 @@ static int process(Agraph_t * g, int gcnt) } else gwrite(g, gcnt, 0); if (doTree) { +#ifdef USE_CGRAPH + tree = agopen("blkcut_tree", Agstrictundirected, 0); +#else tree = agopen("blkcut_tree", AGFLAG_STRICT); +#endif for (blk = state.blks; blk; blk = NEXTBLK(blk)) addCutPts(tree, blk); gwrite(tree, gcnt, -1); @@ -284,7 +350,7 @@ static int process(Agraph_t * g, int gcnt) for (n = agfstnode(g); n; n = agnxtnode(g, n)) if (Cut(n)) cuts++; - fprintf(stderr, "%s: %d blocks %d cutpoints\n", g->name, bcnt, + fprintf(stderr, "%s: %d blocks %d cutpoints\n", agnameof(g), bcnt, cuts); } if (state.blks && NEXTBLK(state.blks)) @@ -330,7 +396,9 @@ static void init(int argc, char *argv[]) { int c; +#ifndef USE_CGRAPH aginit(); +#endif while ((c = getopt(argc, argv, ":o:xstv?")) != -1) { switch (c) { case 'o': @@ -366,6 +434,13 @@ static void init(int argc, char *argv[]) Files = argv; } +#ifdef USE_CGRAPH +static Agraph_t *gread(FILE * fp) +{ + return agread(fp, (Agdisc_t *) 0); +} +#endif + int main(int argc, char *argv[]) { Agraph_t *g; @@ -374,7 +449,11 @@ int main(int argc, char *argv[]) int gcnt = 0; init(argc, argv); +#ifdef USE_CGRAPH + newIngraph(&ig, Files, gread); +#else newIngraph(&ig, Files, agread); +#endif while ((g = nextGraph(&ig)) != 0) { r |= process(g, gcnt); diff --git a/cmd/tools/dot2gxl.c b/cmd/tools/dot2gxl.c index d42235cc4..7689d5458 100644 --- a/cmd/tools/dot2gxl.c +++ b/cmd/tools/dot2gxl.c @@ -16,7 +16,9 @@ #include +#ifndef USE_CGRAPH #include +#endif #include #define SMALLBUF 128 @@ -723,14 +725,22 @@ static void writeBody(gxlstate_t * stp, Agraph_t * g, FILE * gxlFile) writeSubgs(stp, g, gxlFile); dd = (Agdatadict_t *) agdatadict(g); +#ifdef USE_CGRAPH + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { +#else for (n = agfstnode(g); n; n = agnxtnode(n)) { +#endif realn = agidnode(stp->root, AGID(n), 0); if (!writeval(realn)) { writeval(realn) = 1; writeNode(stp, n, gxlFile, dd->dict.n); } +#ifdef USE_CGRAPH + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { +#else for (e = agfstout(n); e; e = agnxtout(e)) { +#endif if (writeEdgeTest(g, e)) writeEdge(stp, e, gxlFile, dd->dict.e); } @@ -771,7 +781,11 @@ static void iterateBody(gxlstate_t * stp, Agraph_t * g) Agedge_t *e; iterate_subgs(stp, g); +#ifdef USE_CGRAPH + for (n = agfstnode(g); n; n = agnxtnode(g, n)) { +#else for (n = agfstnode(g); n; n = agnxtnode(n)) { +#endif char *gxlId; char *nodename = agnameof(n); @@ -786,7 +800,11 @@ static void iterateBody(gxlstate_t * stp, Agraph_t * g) addToMap(stp->nodeMap, nodename, gxlId); } +#ifdef USE_CGRAPH + for (e = agfstout(g, n); e; e = agnxtout(g, e)) { +#else for (e = agfstout(n); e; e = agnxtout(e)) { +#endif if (writeEdgeTest(g, e)) { char *edge_id = agget(e, GXL_ID); if (!EMPTY(edge_id)) diff --git a/cmd/tools/gxl2dot.c b/cmd/tools/gxl2dot.c index b84c6ba90..93ec257a8 100644 --- a/cmd/tools/gxl2dot.c +++ b/cmd/tools/gxl2dot.c @@ -16,7 +16,9 @@ #include +#ifndef USE_CGRAPH #include "aghdr.h" +#endif #include "agxbuf.h" #ifdef HAVE_LIBEXPAT #include @@ -243,7 +245,11 @@ static Agedge_t *bind_edge(const char *tail, const char *head) tailNode = agnode(G, (char *) tail, 1); headNode = agnode(G, (char *) head, 1); +#ifdef USE_CGRAPH + E = agedge(G, tailNode, headNode, key, 1); +#else E = agedge(tailNode, headNode, key, 1); +#endif return E; } -- 2.40.0