Daniel@0: .de TQ
Daniel@0: .  br
Daniel@0: .  ns
Daniel@0: .  TP \\$1
Daniel@0: ..
Daniel@0: .TH GVPR 1 "24 April 2008"
Daniel@0: .SH NAME
Daniel@0: gvpr \- graph pattern scanning and processing language
Daniel@0: .br
Daniel@0: ( previously known as
Daniel@0: .B gpr
Daniel@0: )
Daniel@0: .SH SYNOPSIS
Daniel@0: .B gvpr
Daniel@0: [\fB\-icqV?\fP]
Daniel@0: [
Daniel@0: .BI \-o
Daniel@0: .I outfile
Daniel@0: ]
Daniel@0: [
Daniel@0: .BI \-a
Daniel@0: .I args
Daniel@0: ]
Daniel@0: [
Daniel@0: .I 'prog'
Daniel@0: |
Daniel@0: .BI \-f
Daniel@0: .I progfile
Daniel@0: ]
Daniel@0: [ 
Daniel@0: .I files 
Daniel@0: ]
Daniel@0: .SH DESCRIPTION
Daniel@0: .B gvpr
Daniel@0: is a graph stream editor inspired by \fBawk\fP.
Daniel@0: It copies input graphs to its
Daniel@0: output, possibly transforming their structure and attributes,
Daniel@0: creating new graphs, or printing arbitrary information.
Daniel@0: The graph model is that provided by
Daniel@0: .IR libcgraph (3).
Daniel@0: In particular, \fBgvpr\fP reads and writes graphs using the
Daniel@0: dot language.
Daniel@0: .PP
Daniel@0: Basically,
Daniel@0: .B gvpr
Daniel@0: traverses each input graph, denoted by \fB$G\fP, visiting each node and edge,
Daniel@0: matching it with the predicate\(hyaction rules supplied in the input program.
Daniel@0: The rules are evaluated in order.
Daniel@0: For each predicate evaluating to true, the corresponding 
Daniel@0: action is performed. 
Daniel@0: During the traversal, the current node or edge being visited
Daniel@0: is denoted by \fB$\fP.
Daniel@0: .PP
Daniel@0: For each input graph, there is a target subgraph, denoted by
Daniel@0: \fB$T\fP, initially empty and used to accumulate
Daniel@0: chosen entities, and an output graph, \fB$O\fP, used for final processing
Daniel@0: and then written to output. 
Daniel@0: By default, the output graph is the target graph.
Daniel@0: The output graph can be set in the program or, in a limited sense,
Daniel@0: on the command line.
Daniel@0: .SH OPTIONS
Daniel@0: The following options are supported:
Daniel@0: .TP
Daniel@0: .BI \-a " args"
Daniel@0: The string \fIargs\fP is split into whitespace\(hyseparated tokens, 
Daniel@0: with the individual tokens
Daniel@0: available as strings in the \fBgvpr\fP program 
Daniel@0: as \fBARGV[\fI0\fP],...,ARGV[ARGC\-1]\fR.
Daniel@0: Whitespace characters within single or double quoted substrings, or
Daniel@0: preceded by a backslash, are ignored as separators. 
Daniel@0: In general, a backslash character turns off any special meaning of the
Daniel@0: following character.
Daniel@0: Note that the tokens derived from multiple \fB\-a\fP flags are concatenated.
Daniel@0: .TP
Daniel@0: .B \-c
Daniel@0: Use the source graph as the output graph.
Daniel@0: .TP
Daniel@0: .B \-i
Daniel@0: Derive the node\(hyinduced subgraph extension of the output graph in the context 
Daniel@0: of its root graph.
Daniel@0: .TP
Daniel@0: .BI \-o " outfile"
Daniel@0: Causes the output stream to be written to the specified file; by default,
Daniel@0: output is written to \fBstdout\fP.
Daniel@0: .TP
Daniel@0: .BI \-f " progfile"
Daniel@0: Use the contents of the specified file as the program to execute
Daniel@0: on the input. If \fIprogfile\fP contains a slash character, the name is taken
Daniel@0: as the pathname of the file. Otherwise, \fBgvpr\fP will use the
Daniel@0: directories specified in the environment variable \fBGPRPATH\fP to look
Daniel@0: for the file. If 
Daniel@0: .B \-f
Daniel@0: is not given,
Daniel@0: .B gvpr
Daniel@0: will use the first non\(hyoption argument as the program.
Daniel@0: .TP
Daniel@0: .B \-q
Daniel@0: Turns off warning messages.
Daniel@0: .TP
Daniel@0: .B \-V
Daniel@0: Causes the program to print version information and exit.
Daniel@0: .TP
Daniel@0: .B \-?
Daniel@0: Causes the program to print usage information and exit.
Daniel@0: .SH OPERANDS
Daniel@0: The following operand is supported:
Daniel@0: .TP 8
Daniel@0: .I files
Daniel@0: Names of files containing 1 or more graphs in the dot language.
Daniel@0: If no
Daniel@0: .B \-f
Daniel@0: option is given, the first name is removed from the list and used 
Daniel@0: as the input program. If the list of files is empty, \fBstdin\fP will be used.
Daniel@0: .SH PROGRAMS
Daniel@0: A
Daniel@0: .B gvpr
Daniel@0: program consists of a list of predicate\(hyaction clauses, having one
Daniel@0: of the forms:
Daniel@0: .IP
Daniel@0: .BI "BEGIN { "  action " }"
Daniel@0: .IP
Daniel@0: .BI "BEG_G { "  action " }"
Daniel@0: .IP
Daniel@0: .BI "N [ " predicate " ] { " action " }
Daniel@0: .IP
Daniel@0: .BI "E [ " predicate " ] { " action " }
Daniel@0: .IP
Daniel@0: .BI "END_G { "  action " }"
Daniel@0: .IP
Daniel@0: .BI "END { "  action " }"
Daniel@0: .PP
Daniel@0: A program can contain at most one of each of the \fBBEGIN\fP, \fBBEG_G\fP,
Daniel@0: \fBEND_G\fP and \fBEND\fP clauses. 
Daniel@0: There can be any number of \fBN\fP and \fBE\fP statements,
Daniel@0: the first applied to nodes, the second to edges.
Daniel@0: The top\(hylevel semantics of a \fBgvpr\fP program are:
Daniel@0: .PP
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: Evaluate the \fBBEGIN\fP clause, if any.
Daniel@0: For each input graph \fIG\fP {
Daniel@0:     Set \fIG\fP as the current graph and current object.
Daniel@0:     Evaluate the \fBBEG_G\fP clause, if any.
Daniel@0:     For each node and edge in \fIG\fP {
Daniel@0:       Set the node or edge as the current object.
Daniel@0:       Evaluate the \fBN\fP or \fBE\fP clauses, as appropriate.
Daniel@0:     } 
Daniel@0:     Set \fIG\fP as the current object.
Daniel@0:     Evaluate the \fBEND_G\fP clause, if any.
Daniel@0: } 
Daniel@0: Evaluate the \fBEND\fP clause, if any.
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .DT
Daniel@0: .PP
Daniel@0: The actions of the \fBBEGIN\fP, \fBBEG_G\fP, \fBEND_G\fP and \fBEND\fP clauses
Daniel@0: are performed when the clauses are evaluated.
Daniel@0: For \fBN\fP or \fBE\fP clauses,
Daniel@0: either the predicate or action may be omitted. 
Daniel@0: If there is no predicate with an action, the action is 
Daniel@0: performed on every node or edge, as appropriate.
Daniel@0: If there is no action and the predicate evaluates to true,
Daniel@0: the associated node or edge is added to the target graph. 
Daniel@0: .PP
Daniel@0: Predicates and actions are sequences of statements in the C dialect 
Daniel@0: supported by the
Daniel@0: .IR libexpr (3)
Daniel@0: library.
Daniel@0: The only difference between predicates and actions is that the former
Daniel@0: must have a type that may interpreted as either true or false.
Daniel@0: Here the usual C convention is followed, in which a non\(hyzero value is
Daniel@0: considered true. This would include non\(hyempty strings and non\(hyempty
Daniel@0: references to nodes, edges, etc. However, if a string can be 
Daniel@0: converted to an integer, this value is used.
Daniel@0: .PP
Daniel@0: In addition to the usual C base types
Daniel@0: (\fBvoid\fP, \fBint\fP, \fBchar\fP, \fBfloat\fP, \fBlong\fP, 
Daniel@0: \fBunsigned\fP and \fBdouble\fP), 
Daniel@0: \fBgvpr\fP \fRprovides \fBstring\fP as a synonym for \fBchar*\fP, and 
Daniel@0: the graph\(hybased types \fBnode_t\fP,
Daniel@0: \fBedge_t\fP, \fBgraph_t\fP and \fBobj_t\fP.
Daniel@0: The \fBobj_t\fP type can be viewed as a supertype of the other 3 concrete types;
Daniel@0: the correct base type is maintained dynamically.
Daniel@0: Besides these base types, the only other supported type expressions
Daniel@0: are (associative) arrays. 
Daniel@0: .PP
Daniel@0: Constants follow C syntax, but strings may be quoted with either
Daniel@0: \fB"..."\fP or \fB'...'\fP. In certain contexts, string values are
Daniel@0: interpreted as patterns for the purpose of regular expression matching.
Daniel@0: Patterns use
Daniel@0: .IR ksh (1)
Daniel@0: file match pattern syntax.
Daniel@0: \fBgvpr\fP accepts C++ comments as well as cpp\(hytype comments.
Daniel@0: For the latter, if a line begins with a '#' character, the rest of
Daniel@0: the line is ignored.
Daniel@0: .PP
Daniel@0: A statement can be a declaration of a function, a variable
Daniel@0: or an array, or an executable statement. For declarations, there
Daniel@0: is a single scope. Array declarations have the form: 
Daniel@0: .PP
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: \fI type array \fB[\fP type0 \fB]\fR
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .DT
Daniel@0: .PP
Daniel@0: where \fI type0 \fP is optional. If it is supplied, the parser will 
Daniel@0: enforce that all array subscripts have the specified type. If it is
Daniel@0: not supplied, objects of all types can be used as subscripts.
Daniel@0: As in C, variables and arrays must
Daniel@0: be declared. In particular, an undeclared variable will be interpreted
Daniel@0: as the name of an attribute of a node, edge or graph, depending on the
Daniel@0: context.
Daniel@0: .PP
Daniel@0: Executable statements can be one of the following:
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: \fB{\fR [\fI statement ... \fR] \fB}\fR
Daniel@0: \fIexpression\fP	\fR// commonly\fP\fI var \fB=\fP expression\fR
Daniel@0: \fBif(\fI expression \fP)\fI statement \fR[ \fBelse\fI statement \fR]
Daniel@0: \fBfor(\fI expression \fP;\fI expression \fP;\fI expression \fP)\fI statement\fP
Daniel@0: \fBfor(\fI array \fP[\fI var \fP])\fI statement\fP
Daniel@0: \fBwhile(\fI expression \fP)\fI statement\fP
Daniel@0: \fBswitch(\fI expression \fP)\fI case statements\fP
Daniel@0: \fBbreak [\fI expression \fP]
Daniel@0: \fBcontinue [\fI expression \fP]
Daniel@0: \fBreturn [\fI expression \fP]\fR
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .ST
Daniel@0: Items in brackets are optional.
Daniel@0: .PP
Daniel@0: In the second form of the \fBfor\fP statement, the variable \fIvar\fP
Daniel@0: is set to each value used as an index in the specified array and then
Daniel@0: the associated \fIstatement\fP is evaluated. Function definitions can
Daniel@0: only appear in the \fBBEGIN\fP clause.
Daniel@0: .PP
Daniel@0: Expressions include the usual C expressions. 
Daniel@0: String comparisons using \fB==\fP and \fB!=\fP
Daniel@0: treat the right hand operand as a pattern.
Daniel@0: \fBgvpr\fP will attempt to use an expression as a string or numeric value 
Daniel@0: as appropriate.
Daniel@0: .PP
Daniel@0: Expressions of graphical type (i.e., \fBgraph_t, node_t,
Daniel@0: edge_t, obj_t\fP) may be followed by a field reference in the
Daniel@0: form of \fB.\fP\fIname\fP. The resulting value is the value
Daniel@0: of the attribute named \fIname\fP of the given object.
Daniel@0: In addition, in certain contexts an undeclared, unmodified
Daniel@0: identifier is taken to be an
Daniel@0: attribute name. Specifically, such identifiers denote attributes
Daniel@0: of the current node or edge, respectively, in \fBN\fP
Daniel@0: and \fBE\fP clauses, and the current graph in \fBBEG_G\fP and \fBEND_G\fP
Daniel@0: clauses.
Daniel@0: .PP
Daniel@0: As usual in the 
Daniel@0: .IR libcgraph (3)
Daniel@0: model, attributes are string\(hyvalued.
Daniel@0: In addition,
Daniel@0: .B gvpr
Daniel@0: supports certain pseudo\(hyattributes of graph objects, not necessarily
Daniel@0: string\(hyvalued. These reflect intrinsic properties of the graph objects
Daniel@0: and cannot be set by the user.
Daniel@0: .TP
Daniel@0: \fBhead\fR : \fBnode_t\fR
Daniel@0: the head of an edge.
Daniel@0: .TP
Daniel@0: \fBtail\fR : \fBnode_t\fR
Daniel@0: the tail of an edge.
Daniel@0: .TP
Daniel@0: \fBname\fR : \fBstring\fR
Daniel@0: the name of an edge, node or graph. The name of an edge has the
Daniel@0: form "\fI<tail\(hyname><edge\(hyop><head\(hyname>\fB[\fI<key>\fB]\fR",
Daniel@0: where \fI<edge\(hyop>\fP is "\fB\->\fP" or "\fB\-\-\fP" depending on
Daniel@0: whether the graph is directed or not. The bracket part \fB[\fI<key>\fB]\fR
Daniel@0: only appears if the edge has a non\(hytrivial key.
Daniel@0: .TP
Daniel@0: \fBindegree\fR : \fBint\fR
Daniel@0: the indegree of a node.
Daniel@0: .TP
Daniel@0: \fBoutdegree\fR : \fBint\fR
Daniel@0: the outdegree of a node.
Daniel@0: .TP
Daniel@0: \fBdegree\fR : \fBint\fR
Daniel@0: the degree of a node.
Daniel@0: .TP
Daniel@0: \fBroot\fR : \fBgraph_t\fR
Daniel@0: the root graph of an object. The root of a root graph
Daniel@0: is itself.
Daniel@0: .TP
Daniel@0: \fBparent\fR : \fBgraph_t\fR
Daniel@0: the parent graph of a subgraph. The parent of a root graph
Daniel@0: is \fBNULL\fP
Daniel@0: .TP
Daniel@0: \fBn_edges\fR : \fBint\fR
Daniel@0: the number of edges in the graph
Daniel@0: .TP
Daniel@0: \fBn_nodes\fR : \fBint\fR
Daniel@0: the number of nodes in the graph
Daniel@0: .TP
Daniel@0: \fBdirected\fR : \fBint\fR
Daniel@0: true (non\(hyzero) if the graph is directed
Daniel@0: .TP
Daniel@0: \fBstrict\fR : \fBint\fR
Daniel@0: true (non\(hyzero) if the graph is strict
Daniel@0: .SH "BUILT\(hyIN FUNCTIONS"
Daniel@0: .PP
Daniel@0: The following functions are built into \fBgvpr\fP. Those functions
Daniel@0: returning references to graph objects return \fBNULL\fP in case of failure.
Daniel@0: .SS "Graphs and subgraph"
Daniel@0: .TP
Daniel@0: \fBgraph\fP(\fIs\fP : \fBstring\fP, \fIt\fP : \fBstring\fP) : \fBgraph_t\fP
Daniel@0: creates a graph whose name is \fIs\fP and whose type is
Daniel@0: specified by the string \fIt\fP. Ignoring case, the characters
Daniel@0: \fBU, D, S, N\fR have the interpretation undirected, directed,
Daniel@0: strict, and non\(hystrict, respectively. If \fIt\fP is empty,
Daniel@0: a directed, non\(hystrict graph is generated.
Daniel@0: .TP
Daniel@0: \fBsubg\fP(\fIg\fP : \fBgraph_t\fP, \fIs\fP : \fBstring\fP) : \fBgraph_t\fP
Daniel@0: creates a subgraph in graph \fIg\fP with name \fIs\fP. If the subgraph
Daniel@0: already exists, it is returned.
Daniel@0: .TP
Daniel@0: \fBisSubg\fP(\fIg\fP : \fBgraph_t\fP, \fIs\fP : \fBstring\fP) : \fBgraph_t\fP
Daniel@0: returns the subgraph in graph \fIg\fP with name \fIs\fP, if it exists,
Daniel@0: or \fBNULL\fP otherwise.
Daniel@0: .TP
Daniel@0: \fBfstsubg\fP(\fIg\fP : \fBgraph_t\fP) : \fBgraph_t\fP
Daniel@0: returns the first subgraph in graph \fIg\fP, or \fBNULL\fP if none exists.
Daniel@0: .TP
Daniel@0: \fBnxtsubg\fP(\fIsg\fP : \fBgraph_t\fP) : \fBgraph_t\fP
Daniel@0: returns the next subgraph after \fIsg\fP, or \fBNULL\fP.
Daniel@0: .TP
Daniel@0: \fBisDirect\fP(\fIg\fP : \fBgraph_t\fP) : \fBint\fP
Daniel@0: returns true if and only if \fIg\fP is directed.
Daniel@0: .TP
Daniel@0: \fBisStrict\fP(\fIg\fP : \fBgraph_t\fP) : \fBint\fP
Daniel@0: returns true if and only if \fIg\fP is strict.
Daniel@0: .TP
Daniel@0: \fBnNodes\fP(\fIg\fP : \fBgraph_t\fP) : \fBint\fP
Daniel@0: returns the number of nodes in \fIg\fP.
Daniel@0: .TP
Daniel@0: \fBnEdges\fP(\fIg\fP : \fBgraph_t\fP) : \fBint\fP
Daniel@0: returns the number of edges in \fIg\fP.
Daniel@0: .SS "Nodes"
Daniel@0: .TP
Daniel@0: \fBnode\fP(\fIsg\fP : \fBgraph_t\fP, \fIs\fP : \fBstring\fP) : \fBnode_t\fP
Daniel@0: creates a node in graph \fIg\fP of name \fIs\fP. If such a node
Daniel@0: already exists, it is returned.
Daniel@0: .TP
Daniel@0: \fBsubnode\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBnode_t\fP
Daniel@0: inserts the node \fIn\fP into the subgraph \fIg\fP. Returns the node.
Daniel@0: .TP
Daniel@0: \fBfstnode\fP(\fIg\fP : \fBgraph_t\fP) : \fBnode_t\fP
Daniel@0: returns the first node in graph \fIg\fP, or \fBNULL\fP if none exists.
Daniel@0: .TP
Daniel@0: \fBnxtnode\fP(\fIn\fP : \fBnode_t\fP) : \fBnode_t\fP
Daniel@0: returns the next node after \fIn\fP in the root graph, or \fBNULL\fP.
Daniel@0: .TP
Daniel@0: \fBnxtnode_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBnode_t\fP
Daniel@0: returns the next node after \fIn\fP in \fIsg\fP, or \fBNULL\fP.
Daniel@0: .TP
Daniel@0: \fBisNode\fP(\fIsg\fP : \fBgraph_t\fP, \fIs\fP : \fBstring\fP) : \fBnode_t\fP
Daniel@0: looks for a node in (sub)graph \fIsg\fP of name \fIs\fP. If such a node
Daniel@0: exists, it is returned. Otherwise, \fBNULL\fP is returned.
Daniel@0: .TP
Daniel@0: \fBisSubnode\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBint\fP
Daniel@0: returns non-zero if node \fIn\fP is in (sub)graph \fIsg\fP, or zero
Daniel@0: otherwise.
Daniel@0: .TP
Daniel@0: \fBindegreeOf\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBint\fP
Daniel@0: returns the indegree of node \fIn\fP in (sub)graph \fIsg\fP.
Daniel@0: .TP
Daniel@0: \fBoutdegreeOf\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBint\fP
Daniel@0: returns the outdegree of node \fIn\fP in (sub)graph \fIsg\fP.
Daniel@0: .TP
Daniel@0: \fBdegreeOf\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBint\fP
Daniel@0: returns the degree of node \fIn\fP in (sub)graph \fIsg\fP.
Daniel@0: .SS "Edges"
Daniel@0: .TP
Daniel@0: \fBedge\fP(\fIt\fP : \fBnode_t\fP, \fIh\fP : \fBnode_t\fP, \fIs\fP : \fBstring\fP) : \fBedge_t\fP
Daniel@0: creates an edge with tail node \fIt\fP, head node \fIh\fP and
Daniel@0: name \fIs\fP in the root graph. If the graph is undirected, the 
Daniel@0: distinction between head and tail nodes is unimportant.
Daniel@0: If such an edge already exists, it is returned.
Daniel@0: .TP
Daniel@0: \fBedge_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIt\fP : \fBnode_t\fP, \fIh\fP : \fBnode_t\fP, \fIs\fP : \fBstring\fP) : \fBedge_t\fP
Daniel@0: creates an edge with tail node \fIt\fP, head node \fIh\fP and name \fIs\fP 
Daniel@0: in (sub)graph \fIsg\fP (and all parent graphs). If the graph is undirected, the distinction between
Daniel@0: head and tail nodes is unimportant.
Daniel@0: If such an edge already exists, it is returned.
Daniel@0: .TP
Daniel@0: \fBsubedge\fP(\fIg\fP : \fBgraph_t\fP, \fIe\fP : \fBedge_t\fP) : \fBedge_t\fP
Daniel@0: inserts the edge \fIe\fP into the subgraph \fIg\fP. Returns the edge.
Daniel@0: .TP
Daniel@0: \fBisEdge\fP(\fIt\fP : \fBnode_t\fP, \fIh\fP : \fBnode_t\fP, \fIs\fP : \fBstring\fP) : \fBedge_t\fP
Daniel@0: looks for an edge with tail node \fIt\fP, head node \fIh\fP and
Daniel@0: name \fIs\fP. If the graph is undirected, the distinction between
Daniel@0: head and tail nodes is unimportant.
Daniel@0: If such an edge exists, it is returned. Otherwise, \fBNULL\fP is returned.
Daniel@0: .TP
Daniel@0: \fBisEdge_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIt\fP : \fBnode_t\fP, \fIh\fP : \fBnode_t\fP, \fIs\fP : \fBstring\fP) : \fBedge_t\fP
Daniel@0: looks for an edge with tail node \fIt\fP, head node \fIh\fP and
Daniel@0: name \fIs\fP in (sub)graph \fIsg\fP. If the graph is undirected, the distinction between
Daniel@0: head and tail nodes is unimportant.
Daniel@0: If such an edge exists, it is returned. Otherwise, \fBNULL\fP is returned.
Daniel@0: .TP
Daniel@0: \fBisSubedge\fP(\fIg\fP : \fBgraph_t\fP, \fIe\fP : \fBedge_t\fP) : \fBint\fP
Daniel@0: returns non-zero if edge \fIe\fP is in (sub)graph \fIsg\fP, or zero
Daniel@0: otherwise.
Daniel@0: .TP
Daniel@0: \fBfstout\fP(\fIn\fP : \fBnode_t\fP) : \fBedge_t\fP
Daniel@0: returns the first outedge of node \fIn\fP in the root graph.
Daniel@0: .TP
Daniel@0: \fBfstout_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBedge_t\fP
Daniel@0: returns the first outedge of node \fIn\fP in (sub)graph \fIsg\fP.
Daniel@0: .TP
Daniel@0: \fBnxtout\fP(\fIe\fP : \fBedge_t\fP) : \fBedge_t\fP
Daniel@0: returns the next outedge after \fIe\fP in the root graph.
Daniel@0: .TP
Daniel@0: \fBnxtout_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIe\fP : \fBedge_t\fP) : \fBedge_t\fP
Daniel@0: returns the next outedge after \fIe\fP in graph \fIsg\fP.
Daniel@0: .TP
Daniel@0: \fBfstin\fP(\fIn\fP : \fBnode_t\fP) : \fBedge_t\fP
Daniel@0: returns the first inedge of node \fIn\fP in the root graph.
Daniel@0: .TP
Daniel@0: \fBfstin_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBedge_t\fP
Daniel@0: returns the first inedge of node \fIn\fP in graph \fIsg\fP.
Daniel@0: .TP
Daniel@0: \fBnxtin\fP(\fIe\fP : \fBedge_t\fP) : \fBedge_t\fP
Daniel@0: returns the next inedge after \fIe\fP in the root graph.
Daniel@0: .TP
Daniel@0: \fBnxtin_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIe\fP : \fBedge_t\fP) : \fBedge_t\fP
Daniel@0: returns the next inedge after \fIe\fP in graph \fIsg\fP.
Daniel@0: .TP
Daniel@0: \fBfstedge\fP(\fIn\fP : \fBnode_t\fP) : \fBedge_t\fP
Daniel@0: returns the first edge of node \fIn\fP in the root graph.
Daniel@0: .TP
Daniel@0: \fBfstedge_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBedge_t\fP
Daniel@0: returns the first edge of node \fIn\fP in graph \fIsg\fP.
Daniel@0: .TP
Daniel@0: \fBnxtedge\fP(\fIe\fP : \fBedge_t\fP, \fBnode_t\fP) : \fBedge_t\fP
Daniel@0: returns the next edge after \fIe\fP in the root graph.
Daniel@0: .TP
Daniel@0: \fBnxtedge_sg\fP(\fIsg\fP : \fBgraph_t\fP, \fIe\fP : \fBedge_t\fP, \fBnode_t\fP) : \fBedge_t\fP
Daniel@0: returns the next edge after \fIe\fP in the graph \fIsg\fP.
Daniel@0: .SS "Graph I/O"
Daniel@0: .TP
Daniel@0: \fBwrite\fP(\fIg\fP : \fBgraph_t\fP) : \fBvoid\fP
Daniel@0: prints \fIg\fP in dot format onto the output stream.
Daniel@0: .TP
Daniel@0: \fBwriteG\fP(\fIg\fP : \fBgraph_t\fP, \fIfname\fP : \fBstring\fP) : \fBvoid\fP
Daniel@0: prints \fIg\fP in dot format into the file \fIfname\fP.
Daniel@0: .TP
Daniel@0: \fBfwriteG\fP(\fIg\fP : \fBgraph_t\fP, \fIfd\fP : \fBint\fP) : \fBvoid\fP
Daniel@0: prints \fIg\fP in dot format onto the open stream denoted
Daniel@0: by the integer \fIfd\fP.
Daniel@0: .TP
Daniel@0: \fBreadG\fP(\fIfname\fP : \fBstring\fP) : \fBgraph_t\fP
Daniel@0: returns a graph read from the file \fIfname\fP. The graph should be
Daniel@0: in dot format. If no graph can be read, \fBNULL\fP is returned.
Daniel@0: .TP
Daniel@0: \fBfreadG\fP(\fIfd\fP : \fBint\fP) : \fBgraph_t\fP
Daniel@0: returns the next graph read from the open stream \fIfd\fP.
Daniel@0: Returns \fBNULL\fP at end of file.
Daniel@0: .SS "Graph miscellany"
Daniel@0: .TP
Daniel@0: \fBdelete\fP(\fIg\fP : \fBgraph_t\fP, \fIx\fP : \fBobj_t\fP) : \fBvoid\fP
Daniel@0: deletes object \fIx\fP from graph \fIg\fP.
Daniel@0: If \fIg\fP is \fBNULL\fP, the function uses the root graph of \fIx\fP.
Daniel@0: If \fIx\fP is a graph or subgraph, it is closed unless \fIx\fP is locked.
Daniel@0: .TP
Daniel@0: \fBisIn\fP(\fIg\fP : \fBgraph_t\fP, \fIx\fP : \fBobj_t\fP) : \fBint\fP
Daniel@0: returns true if \fIx\fP is in subgraph \fIg\fP.
Daniel@0: .TP
Daniel@0: \fBclone\fP(\fIg\fP : \fBgraph_t\fP, \fIx\fP : \fBobj_t\fP) : \fBobj_t\fP
Daniel@0: creates a clone of object \fIx\fP in graph \fIg\fP.
Daniel@0: In particular, the new object has the same name/value attributes
Daniel@0: and structure as the original object.
Daniel@0: If an object with the same key as \fIx\fP already exists, its attributes
Daniel@0: are overlaid by those of \fIx\fP and the object is returned.
Daniel@0: If an edge is cloned, both endpoints are implicitly cloned.
Daniel@0: If a graph is cloned, all nodes, edges and subgraphs are implicitly
Daniel@0: cloned.
Daniel@0: If \fIx\fP is a graph, \fIg\fP may be \fBNULL\fP, in which case the cloned
Daniel@0: object will be a new root graph.
Daniel@0: .TP
Daniel@0: \fBcopy\fP(\fIg\fP : \fBgraph_t\fP, \fIx\fP : \fBobj_t\fP) : \fBobj_t\fP
Daniel@0: creates a copy of object \fIx\fP in graph \fIg\fP,
Daniel@0: where the new object has the same name/value attributes
Daniel@0: as the original object.
Daniel@0: If an object with the same key as \fIx\fP already exists, its attributes
Daniel@0: are overlaid by those of \fIx\fP and the object is returned.
Daniel@0: Note that this is a shallow copy. If \fIx\fP is a graph, none of its nodes, 
Daniel@0: edges or subgraphs are copied into the new graph. If \fIx\fP is an edge,
Daniel@0: the endpoints are created if necessary, but they are not cloned.
Daniel@0: If \fIx\fP is a graph, \fIg\fP may be \fBNULL\fP, in which case the cloned
Daniel@0: object will be a new root graph.
Daniel@0: .TP
Daniel@0: \fBcopyA\fP(\fIsrc\fP : \fBobj_t\fP, \fItgt\fP : \fBobj_t\fP) : \fBint\fP
Daniel@0: copies the attributes of object \fIsrc\fP to object \fItgt\fP, overwriting
Daniel@0: any attribute values \fItgt\fP may initially have.
Daniel@0: .TP
Daniel@0: \fBinduce\fP(\fIg\fP : \fBgraph_t\fP) : \fBvoid\fP
Daniel@0: extends \fIg\fP to its node\(hyinduced subgraph extension in its root graph.
Daniel@0: .TP
Daniel@0: \fBhasAttr\fP(\fIsrc\fP : \fBobj_t\fP, \fIname\fP : \fBstring\fP) : \fBint\fP
Daniel@0: returns non-zero if object \fIsrc\fP has an attribute whose name is
Daniel@0: \fIname\fP. It returns 0 otherwise.
Daniel@0: .TP
Daniel@0: \fBisAttr\fP(\fIg\fP : \fBgraph_t\fP, \fIkind\fP : \fBstring\fP, \fIname\fP : \fBstring\fP) : \fBint\fP
Daniel@0: returns non-zero if an attribute \fIname\fP has been defined in \fIg\fP
Daniel@0: for objects of the given \fIkind\fP. For nodes, edges, and graphs, \fIkind\fP
Daniel@0: should be "N", "E", and "G", respectively.
Daniel@0: It returns 0 otherwise.
Daniel@0: .TP
Daniel@0: \fBaget\fP(\fIsrc\fP : \fBobj_t\fP, \fIname\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns the value of attribute \fIname\fP in object \fIsrc\fP. This is
Daniel@0: useful for those cases when \fIname\fP conflicts with one of the keywords
Daniel@0: such as "head" or "root".
Daniel@0: If the attribute has not been declared in the graph, the function will
Daniel@0: initialize it with a default value of "". To avoid this, one should use
Daniel@0: the \fBhasAttr\fP or \fBisAttr\fP function to check that the attribute exists.
Daniel@0: .TP
Daniel@0: \fBaset\fP(\fIsrc\fP : \fBobj_t\fP, \fIname\fP : \fBstring\fP, \fIvalue\fP : \fBstring\fP) : \fBint\fP
Daniel@0: sets the value of attribute \fIname\fP in object \fIsrc\fP to \fIvalue\fP.
Daniel@0: Returns 0 on success, non\(hyzero on failure. See \fBaget\fP above.
Daniel@0: .TP
Daniel@0: \fBgetDflt\fP(\fIg\fP : \fBgraph_t\fP, \fIkind\fP : \fBstring\fP, \fIname\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns the default value of attribute \fIname\fP in objects in \fIg\fP of
Daniel@0: the given \fIkind\fP. For nodes, edges, and graphs, \fIkind\fP
Daniel@0: should be "N", "E", and "G", respectively.
Daniel@0: If the attribute has not been declared in the graph, the function will
Daniel@0: initialize it with a default value of "". To avoid this, one should use
Daniel@0: the \fBisAttr\fP function to check that the attribute exists.
Daniel@0: .TP
Daniel@0: \fBsetDflt\fP(\fIg\fP : \fBgraph_t\fP, \fIkind\fP : \fBstring\fP, \fIname\fP : \fBstring\fP, \fIvalue\fP : \fBstring\fP) : \fBint\fP
Daniel@0: sets the default value of attribute \fIname\fP to \fIvalue\fP in 
Daniel@0: objects in \fIg\fP of
Daniel@0: the given \fIkind\fP. For nodes, edges, and graphs, \fIkind\fP
Daniel@0: should be "N", "E", and "G", respectively.
Daniel@0: Returns 0 on success, non\(hyzero on failure. See \fBgetDflt\fP above.
Daniel@0: .TP
Daniel@0: \fBfstAttr\fP(\fIg\fP : \fBgraph_t\fP, \fIkind\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns the name of the first attribute of objects in \fIg\fP of
Daniel@0: the given \fIkind\fP. For nodes, edges, and graphs, \fIkind\fP
Daniel@0: should be "N", "E", and "G", respectively.
Daniel@0: If there are no attributes, the string "" is returned.
Daniel@0: .TP
Daniel@0: \fBnxtAttr\fP(\fIg\fP : \fBgraph_t\fP, \fIkind\fP : \fBstring\fP, \fIname\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns the name of the next attribute of objects in \fIg\fP of
Daniel@0: the given \fIkind\fP after the attribute \fIname\fP. 
Daniel@0: The argument \fIname\fP must be the name of an existing attribute; it will
Daniel@0: typically be the return value of an previous call to \fBfstAttr\fP or
Daniel@0: \fBnxtAttr\fP.
Daniel@0: For nodes, edges, and graphs, \fIkind\fP
Daniel@0: should be "N", "E", and "G", respectively.
Daniel@0: If there are no attributes left, the string "" is returned.
Daniel@0: .TP
Daniel@0: \fBcompOf\fP(\fIg\fP : \fBgraph_t\fP, \fIn\fP : \fBnode_t\fP) : \fBgraph_t\fP
Daniel@0: returns the connected component of the graph \fIg\fP containing node \fIn\fP,
Daniel@0: as a subgraph of \fIg\fP. The subgraph only contains the nodes. One can
Daniel@0: use \fIinduce\fP to add the edges. The function fails and returns \fBNULL\fP
Daniel@0: if \fIn\fP is not in \fIg\fP. Connectivity is based on the underlying
Daniel@0: undirected graph of \fIg\fP.
Daniel@0: .TP
Daniel@0: \fBkindOf\fP(\fIobj\fP : \fBobj_t\fP) : \fBstring\fP
Daniel@0: returns an indication of what kind of graph object is the argument.
Daniel@0: For nodes, edges, and graphs, it returns
Daniel@0: should be "N", "E", and "G", respectively.
Daniel@0: .TP
Daniel@0: \fBlock\fP(\fIg\fP : \fBgraph_t\fP, \fIv\fP : \fBint\fP) : \fBint\fP
Daniel@0: implements graph locking on root graphs. If the integer \fIv\fP is positive, the
Daniel@0: graph is set so that future calls to \fBdelete\fP have no immediate effect.
Daniel@0: If \fIv\fP is zero, the graph is unlocked. If there has been a call
Daniel@0: to delete the graph while it was locked, the graph is closed.
Daniel@0: If \fIv\fP is negative, nothing is done.
Daniel@0: In all cases, the previous lock value is returned.
Daniel@0: .SS "Strings"
Daniel@0: .TP
Daniel@0: \fBsprintf\fP(\fIfmt\fP : \fBstring\fP, \fI...\fP) : \fBstring\fP
Daniel@0: returns the string resulting from formatting
Daniel@0: the values of the expressions occurring after \fIfmt\fP
Daniel@0: according to the
Daniel@0: .IR printf (3)
Daniel@0: format
Daniel@0: .I fmt
Daniel@0: .TP
Daniel@0: \fBgsub\fP(\fIstr\fP : \fBstring\fP, \fIpat\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: .TP
Daniel@0: \fBgsub\fP(\fIstr\fP : \fBstring\fP, \fIpat\fP : \fBstring\fP, \fIrepl\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns \fIstr\fP with all substrings matching \fIpat\fP
Daniel@0: deleted or replaced by \fIrepl\fP, respectively.
Daniel@0: .TP
Daniel@0: \fBsub\fP(\fIstr\fP : \fBstring\fP, \fIpat\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: .TP
Daniel@0: \fBsub\fP(\fIstr\fP : \fBstring\fP, \fIpat\fP : \fBstring\fP, \fIrepl\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns \fIstr\fP with the leftmost substring matching \fIpat\fP
Daniel@0: deleted or replaced by \fIrepl\fP, respectively. The 
Daniel@0: characters '^' and '$'
Daniel@0: may be used at the beginning and end, respectively,
Daniel@0: of \fIpat\fP to anchor the pattern to the beginning or end of \fIstr\fP.
Daniel@0: .TP
Daniel@0: \fBsubstr\fP(\fIstr\fP : \fBstring\fP, \fIidx\fP : \fBint\fP) : \fBstring\fP
Daniel@0: .TP
Daniel@0: \fBsubstr\fP(\fIstr\fP : \fBstring\fP, \fIidx\fP : \fBint\fP, \fIlen\fP : \fBint\fP) : \fBstring\fP
Daniel@0: returns the substring of \fIstr\fP starting at position \fIidx\fP to
Daniel@0: the end of the string or of length \fIlen\fP, respectively.
Daniel@0: Indexing starts at 0. If \fIidx\fP is negative or \fIidx\fP is greater than
Daniel@0: the length of \fIstr\fP, a fatal error occurs. Similarly, in the second
Daniel@0: case, if \fIlen\fP is negative or \fIidx\fP + \fIlen\fP is greater than the
Daniel@0: length of \fIstr\fP, a fatal error occurs.
Daniel@0: .TP
Daniel@0: \fBlength\fP(\fIs\fP : \fBstring\fP) : \fBint\fP
Daniel@0: returns the length of the string \fIs\fP.
Daniel@0: .TP
Daniel@0: \fBindex\fP(\fIs\fP : \fBstring\fP, \fIt\fP : \fBstring\fP) : \fBint\fP
Daniel@0: .TP
Daniel@0: \fBrindex\fP(\fIs\fP : \fBstring\fP, \fIt\fP : \fBstring\fP) : \fBint\fP
Daniel@0: returns the index of the character in string \fIs\fP where the leftmost
Daniel@0: (rightmost) copy of string \fIt\fP can be found, or \-1 if \fIt\fP is not a 
Daniel@0: substring of \fIs\fP.
Daniel@0: .TP
Daniel@0: \fBmatch\fP(\fIs\fP : \fBstring\fP, \fIp\fP : \fBstring\fP) : \fBint\fP
Daniel@0: returns the index of the character in string \fIs\fP where the leftmost
Daniel@0: match of pattern \fIp\fP can be found, or \-1 if no substring of \fIs\fP
Daniel@0: matches \fIp\fP.
Daniel@0: .TP
Daniel@0: \fBcanon\fP(\fIs\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns a version of \fIs\fP appropriate to be used as an identifier
Daniel@0: in a dot file.
Daniel@0: .TP
Daniel@0: \fBxOf\fP(\fIs\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns the string "\fIx\fP" if \fIs\fP has the form "\fIx\fP,\fIy\fP", 
Daniel@0: where both \fIx\fP and \fIy\fP are numeric.
Daniel@0: .TP
Daniel@0: \fByOf\fP(\fIs\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns the string "\fIy\fP" if \fIs\fP has the form "\fIx\fP,\fIy\fP", 
Daniel@0: where both \fIx\fP and \fIy\fP are numeric.
Daniel@0: .TP
Daniel@0: \fBllOf\fP(\fIs\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns the string "\fIllx\fP,\fIlly\fP" if \fIs\fP has the form 
Daniel@0: "\fIllx\fP,\fIlly\fP,\fIurx\fP,\fIury\fP",
Daniel@0: where all of \fIllx\fP, \fIlly\fP, \fIurx\fP, and \fIury\fP are numeric.
Daniel@0: .TP
Daniel@0: .BI urOf( s )
Daniel@0: \fBurOf\fP(\fIs\fP : \fBstring\fP) : \fBstring\fP
Daniel@0: returns the string "\fIurx\fP,\fIury\fP" if \fIs\fP has the form 
Daniel@0: "\fIllx\fP,\fIlly\fP,\fIurx\fP,\fIury\fP",
Daniel@0: where all of \fIllx\fP, \fIlly\fP, \fIurx\fP, and \fIury\fP are numeric.
Daniel@0: .TP
Daniel@0: \fBsscanf\fP(\fIs\fP : \fBstring\fP, \fIfmt\fP : \fBstring\fP, \fI...\fP) : \fBint\fP
Daniel@0: scans the string \fIs\fP, extracting values
Daniel@0: according to the
Daniel@0: .IR sscanf (3)
Daniel@0: format
Daniel@0: .IR fmt .
Daniel@0: The values are stored in the addresses following \fIfmt\fP,
Daniel@0: addresses having the form \fB&\fP\fIv\fP, where \fIv\fP is some declared
Daniel@0: variable of the correct type.
Daniel@0: Returns the number of items successfully scanned.
Daniel@0: .SS "I/O"
Daniel@0: .TP
Daniel@0: \fBprint\fP(\fI...\fP) : \fBvoid\fP
Daniel@0: .BI print( " expr" , " ...\fB )
Daniel@0: prints a string representation of each argument in turn onto
Daniel@0: \fBstdout\fP, followed by a newline.
Daniel@0: .TP
Daniel@0: \fBprintf\fP(\fIfmt\fP : \fBstring\fP, \fI...\fP) : \fBint\fP
Daniel@0: .TP
Daniel@0: \fBprintf\fP(\fIfd\fP : \fBint\fP, \fIfmt\fP : \fBstring\fP, \fI...\fP) : \fBint\fP
Daniel@0: prints the string resulting from formatting
Daniel@0: the values of the expressions following \fIfmt\fP
Daniel@0: according to the
Daniel@0: .IR printf (3)
Daniel@0: format
Daniel@0: .IR fmt .
Daniel@0: Returns 0 on success.
Daniel@0: By default, it prints on \fBstdout\fP.
Daniel@0: If the optional integer \fIfd\fP is given, output is written on the open
Daniel@0: stream associated with \fIfd\fP.
Daniel@0: .TP
Daniel@0: \fBscanf\fP(\fIfmt\fP : \fBstring\fP, \fI...\fP) : \fBint\fP
Daniel@0: .TP
Daniel@0: \fBscanf\fP(\fIfd\fP : \fBint\fP, \fIfmt\fP : \fBstring\fP, \fI...\fP) : \fBint\fP
Daniel@0: scans in values from an input stream according to the
Daniel@0: .IR scanf (3)
Daniel@0: format
Daniel@0: .IR fmt .
Daniel@0: The values are stored in the addresses following \fIfmt\fP,
Daniel@0: addresses having the form \fB&\fP\fIv\fP, where \fIv\fP is some declared
Daniel@0: variable of the correct type.
Daniel@0: By default, it reads from \fBstdin\fP.
Daniel@0: If the optional integer \fIfd\fP is given, input is read from the open
Daniel@0: stream associated with \fIfd\fP.
Daniel@0: Returns the number of items successfully scanned.
Daniel@0: .TP
Daniel@0: \fBopenF\fP(\fIs\fP : \fBstring\fP, \fIt\fP : \fBstring\fP) : \fBint\fP
Daniel@0: opens the file \fIs\fP as an I/O stream. The string argument \fIt\fP
Daniel@0: specifies how the file is opened. The arguments are the same as for
Daniel@0: the C function
Daniel@0: .IR fopen (3).
Daniel@0: It returns an integer denoting the stream, or \-1 on error.
Daniel@0: .sp
Daniel@0: As usual, streams 0, 1 and 2 are already open as \fBstdin\fP, \fBstdout\fP,
Daniel@0: and \fBstderr\fP, respectively. Since \fBgvpr\fP may use \fBstdin\fP to
Daniel@0: read the input graphs, the user should avoid using this stream.
Daniel@0: .TP
Daniel@0: \fBcloseF\fP(\fIfd\fP : \fBint\fP) : \fBint\fP
Daniel@0: closes the open stream denoted by the integer \fIfd\fP.
Daniel@0: Streams  0, 1 and 2 cannot be closed.
Daniel@0: Returns 0 on success.
Daniel@0: .TP
Daniel@0: \fBreadL\fP(\fIfd\fP : \fBint\fP) : \fBstring\fP
Daniel@0: returns the next line read from the input stream \fIfd\fP. It returns
Daniel@0: the empty string "" on end of file. Note that the newline character is
Daniel@0: left in the returned string.
Daniel@0: .SS "Math"
Daniel@0: .TP
Daniel@0: \fBexp\fP(\fId\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns e to the \fId\fPth power.
Daniel@0: .TP
Daniel@0: \fBlog\fP(\fId\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns the natural log of \fId\fP.
Daniel@0: .TP
Daniel@0: \fBsqrt\fP(\fId\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns the square root of the double \fId\fP.
Daniel@0: .TP
Daniel@0: \fBpow\fP(\fId\fP : \fBdouble\fP, \fIx\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns \fId\fP raised to the \fIx\fPth power.
Daniel@0: .TP
Daniel@0: \fBcos\fP(\fId\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns the cosine of \fId\fP.
Daniel@0: .TP
Daniel@0: \fBsin\fP(\fId\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns the sine of \fId\fP.
Daniel@0: .TP
Daniel@0: \fBatan2\fP(\fIy\fP : \fBdouble\fP, \fIx\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns the arctangent of \fIy/x\fP in the range \-pi to pi.
Daniel@0: .TP
Daniel@0: \fBMIN\fP(\fIy\fP : \fBdouble\fP, \fIx\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns the minimum of \fIy\fP and \fIx\fP.
Daniel@0: .TP
Daniel@0: \fBMAX\fP(\fIy\fP : \fBdouble\fP, \fIx\fP : \fBdouble\fP) : \fBdouble\fP
Daniel@0: returns the maximum of \fIy\fP and \fIx\fP.
Daniel@0: .SS "Miscellaneous"
Daniel@0: .TP
Daniel@0: \fBexit\fP(\fIv\fP : \fBint\fP) : \fBvoid\fP
Daniel@0: causes
Daniel@0: .B gvpr
Daniel@0: to exit with the exit code
Daniel@0: .IR v .
Daniel@0: .TP
Daniel@0: \fBsystem\fP(\fIcmd\fP : \fBstring\fP) : \fBint\fP
Daniel@0: provides the standard C function
Daniel@0: .IR system (3).
Daniel@0: It executes \fIcmd\fP if the user's shell environment, and
Daniel@0: returns the exit status of the shell.
Daniel@0: .TP
Daniel@0: \fBrand\fP() : \fBdouble\fP
Daniel@0: returns a pseudo\(hyrandom double between 0 and 1.
Daniel@0: .TP
Daniel@0: \fBsrand\fP() : \fBint\fP
Daniel@0: .TP
Daniel@0: \fBsrand\fP(\fIv\fP : \fBint\fP) : \fBint\fP
Daniel@0: sets a seed for the random number generator. The optional argument gives
Daniel@0: the seed; if it is omitted, the current time is used. The previous seed
Daniel@0: value is returned. \fBsrand\fP should be called before any calls to
Daniel@0: \fBrand\fP.
Daniel@0: .SH "BUILT\(hyIN VARIABLES"
Daniel@0: .PP
Daniel@0: .B gvpr
Daniel@0: provides certain special, built\(hyin variables, whose values are set
Daniel@0: automatically by \fBgvpr\fP depending on the context. Except as noted,
Daniel@0: the user cannot modify their values.
Daniel@0: .TP
Daniel@0: \fB$\fP : \fBobj_t\fP
Daniel@0: denotes the current object (node, edge, graph) depending on the
Daniel@0: context.  It is not available in \fBBEGIN\fP or \fBEND\fP clauses.
Daniel@0: .TP
Daniel@0: \fB$F\fP : \fBstring\fP
Daniel@0: is the name of the current input file. 
Daniel@0: .TP
Daniel@0: \fB$G\fP : \fBgraph_t\fP
Daniel@0: denotes the current graph being processed. It is not available
Daniel@0: in \fBBEGIN\fP or \fBEND\fP clauses.
Daniel@0: .TP
Daniel@0: \fB$O\fP : \fBgraph_t\fP
Daniel@0: denotes the output graph. Before graph traversal, it is initialized
Daniel@0: to the target graph. After traversal and any \fBEND_G\fP actions,
Daniel@0: if it refers to a non\(hyempty graph, that graph is printed onto the output stream.
Daniel@0: It is only valid in \fBN\fP, \fBE\fP and \fBEND_G\fP clauses.
Daniel@0: The output graph may be set by the user.
Daniel@0: .TP
Daniel@0: \fB$T\fP : \fBgraph_t\fP
Daniel@0: denotes the current target graph. It is a subgraph of \fB$G\fP
Daniel@0: and is available only in \fBN\fP, \fBE\fP and \fBEND_G\fP clauses.
Daniel@0: .TP
Daniel@0: \fB$tgtname\fP : \fBstring\fP
Daniel@0: denotes the name of the target graph. 
Daniel@0: By default, it is set to \fB"gvpr_result"\fP.
Daniel@0: If used multiple times during the execution of
Daniel@0: .BR gvpr ,
Daniel@0: the name will be appended with an integer. 
Daniel@0: This variable may be set by the user.
Daniel@0: .TP
Daniel@0: \fB$tvroot\fP : \fBnode_t\fP
Daniel@0: indicates the starting node for a (directed or undirected)
Daniel@0: depth\(hyfirst traversal of the
Daniel@0: graph (cf. \fB$tvtype\fP below).
Daniel@0: The default value is \fBNULL\fP for each input graph.
Daniel@0: .TP
Daniel@0: \fB$tvtype\fP : \fBtvtype_t\fP
Daniel@0: indicates how \fBgvpr\fP traverses a graph. It can only take
Daniel@0: one of the constant values with the previx "TV_" described below.
Daniel@0: \fBTV_flat\fP is the default.
Daniel@0: .IP
Daniel@0: In the underlying graph library
Daniel@0: .IR cgraph (3),
Daniel@0: edges in undirected graphs are given an arbitrary direction. This is
Daniel@0: used for traversals, such as \fBTV_fwd\fR, requiring directed edges.
Daniel@0: .
Daniel@0: .TP
Daniel@0: \fBARGC\fP : \fBint\fP
Daniel@0: denotes the number of arguments specified by the 
Daniel@0: \fB\-a\fP \fIargs\fP command\(hyline argument.
Daniel@0: .TP
Daniel@0: \fBARGV\fP : \fBstring array\fP
Daniel@0: denotes the array of arguments specified by the 
Daniel@0: \fB\-a\fP \fIargs\fP
Daniel@0: command\(hyline argument. The \fIi\fPth argument is given
Daniel@0: by \fBARGV[\fIi\fP]\fR.
Daniel@0: .SH "BUILT\(hyIN CONSTANTS"
Daniel@0: .PP
Daniel@0: There are several symbolic constants defined by \fBgvpr\fP.
Daniel@0: .TP
Daniel@0: \fBNULL\fR : \fIobj_t\fR
Daniel@0: a null object reference, equivalent to 0.
Daniel@0: .TP
Daniel@0: \fBTV_flat\fR : \fItvtype_t\fR
Daniel@0: a simple, flat traversal, with graph objects visited in
Daniel@0: seemingly arbitrary order.
Daniel@0: .TP
Daniel@0: \fBTV_ne\fR : \fItvtype_t\fR
Daniel@0: a traversal which first visits all of the nodes, then all
Daniel@0: of the edges.
Daniel@0: .TP
Daniel@0: \fBTV_en\fR : \fItvtype_t\fR
Daniel@0: a traversal which first visits all of the edges, then all
Daniel@0: of the nodes.
Daniel@0: .TP
Daniel@0: \fBTV_dfs\fR : \fItvtype_t\fR
Daniel@0: .TQ
Daniel@0: \fBTV_postdfs\fR : \fItvtype_t\fR
Daniel@0: .TQ
Daniel@0: \fBTV_prepostdfs\fR : \fItvtype_t\fR
Daniel@0: a traversal of the graph using a depth\(hyfirst search on the
Daniel@0: underlying undirected graph. 
Daniel@0: To do the traversal, \fBgvpr\fP will check the value of
Daniel@0: \fB$tvroot\fP. If this has the same value that it had previously
Daniel@0: (at the start, the previous value is initialized to \fBNULL\fP.), \fBgvpr\fP
Daniel@0: will simply look for some unvisited node and traverse its connected
Daniel@0: component. On the other hand, if \fB$tvroot\fP has changed, its connected
Daniel@0: component will be toured, assuming it has not been previously visited or,
Daniel@0: if \fB$tvroot\fP is \fBNULL\fP, the traversal will stop. Note that using
Daniel@0: \fBTV_dfs\fP and \fB$tvroot\fP, it is possible to create an infinite loop.
Daniel@0: .
Daniel@0: .IP
Daniel@0: By default, the traversal is done in pre-order. That is, a node is
Daniel@0: visited before all of its unvisited edges. For \fBTV_postdfs\fR,
Daniel@0: all of a node's unvisited edges are visited before the node. For
Daniel@0: \fBTV_prepostdfs\fR, a node is visited twice, before and after all of
Daniel@0: its unvisited edges.
Daniel@0: .
Daniel@0: .TP
Daniel@0: \fBTV_fwd\fR : \fItvtype_t\fR
Daniel@0: .TQ
Daniel@0: \fBTV_postfwd\fR : \fItvtype_t\fR
Daniel@0: .TQ
Daniel@0: \fBTV_prepostfwd\fR : \fItvtype_t\fR
Daniel@0: A traversal of the graph using a depth\(hyfirst search on the
Daniel@0: graph following only forward arcs.
Daniel@0: The choice of roots for the traversal is the
Daniel@0: same as described for \fBTV_dfs\fR above.
Daniel@0: The different order of visitation specified by \fBTV_fwd\fR,
Daniel@0: \fBTV_postfwd\fR and \fBTV_prepostfwd\fR are the same as those
Daniel@0: specified by the analogous traversals \fBTV_dfs\fR,
Daniel@0: \fBTV_postdfs\fR and \fBTV_prepostdfs\fR.
Daniel@0: .TP
Daniel@0: \fBTV_rev\fR : \fItvtype_t\fR
Daniel@0: .TQ
Daniel@0: \fBTV_postrev\fR : \fItvtype_t\fR
Daniel@0: .TQ
Daniel@0: \fBTV_prepostrev\fR : \fItvtype_t\fR
Daniel@0: A traversal of the graph using a depth\(hyfirst search on the
Daniel@0: graph following only reverse arcs.
Daniel@0: The choice of roots for the traversal is the
Daniel@0: same as described for \fBTV_dfs\fR above.
Daniel@0: The different order of visitation specified by \fBTV_rev\fR,
Daniel@0: \fBTV_postrev\fR and \fBTV_prepostrev\fR are the same as those
Daniel@0: specified by the analogous traversals \fBTV_dfs\fR,
Daniel@0: \fBTV_postdfs\fR and \fBTV_prepostdfs\fR.
Daniel@0: .TP
Daniel@0: \fBTV_bfs\fR : \fItvtype_t\fR
Daniel@0: A traversal of the graph using a bread\(hyfirst search on the
Daniel@0: graph ignoring edge directions. See the item on \fBTV_dfs\fR above
Daniel@0: for the role of \fB$tvroot\fP.
Daniel@0: .SH EXAMPLES
Daniel@0: .PP
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: \fBgvpr \-i 'N[color=="blue"]' file.dot\fP
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .DT
Daniel@0: .PP
Daniel@0: Generate the node\(hyinduced subgraph of all nodes with color blue.
Daniel@0: .PP
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: \fBgvpr \-c 'N[color=="blue"]{color = "red"}' file.dot\fP
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .DT
Daniel@0: .PP
Daniel@0: Make all blue nodes red.
Daniel@0: .PP
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: \fBBEGIN { int n, e; int tot_n = 0; int tot_e = 0; }
Daniel@0: BEG_G {
Daniel@0:   n = nNodes($G);
Daniel@0:   e = nEdges($G);
Daniel@0:   printf ("%d nodes %d edges %s\n", n, e, $G.name);
Daniel@0:   tot_n += n;
Daniel@0:   tot_e += e;
Daniel@0: }
Daniel@0: END { printf ("%d nodes %d edges total\n", tot_n, tot_e) }\fP
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .DT
Daniel@0: .PP
Daniel@0: Version of the program \fBgc\fP.
Daniel@0: .PP
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: \fBgvpr \-c ""\fP
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .DT
Daniel@0: .PP
Daniel@0: Equivalent to \fBnop\fP.
Daniel@0: .PP
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: \fBBEG_G { graph_t g = graph ("merge", "S"); }
Daniel@0: E {
Daniel@0:   node_t h = clone(g,$.head);
Daniel@0:   node_t t = clone(g,$.tail);
Daniel@0:   edge_t e = edge(t,h,"");
Daniel@0:   e.weight = e.weight + 1;
Daniel@0: }
Daniel@0: END_G { $O = g; }\fP
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .DT
Daniel@0: .PP
Daniel@0: Produces a strict version of the input graph, where the weight attribute
Daniel@0: of an edge indicates how many edges from the input graph the edge represents.
Daniel@0: .PP
Daniel@0: .ta \w'\f(CWdelete array[expression]'u
Daniel@0: .RS
Daniel@0: .nf
Daniel@0: \fBBEGIN {node_t n; int deg[]}
Daniel@0: E{deg[head]++; deg[tail]++; }
Daniel@0: END_G {
Daniel@0:   for (deg[n]) {
Daniel@0:     printf ("deg[%s] = %d\n", n.name, deg[n]);
Daniel@0:   }
Daniel@0: }\fP
Daniel@0: .fi
Daniel@0: .RE
Daniel@0: .DT
Daniel@0: .PP
Daniel@0: Computes the degrees of nodes with edges.
Daniel@0: .SH ENVIRONMENT
Daniel@0: .TP
Daniel@0: .B GPRPATH
Daniel@0: Colon\(hyseparated list of directories to be searched to find
Daniel@0: the file specified by the \-f option.
Daniel@0: .SH BUGS AND WARNINGS
Daniel@0: When the program is given as a command line argument, the usual
Daniel@0: shell interpretation takes place, which may affect some of the
Daniel@0: special names in \fBgvpr\fP. To avoid this, it is best to wrap the
Daniel@0: program in single quotes.
Daniel@0: .PP
Daniel@0: As of 24 April 2008, \fBgvpr\fP switched to using a new, underlying
Daniel@0: graph library, which uses the simpler model that there is only one
Daniel@0: copy of a node, not one copy for each subgraph logically containing
Daniel@0: it. This means that iterators such as \Inxtnode\P cannot traverse
Daniel@0: a subgraph using just a node argument. For this reason, subgraph
Daniel@0: traversal requires new functions ending in "_sg", which also take
Daniel@0: a subgraph argument. The versions without that suffix will always
Daniel@0: traverse the root graph.
Daniel@0: .PP
Daniel@0: There is a single global scope, except for formal function parameters,
Daniel@0: and even these can interfere with the type system. Also, the 
Daniel@0: extent of all variables is the entire life of the program. 
Daniel@0: It might be preferable for scope
Daniel@0: to reflect the natural nesting of the clauses, or for the program
Daniel@0: to at least reset locally declared variables.
Daniel@0: For now, it is advisable to use distinct names for all variables.
Daniel@0: .PP
Daniel@0: If a function ends with a complex statement, such as an
Daniel@0: IF statement, with each branch doing a return, type checking may fail. 
Daniel@0: Functions should use a return at the end.
Daniel@0: .PP
Daniel@0: The expr library does not support string values of (char*)0.
Daniel@0: This means we can't distinguish between "" and (char*)0 edge keys.
Daniel@0: For the purposes of looking up and creating edges, we translate "" 
Daniel@0: to be (char*)0, since this latter value is
Daniel@0: necessary in order to look up any edge with a matching head and tail.
Daniel@0: .PP
Daniel@0: Related to this, strings converted to integers act like char pointers,
Daniel@0: getting the value 0 or 1 depending on whether the string consists
Daniel@0: solely of zeroes or not. Thus, the ((int)"2") evaluates to 1.
Daniel@0: .PP
Daniel@0: The language inherits the usual C problems such as dangling references
Daniel@0: and the confusion between '=' and '=='.
Daniel@0: .SH AUTHOR
Daniel@0: Emden R. Gansner <erg@research.att.com>
Daniel@0: .SH "SEE ALSO"
Daniel@0: .PP
Daniel@0: awk(1), gc(1), dot(1), nop(1), libexpr(3), libcgraph(3)