1GVPR(1) General Commands Manual GVPR(1)
2
6 gvpr - graph pattern scanning and processing language
7 ( previously known as gpr )
8
10 gvpr [-icqV?] [ -o outfile ] [ -a args ] [ 'prog' | -f progfile ] [
11 files ]
12
14 gvpr is a graph stream editor inspired by awk. It copies input graphs
15 to its output, possibly transforming their structure and attributes,
16 creating new graphs, or printing arbitrary information. The graph
17 model is that provided by libcgraph(3). In particular, gvpr reads and
18 writes graphs using the dot language.
19 Basically, gvpr traverses each input graph, denoted by $G, visiting
21 each node and edge, matching it with the predicate‐action rules sup‐
22 plied in the input program. The rules are evaluated in order. For
23 each predicate evaluating to true, the corresponding action is per‐
24 formed. During the traversal, the current node or edge being visited
25 is denoted by $.
26 For each input graph, there is a target subgraph, denoted by $T, ini‐
28 tially empty and used to accumulate chosen entities, and an output
29 graph, $O, used for final processing and then written to output. By
30 default, the output graph is the target graph. The output graph can be
31 set in the program or, in a limited sense, on the command line.
32
34 The following options are supported:
35 -a args
37 The string args is split into whitespace‐separated tokens, with
38 the individual tokens available as strings in the gvpr program
39 as ARGV[0],...,ARGV[ARGC-1]. Whitespace characters within sin‐
40 gle or double quoted substrings, or preceded by a backslash, are
41 ignored as separators. In general, a backslash character turns
42 off any special meaning of the following character. Note that
43 the tokens derived from multiple -a flags are concatenated.
44 -c Use the source graph as the output graph.
46 -i Derive the node‐induced subgraph extension of the output graph
48 in the context of its root graph.
49 -o outfile
51 Causes the output stream to be written to the specified file; by
52 default, output is written to stdout.
53 -f progfile
55 Use the contents of the specified file as the program to execute
56 on the input. If progfile contains a slash character, the name
57 is taken as the pathname of the file. Otherwise, gvpr will use
58 the directories specified in the environment variable GPRPATH to
59 look for the file. If -f is not given, gvpr will use the first
60 non‐option argument as the program.
61 -q Turns off warning messages.
63 -V Causes the program to print version information and exit.
65 -? Causes the program to print usage information and exit.
67
69 The following operand is supported:
70 files Names of files containing 1 or more graphs in the dot language.
72 If no -f option is given, the first name is removed from the
73 list and used as the input program. If the list of files is
74 empty, stdin will be used.
75
77 A gvpr program consists of a list of predicate‐action clauses, having
78 one of the forms:
79 BEGIN { action }
81 BEG_G { action }
83 N [ predicate ] { action }
85 E [ predicate ] { action }
87 END_G { action }
89 END { action }
91 A program can contain at most one of each of the BEGIN, END_G and END
93 clauses. There can be any number of BEG_G, N and E statements, the
94 first applied to graphs, the second to nodes, the third to edges.
95 These are separated into blocks, a block consisting of an optional
96 BEG_G statement and all N and E statements up to the next BEG_G state‐
97 ment, if any. The top‐level semantics of a gvpr program are:
98 Evaluate the BEGIN clause, if any.
100 For each input graph G {
101 For each block {
102 Set G as the current graph and current object.
103 Evaluate the BEG_G clause, if any.
104 For each node and edge in G {
105 Set the node or edge as the current object.
106 Evaluate the N or E clauses, as appropriate.
107 }
108 }
109 Set G as the current object.
110 Evaluate the END_G clause, if any.
111 }
112 Evaluate the END clause, if any.
113 The actions of the BEGIN, BEG_G, END_G and END clauses are performed
115 when the clauses are evaluated. For N or E clauses, either the predi‐
116 cate or action may be omitted. If there is no predicate with an
117 action, the action is performed on every node or edge, as appropriate.
118 If there is no action and the predicate evaluates to true, the associ‐
119 ated node or edge is added to the target graph.
120 The blocks are evaluated in the order in which they occur. Within a
122 block, the N clauses (E clauses, respectively) are evaluated in the
123 order in which the occur. Note, though, that within a block, N or E
124 clauses may be interlaced, depending on the traversal order.
125 Predicates and actions are sequences of statements in the C dialect
127 supported by the libexpr(3) library. The only difference between pred‐
128 icates and actions is that the former must have a type that may inter‐
129 preted as either true or false. Here the usual C convention is fol‐
130 lowed, in which a non‐zero value is considered true. This would include
131 non‐empty strings and non‐empty references to nodes, edges, etc. How‐
132 ever, if a string can be converted to an integer, this value is used.
133 In addition to the usual C base types (void, int, char, float, long,
135 unsigned and double), gvpr provides string as a synonym for char*, and
136 the graph‐based types node_t, edge_t, graph_t and obj_t. The obj_t
137 type can be viewed as a supertype of the other 3 concrete types; the
138 correct base type is maintained dynamically. Besides these base types,
139 the only other supported type expressions are (associative) arrays.
140 Constants follow C syntax, but strings may be quoted with either "..."
142 or '...'. In certain contexts, string values are interpreted as pat‐
143 terns for the purpose of regular expression matching. Patterns use
144 ksh(1) file match pattern syntax. gvpr accepts C++ comments as well as
145 cpp‐type comments. For the latter, if a line begins with a '#' charac‐
146 ter, the rest of the line is ignored.
147 A statement can be a declaration of a function, a variable or an array,
149 or an executable statement. For declarations, there is a single scope.
150 Array declarations have the form:
151 type array [ type0 ]
153 where type0 is optional. If it is supplied, the parser will enforce
155 that all array subscripts have the specified type. If it is not sup‐
156 plied, objects of all types can be used as subscripts. As in C, vari‐
157 ables and arrays must be declared. In particular, an undeclared vari‐
158 able will be interpreted as the name of an attribute of a node, edge or
159 graph, depending on the context.
160 Executable statements can be one of the following:
162 { [ statement ... ] }
163 expression // commonly var = expression
164 if( expression ) statement [ else statement ]
165 for( expression ; expression ; expression ) statement
166 for( array [ var ]) statement
167 forr( array [ var ]) statement
168 while( expression ) statement
169 switch( expression ) case statements
170 break [ expression ]
171 continue [ expression ]
172 return [ expression ]
173 Items in brackets are optional.
174 In the second form of the for statement and the forr statement, the
176 variable var is set to each value used as an index in the specified
177 array and then the associated statement is evaluated. For numeric and
178 string indices, the indices are returned in increasing (decreasing)
179 numeric or lexicographic order for for (forr, respectively). This can
180 be used for sorting.
181 Function definitions can only appear in the BEGIN clause.
183 Expressions include the usual C expressions. String comparisons using
185 == and != treat the right hand operand as a pattern. gvpr will attempt
186 to use an expression as a string or numeric value as appropriate.
187 Expressions of graphical type (i.e., graph_t, node_t, edge_t, obj_t)
189 may be followed by a field reference in the form of .name. The result‐
190 ing value is the value of the attribute named name of the given object.
191 In addition, in certain contexts an undeclared, unmodified identifier
192 is taken to be an attribute name. Specifically, such identifiers denote
193 attributes of the current node or edge, respectively, in N and E
194 clauses, and the current graph in BEG_G and END_G clauses.
195 As usual in the libcgraph(3) model, attributes are string‐valued. In
197 addition, gvpr supports certain pseudo‐attributes of graph objects, not
198 necessarily string‐valued. These reflect intrinsic properties of the
199 graph objects and cannot be set by the user.
200 head : node_t
202 the head of an edge.
203 tail : node_t
205 the tail of an edge.
206 name : string
208 the name of an edge, node or graph. The name of an edge has the
209 form "<tail‐name><edge‐op><head‐name>[<key>]", where <edge‐op>
210 is "->" or "--" depending on whether the graph is directed or
211 not. The bracket part [<key>] only appears if the edge has a
212 non‐trivial key.
213 indegree : int
215 the indegree of a node.
216 outdegree : int
218 the outdegree of a node.
219 degree : int
221 the degree of a node.
222 root : graph_t
224 the root graph of an object. The root of a root graph is itself.
225 parent : graph_t
227 the parent graph of a subgraph. The parent of a root graph is
228 NULL
229 n_edges : int
231 the number of edges in the graph
232 n_nodes : int
234 the number of nodes in the graph
235 directed : int
237 true (non‐zero) if the graph is directed
238 strict : int
240 true (non‐zero) if the graph is strict
241
243 The following functions are built into gvpr. Those functions returning
244 references to graph objects return NULL in case of failure.
245 Graphs and subgraph
247 graph(s : string, t : string) : graph_t
248 creates a graph whose name is s and whose type is specified by
249 the string t. Ignoring case, the characters U, D, S, N have the
250 interpretation undirected, directed, strict, and non‐strict,
251 respectively. If t is empty, a directed, non‐strict graph is
252 generated.
253 subg(g : graph_t, s : string) : graph_t
255 creates a subgraph in graph g with name s. If the subgraph
256 already exists, it is returned.
257 isSubg(g : graph_t, s : string) : graph_t
259 returns the subgraph in graph g with name s, if it exists, or
260 NULL otherwise.
261 fstsubg(g : graph_t) : graph_t
263 returns the first subgraph in graph g, or NULL if none exists.
264 nxtsubg(sg : graph_t) : graph_t
266 returns the next subgraph after sg, or NULL.
267 isDirect(g : graph_t) : int
269 returns true if and only if g is directed.
270 isStrict(g : graph_t) : int
272 returns true if and only if g is strict.
273 nNodes(g : graph_t) : int
275 returns the number of nodes in g.
276 nEdges(g : graph_t) : int
278 returns the number of edges in g.
279 Nodes
281 node(sg : graph_t, s : string) : node_t
282 creates a node in graph g of name s. If such a node already
283 exists, it is returned.
284 subnode(sg : graph_t, n : node_t) : node_t
286 inserts the node n into the subgraph g. Returns the node.
287 fstnode(g : graph_t) : node_t
289 returns the first node in graph g, or NULL if none exists.
290 nxtnode(n : node_t) : node_t
292 returns the next node after n in the root graph, or NULL.
293 nxtnode_sg(sg : graph_t, n : node_t) : node_t
295 returns the next node after n in sg, or NULL.
296 isNode(sg : graph_t, s : string) : node_t
298 looks for a node in (sub)graph sg of name s. If such a node
299 exists, it is returned. Otherwise, NULL is returned.
300 isSubnode(sg : graph_t, n : node_t) : int
302 returns non-zero if node n is in (sub)graph sg, or zero other‐
303 wise.
304 indegreeOf(sg : graph_t, n : node_t) : int
306 returns the indegree of node n in (sub)graph sg.
307 outdegreeOf(sg : graph_t, n : node_t) : int
309 returns the outdegree of node n in (sub)graph sg.
310 degreeOf(sg : graph_t, n : node_t) : int
312 returns the degree of node n in (sub)graph sg.
313 Edges
315 edge(t : node_t, h : node_t, s : string) : edge_t
316 creates an edge with tail node t, head node h and name s in the
317 root graph. If the graph is undirected, the distinction between
318 head and tail nodes is unimportant. If such an edge already
319 exists, it is returned.
320 edge_sg(sg : graph_t, t : node_t, h : node_t, s : string) : edge_t
322 creates an edge with tail node t, head node h and name s in
323 (sub)graph sg (and all parent graphs). If the graph is undi‐
324 rected, the distinction between head and tail nodes is unimpor‐
325 tant. If such an edge already exists, it is returned.
326 subedge(g : graph_t, e : edge_t) : edge_t
328 inserts the edge e into the subgraph g. Returns the edge.
329 isEdge(t : node_t, h : node_t, s : string) : edge_t
331 looks for an edge with tail node t, head node h and name s. If
332 the graph is undirected, the distinction between head and tail
333 nodes is unimportant. If such an edge exists, it is returned.
334 Otherwise, NULL is returned.
335 isEdge_sg(sg : graph_t, t : node_t, h : node_t, s : string) : edge_t
337 looks for an edge with tail node t, head node h and name s in
338 (sub)graph sg. If the graph is undirected, the distinction
339 between head and tail nodes is unimportant. If such an edge
340 exists, it is returned. Otherwise, NULL is returned.
341 isSubedge(g : graph_t, e : edge_t) : int
343 returns non-zero if edge e is in (sub)graph sg, or zero other‐
344 wise.
345 fstout(n : node_t) : edge_t
347 returns the first outedge of node n in the root graph.
348 fstout_sg(sg : graph_t, n : node_t) : edge_t
350 returns the first outedge of node n in (sub)graph sg.
351 nxtout(e : edge_t) : edge_t
353 returns the next outedge after e in the root graph.
354 nxtout_sg(sg : graph_t, e : edge_t) : edge_t
356 returns the next outedge after e in graph sg.
357 fstin(n : node_t) : edge_t
359 returns the first inedge of node n in the root graph.
360 fstin_sg(sg : graph_t, n : node_t) : edge_t
362 returns the first inedge of node n in graph sg.
363 nxtin(e : edge_t) : edge_t
365 returns the next inedge after e in the root graph.
366 nxtin_sg(sg : graph_t, e : edge_t) : edge_t
368 returns the next inedge after e in graph sg.
369 fstedge(n : node_t) : edge_t
371 returns the first edge of node n in the root graph.
372 fstedge_sg(sg : graph_t, n : node_t) : edge_t
374 returns the first edge of node n in graph sg.
375 nxtedge(e : edge_t, node_t) : edge_t
377 returns the next edge after e in the root graph.
378 nxtedge_sg(sg : graph_t, e : edge_t, node_t) : edge_t
380 returns the next edge after e in the graph sg.
381 Graph I/O
383 write(g : graph_t) : void
384 prints g in dot format onto the output stream.
385 writeG(g : graph_t, fname : string) : void
387 prints g in dot format into the file fname.
388 fwriteG(g : graph_t, fd : int) : void
390 prints g in dot format onto the open stream denoted by the inte‐
391 ger fd.
392 readG(fname : string) : graph_t
394 returns a graph read from the file fname. The graph should be in
395 dot format. If no graph can be read, NULL is returned.
396 freadG(fd : int) : graph_t
398 returns the next graph read from the open stream fd. Returns
399 NULL at end of file.
400 Graph miscellany
402 delete(g : graph_t, x : obj_t) : void
403 deletes object x from graph g. If g is NULL, the function uses
404 the root graph of x. If x is a graph or subgraph, it is closed
405 unless x is locked.
406 isIn(g : graph_t, x : obj_t) : int
408 returns true if x is in subgraph g.
409 clone(g : graph_t, x : obj_t) : obj_t
411 creates a clone of object x in graph g. In particular, the new
412 object has the same name/value attributes and structure as the
413 original object. If an object with the same key as x already
414 exists, its attributes are overlaid by those of x and the object
415 is returned. If an edge is cloned, both endpoints are implic‐
416 itly cloned. If a graph is cloned, all nodes, edges and sub‐
417 graphs are implicitly cloned. If x is a graph, g may be NULL,
418 in which case the cloned object will be a new root graph.
419 copy(g : graph_t, x : obj_t) : obj_t
421 creates a copy of object x in graph g, where the new object has
422 the same name/value attributes as the original object. If an
423 object with the same key as x already exists, its attributes are
424 overlaid by those of x and the object is returned. Note that
425 this is a shallow copy. If x is a graph, none of its nodes,
426 edges or subgraphs are copied into the new graph. If x is an
427 edge, the endpoints are created if necessary, but they are not
428 cloned. If x is a graph, g may be NULL, in which case the
429 cloned object will be a new root graph.
430 copyA(src : obj_t, tgt : obj_t) : int
432 copies the attributes of object src to object tgt, overwriting
433 any attribute values tgt may initially have.
434 induce(g : graph_t) : void
436 extends g to its node‐induced subgraph extension in its root
437 graph.
438 hasAttr(src : obj_t, name : string) : int
440 returns non-zero if object src has an attribute whose name is
441 name. It returns 0 otherwise.
442 isAttr(g : graph_t, kind : string, name : string) : int
444 returns non-zero if an attribute name has been defined in g for
445 objects of the given kind. For nodes, edges, and graphs, kind
446 should be "N", "E", and "G", respectively. It returns 0 other‐
447 wise.
448 aget(src : obj_t, name : string) : string
450 returns the value of attribute name in object src. This is use‐
451 ful for those cases when name conflicts with one of the keywords
452 such as "head" or "root". If the attribute has not been
453 declared in the graph, the function will initialize it with a
454 default value of "". To avoid this, one should use the hasAttr
455 or isAttr function to check that the attribute exists.
456 aset(src : obj_t, name : string, value : string) : int
458 sets the value of attribute name in object src to value.
459 Returns 0 on success, non‐zero on failure. See aget above.
460 getDflt(g : graph_t, kind : string, name : string) : string
462 returns the default value of attribute name in objects in g of
463 the given kind. For nodes, edges, and graphs, kind should be
464 "N", "E", and "G", respectively. If the attribute has not been
465 declared in the graph, the function will initialize it with a
466 default value of "". To avoid this, one should use the isAttr
467 function to check that the attribute exists.
468 setDflt(g : graph_t, kind : string, name : string, value : string) :
470 int
471 sets the default value of attribute name to value in objects in
472 g of the given kind. For nodes, edges, and graphs, kind should
473 be "N", "E", and "G", respectively. Returns 0 on success, non‐
474 zero on failure. See getDflt above.
475 fstAttr(g : graph_t, kind : string) : string
477 returns the name of the first attribute of objects in g of the
478 given kind. For nodes, edges, and graphs, kind should be "N",
479 "E", and "G", respectively. If there are no attributes, the
480 string "" is returned.
481 nxtAttr(g : graph_t, kind : string, name : string) : string
483 returns the name of the next attribute of objects in g of the
484 given kind after the attribute name. The argument name must be
485 the name of an existing attribute; it will typically be the
486 return value of an previous call to fstAttr or nxtAttr. For
487 nodes, edges, and graphs, kind should be "N", "E", and "G",
488 respectively. If there are no attributes left, the string "" is
489 returned.
490 compOf(g : graph_t, n : node_t) : graph_t
492 returns the connected component of the graph g containing node
493 n, as a subgraph of g. The subgraph only contains the nodes. One
494 can use induce to add the edges. The function fails and returns
495 NULL if n is not in g. Connectivity is based on the underlying
496 undirected graph of g.
497 kindOf(obj : obj_t) : string
499 returns an indication of what kind of graph object is the argu‐
500 ment. For nodes, edges, and graphs, it returns should be "N",
501 "E", and "G", respectively.
502 lock(g : graph_t, v : int) : int
504 implements graph locking on root graphs. If the integer v is
505 positive, the graph is set so that future calls to delete have
506 no immediate effect. If v is zero, the graph is unlocked. If
507 there has been a call to delete the graph while it was locked,
508 the graph is closed. If v is negative, nothing is done. In all
509 cases, the previous lock value is returned.
510 Strings
512 sprintf(fmt : string, ...) : string
513 returns the string resulting from formatting the values of the
514 expressions occurring after fmt according to the printf(3) for‐
515 mat fmt
516 gsub(str : string, pat : string) : string
518 gsub(str : string, pat : string, repl : string) : string
520 returns str with all substrings matching pat deleted or replaced
521 by repl, respectively.
522 sub(str : string, pat : string) : string
524 sub(str : string, pat : string, repl : string) : string
526 returns str with the leftmost substring matching pat deleted or
527 replaced by repl, respectively. The characters '^' and '$' may
528 be used at the beginning and end, respectively, of pat to anchor
529 the pattern to the beginning or end of str.
530 substr(str : string, idx : int) : string
532 substr(str : string, idx : int, len : int) : string
534 returns the substring of str starting at position idx to the end
535 of the string or of length len, respectively. Indexing starts
536 at 0. If idx is negative or idx is greater than the length of
537 str, a fatal error occurs. Similarly, in the second case, if len
538 is negative or idx + len is greater than the length of str, a
539 fatal error occurs.
540 length(s : string) : int
542 returns the length of the string s.
543 index(s : string, t : string) : int
545 rindex(s : string, t : string) : int
547 returns the index of the character in string s where the left‐
548 most (rightmost) copy of string t can be found, or -1 if t is
549 not a substring of s.
550 match(s : string, p : string) : int
552 returns the index of the character in string s where the left‐
553 most match of pattern p can be found, or -1 if no substring of s
554 matches p.
555 toupper(s : string) : string
557 returns a version of s with the alphabetic characters converted
558 to upper-case.
559 tolower(s : string) : string
561 returns a version of s with the alphabetic characters converted
562 to lower-case.
563 canon(s : string) : string
565 returns a version of s appropriate to be used as an identifier
566 in a dot file.
567 xOf(s : string) : string
569 returns the string "x" if s has the form "x,y", where both x and
570 y are numeric.
571 yOf(s : string) : string
573 returns the string "y" if s has the form "x,y", where both x and
574 y are numeric.
575 llOf(s : string) : string
577 returns the string "llx,lly" if s has the form
578 "llx,lly,urx,ury", where all of llx, lly, urx, and ury are
579 numeric.
580 urOf(s)
582 urOf(s : string) : string returns the string "urx,ury" if s has
583 the form "llx,lly,urx,ury", where all of llx, lly, urx, and ury
584 are numeric.
585 sscanf(s : string, fmt : string, ...) : int
587 scans the string s, extracting values according to the sscanf(3)
588 format fmt. The values are stored in the addresses following
589 fmt, addresses having the form &v, where v is some declared
590 variable of the correct type. Returns the number of items suc‐
591 cessfully scanned.
592 split(s : string, arr : array, seps : string) : int
594 split(s : string, arr : array) : int
596 tokens(s : string, arr : array, seps : string) : int
598 tokens(s : string, arr : array) : int
600 The split function breaks the string s into fields, while the
601 tokens function breaks the string into tokens. A field consists
602 of all non-separator characters between two separator characters
603 or the beginning or end of the string. Thus, a field may be the
604 empty string. A token is a maximal, non-empty substring not con‐
605 taining a separator character. The separator characters are
606 those given in the seps argument. If seps is not provided, the
607 default value is " \t\n". The functions return the number of
608 fields or tokens.
609 The fields and tokens are stored in the argument array. The
611 array must be string-valued and, if an index type is specified,
612 it must be int. The entries are indexed by consecutive integers,
613 starting at 0. Any values already stored in the array will be
614 either overwritten, or still be present after the function
615 returns.
616 I/O
618 print(...) : void
619 print( expr, ... ) prints a string representation of each argu‐
620 ment in turn onto stdout, followed by a newline.
621 printf(fmt : string, ...) : int
623 printf(fd : int, fmt : string, ...) : int
625 prints the string resulting from formatting the values of the
626 expressions following fmt according to the printf(3) format fmt.
627 Returns 0 on success. By default, it prints on stdout. If the
628 optional integer fd is given, output is written on the open
629 stream associated with fd.
630 scanf(fmt : string, ...) : int
632 scanf(fd : int, fmt : string, ...) : int
634 scans in values from an input stream according to the scanf(3)
635 format fmt. The values are stored in the addresses following
636 fmt, addresses having the form &v, where v is some declared
637 variable of the correct type. By default, it reads from stdin.
638 If the optional integer fd is given, input is read from the open
639 stream associated with fd. Returns the number of items success‐
640 fully scanned.
641 openF(s : string, t : string) : int
643 opens the file s as an I/O stream. The string argument t speci‐
644 fies how the file is opened. The arguments are the same as for
645 the C function fopen(3). It returns an integer denoting the
646 stream, or -1 on error.
647 As usual, streams 0, 1 and 2 are already open as stdin, stdout,
649 and stderr, respectively. Since gvpr may use stdin to read the
650 input graphs, the user should avoid using this stream.
651 closeF(fd : int) : int
653 closes the open stream denoted by the integer fd. Streams 0, 1
654 and 2 cannot be closed. Returns 0 on success.
655 readL(fd : int) : string
657 returns the next line read from the input stream fd. It returns
658 the empty string "" on end of file. Note that the newline char‐
659 acter is left in the returned string.
660 Math
662 exp(d : double) : double
663 returns e to the dth power.
664 log(d : double) : double
666 returns the natural log of d.
667 sqrt(d : double) : double
669 returns the square root of the double d.
670 pow(d : double, x : double) : double
672 returns d raised to the xth power.
673 cos(d : double) : double
675 returns the cosine of d.
676 sin(d : double) : double
678 returns the sine of d.
679 atan2(y : double, x : double) : double
681 returns the arctangent of y/x in the range -pi to pi.
682 MIN(y : double, x : double) : double
684 returns the minimum of y and x.
685 MAX(y : double, x : double) : double
687 returns the maximum of y and x.
688 Associative Arrays
690 # arr : int
691 returns the number of elements in the array arr.
692 idx in arr : int
694 returns 1 if a value has been set for index idx in the array
695 arr. It returns 0 otherwise.
696 unset(v : array, IidxP) : int
698 removes the item indexed by idx. It returns 1 if the item
699 existed, 0 otherwise.
700 unset(v : array) : void
702 re-initializes the array.
703 Miscellaneous
705 exit(v : int) : void
706 causes gvpr to exit with the exit code v.
707 system(cmd : string) : int
709 provides the standard C function system(3). It executes cmd if
710 the user's shell environment, and returns the exit status of the
711 shell.
712 rand() : double
714 returns a pseudo‐random double between 0 and 1.
715 srand() : int
717 srand(v : int) : int
719 sets a seed for the random number generator. The optional argu‐
720 ment gives the seed; if it is omitted, the current time is used.
721 The previous seed value is returned. srand should be called
722 before any calls to rand.
723 colorx(color : string, fmt : string) : string
725 translates a color from one format to another. The color argu‐
726 ment should be a color in one of the recognized string represen‐
727 tations. The fmt value should be one of "RGB", "RGBA", "HSV",
728 "HSVA", or "CMYK". An empty string is returned on error.
729
731 gvpr provides certain special, built‐in variables, whose values are set
732 automatically by gvpr depending on the context. Except as noted, the
733 user cannot modify their values.
734 $ : obj_t
736 denotes the current object (node, edge, graph) depending on the
737 context. It is not available in BEGIN or END clauses.
738 $F : string
740 is the name of the current input file.
741 $G : graph_t
743 denotes the current graph being processed. It is not available
744 in BEGIN or END clauses.
745 $O : graph_t
747 denotes the output graph. Before graph traversal, it is initial‐
748 ized to the target graph. After traversal and any END_G actions,
749 if it refers to a non‐empty graph, that graph is printed onto
750 the output stream. It is only valid in N, E and END_G clauses.
751 The output graph may be set by the user.
752 $T : graph_t
754 denotes the current target graph. It is a subgraph of $G and is
755 available only in N, E and END_G clauses.
756 $tgtname : string
758 denotes the name of the target graph. By default, it is set to
759 "gvpr_result". If used multiple times during the execution of
760 gvpr, the name will be appended with an integer. This variable
761 may be set by the user.
762 $tvroot : node_t
764 indicates the starting node for a (directed or undirected)
765 depth‐first traversal of the graph (cf. $tvtype below). The
766 default value is NULL for each input graph.
767 $tvedge : edge_t
769 For BFS and DFS traversals, this is set to the edge used to
770 arrive at the current node or edge. At the beginning of a tra‐
771 versal, or for other traversal types, the value is NULL.
772 $tvtype : tvtype_t
774 indicates how gvpr traverses a graph. It can only take one of
775 the constant values with the previx "TV_" described below.
776 TV_flat is the default.
777 In the underlying graph library cgraph(3), edges in undirected
779 graphs are given an arbitrary direction. This is used for tra‐
780 versals, such as TV_fwd, requiring directed edges.
781 ARGC : int
783 denotes the number of arguments specified by the -a args com‐
784 mand‐line argument.
785 ARGV : string array
787 denotes the array of arguments specified by the -a args command‐
788 line argument. The ith argument is given by ARGV[i].
789
791 There are several symbolic constants defined by gvpr.
792 NULL : obj_t
794 a null object reference, equivalent to 0.
795 TV_flat : tvtype_t
797 a simple, flat traversal, with graph objects visited in seem‐
798 ingly arbitrary order.
799 TV_ne : tvtype_t
801 a traversal which first visits all of the nodes, then all of the
802 edges.
803 TV_en : tvtype_t
805 a traversal which first visits all of the edges, then all of the
806 nodes.
807 TV_dfs : tvtype_t
809 TV_postdfs : tvtype_t
810 TV_prepostdfs : tvtype_t
811 a traversal of the graph using a depth‐first search on the
812 underlying undirected graph. To do the traversal, gvpr will
813 check the value of $tvroot. If this has the same value that it
814 had previously (at the start, the previous value is initialized
815 to NULL.), gvpr will simply look for some unvisited node and
816 traverse its connected component. On the other hand, if $tvroot
817 has changed, its connected component will be toured, assuming it
818 has not been previously visited or, if $tvroot is NULL, the tra‐
819 versal will stop. Note that using TV_dfs and $tvroot, it is pos‐
820 sible to create an infinite loop.
821 By default, the traversal is done in pre-order. That is, a node
823 is visited before all of its unvisited edges. For TV_postdfs,
824 all of a node's unvisited edges are visited before the node. For
825 TV_prepostdfs, a node is visited twice, before and after all of
826 its unvisited edges.
827 TV_fwd : tvtype_t
829 TV_postfwd : tvtype_t
830 TV_prepostfwd : tvtype_t
831 A traversal of the graph using a depth‐first search on the graph
832 following only forward arcs. The choice of roots for the tra‐
833 versal is the same as described for TV_dfs above. The different
834 order of visitation specified by TV_fwd, TV_postfwd and TV_pre‐
835 postfwd are the same as those specified by the analogous traver‐
836 sals TV_dfs, TV_postdfs and TV_prepostdfs.
837 TV_rev : tvtype_t
839 TV_postrev : tvtype_t
840 TV_prepostrev : tvtype_t
841 A traversal of the graph using a depth‐first search on the graph
842 following only reverse arcs. The choice of roots for the tra‐
843 versal is the same as described for TV_dfs above. The different
844 order of visitation specified by TV_rev, TV_postrev and TV_pre‐
845 postrev are the same as those specified by the analogous traver‐
846 sals TV_dfs, TV_postdfs and TV_prepostdfs.
847 TV_bfs : tvtype_t
849 A traversal of the graph using a bread‐first search on the graph
850 ignoring edge directions. See the item on TV_dfs above for the
851 role of $tvroot.
852
854 gvpr -i 'N[color=="blue"]' file.dot
855 Generate the node‐induced subgraph of all nodes with color blue.
857 gvpr -c 'N[color=="blue"]{color = "red"}' file.dot
859 Make all blue nodes red.
861 BEGIN { int n, e; int tot_n = 0; int tot_e = 0; }
863 BEG_G {
864 n = nNodes($G);
865 e = nEdges($G);
866 printf ("%d nodes %d edges %s0, n, e, $G.name);
867 tot_n += n;
868 tot_e += e;
869 }
870 END { printf ("%d nodes %d edges total0, tot_n, tot_e) }
871 Version of the program gc.
873 gvpr -c ""
875 Equivalent to nop.
877 BEG_G { graph_t g = graph ("merge", "S"); }
879 E {
880 node_t h = clone(g,$.head);
881 node_t t = clone(g,$.tail);
882 edge_t e = edge(t,h,"");
883 e.weight = e.weight + 1;
884 }
885 END_G { $O = g; }
886 Produces a strict version of the input graph, where the weight
888 attribute of an edge indicates how many edges from the input graph the
889 edge represents.
890 BEGIN {node_t n; int deg[]}
892 E{deg[head]++; deg[tail]++; }
893 END_G {
894 for (deg[n]) {
895 printf ("deg[%s] = %d0, n.name, deg[n]);
896 }
897 }
898 Computes the degrees of nodes with edges.
900
902 GPRPATH
903 Colon‐separated list of directories to be searched to find the
904 file specified by the -f option.
905
907 When the program is given as a command line argument, the usual shell
908 interpretation takes place, which may affect some of the special names
909 in gvpr. To avoid this, it is best to wrap the program in single
910 quotes.
911 As of 24 April 2008, gvpr switched to using a new, underlying graph
913 library, which uses the simpler model that there is only one copy of a
914 node, not one copy for each subgraph logically containing it. This
915 means that iterators such as InxtnodeP cannot traverse a subgraph using
916 just a node argument. For this reason, subgraph traversal requires new
917 functions ending in "_sg", which also take a subgraph argument. The
918 versions without that suffix will always traverse the root graph.
919 There is a single global scope, except for formal function parameters,
921 and even these can interfere with the type system. Also, the extent of
922 all variables is the entire life of the program. It might be prefer‐
923 able for scope to reflect the natural nesting of the clauses, or for
924 the program to at least reset locally declared variables. For now, it
925 is advisable to use distinct names for all variables.
926 If a function ends with a complex statement, such as an IF statement,
928 with each branch doing a return, type checking may fail. Functions
929 should use a return at the end.
930 The expr library does not support string values of (char*)0. This
932 means we can't distinguish between "" and (char*)0 edge keys. For the
933 purposes of looking up and creating edges, we translate "" to be
934 (char*)0, since this latter value is necessary in order to look up any
935 edge with a matching head and tail.
936 Related to this, strings converted to integers act like char pointers,
938 getting the value 0 or 1 depending on whether the string consists
939 solely of zeroes or not. Thus, the ((int)"2") evaluates to 1.
940 The language inherits the usual C problems such as dangling references
942 and the confusion between '=' and '=='.
943
945 Emden R. Gansner <erg@research.att.com>
946
948 awk(1), gc(1), dot(1), nop(1), libexpr(3), libcgraph(3)
949 3 July 2009 GVPR(1)