Table of Contents

Name

Tcldgr - dynamic graph manipulation in tcl

Synopsis

#!/bin/sh
# next line is a comment in tcl \
exec tclsh "$0" ${1+"$@"}

package require Tcldgr

Usage

Requires the dynamic loading facilities of tcl7.6 or later. Does not require tk.

Introduction

Tcldgr is a member of the Tcldg family of extensions, another being Tcldgl (layouts). Tcldgr provides an interface to the graph manipulation facilities of libgraph(3) .

This extension is an evolution from its tcldot heritage. The major differences are the "bindings" to graph for incremental graph events, and the removal to the companion package Tcldgl of all layout features.

All tcl commands used in this family of extensions use the prefix "dg".

Command Summary

Tcldgr extends the Tcl (Tool Command Language). Tcl provides control flow (e.g., if, for, break), expression evaluation and several other features such as recursion, procedure definition, etc. Commands used in this man page but not defined (e.g., set, if, exec) are Tcl commands (see Tcl(n) for more details).

Tcldgr initially adds only five commands to the tcl interpreter, namely: dgnew, dgread, dgstring, dg, and dgreset. The command: dgreset is intended for use only in regression tests and is not documented further in these man pages.

Many Tcldgr commands return a handle of a graph, node, or edge. Handles take forms like: "dgG0" "dgN5" "dgE20". The prefix of handles is always "dg", the "G", "N", or "E", indicate the type of object (Graph, Node, Edge), and the number is a unique ID across all dg objects used in a single interpreter session. IDs are reused if objects are deleted.

There are two script styles supported by Tcldgr, the style is selected by the first command used to create a graph in an interpreter.

The first style is selected if dgnew, dgread, or dgstring are used. In this style the handles of created objects are themselves registered as tcl commands to permit direct operations on the objects. In this case the dg command is deleted from the interpreter to prevent mixing styles in the script. The additional commands are all of the form:

    <handle> <method> <parameters>

In the second style, the only tcl command used is dg and handles are not registered as commands. This style may be used if the user is concerned about pollution of the tcl command namespace. There isn't likely to be much difference in efficiency. Once dg is used the first time the commands dgnew, dgread, and dgstring are deleted to prevent mixing of styles. The dg commands are:

    dg new <same parameters as dgnew>
    dg read <same parameters as dgread>
    dg string <same parameters as dgstring>
    dg <handle> <method> <parameters>

The remainder of this man page uses the first style and the dg ... style is not further discussed.

The commands and methods are described in detail below, but in summary:

Tcl commands are:

dgnew, dgread, dgstring, dg, dgreset.
Graph methods are:

addedge, addnode, addsubgraph, batch, bind, concatfile, countedges, countnodes, findedge, graphof, listattributes, listedgeattributes, listnodeattributes, listedges, listnodes, listsubgraphs, nextedge, nextnode, parentgraph, queryattributes, queryedgeattributes, querynodeattributes, set, setattributes, setedgeattributes, setnodeattributes, showname, showtype, write.
Node methods are:

addedge, countedges, countinedges, countoutedges, delete, findedge, graphof, listattributes, listedges, listinedges, listoutedges, nextedge, nextinedge, nextoutedge, queryattributes, set, setattributes, showname.
Edge methods are:

delete, graphof, headof, listattributes, listnodes, listheadnodes, listtailnodes, queryattributes, set, setattributes, showname, tailof.

Also, if a graph, node or edge has an attributeName that begins with '_' then the attributeName is accepted as a method somewhat like a method in an OO language. When the _attributeName is invoked then the attributeValue is interpreted as a script after first substituting and %g, %n, %e, or %a in the script with graphHandle, nodeHandle, edgeHandle, and arglist from the command. For example:

     set g [dgnew graph]
     set n [$g addnode]
     $n set _mymethod {puts "msg from %n: %a"}
     $n _mymethod hello world
when evaluated will print out:
     msg from dgN1: hello world

Common methods can be provided to all nodes, or edges, in a graph by use of:

    $g setnodeattribute _method {script...}
    $g setedgeattribute _method {script...}

Graph Commands

dgnew graphType ?graphName? ?attributeName attributeValue? ?...?

creates a new empty graph and returns its graphHandle.

