Man Linux: Main Page and Category List

gvpr - graph pattern scanning and processing language ( previously known asgpr)

gvpr[-icqV?] [-ooutfile] [-aargs] [prog|-fprogfile] [files]

gvpris a graph stream editor inspired byawk. It copies input graphs to its output, possibly transforming their structure and attributes, creating new graphs, or printing arbitrary information. The graph model is that provided bylibcgraph(3). In particular,gvprreads and writes graphs using the dot language. Basically,gvprtraverses each input graph, denoted by$G, visiting each node and edge, matching it with the predicate‐action rules supplied in the input program. The rules are evaluated in order. For each predicate evaluating to true, the corresponding action is performed. During the traversal, the current node or edge being visited is denoted by$. For each input graph, there is a target subgraph, denoted by$T, initially empty and used to accumulate chosen entities, and an output graph,$O, used for final processing and then written to output. By default, the output graph is the target graph. The output graph can be set in the program or, in a limited sense, on the command line.

The following options are supported:-aargsThe stringargsis split into whitespace‐separated tokens, with the individual tokens available as strings in thegvprprogram asARGV[0],...,ARGV[ARGC-1]. Whitespace characters within single or double quoted substrings, or preceded by a backslash, are ignored as separators. In general, a backslash character turns off any special meaning of the following character. Note that the tokens derived from multiple-aflags are concatenated.-cUse the source graph as the output graph.-iDerive the node‐induced subgraph extension of the output graph in the context of its root graph.-ooutfileCauses the output stream to be written to the specified file; by default, output is written tostdout.-fprogfileUse the contents of the specified file as the program to execute on the input. Ifprogfilecontains a slash character, the name is taken as the pathname of the file. Otherwise,gvprwill use the directories specified in the environment variableGPRPATHto look for the file. If-fis not given,gvprwill use the first non‐option argument as the program.-qTurns off warning messages.-VCauses the program to print version information and exit.-?Causes the program to print usage information and exit.

The following operand is supported:filesNames of files containing 1 or more graphs in the dot language. If no-foption is given, the first name is removed from the list and used as the input program. If the list of files is empty,stdinwill be used.

