From f100c836d156af7ef0f6ff118254a1d97885fd29 Mon Sep 17 00:00:00 2001 From: erg Date: Mon, 15 Dec 2008 18:26:25 +0000 Subject: [PATCH] Fix bug in DFS edge traversal; add post and prepost variants to DFS traversals. --- cmd/gvpr/compile.c | 226 +++++++++++++++++++++++++++----------------- cmd/gvpr/gprdata | 22 +++-- cmd/gvpr/gprstate.c | 15 +-- cmd/gvpr/gprstate.h | 8 +- cmd/gvpr/gvpr.1 | 72 ++++++++++---- cmd/gvpr/gvpr.c | 65 +++++++++++-- 6 files changed, 268 insertions(+), 140 deletions(-) diff --git a/cmd/gvpr/compile.c b/cmd/gvpr/compile.c index df6bf5ef3..bada6a43c 100644 --- a/cmd/gvpr/compile.c +++ b/cmd/gvpr/compile.c @@ -1563,14 +1563,20 @@ refval(Expr_t * pgm, Exnode_t * node, Exid_t * sym, Exref_t * ref, Extype_t v; if (sym->lex == CONSTANT) { switch (sym->index) { - case C_dfs: - v.integer = TV_dfs; + case C_flat: + v.integer = TV_flat; + break; + case C_ne: + v.integer = TV_ne; + break; + case C_en: + v.integer = TV_en; break; case C_bfs: v.integer = TV_bfs; break; - case C_flat: - v.integer = TV_flat; + case C_dfs: + v.integer = TV_dfs; break; case C_fwd: v.integer = TV_fwd; @@ -1578,11 +1584,23 @@ refval(Expr_t * pgm, Exnode_t * node, Exid_t * sym, Exref_t * ref, case C_rev: v.integer = TV_rev; break; - case C_ne: - v.integer = TV_ne; + case C_postdfs: + v.integer = TV_postdfs; break; - case C_en: - v.integer = TV_en; + case C_postfwd: + v.integer = TV_postfwd; + break; + case C_postrev: + v.integer = TV_postrev; + break; + case C_prepostdfs: + v.integer = TV_prepostdfs; + break; + case C_prepostfwd: + v.integer = TV_prepostfwd; + break; + case C_prepostrev: + v.integer = TV_prepostrev; break; case C_null: v.integer = 0; @@ -1604,9 +1622,9 @@ refval(Expr_t * pgm, Exnode_t * node, Exid_t * sym, Exref_t * ref, static void cvtError(Exid_t * xref, char *msg) { if (xref) - error(1, "%s: %s", xref->name, msg); + error(ERROR_FATAL, "%s: %s", xref->name, msg); else - error(1, "%s", msg); + error(ERROR_FATAL, "%s", msg); } #endif @@ -1733,8 +1751,106 @@ binary(Expr_t * pg, Exnode_t * l, Exnode_t * ex, Exnode_t * r, int arg, return ret; } +/* strToTvtype: + */ +static int +strToTvtype (char* s) +{ + int rt = 0; + char* sfx; + + if (!strncmp(s, "TV_", 3)) { + sfx = s + 3; + if (!strcmp(sfx, "flat")) { + rt = TV_flat; + } else if (!strcmp(sfx, "ne")) { + rt = TV_ne; + } else if (!strcmp(sfx, "en")) { + rt = TV_en; + } else if (!strcmp(sfx, "bfs")) { + rt = TV_bfs; + } else if (!strcmp(sfx, "dfs")) { + rt = TV_dfs; + } else if (!strcmp(sfx, "fwd")) { + rt = TV_fwd; + } else if (!strcmp(sfx, "rev")) { + rt = TV_rev; + } else if (!strcmp(sfx, "postdfs")) { + rt = TV_postdfs; + } else if (!strcmp(sfx, "postfwd")) { + rt = TV_postfwd; + } else if (!strcmp(sfx, "postrev")) { + rt = TV_postrev; + } else if (!strcmp(sfx, "prepostdfs")) { + rt = TV_prepostdfs; + } else if (!strcmp(sfx, "prepostfwd")) { + rt = TV_prepostfwd; + } else if (!strcmp(sfx, "prepostrev")) { + rt = TV_prepostrev; + } else + error(ERROR_FATAL, "illegal string \"%s\" for type tvtype_t", s); + } else + error(ERROR_FATAL, "illegal string \"%s\" for type tvtype_t", s); + return rt; +} + +/* tvtypeToStr: + */ +static char* +tvtypeToStr (int v) +{ + char* s = 0; + + switch (v) { + case TV_flat: + s = "TV_flat"; + break; + case TV_ne: + s = "TV_ne"; + break; + case TV_en: + s = "TV_en"; + break; + case TV_bfs: + s = "TV_bfs"; + break; + case TV_dfs: + s = "TV_dfs"; + break; + case TV_fwd: + s = "TV_fwd"; + break; + case TV_rev: + s = "TV_rev"; + break; + case TV_postdfs: + s = "TV_postdfs"; + break; + case TV_postfwd: + s = "TV_postfwd"; + break; + case TV_postrev: + s = "TV_postrev"; + break; + case TV_prepostdfs: + s = "TV_prepostdfs"; + break; + case TV_prepostfwd: + s = "TV_prepostfwd"; + break; + case TV_prepostrev: + s = "TV_prepostrev"; + break; + default: + exerror("Unexpected value %d for type tvtype_t", + v); + break; + } + return s; +} + /* stringOf: - * Convert value x of type string. + * Convert value x to type string. * Assume x does not have a built-in type * Return -1 if conversion cannot be done, 0 otherwise. * If arg is > 0, conversion unnecessary; just report possibility. @@ -1747,27 +1863,8 @@ int stringOf(Expr_t * prog, register Exnode_t * x, int arg) return 0; if (x->type == T_tvtyp) { - switch (x->data.constant.value.integer) { - case TV_flat: - x->data.constant.value.string = "TV_flat"; - break; - case TV_dfs: - x->data.constant.value.string = "TV_dfs"; - break; - case TV_bfs: - x->data.constant.value.string = "TV_bfs"; - break; - case TV_fwd: - x->data.constant.value.string = "TV_fwd"; - break; - case TV_rev: - x->data.constant.value.string = "TV_rev"; - break; - default: - exerror("Unexpected value %d for type tvtype_t", - x->data.constant.value.integer); - break; - } + x->data.constant.value.string = + tvtypeToStr (x->data.constant.value.integer); } else { objp = INT2PTR(Agobj_t *, x->data.constant.value.integer); if (!objp) @@ -1835,28 +1932,10 @@ convert(Expr_t * prog, register Exnode_t * x, int type, } else if (type == STRING) { if (x->type == T_tvtyp) { ret = 0; - if (!arg) - switch (x->data.constant.value.integer) { - case TV_flat: - x->data.constant.value.string = "TV_flat"; - break; - case TV_dfs: - x->data.constant.value.string = "TV_dfs"; - break; - case TV_bfs: - x->data.constant.value.string = "TV_bfs"; - break; - case TV_fwd: - x->data.constant.value.string = "TV_fwd"; - break; - case TV_rev: - x->data.constant.value.string = "TV_rev"; - break; - default: - error(3, "Unexpected value %d for type tvtype_t", - x->data.constant.value.integer); - break; - } + if (!arg) { + x->data.constant.value.string = + tvtypeToStr (x->data.constant.value.integer); + } } #ifdef OLD else { @@ -1871,19 +1950,11 @@ convert(Expr_t * prog, register Exnode_t * x, int type, } else if ((type == T_tvtyp) && (x->type == INTEGER)) { if (arg) ret = 0; + else if (validTVT(x->data.constant.value.integer)) + ret = 0; else - switch (x->data.constant.value.integer) { - case TV_flat: - case TV_dfs: - case TV_bfs: - case TV_fwd: - case TV_rev: - break; - default: - error(1, "Integer value %d not legal for type tvtype_t", - x->data.constant.value.integer); - break; - } + error(ERROR_FATAL, "Integer value %d not legal for type tvtype_t", + x->data.constant.value.integer); } /* in case libexpr hands us the trivial case */ else if (x->type == type) { @@ -1894,28 +1965,9 @@ convert(Expr_t * prog, register Exnode_t * x, int type, if (arg) ret = 0; else { + ret = 0; s = x->data.constant.value.string; - if (!strncmp(s, "TV_", 3)) { - if (!strcmp(s + 3, "flat")) { - x->data.constant.value.integer = TV_flat; - ret = 0; - } else if (!strcmp(s + 3, "dfs")) { - x->data.constant.value.integer = TV_dfs; - ret = 0; - } else if (!strcmp(s + 3, "bfs")) { - x->data.constant.value.integer = TV_bfs; - ret = 0; - } else if (!strcmp(s + 3, "fwd")) { - x->data.constant.value.integer = TV_fwd; - ret = 0; - } else if (!strcmp(s + 3, "rev")) { - x->data.constant.value.integer = TV_rev; - ret = 0; - } else - error(ERROR_FATAL, - "illegal string \"%s\" for type tvtype_t", - s); - } + x->data.constant.value.integer = strToTvtype(s); } } } diff --git a/cmd/gvpr/gprdata b/cmd/gvpr/gprdata index 114b79404..87742cf79 100644 --- a/cmd/gvpr/gprdata +++ b/cmd/gvpr/gprdata @@ -102,11 +102,17 @@ F_hasattr "hasAttr" FUNCTION I|A(1,O)|A(2,S) F_isattr "isAttr" FUNCTION I|A(1,G)|A(2,S)|A(3,S) F_fstattr "fstAttr" FUNCTION S|A(1,G)|A(2,S) F_nxtattr "nxtAttr" FUNCTION S|A(1,G)|A(2,S)|A(3,S) -C_flat "TV_flat" CONSTANT T_tvtyp -C_dfs "TV_dfs" CONSTANT T_tvtyp -C_bfs "TV_bfs" CONSTANT T_tvtyp -C_fwd "TV_fwd" CONSTANT T_tvtyp -C_rev "TV_rev" CONSTANT T_tvtyp -C_ne "TV_ne" CONSTANT T_tvtyp -C_en "TV_en" CONSTANT T_tvtyp -C_null "NULL" CONSTANT T_obj +C_flat "TV_flat" CONSTANT T_tvtyp +C_ne "TV_ne" CONSTANT T_tvtyp +C_en "TV_en" CONSTANT T_tvtyp +C_bfs "TV_bfs" CONSTANT T_tvtyp +C_dfs "TV_dfs" CONSTANT T_tvtyp +C_fwd "TV_fwd" CONSTANT T_tvtyp +C_rev "TV_rev" CONSTANT T_tvtyp +C_postdfs "TV_postdfs" CONSTANT T_tvtyp +C_postfwd "TV_postfwd" CONSTANT T_tvtyp +C_postrev "TV_postrev" CONSTANT T_tvtyp +C_prepostdfs "TV_prepostdfs" CONSTANT T_tvtyp +C_prepostfwd "TV_prepostfwd" CONSTANT T_tvtyp +C_prepostrev "TV_prepostrev" CONSTANT T_tvtyp +C_null "NULL" CONSTANT T_obj diff --git a/cmd/gvpr/gprstate.c b/cmd/gvpr/gprstate.c index b84c0df00..8a60a5f53 100644 --- a/cmd/gvpr/gprstate.c +++ b/cmd/gvpr/gprstate.c @@ -26,20 +26,7 @@ int validTVT(int c) { - int rv = 0; - - switch (c) { - case TV_flat: - case TV_bfs: - case TV_dfs: - case TV_fwd: - case TV_rev: - case TV_ne: - case TV_en: - rv = 1; - break; - } - return rv; + return ((TV_flat <= c) && (c <= TV_prepostrev)); } void initGPRState(Gpr_t * state, Vmalloc_t * vm, gpr_info * info) diff --git a/cmd/gvpr/gprstate.h b/cmd/gvpr/gprstate.h index 0f1b0be2f..bc421e3bd 100644 --- a/cmd/gvpr/gprstate.h +++ b/cmd/gvpr/gprstate.h @@ -26,8 +26,12 @@ extern "C" { #include "ast.h" #include "vmalloc.h" - typedef enum { TV_flat, TV_bfs, TV_dfs, TV_fwd, TV_rev, TV_ne, - TV_en } trav_type; + typedef enum { TV_flat, TV_ne, TV_en, + TV_bfs, + TV_dfs, TV_fwd, TV_rev, + TV_postdfs, TV_postfwd, TV_postrev, + TV_prepostdfs, TV_prepostfwd, TV_prepostrev, + } trav_type; typedef struct { Agraph_t *curgraph; diff --git a/cmd/gvpr/gvpr.1 b/cmd/gvpr/gvpr.1 index 42655dc15..d5472ab15 100644 --- a/cmd/gvpr/gvpr.1 +++ b/cmd/gvpr/gvpr.1 @@ -1,3 +1,9 @@ +. +.de TQ +. br +. ns +. TP \\$1 +.. .TH GVPR 1 "24 April 2008" .SH NAME gvpr \- graph pattern scanning and processing language @@ -798,11 +804,15 @@ graph (cf. \fB$tvtype\fP below). The default value is \fBNULL\fP for each input graph. .TP \fB$tvtype\fP : \fBtvtype_t\fP -indicates how \fBgvpr\fP traverses a graph. At present, it can only take -one of six values: \fBTV_flat\fP, \fBTV_dfs\fP, \fBTV_fwd\fP, -\fBTV_rev\fP, \fBTV_bfs\fP, \fBTV_ne\fP, and \fBTV_en\fP. +indicates how \fBgvpr\fP traverses a graph. It can only take +one of the constant values with the previx "TV_" described below. \fBTV_flat\fP is the default. -The meaning of these values is discussed below. +.IP +In the underlying graph library +.IR cgraph (3), +edges in undirected graphs are given an arbitrary direction. This is +used for traversals, such as \fBTV_fwd\fR, requiring directed edges. +. .TP \fBARGC\fP : \fBint\fP denotes the number of arguments specified by the @@ -833,6 +843,10 @@ a traversal which first visits all of the edges, then all of the nodes. .TP \fBTV_dfs\fR : \fItvtype_t\fR +.TQ +\fBTV_postdfs\fR : \fItvtype_t\fR +.TQ +\fBTV_prepostdfs\fR : \fItvtype_t\fR a traversal of the graph using a depth\(hyfirst search on the underlying undirected graph. To do the traversal, \fBgvpr\fP will check the value of @@ -843,27 +857,47 @@ component. On the other hand, if \fB$tvroot\fP has changed, its connected component will be toured, assuming it has not been previously visited or, if \fB$tvroot\fP is \fBNULL\fP, the traversal will stop. Note that using \fBTV_dfs\fP and \fB$tvroot\fP, it is possible to create an infinite loop. +. +.IP +By default, the traversal is done in pre-order. That is, a node is +visited before all of its unvisited edges. For \fBTV_postdfs\fR, +all of a node's unvisited edges are visited before the node. For +\fBTV_prepostdfs\fR, a node is visited twice, before and after all of +its unvisited edges. +. .TP \fBTV_fwd\fR : \fItvtype_t\fR -a traversal of the graph using a depth\(hyfirst search on the -graph following only forward arcs. In -.TP -\fBTV_bfs\fR : \fItvtype_t\fR -a traversal of the graph using a bread\(hyfirst search on the -graph ignoring edge directions. See the item on \fBTV_dfs\fR above -for the role of \fB$tvroot\fP. -.IR libcgraph (3), -edges in undirected graphs are given an arbitrary direction, which is -used for this traversal. The choice of roots for the traversal is the +.TQ +\fBTV_postfwd\fR : \fItvtype_t\fR +.TQ +\fBTV_prepostfwd\fR : \fItvtype_t\fR +A traversal of the graph using a depth\(hyfirst search on the +graph following only forward arcs. +The choice of roots for the traversal is the same as described for \fBTV_dfs\fR above. +The different order of visitation specified by \fBTV_fwd\fR, +\fBTV_postfwd\fR and \fBTV_prepostfwd\fR are the same as those +specified by the analogous traversals \fBTV_dfs\fR, +\fBTV_postdfs\fR and \fBTV_prepostdfs\fR. .TP \fBTV_rev\fR : \fItvtype_t\fR -a traversal of the graph using a depth\(hyfirst search on the -graph following only reverse arcs. In -.IR libcgraph (3), -edges in undirected graphs are given an arbitrary direction, which is -used for this traversal. The choice of roots for the traversal is the +.TQ +\fBTV_postrev\fR : \fItvtype_t\fR +.TQ +\fBTV_prepostrev\fR : \fItvtype_t\fR +A traversal of the graph using a depth\(hyfirst search on the +graph following only reverse arcs. +The choice of roots for the traversal is the same as described for \fBTV_dfs\fR above. +The different order of visitation specified by \fBTV_rev\fR, +\fBTV_postrev\fR and \fBTV_prepostrev\fR are the same as those +specified by the analogous traversals \fBTV_dfs\fR, +\fBTV_postdfs\fR and \fBTV_prepostdfs\fR. +.TP +\fBTV_bfs\fR : \fItvtype_t\fR +A traversal of the graph using a bread\(hyfirst search on the +graph ignoring edge directions. See the item on \fBTV_dfs\fR above +for the role of \fB$tvroot\fP. .SH EXAMPLES .PP .ta \w'\f(CWdelete array[expression]'u diff --git a/cmd/gvpr/gvpr.c b/cmd/gvpr/gvpr.c index 6fb7d3bed..75ce60ee8 100644 --- a/cmd/gvpr/gvpr.c +++ b/cmd/gvpr/gvpr.c @@ -279,11 +279,11 @@ static void scanArgs(int argc, char **argv) error(ERROR_USAGE, "%s", usage); exit(0); } else { - error(2, "option -%c unrecognized", optopt); + error(ERROR_ERROR, "option -%c unrecognized", optopt); } break; case ':': - error(2, "missing argument for option -%c", optopt); + error(ERROR_ERROR, "missing argument for option -%c", optopt); break; } } @@ -293,7 +293,7 @@ static void scanArgs(int argc, char **argv) /* Handle additional semantics */ if (options.useFile == 0) { if (argc == 0) { - error(2, "No program supplied via argument or -f option"); + error(ERROR_ERROR, "No program supplied via argument or -f option"); #ifdef GVDLL setErrorErrors (1); #else @@ -393,14 +393,19 @@ static Agnode_t *nextNode(Gpr_t * state, nodestream * nodes) typedef Agedge_t *(*fstedgefn_t) (Agraph_t*, Agnode_t *); typedef Agedge_t *(*nxttedgefn_t) (Agraph_t*, Agedge_t *, Agnode_t *); +#define PRE_VISIT 1 +#define POST_VISIT 2 + typedef struct { fstedgefn_t fstedge; nxttedgefn_t nxtedge; + unsigned char undirected; + unsigned char visit; } trav_fns; -static trav_fns DFSfns = { agfstedge, agnxtedge }; -static trav_fns FWDfns = { agfstout, (nxttedgefn_t) agnxtout }; -static trav_fns REVfns = { agfstin, (nxttedgefn_t) agnxtin }; +static trav_fns DFSfns = { agfstedge, agnxtedge, 1, 0}; +static trav_fns FWDfns = { agfstout, (nxttedgefn_t) agnxtout, 0, 0}; +static trav_fns REVfns = { agfstin, (nxttedgefn_t) agnxtin, 0, 0}; static void travBFS(Gpr_t * state, comp_prog * xprog) { @@ -465,7 +470,8 @@ static void travDFS(Gpr_t * state, comp_prog * xprog, trav_fns * fns) cure = 0; MARK(nd); PUSH(nd); - evalNode(state, xprog, n); + if (fns->visit & PRE_VISIT) + evalNode(state, xprog, n); more = 1; while (more) { if (cure) @@ -473,11 +479,20 @@ static void travDFS(Gpr_t * state, comp_prog * xprog, trav_fns * fns) else cure = fns->fstedge(state->curgraph, curn); if (cure) { - if (entry == agopp(cure)) +#if 0 + if (entry == agopp(cure)) /* skip loops */ continue; +#endif nd = nData(cure->node); if (MARKED(nd)) { - if (ONSTACK(nd)) + /* For undirected DFS, visit an edge only if its head + * is on the stack, to avoid visiting it twice. + * This is no problem in directed DFS. + */ + if (fns->undirected) { + if (ONSTACK(nd)) evalEdge(state, xprog, cure); + } + else evalEdge(state, xprog, cure); } else { evalEdge(state, xprog, cure); @@ -485,11 +500,14 @@ static void travDFS(Gpr_t * state, comp_prog * xprog, trav_fns * fns) entry = cure; curn = cure->node; cure = 0; - evalNode(state, xprog, curn); + if (fns->visit & PRE_VISIT) + evalNode(state, xprog, curn); MARK(nd); PUSH(nd); } } else { + if (fns->visit & POST_VISIT) + evalNode(state, xprog, curn); nd = nData(curn); POP(nd); cure = entry; @@ -564,12 +582,39 @@ static void traverse(Gpr_t * state, comp_prog * xprog) travBFS(state, xprog); break; case TV_dfs: + DFSfns.visit = PRE_VISIT; travDFS(state, xprog, &DFSfns); break; case TV_fwd: + FWDfns.visit = PRE_VISIT; travDFS(state, xprog, &FWDfns); break; case TV_rev: + REVfns.visit = PRE_VISIT; + travDFS(state, xprog, &REVfns); + break; + case TV_postdfs: + DFSfns.visit = POST_VISIT; + travDFS(state, xprog, &DFSfns); + break; + case TV_postfwd: + FWDfns.visit = POST_VISIT; + travDFS(state, xprog, &FWDfns); + break; + case TV_postrev: + REVfns.visit = POST_VISIT | PRE_VISIT; + travDFS(state, xprog, &REVfns); + break; + case TV_prepostdfs: + DFSfns.visit = POST_VISIT | PRE_VISIT; + travDFS(state, xprog, &DFSfns); + break; + case TV_prepostfwd: + FWDfns.visit = POST_VISIT | PRE_VISIT; + travDFS(state, xprog, &FWDfns); + break; + case TV_prepostrev: + REVfns.visit = POST_VISIT; travDFS(state, xprog, &REVfns); break; case TV_ne: -- 2.40.0