graphType can be any of: "graph," "digraph," "strictgraph," or "strictdigraph." (In digraphs edges have a direction from tail to head. "Strict" graphs or digraphs collapse multiple edges between the same pair of nodes into a single edge, and disallow self-edges.)

Following the mandatory graphType parameter the dgnew command will accept an optional name for the graph and an arbitrary number of attribute name/value pairs. In Tcldgr (unlike tcldot) there are no predifined attributes, so the script programmer can freely use attributes for the application. e.g.

    set g [dgnew digraph G author "John Ellson"]
dgread fileHandle

reads in a dot-language description of a graph from a previously opened file identified by the fileHandle. The command returns the graphHandle of the newly read graph. e.g.

    
    set f [open test.dot r]
    set g [dgread $f]
dgstring string

accepts a dot-language string description of a graph. The command returns the graphHandle of the newly read graph. e.g.

    
    set s "digraph G {a->b}"
    set g [dgstring $s]
graphHandle addnode ?nodeName? ?attributeName attributeValue? ?...?

creates a new node in the graph whose handle is graphHandle and returns its nodeHandle. The handle of a node is a string like: "dgN0" where the integer value is different for each node. An optional name may be provided for the node, followed by an arbitrary number of attribute name/value pairs. e.g.

    
    set n [$g addnode "N" label "Top\nNode" ]
Execution of addnode will have the side effect of also executing any scripts that have been attached to the insert_node event by the bind method on the graph.

A possible cause of confusion in Tcldgr is the distinction between handles, names, labels, and variables. The distinction is primarily in who owns them. Handles are owned by Tcldgr and are guaranteed to be unique within one interpreter session. Typically handles are assigned to variables, like "n" above, for manipulation within a tcl script. Variables are owned by the programmer. Names are owned by the application that is using the graph, typically names are important when reading in a graph from an external program or file. Labels are the text that is displayed with the node (or edge) when the graph is displayed, labels are meaningful to the reader of the graph. Only the handles and variables are essential to Tcldgr's ability to manipulate abstract graphs. If a name is not specified then it defaults to a "%<num>" form where <num> is the numeric part of the handle. Unlike tcldot, labels are no longer specifically provided for, but it is probably a good idea to continue to use the attributName "label" so that dot files can be interpreted by the older tools..

graphHandle addedge tailNode headNode ?edgeName? ?attributeName attributeValue? ?...?
nodeHandle addedge headNode ?edgeName? ?attributeName attributeValue? ?...?

creates a new edge and returns its edgeHandle. The tailNode and headNode can be specified either by their nodeHandle or by their nodeName e.g.

    set n [$g addnode]
    set m [$g addnode M]
    set p [$g addnode]
    $g addedge $n M myedge label "NM"
    $p addedge M label "PM"
    $p addedge $n
The tailNode and headNode parameters are recognized as handles in preference to names, so it is best to avoid names like "dgN6" for nodes. If there is potential for conflict then use findnode which gives preference to names over handles instead. e.g.
    $g addnode "dgN6"
    $g addnode "dgN99"
    $g addedge [$g findnode "dgN6"] [$g findnode "dgN99"]
An optional name may be provided for the edge, followed by an arbitrary number of attribute name/value pairs.

Execution of addedge will have the side effect of also executing any scripts that have been attached to the insert_edge event by the bind method on the graph.

graphHandle addsubgraph ?graphName? ?attributeName attributeValue? ?...?

creates a new subgraph in the graph and returns its graphHandle. If the graphName is omitted then the name of the subgraph defaults to it's graphHandle. There can be an arbitrary number of attribute name/value pairs for the subgraph. e.g.

    
    set sg [$g addsubgraph]

Execution of addsubgraph will have the side effect of also executing any scripts that have been attached to the insert_graph event by the bind method on the graph.

graphHandle batch boolean

When set, batches up all events in a buffer until cleared. Initially batch is cleared so that events immediately invoke any scripts that have been attached with "bind".

Some operations on the graph may result in multiple events, and so it is useful to be able to bracket the set of events generated by a single input action. To support this, all events (even singletons) reported by a graph are surrounded by "batch 1" ... "batch 0" events. These batch events can themselves be bound (see next section). If the batch command is used then the interval of the batched is enlarged to the interval of the commanded batching, thus allowing the user to define larger atomic transactions.

graphHandle bind graphEvent ?+??script?