Agvprprogram consists of a list of predicate‐action clauses, having one of the forms:BEGIN{action}BEG_G{action}N[predicate]{action}E[predicate]{action}END_G{action}END{action}A program can contain at most one of each of theBEGIN,END_GandENDclauses. There can be any number ofBEG_G,NandEstatements, the first applied to graphs, the second to nodes, the third to edges. These are separated into blocks, a block consisting of an optionalBEG_Gstatement and allNandEstatements up to the nextBEG_Gstatement, if any. The top‐level semantics of agvprprogram are: Evaluate theBEGINclause, if any. For each input graphG{ For each block { SetGas the current graph and current object. Evaluate theBEG_Gclause, if any. For each node and edge inG{ Set the node or edge as the current object. Evaluate theNorEclauses, as appropriate. } } SetGas the current object. Evaluate theEND_Gclause, if any. } Evaluate theENDclause, if any. The actions of theBEGIN,BEG_G,END_GandENDclauses are performed when the clauses are evaluated. ForNorEclauses, either the predicate or action may be omitted. If there is no predicate with an action, the action is performed on every node or edge, as appropriate. If there is no action and the predicate evaluates to true, the associated node or edge is added to the target graph. The blocks are evaluated in the order in which they occur. Within a block, theNclauses (Eclauses, respectively) are evaluated in the order in which the occur. Note, though, that within a block,NorEclauses may be interlaced, depending on the traversal order. Predicates and actions are sequences of statements in the C dialect supported by thelibexpr(3) library. The only difference between predicates and actions is that the former must have a type that may interpreted as either true or false. Here the usual C convention is followed, in which a non‐zero value is considered true. This would include non‐empty strings and non‐empty references to nodes, edges, etc. However, if a string can be converted to an integer, this value is used. In addition to the usual C base types (void,int,char,float,long,unsignedanddouble),gvprprovidesstringas a synonym forchar*, and the graph‐based typesnode_t,edge_t,graph_tandobj_t. Theobj_ttype can be viewed as a supertype of the other 3 concrete types; the correct base type is maintained dynamically. Besides these base types, the only other supported type expressions are (associative) arrays. Constants follow C syntax, but strings may be quoted with either"..."or ’...’. In certain contexts, string values are interpreted as patterns for the purpose of regular expression matching. Patterns useksh(1) file match pattern syntax.gvpraccepts C++ comments as well as cpp‐type comments. For the latter, if a line begins with a ’#’ character, the rest of the line is ignored. A statement can be a declaration of a function, a variable or an array, or an executable statement. For declarations, there is a single scope. Array declarations have the form:typearray[type0]wheretype0is optional. If it is supplied, the parser will enforce that all array subscripts have the specified type. If it is not supplied, objects of all types can be used as subscripts. As in C, variables and arrays must be declared. In particular, an undeclared variable will be interpreted as the name of an attribute of a node, edge or graph, depending on the context. Executable statements can be one of the following:{[statement...]}expression// commonlyvar=expressionif(expression)statement[elsestatement]for(expression;expression;expression)statementfor(array[var])statementforr(array[var])statementwhile(expression)statementswitch(expression)casestatementsbreak[expression]continue[expression]return[expression]Items in brackets are optional. In the second form of theforstatement and theforrstatement, the variablevaris set to each value used as an index in the specified array and then the associatedstatementis evaluated. For numeric and string indices, the indices are returned in increasing (decreasing) numeric or lexicographic order forfor(forr, respectively). This can be used for sorting. Function definitions can only appear in theBEGINclause. Expressions include the usual C expressions. String comparisons using==and!=treat the right hand operand as a pattern.gvprwill attempt to use an expression as a string or numeric value as appropriate. Expressions of graphical type (i.e.,graph_t,node_t,edge_t,obj_t) may be followed by a field reference in the form of.name. The resulting value is the value of the attribute namednameof the given object. In addition, in certain contexts an undeclared, unmodified identifier is taken to be an attribute name. Specifically, such identifiers denote attributes of the current node or edge, respectively, inNandEclauses, and the current graph inBEG_GandEND_Gclauses. As usual in thelibcgraph(3) model, attributes are string‐valued. In addition,gvprsupports certain pseudo‐attributes of graph objects, not necessarily string‐valued. These reflect intrinsic properties of the graph objects and cannot be set by the user.head:node_tthe head of an edge.tail:node_tthe tail of an edge.name:stringthe name of an edge, node or graph. The name of an edge has the form "<tailname><edgeop><headname>[<key>]", where<edgeop>is "->" or "--" depending on whether the graph is directed or not. The bracket part[<key>]only appears if the edge has a non‐trivial key.indegree:intthe indegree of a node.outdegree:intthe outdegree of a node.degree:intthe degree of a node.root:graph_tthe root graph of an object. The root of a root graph is itself.parent:graph_tthe parent graph of a subgraph. The parent of a root graph isNULLn_edges:intthe number of edges in the graphn_nodes:intthe number of nodes in the graphdirected:inttrue (non‐zero) if the graph is directedstrict:inttrue (non‐zero) if the graph is strictBUILT‐INFUNCTIONSThe following functions are built intogvpr. Those functions returning references to graph objects returnNULLin case of failure.Graphsandsubgraphgraph(s:string,t:string) :graph_tcreates a graph whose name issand whose type is specified by the stringt. Ignoring case, the charactersU,D,S,Nhave the interpretation undirected, directed, strict, and non‐strict, respectively. Iftis empty, a directed, non‐strict graph is generated.subg(g:graph_t,s:string) :graph_tcreates a subgraph in graphgwith names. If the subgraph already exists, it is returned.isSubg(g:graph_t,s:string) :graph_treturns the subgraph in graphgwith names, if it exists, orNULLotherwise.fstsubg(g:graph_t) :graph_treturns the first subgraph in graphg, orNULLif none exists.nxtsubg(sg:graph_t) :graph_treturns the next subgraph aftersg, orNULL.isDirect(g:graph_t) :intreturns true if and only ifgis directed.isStrict(g:graph_t) :intreturns true if and only ifgis strict.nNodes(g:graph_t) :intreturns the number of nodes ing.nEdges(g:graph_t) :intreturns the number of edges ing.Nodesnode(sg:graph_t,s:string) :node_tcreates a node in graphgof names. If such a node already exists, it is returned.subnode(sg:graph_t,n:node_t) :node_tinserts the nodeninto the subgraphg. Returns the node.fstnode(g:graph_t) :node_treturns the first node in graphg, orNULLif none exists.nxtnode(n:node_t) :node_treturns the next node afternin the root graph, orNULL.nxtnode_sg(sg:graph_t,n:node_t) :node_treturns the next node afterninsg, orNULL.isNode(sg:graph_t,s:string) :node_tlooks for a node in (sub)graphsgof names. If such a node exists, it is returned. Otherwise,NULLis returned.isSubnode(sg:graph_t,n:node_t) :intreturns non-zero if nodenis in (sub)graphsg, or zero otherwise.indegreeOf(sg:graph_t,n:node_t) :intreturns the indegree of nodenin (sub)graphsg.outdegreeOf(sg:graph_t,n:node_t) :intreturns the outdegree of nodenin (sub)graphsg.degreeOf(sg:graph_t,n:node_t) :intreturns the degree of nodenin (sub)graphsg.Edgesedge(t:node_t,h:node_t,s:string) :edge_tcreates an edge with tail nodet, head nodehand namesin the root graph. If the graph is undirected, the distinction between head and tail nodes is unimportant. If such an edge already exists, it is returned.edge_sg(sg:graph_t,t:node_t,h:node_t,s:string) :edge_tcreates an edge with tail nodet, head nodehand namesin (sub)graphsg(and all parent graphs). If the graph is undirected, the distinction between head and tail nodes is unimportant. If such an edge already exists, it is returned.subedge(g:graph_t,e:edge_t) :edge_tinserts the edgeeinto the subgraphg. Returns the edge.isEdge(t:node_t,h:node_t,s:string) :edge_tlooks for an edge with tail nodet, head nodehand names. If the graph is undirected, the distinction between head and tail nodes is unimportant. If such an edge exists, it is returned. Otherwise,NULLis returned.isEdge_sg(sg:graph_t,t:node_t,h:node_t,s:string) :edge_tlooks for an edge with tail nodet, head nodehand namesin (sub)graphsg. If the graph is undirected, the distinction between head and tail nodes is unimportant. If such an edge exists, it is returned. Otherwise,NULLis returned.isSubedge(g:graph_t,e:edge_t) :intreturns non-zero if edgeeis in (sub)graphsg, or zero otherwise.fstout(n:node_t) :edge_treturns the first outedge of nodenin the root graph.fstout_sg(sg:graph_t,n:node_t) :edge_treturns the first outedge of nodenin (sub)graphsg.nxtout(e:edge_t) :edge_treturns the next outedge afterein the root graph.nxtout_sg(sg:graph_t,e:edge_t) :edge_treturns the next outedge afterein graphsg.fstin(n:node_t) :edge_treturns the first inedge of nodenin the root graph.fstin_sg(sg:graph_t,n:node_t) :edge_treturns the first inedge of nodenin graphsg.nxtin(e:edge_t) :edge_treturns the next inedge afterein the root graph.nxtin_sg(sg:graph_t,e:edge_t) :edge_treturns the next inedge afterein graphsg.fstedge(n:node_t) :edge_treturns the first edge of nodenin the root graph.fstedge_sg(sg:graph_t,n:node_t) :edge_treturns the first edge of nodenin graphsg.nxtedge(e:edge_t,node_t) :edge_treturns the next edge afterein the root graph.nxtedge_sg(sg:graph_t,e:edge_t,node_t) :edge_treturns the next edge afterein the graphsg.GraphI/Owrite(g:graph_t) :voidprintsgin dot format onto the output stream.writeG(g:graph_t,fname:string) :voidprintsgin dot format into the filefname.fwriteG(g:graph_t,fd:int) :voidprintsgin dot format onto the open stream denoted by the integerfd.readG(fname:string) :graph_treturns a graph read from the filefname. The graph should be in dot format. If no graph can be read,NULLis returned.freadG(fd:int) :graph_treturns the next graph read from the open streamfd. ReturnsNULLat end of file.Graphmiscellanydelete(g:graph_t,x:obj_t) :voiddeletes objectxfrom graphg. IfgisNULL, the function uses the root graph ofx. Ifxis a graph or subgraph, it is closed unlessxis locked.isIn(g:graph_t,x:obj_t) :intreturns true ifxis in subgraphg.clone(g:graph_t,x:obj_t) :obj_tcreates a clone of objectxin graphg. In particular, the new object has the same name/value attributes and structure as the original object. If an object with the same key asxalready exists, its attributes are overlaid by those ofxand the object is returned. If an edge is cloned, both endpoints are implicitly cloned. If a graph is cloned, all nodes, edges and subgraphs are implicitly cloned. Ifxis a graph,gmay beNULL, in which case the cloned object will be a new root graph.copy(g:graph_t,x:obj_t) :obj_tcreates a copy of objectxin graphg, where the new object has the same name/value attributes as the original object. If an object with the same key asxalready exists, its attributes are overlaid by those ofxand the object is returned. Note that this is a shallow copy. Ifxis a graph, none of its nodes, edges or subgraphs are copied into the new graph. Ifxis an edge, the endpoints are created if necessary, but they are not cloned. Ifxis a graph,gmay beNULL, in which case the cloned object will be a new root graph.copyA(src:obj_t,tgt:obj_t) :intcopies the attributes of objectsrcto objecttgt, overwriting any attribute valuestgtmay initially have.induce(g:graph_t) :voidextendsgto its node‐induced subgraph extension in its root graph.hasAttr(src:obj_t,name:string) :intreturns non-zero if objectsrchas an attribute whose name isname. It returns 0 otherwise.isAttr(g:graph_t,kind:string,name:string) :intreturns non-zero if an attributenamehas been defined ingfor objects of the givenkind. For nodes, edges, and graphs,kindshould be "N", "E", and "G", respectively. It returns 0 otherwise.aget(src:obj_t,name:string) :stringreturns the value of attributenamein objectsrc. This is useful for those cases whennameconflicts with one of the keywords such as "head" or "root". If the attribute has not been declared in the graph, the function will initialize it with a default value of "". To avoid this, one should use thehasAttrorisAttrfunction to check that the attribute exists.aset(src:obj_t,name:string,value:string) :intsets the value of attributenamein objectsrctovalue. Returns 0 on success, non‐zero on failure. Seeagetabove.getDflt(g:graph_t,kind:string,name:string) :stringreturns the default value of attributenamein objects ingof the givenkind. For nodes, edges, and graphs,kindshould be "N", "E", and "G", respectively. If the attribute has not been declared in the graph, the function will initialize it with a default value of "". To avoid this, one should use theisAttrfunction to check that the attribute exists.setDflt(g:graph_t,kind:string,name:string,value:string) :intsets the default value of attributenametovaluein objects ingof the givenkind. For nodes, edges, and graphs,kindshould be "N", "E", and "G", respectively. Returns 0 on success, non‐zero on failure. SeegetDfltabove.fstAttr(g:graph_t,kind:string) :stringreturns the name of the first attribute of objects ingof the givenkind. For nodes, edges, and graphs,kindshould be "N", "E", and "G", respectively. If there are no attributes, the string "" is returned.nxtAttr(g:graph_t,kind:string,name:string) :stringreturns the name of the next attribute of objects ingof the givenkindafter the attributename. The argumentnamemust be the name of an existing attribute; it will typically be the return value of an previous call tofstAttrornxtAttr. For nodes, edges, and graphs,kindshould be "N", "E", and "G", respectively. If there are no attributes left, the string "" is returned.compOf(g:graph_t,n:node_t) :graph_treturns the connected component of the graphgcontaining noden, as a subgraph ofg. The subgraph only contains the nodes. One can useinduceto add the edges. The function fails and returnsNULLifnis not ing. Connectivity is based on the underlying undirected graph ofg.kindOf(obj:obj_t) :stringreturns an indication of what kind of graph object is the argument. For nodes, edges, and graphs, it returns should be "N", "E", and "G", respectively.lock(g:graph_t,v:int) :intimplements graph locking on root graphs. If the integervis positive, the graph is set so that future calls todeletehave no immediate effect. Ifvis zero, the graph is unlocked. If there has been a call to delete the graph while it was locked, the graph is closed. Ifvis negative, nothing is done. In all cases, the previous lock value is returned.Stringssprintf(fmt:string,...) :stringreturns the string resulting from formatting the values of the expressions occurring afterfmtaccording to theprintf(3) formatfmtgsub(str:string,pat:string) :stringgsub(str:string,pat:string,repl:string) :stringreturnsstrwith all substrings matchingpatdeleted or replaced byrepl, respectively.sub(str:string,pat:string) :stringsub(str:string,pat:string,repl:string) :stringreturnsstrwith the leftmost substring matchingpatdeleted or replaced byrepl, respectively. The characters ’^’ and ’$’ may be used at the beginning and end, respectively, ofpatto anchor the pattern to the beginning or end ofstr.substr(str:string,idx:int) :stringsubstr(str:string,idx:int,len:int) :stringreturns the substring ofstrstarting at positionidxto the end of the string or of lengthlen, respectively. Indexing starts at 0. Ifidxis negative oridxis greater than the length ofstr, a fatal error occurs. Similarly, in the second case, iflenis negative oridx+lenis greater than the length ofstr, a fatal error occurs.length(s:string) :intreturns the length of the strings.index(s:string,t:string) :intrindex(s:string,t:string) :intreturns the index of the character in stringswhere the leftmost (rightmost) copy of stringtcan be found, or -1 iftis not a substring ofs.match(s:string,p:string) :intreturns the index of the character in stringswhere the leftmost match of patternpcan be found, or -1 if no substring ofsmatchesp.toupper(s:string) :stringreturns a version ofswith the alphabetic characters converted to upper-case.tolower(s:string) :stringreturns a version ofswith the alphabetic characters converted to lower-case.canon(s:string) :stringreturns a version ofsappropriate to be used as an identifier in a dot file.xOf(s:string) :stringreturns the string "x" ifshas the form "x,y", where bothxandyare numeric.yOf(s:string) :stringreturns the string "y" ifshas the form "x,y", where bothxandyare numeric.llOf(s:string) :stringreturns the string "llx,lly" ifshas the form "llx,lly,urx,ury", where all ofllx,lly,urx, anduryare numeric.urOf(s)urOf(s:string) :stringreturns the string "urx,ury" ifshas the form "llx,lly,urx,ury", where all ofllx,lly,urx, anduryare numeric.sscanf(s:string,fmt:string,...) :intscans the strings, extracting values according to thesscanf(3) formatfmt. The values are stored in the addresses followingfmt, addresses having the form&v, wherevis some declared variable of the correct type. Returns the number of items successfully scanned.split(s:string,arr:array,seps:string) :intsplit(s:string,arr:array) :inttokens(s:string,arr:array,seps:string) :inttokens(s:string,arr:array) :intThesplitfunction breaks the stringsinto fields, while thetokensfunction breaks the string into tokens. A field consists of all non-separator characters between two separator characters or the beginning or end of the string. Thus, a field may be the empty string. A token is a maximal, non-empty substring not containing a separator character. The separator characters are those given in thesepsargument. Ifsepsis not provided, the default value is " \t\n". The functions return the number of fields or tokens. The fields and tokens are stored in the argument array. The array must bestring-valued and, if an index type is specified, it must beint. The entries are indexed by consecutive integers, starting at 0. Any values already stored in the array will be either overwritten, or still be present after the function returns.I/O...) :voidprint(expr,...)prints a string representation of each argument in turn ontostdout, followed by a newline.printf(fmt:string,...) :intprintf(fd:int,fmt:string,...) :intprints the string resulting from formatting the values of the expressions followingfmtaccording to theprintf(3) formatfmt. Returns 0 on success. By default, it prints onstdout. If the optional integerfdis given, output is written on the open stream associated withfd.scanf(fmt:string,...) :intscanf(fd:int,fmt:string,...) :intscans in values from an input stream according to thescanf(3) formatfmt. The values are stored in the addresses followingfmt, addresses having the form&v, wherevis some declared variable of the correct type. By default, it reads fromstdin. If the optional integerfdis given, input is read from the open stream associated withfd. Returns the number of items successfully scanned.openF(s:string,t:string) :intopens the filesas an I/O stream. The string argumenttspecifies how the file is opened. The arguments are the same as for the C functionfopen(3). It returns an integer denoting the stream, or -1 on error. As usual, streams 0, 1 and 2 are already open asstdin,stdout, andstderr, respectively. Sincegvprmay usestdinto read the input graphs, the user should avoid using this stream.closeF(fd:int) :intcloses the open stream denoted by the integerfd. Streams 0, 1 and 2 cannot be closed. Returns 0 on success.readL(fd:int) :stringreturns the next line read from the input streamfd. It returns the empty string "" on end of file. Note that the newline character is left in the returned string.Mathexp(d:double) :doublereturns e to thedth power.log(d:double) :doublereturns the natural log ofd.sqrt(d:double) :doublereturns the square root of the doubled.pow(d:double,x:double) :doublereturnsdraised to thexth power.cos(d:double) :doublereturns the cosine ofd.sin(d:double) :doublereturns the sine ofd.atan2(y:double,x:double) :doublereturns the arctangent ofy/xin the range -pi to pi.MIN(y:double,x:double) :doublereturns the minimum ofyandx.MAX(y:double,x:double) :doublereturns the maximum ofyandx.AssociativeArrays#arr:intreturns the number of elements in the arrayarr.idxinarr:intreturns 1 if a value has been set for indexidxin the arrayarr. It returns 0 otherwise.unset(v:array, IidxP) :intremoves the item indexed byidx. It returns 1 if the item existed, 0 otherwise.unset(v:array) :voidre-initializes the array.Miscellaneousexit(v:int) :voidcausesgvprto exit with the exit codev.system(cmd:string) :intprovides the standard C functionsystem(3). It executescmdif the user’s shell environment, and returns the exit status of the shell.rand() :doublereturns a pseudo‐random double between 0 and 1.srand() :intsrand(v:int) :intsets a seed for the random number generator. The optional argument gives the seed; if it is omitted, the current time is used. The previous seed value is returned.srandshould be called before any calls torand.colorx(color:string,fmt:string) :stringtranslates a color from one format to another. Thecolorargument should be a color in one of the recognized string representations. Thefmtvalue should be one of "RGB", "RGBA", "HSV", "HSVA", or "CMYK". An empty string is returned on error.BUILT‐INVARIABLESgvprprovides certain special, built‐in variables, whose values are set automatically bygvprdepending on the context. Except as noted, the user cannot modify their values.$:obj_tdenotes the current object (node, edge, graph) depending on the context. It is not available inBEGINorENDclauses.$F:stringis the name of the current input file.$G:graph_tdenotes the current graph being processed. It is not available inBEGINorENDclauses.$O:graph_tdenotes the output graph. Before graph traversal, it is initialized to the target graph. After traversal and anyEND_Gactions, if it refers to a non‐empty graph, that graph is printed onto the output stream. It is only valid inN,EandEND_Gclauses. The output graph may be set by the user.$T:graph_tdenotes the current target graph. It is a subgraph of$Gand is available only inN,EandEND_Gclauses.$tgtname:stringdenotes the name of the target graph. By default, it is set to"gvpr_result". If used multiple times during the execution ofgvpr, the name will be appended with an integer. This variable may be set by the user.$tvroot:node_tindicates the starting node for a (directed or undirected) depth‐first traversal of the graph (cf.$tvtypebelow). The default value isNULLfor each input graph.$tvedge:edge_tFor BFS and DFS traversals, this is set to the edge used to arrive at the current node or edge. At the beginning of a traversal, or for other traversal types, the value isNULL.$tvtype:tvtype_tindicates howgvprtraverses a graph. It can only take one of the constant values with the previx "TV_" described below.TV_flatis the default. In the underlying graph librarycgraph(3), edges in undirected graphs are given an arbitrary direction. This is used for traversals, such asTV_fwd, requiring directed edges.ARGC:intdenotes the number of arguments specified by the-aargscommand‐line argument.ARGV:stringarraydenotes the array of arguments specified by the-aargscommand‐line argument. Theith argument is given byARGV[i].BUILT‐INCONSTANTSThere are several symbolic constants defined bygvpr.NULL:obj_ta null object reference, equivalent to 0.TV_flat:tvtype_ta simple, flat traversal, with graph objects visited in seemingly arbitrary order.TV_ne:tvtype_ta traversal which first visits all of the nodes, then all of the edges.TV_en:tvtype_ta traversal which first visits all of the edges, then all of the nodes.TV_dfs:tvtype_tTV_postdfs:tvtype_tTV_prepostdfs:tvtype_ta traversal of the graph using a depth‐first search on the underlying undirected graph. To do the traversal,gvprwill check the value of$tvroot. If this has the same value that it had previously (at the start, the previous value is initialized toNULL.),gvprwill simply look for some unvisited node and traverse its connected component. On the other hand, if$tvroothas changed, its connected component will be toured, assuming it has not been previously visited or, if$tvrootisNULL, the traversal will stop. Note that usingTV_dfsand$tvroot, it is possible to create an infinite loop. By default, the traversal is done in pre-order. That is, a node is visited before all of its unvisited edges. ForTV_postdfs, all of a node’s unvisited edges are visited before the node. ForTV_prepostdfs, a node is visited twice, before and after all of its unvisited edges.TV_fwd:tvtype_tTV_postfwd:tvtype_tTV_prepostfwd:tvtype_tA traversal of the graph using a depth‐first search on the graph following only forward arcs. The choice of roots for the traversal is the same as described forTV_dfsabove. The different order of visitation specified byTV_fwd,TV_postfwdandTV_prepostfwdare the same as those specified by the analogous traversalsTV_dfs,TV_postdfsandTV_prepostdfs.TV_rev:tvtype_tTV_postrev:tvtype_tTV_prepostrev:tvtype_tA traversal of the graph using a depth‐first search on the graph following only reverse arcs. The choice of roots for the traversal is the same as described forTV_dfsabove. The different order of visitation specified byTV_rev,TV_postrevandTV_prepostrevare the same as those specified by the analogous traversalsTV_dfs,TV_postdfsandTV_prepostdfs.TV_bfs:tvtype_tA traversal of the graph using a bread‐first search on the graph ignoring edge directions. See the item onTV_dfsabove for the role of$tvroot.

