GPR(1)

NAME
gpr - graph pattern scanning and processing language

SYNOPSIS
gpr [-ic] [ -ooutfile ] [ 'prog' | -f progfile ] [ files ]

DESCRIPTION
gpr is a graph stream editor inspired by awk. It copies input graphs to its output, possibly transforming their structure and attributes, creating new graphs, or printing arbitrary information.

Basically, gpr traverses each input graph, denoted by $G, visiting each node and edge, matching it with the pattern-action rules supplied in the input program. The patterns are evaluated in order. For each pattern for which a match is found, the resulting action is performed. During the traversal, the current node or edge being visited is denoted by $.

For each input graph, there is a target graph, denoted by $T, 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.

OPTIONS
The following options are supported:

-c  Use source graph for output.

-i  Derive the node-induced subgraph extension of the output graph in the context of its root graph.

-o outfile
    Causes the output to be written to the specified file; by default, output is written to stdout.

-f progfile
    Use the contents of the specified file as the program to execute on the input. If -f is not given, gpr will use the first non-option argument as the program.

-?  Causes the program to print usage information.

OPERANDS
The following operand is supported:

files
    Names of files containing 1 or more graphs in dot format. If no -f option is given, the first name removed from the list and used as the input program. If the list of files is empty, the standard input will be used.

PROGRAMS
A gpr program consists of list of pattern-action clauses, having one of the forms:

    BEGIN { action }

    BEG_G { action }

    N [ pattern ] { action }

    E [ pattern ] { action }

    END_G { action }

    END { action }

A program can contain at most one of each of the BEGIN, BEG_G, END_G and END clauses. The action is performed at specific times in gpr:

BEGIN
    At the beginning before any graphs are read.

BEG_G
    After a new root graph has been read, but before traversal.

END_G
    After the traversal of a root graph has finished.

END After all graphs have been processed.

There can be any number of N and E statements, the first applied to nodes, the second to edges. Either the pattern or action may be omitted. If there is no pattern with an action, the action is performed on every node or edge, as appropriate. If there is no action, the matched object is added to the target.

Patterns and actions are sequences of statements in the C dialect supported by libexpr. The only difference between patterns 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, string, float, long, unsigned and double), gpr provides the graph-based types node_t, edge_t, graph_t and obj_t. The obj_t 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.

A statement can be a declaration of a function, a variable or an array, or one of the following:

    { [ statement ... ] }
    expression	# commonly var = expression
    if( expression ) statement [ else statement ]
    for( expression ; expression ; expression ) statement
    for( array [ var ]) statement
    while( expression ) statement
    switch( expression ) case statements
    break [ expression ]
    continue [ expression ]
    return [ expression ]

Expressions include the usual C expressions. In addition, 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 named name of the given object. If an undeclared identifier appears in a program, it is taken to be an attribute name. If name is not used explicitly as a field name, it is taken to denote the attribute name of the current node or edge, i.e, $.name.

As usual in the dot model, attributes are string-valued. In addition, gpr supports certain pseudo-attributes of graph objects, not necessarily string-valued. These reflect intrinsic properties of a graph and cannot be assigned to.

head
    refers to the head of an edge.

tail
    refers to the tail of an edge.

name
    refers to the name of an edge, node or graph.

indegree
    refers to the indegree of a node.

outdegree
    refers to the outdegree of a node.

degree
    refers to the degree of a node.

The following expression functions are also supported:

exit(expr)
    causes gpr to exit with the exit code expr. expr defaults to 0 if omitted.

sprintf(fmt, expr, ... )
    returns the string resulting from formatting expr ... according to the printf(3) format fmt

printf(fmt, expr, ... )
    prints the string resulting from formatting expr ... according to the printf(3) format fmt. Returns 1 on success; 0, otherwise.

Constants follow C syntax, but strings may be quoted with either "..." or '...'. String comparisons (== and !=) treat the right hand operand as a ksh(1) file match pattern. Expressions take on string or numeric values as appropriate. gpr uses C++ comments.

Built-in functions include:

graph(s, t)
    creates a graph whose name is s and whose type is specified by the string t. Ignoring case, characters U, D, S, N have the interpretation undirected, directed, strict, and non-strict, respectively. If t is empty, a directed, non-strict graph is generated.

node(g, s)
    creates a node in graph g of name s. If such a node already exists, it is returned.

isNode(g, s)
    looks for a node in graph g of name s. If such a node exists, it is returned; NULL otherwise.

edge(t, h, s)
    creates an edge with tail node t, head node h and name s. If the graph is undirected, the distinction between head and tail nodes is unimportant. If such an edge already exists, it is returned.

isEdge(t, h, s)
    looks for an edge with tail node t, head node h and name s. If the graph is undirected, the distinction between head and tail nodes is unimportant. If such an edge exists, it is returned; NULL otherwise.

clone(g, x)
    creates a copy of object x in graph g. In particular, the new object has the same name/value attributes as the original object. If an object with the same key as x already exists, its attributes are overlaid by those of x and the object is returned. Note that this is a shallow clone. For example, if an edge is being cloned, the endpoints are created if necessary, but the endpoints are not cloned. Currently not implemented when x is a graph.

induce(g)
    extends g to its node-induced subgraph extension in its root graph.

write(g)
    prints g in dot format on the output stream.

isDirect(g)
    returns true if and only if g is directed.

isStrict(g)
    returns true if and only if g is strict.

delete(g, x)
    deletes object x from graph g.

nNodes(g)
    returns the number of nodes in g.

nEdges(g)
    returns the number of edges in g.

gpr provides certain special, built-in variables.

$   denotes the current node or edge during the traversal of a graph. It is only available in N or E clauses. A program cannot assign to it.

$G  denotes the current graph being processed. It is not available in BEGIN or END clauses. A program cannot assign to it.

$T  denotes the current target graph. It is a subgraph of $G and is available only in N, E and END_G clauses. A program cannot assign to it.

$O  denotes the output graph. Before graph traversal, it is initialized to the target graph. After traversal and any END_G actions, if it refers to a non-empty graph, that graph is printed. It is only valid in N, E and END_G clauses.

Tname
    denotes the name of the target graph. By default, it is set to "gpr_result". If used multiple times during the execution of gpr, the name will be appended with an integer.

EXAMPLES
    gpr -i 'N[color=="blue"]' file.dot
Generate the node-induced subgraph of all nodes with color blue.
    gpr -c 'N[color=="blue"]{color = "red"}' file.dot
Make all blue nodes red.
    BEGIN { int n, e; int tot_n = 0; int tot_e = 0; }
    BEG_G {
      n = nNodes($G);
      e = nEdges($G);
      printf ("%d nodes %d edges %s, n, e, $G.name);
      tot_n += n;
      tot_e += e;
    }
    END { printf ("%d nodes %d edges total, tot_n, tot_e) }
Version of the program gc.
    gpr -c ""
Equivalent to nop.
    BEG_G { graph_t g = graph ("merge", "S"); }
    E {
      node_t h = clone(g,$.head);
      node_t t = clone(g,$.tail);
      edge_t e = 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_t n; int deg[]}
    E{deg[head]++; deg[tail]++; }
    END_G {
      for (deg[n]) {
        printf ("deg[%s] = %d, n.name, deg[n]);
      }
    }
Computes the degrees of nodes with edges.

BUGS
When the program is given as a command line argument, the usual shell interpretation takes place, which may affect some of the special names in gpr. To avoid this, it is best to wrap the program in single quotes.

There is a single scope and 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.

The expr library does not support NULL strings. This means we can't distinguish between empty and NULL edge keys. For the purposes of looking up and creating edges, we translate "" to be NULL, since this latter value is necessary in order to look up any edge with a matching head and tail.

The language inherits the usual C problems such as dangling references and the confusion between '=' and '=='.

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

SEE ALSO

gc(1), colorize(1), dot(1), gpr(1), neato(1), sccmap(1), libexpr(3), libagraph(3)