attaches a script to be executed whenever a specified event occurs. graphEvent can be any one of:


batch    %g %a
insert_graph    %g
insert_node    %g %n
insert_edge    %g %t %e %h
modify_graph    %g %n %e %A %a
modify_node    %g %n %A %a
modify_edge    %g %e %A %a
delete_graph    %g
delete_node    %g %n
delete_edge    %g %e

Where the substitutions are:


%g    the graph handle
%n    the node handle (or tail node handle)
   or "node" when modify_graph reports node attribute creation
%t    tail node handle (%t is an alias for %n)
%e    the edge handle
   or "edge" when modify_graph reports edge attribute creation
%h    head node handle (%h is an alias for %A)
%A    the attribute name (or head node handle)
%a    the attribute value ("0" or "1" for batch bindings)

If the script parameter starts with a "+" then the binding is appended to any existing binding on the event, otherwise the binding replaces any existing binding. Bindings can be deleted by use of a zero length script string.

Debugging hint: To set up bindings to all possible events and parameters from a graph you can use:

    foreach b [$g bind] {$g bind $b "+puts \"%g $b %n %e %A %a\""}

graphHandle countnodes
graphHandle countedges

Returns the number of nodes, or edges, in the graph.

nodeHandle countedges
nodeHandle countinedges
nodeHandle countoutedges

Returns the number of edges at a node.

graphHandle concatfile fileHandle
graphHandle concatstring dot_language_string

Reads in a dot file from an open fileHandle, or from a string, and concatenates the graph to any existing graph in graphHandle.

(This mechanism was introduced so that event bindings could be established on an empty graph before the file was read in, so that the callbacks occur for the contents of the file. It is not clear that concatenating a graph to a non-empty graph produces intuitively predictable results.)

graphHandle delete
nodeHandle delete
edgeHandle delete

Delete all data structures associated with the graph, node, edge from the internal storage of the interpreter. Deletion of a node also results in the deletion of all subtending edges on that node. Deletion of a graph also results in the deletion of all nodes edges and subgraphs within that graph.

Execution of graph, node or edge delete will have the side effect of also executing any scripts that have been attached to the delete_graph, delete_node, delete_edge events by the bind method on the graph.

graphHandle findnode nodeName
graphHandle findedge tailnodeName headNodeName
nodeHandle findedge nodeName

Each return the handle of the item if found, or an error if none are found. For non-strict graphs when there are multiple edges between two nodes findedge will return an arbitrary edge from the set. Name parameters to the find method can be either names or handles, but priority is given to a name interpretation.

graphHandle graphof
nodeHandle graphof
edgeHandle graphof

Returns the handle of the root graph which contains the graph, subgraph, node, or edge.

edgeHandle headof

(Synonym for listheadnodes.)

graphHandle listattributes ?attributeNamePattern?
nodeHandle listattributes ?attributeNamePattern?
edgeHandle listattributes ?attributeNamePattern?

Return a list of attribute names (attribute values are provided by queryattribute). If an attributeNamePattern is specified then only those attributeNames that match the pattern are returned. The pattern can contain "*?[]" as in Tcl's string match command.

graphHandle listnodes ?attributeName attributeValuePattern? ?...?
graphHandle listedges ?attributeName attributeValuePattern? ?...?
graphHandle listsubgraphs ?attributeName attributeValuePattern? ?...?
nodeHandle listedges ?attributeName attributeValuePattern? ?...?
nodeHandle listinedges ?attributeName attributeValuePattern? ?...?
nodeHandle listoutedges ?attributeName attributeValuePattern? ?...?
edgeHandle listnodes ?attributeName attributeValuePattern? ?...?
edgeHandle listheadnodes ?attributeName attributeValuePattern? ?...?
edgeHandle listtailnodes ?attributeName attributeValuePattern? ?...?

Each return a list of handles of nodes, edges, or subgraphs, as appropriate. If an attributeName and attributeValuePattern pairs are specified then only those objects whose attributeValue match all of them are returned. The pattern matching supports "*?[]" as in Tcl's string match command.

graphHandle nextedge ?edgeHandle? ?attributeName attributeValuePattern? ?...?
graphHandle nextnode ?nodeHandle? ?attributeName attributeValuePattern? ?...?
nodeHandle nextedge ?edgeHandle? ?attributeName attributeValuePattern? ?...?
nodeHandle nextinedge ?edgeHandle? ?attributeName attributeValuePattern? ?...?
nodeHandle nextoutedge ?edgeHandle? ?attributeName attributeValuePattern? ?...?