gvpr-i’N[color=="blue"]’file.dotGenerate the node‐induced subgraph of all nodes with color blue.gvpr-c’N[color=="blue"]{color="red"}’file.dotMake all blue nodes red.BEGIN{intn,e;inttot_n=0;inttot_e=0;}BEG_G{n=nNodes($G);e=nEdges($G);printf("%dnodes%dedges%s0,n,e,$G.name);tot_n+=n;tot_e+=e;}END{printf("%dnodes%dedgestotal0,tot_n,tot_e)}Version of the programgc.gvpr-c""Equivalent tonop.BEG_G{graph_tg=graph("merge","S");}E{node_th=clone(g,$.head);node_tt=clone(g,$.tail);edge_te=edge(t,h,"");e.weight=e.weight+1;}END_G{$O=g;}Produces a strict version of the input graph, where the weight attribute of an edge indicates how many edges from the input graph the edge represents.BEGIN{node_tn;intdeg[]}E{deg[head]++;deg[tail]++;}END_G{for(deg[n]){printf("deg[%s]=%d0,n.name,deg[n]);}}Computes the degrees of nodes with edges.

GPRPATHColon‐separated list of directories to be searched to find the file specified by the -f option.

When the program is given as a command line argument, the usual shell interpretation takes place, which may affect some of the special names ingvpr. To avoid this, it is best to wrap the program in single quotes. As of 24 April 2008,gvprswitched to using a new, underlying graph library, which uses the simpler model that there is only one copy of a node, not one copy for each subgraph logically containing it. This means that iterators such as InxtnodeP cannot traverse a subgraph using just a node argument. For this reason, subgraph traversal requires new functions ending in "_sg", which also take a subgraph argument. The versions without that suffix will always traverse the root graph. There is a single global scope, except for formal function parameters, and even these can interfere with the type system. Also, the extent of all variables is the entire life of the program. It might be preferable for scope to reflect the natural nesting of the clauses, or for the program to at least reset locally declared variables. For now, it is advisable to use distinct names for all variables. If a function ends with a complex statement, such as an IF statement, with each branch doing a return, type checking may fail. Functions should use a return at the end. The expr library does not support string values of (char*)0. This means we can’t distinguish between "" and (char*)0 edge keys. For the purposes of looking up and creating edges, we translate "" to be (char*)0, since this latter value is necessary in order to look up any edge with a matching head and tail. Related to this, strings converted to integers act like char pointers, getting the value 0 or 1 depending on whether the string consists solely of zeroes or not. Thus, the ((int)"2") evaluates to 1. The language inherits the usual C problems such as dangling references and the confusion between ’=’ and ’==’.

Emden R. Gansner <erg@research.att.com>

awk(1), gc(1), dot(1), nop(1), libexpr(3), libcgraph(3) 3 July 2009