Provide an iteration through nodes or edges. Returns the handle of the "next" node or edge that follows the one identified in first parameter that matches the attribute/value patterns. If the first parameter is omitted then it returns the first node or edge that matches the attribute/value patterns. The pattern matching supports "*?[]" as in Tcl's string match command.

graphHandle parentgraph

If the graph is a subgraph the this method returns the handle of its parent graph. If the graph is the root graph then this method returns a null string. (See also: graphof)

graphHandle queryattributes attributeName ?...?
nodeHandle queryattributes attributeName ?...?
edgeHandle queryattributes attributeName ?...?

Return a list of attribute values, one value for each of the attribute names provided with the method. (See also the set method which can be used to query a single attribute without returning the value in a list.)

graphHandle showname
nodeHandle showname
edgeHandle showname

Each return the name of the graph, node, or edge. Edge names are of the form: "a->b" where "a" and "b" are the names of the nodes and the connector "->" indicates the tail-to-head direction of the edge. In undirected graphs the connector "--" is used.

graphHandle set attributeName ?attributeValue?
nodeHandle set attributeName ?attributeValue?
edgeHandle set attributeName ?attributeValue?

Set, or query, (in the style of Tcl's set) one attribute name/value pair for a specific graph, node, or edge instance.

Attributes whose attributeName starts with the character '_' can be used to extend the method set of graphs, nodes or edges by evaluating the as a script after first substituting %g %n %e %a with graphHandle, nodeHandle, edgeHandle and arglist.

Execution of set with a new value, i.e. a string value different from the current value, will have the side effect of also executing any scripts that have been attached to the modify_graph, modify_node, or modify_edge events by the bind method on the graph. Note that this is different from setattributes which will execute scripts when a new value is written regardless of whether its string value has changed.

graphHandle setnodeattributes attributeName attributeValue ?...?
graphHandle setedgeattributes attributeName attributeValue ?...?

Set one or more default attribute name/values that are to apply to all subsequent nodes, or edges unless overridden.

Attributes whose attributeName starts with the charater '_' can be used to extend the method set of nodes or edges by evaluating the as a script after first substituting %g %n %e %a with graphHandle, nodeHandle, edgeHandle and arglist.

Execution of setnodeattributes, or setedgeattributes, will have the side effect of also executing any scripts that have been attached to the modify_node, or modify_edge events by the bind method on the graph.

graphHandle setattributes attributeName attributeValue ?...?
nodeHandle setattributes attributeName attributeValue ?...?
edgeHandle setattributes attributeName attributeValue ?...?

Set one or more attribute name/value pairs for a specific graph, node, or edge instance.

Attributes whose attributeName starts with the charater '_' can be used to extend the method set of graphs, nodes or edges by evaluating the as a script after first substituting %g %n %e %a with graphHandle, nodeHandle, edgeHandle and arglist.

Execution of setattributes, will have the side effect of also executing any scripts that have been attached to the modify_graph, modify_node, or modify_edge events by the bind method on the graph.

(The only real advantage of setattributes over set is that it allows multiple attributes to be set in a single atomic action. The other difference is that the bindings will be executed even if the string value of the attribute is the same as before.)

edgeHandle tailof

(Synonym for listtailnodes.)

graphHandle write ?fileHandle?

Write a graph in the dot_language to the open file represented by fileHandle or, if fileHandle is omitted, then return the dot-language result as a string.

Bugs

This man page is impossible to comprehend in a single reading.

It would be useful to be able to delete individual parts of a binding that was built from "+" appended parts.

It probably should be modified to use Tcl_Obj in tcl8.0 and later.

Author

John Ellson, Lucent Technologies, Holmdel, NJ. (ellson@lucent.com)

Acknowledgements

John Ousterhout, of course, for tcl and tk. Steven North and Eleftherios Koutsofios for dot, libgraph and libincr. Karl Lehenbauer and Mark Diekhans of NeoSoft for the dghandles.c code which was derived from tclXhandles.c.

Keywords

Tcldgr, graph, tcl, tk, dot, tcldot, graphviz.


Table of Contents