Graphs

set g [graph]

The object returned from graph is both a handle for the graph and a Tcl command which is used to invoke operations on the graph. The syntax for graph operations is

$g command command(s) argument1 argument2 …

This is the same scheme as used in Tk, and mimicks object oriented behaviour. For example, the follwing commands create a directed graph, adds a single node and assigns the label "Hello, World" to the node:

set g [graph]
set n [$g create node]
$g set $n -x 100 -y 100 -label "Hello, World"

Undirected Graphs

A new graph is directed by default. To create an undirected graph, change the -directed attribute of the graph:

set g [graph]
$g set -directed false

Note: Graphs can be switched from directed to undirected or back at any time in a program.

Warning:Switching between directed and undirected graphs should be used with extreme caution in an interactive system. This because this may change the nature of on the graph. For example, a directed graph may be acyclic but its undirected equivalent is usually not. Worse, the user might not expect such a behaviour from your algorithm, and gets getting confused.

Nodes and Edges

New nodes and edges are created with the graph commands create node and create edge :

set source [$g create node]
set target [$g create node]
set n [$g create edge $source $target]

These commands return identifiers for the new node resp. new edge. Unlike graphs, nodes are not Tcl commands (this is for performance reason; also nodes and edges in GTL are not objects either).

Graphscript supports the graph commands new_node and new_edge as aliases for create node and create edge. These are modelled after the GTL graph methods.

configure, set and get

The graph commands configure, set and get manipulate attributes of graphs, nodes and edges. configure and set are modeled after Tk's configure. For example, to set the label of a graph, use

set g [graph]
$g configure -label "My Graph"

set g [graph]
$g set -label "My Graph"

puts [label $g get -label]

set label [$g configure -label]

{-label {Complete Graph}}

Furthermore, if the attribute is omitted, then configure returns a list of all attributes :

puts [$g configure]

{{-directed 1} {-id 42} {-label {}} ... }

Node and Edge Attributes

The graph commands configure, get and set can also manipulate the attributes of nodes and edges, as shown in the following example:

set source [$g create node]
$g set $source -label S
set target [$g create node]
$g set $target -label T
set edge [$graph create edge $source $target]
$g set $edge -label "[$graph get $source -label] -> [$graph get $target -label]"

Like most Graphscript commands, configure, get and set also accept lists of nodes and lists of edges. With that, we can change the attributes of a set of nodes :

$graph configure [list $source $target] -fill black

$graph configure [list $source $target $edge] -fill black

User defined Attributes

The graph commands configure, get and set can also manipulate user defined attributes:

$graph set .my_attribute 42
$graph set $node1 .country "Germany"
$graph set $node2 .country "USA"
$graph set $edge .distance 6000.0

User attributes must start with a dot (which is not part of the actual name of the attribute). They can be either integers, floating point numbers or strings. User attributes are automatically saved to and loded from GML files. The file associated with the above graph looks as follows:

Furthermore, configure may be used to return all user defined attributes in a list:

Source and Target

Edges have special attributes source and target which hold the source and target nodes, as in the following example :

set source [$graph get $edge -source]
set target [$graph get $edge -target]

source and target are (obviously) read only attributes. They are defined for both directed and undirected graphs. More precisely, if the graph is switched to a directed, then the nodes returned for -source and -target remain the same (or, vice versa, if a directed graph is switched to undirected).

Even in undirected graphs, the distinction between source and target nodes is often neccessary. For example, if an edge has bends, then the sequence of the points (bends) implies a distinction between start (source) and end (target) nodes.

In addition to source and target, the graph command nodes -edge returns the endpoints of an edge in a list. nodes -edge is more efficient than constructing a list of source and target nodes.

set endnodes [$graph nodes -edge $edge]
set source [lindex $endnodes 0]
set target [lindex $endnodes 1]

is more efficient than

set endnodes [list [$graph get $edge -source] [$graph get $edge -target]]
set source [lindex $endnodes 0]
set target [lindex $endnodes 1]

Finally, the graph command nodes -opposite returns the node at the opposite end of an edge, as in

set g [graph]
set e [$g create edge [$g create node] [$g create node]]
set s [$g get $e -source]
set t [$g get $e nodes -opposite $s $e]

Coordinates and Geometry

$graph set $node -x 100 -y 100

All coordinates in Graphscript are pixels. The size of a node is determined by the attributes -w and -h :

$graph configure $node -w 16 -h 16

Note: Not all graphic object types support the -w and -h attributes. More precisely, nodes of type bitmap, image or text do not accept width and height specifications, because the dimensions of these objects are intrinsically determined by the bitmap, image or text/font combination.

Edges are represented by polylines. A polyline is a list of coordinates, as in the following example:

set source [$graph create node]
set target [$graph create node]
$graph configure $source -x 100 -y 100
$graph configure $target -x 200 -y 200
set edge [$graph create edge]
$graph set $edge -line [list 100 100 100 200 200 200]

Polylines must have even length, and must consist of at least 4 coordinates (i.e. start and end point).

There is usually no need to set coordinates for straight line edges explicitly. Graphscript will automatically calculate coordinates for the endpoints when neccessary. See the sections on anchors and ports for details on how Graphscript determines adjusts the endpoints of edges.

Graphics

Each graph, node and edge has two sets of graphics attributes associated with it, graphics and label_graphics. Again, the configure, get and set commands are used to access the graphical attributes :

set node [$graph create node]
$graph configure $node graphics -fill red
$graph configure $node label_graphics -fill white

The above example creates a red node with a blue label. -fill specifies the color with which an object is filled (as opposed to -outline, which is the color of the border of an object). Other common attributes include -type, which specifies the shape of an object, and -width which sets line or border width. The attribute -width is often combined with -fill to make an object catch the user's attention :

set edges [maximum_bipartite_matching $graph]
$graph configure $edges graphics -fill blue -width 3

The keyword graphics is optional. That is, -x is a shortcut for graphics -x.

Types

Graphlet's graphics -type attribute is modelled after Tk's canvas item types. Nodes may have one of arc, bitmap, line, image, polygon, oval, rectangle or text (that is, all Tk canvas item types except window). Edges are always of type line, and labels of type text. The default type for nodes is rectangle. The following code creates an odd shaped oval green node :

set node [$graph create node]
$graph configure $node graphics \
    -type oval \
    -x 100 -y 100 -w 7 -h 39 \
    -fill green -outline green

Unlike in Tk canvases, the type of an object can be changed dynamically. That is, a node may be a rectangle first and become a circle (oval) later.

set node [$graph create node]
$graph configure $node -type rectangle -w 16 -h 16
...
$graph configure $node -type oval

Note: not all attributes apply to all types of graphics objects. See the graphlet attribute compendium for a complete listing of attributes.

Anchors

Ports

Ports can be used to finetune the endpoints of edges. A port is a named location inside an edge to which edges may be attached:

The attribute -ports assigns a list of ports to a node. Each port conists of a name and x- and y-coordinates relative to the center of the node. The coordinates must be in a range [-1…1,-1…1]. Each edge may have a source port (-source_port)) and a target port (-target_port), which must be the name of a port at the respective node.

If no ports are specified (which is the default), then edges are routed according their anchors, and towards the center of the source or target node otherwise.

Iterating Through Nodes and Edges

The standard method in Tcl to iterate through a data structure is the foreach loop. Graphscript uses foreach to iterate through nodes and edges in a graph. The graph command nodes returns the list of nodes of a graph. In the following example, we assign consecutive numbers all nodes in a graph :

proc number {graph} {
    set n 0
    foreach node [$graph nodes] {
        $graph set $node -label [incr n]
    }
}

Similarly, the graph command edges returns the list of all edges of a graph. The following example labels all edges with a string "source-target" :

proc label_edges {graph} {
    foreach edge [$graph edges] {
        set s [$graph get [$graph get $edge -source] -label]
        set t [$graph get [$graph get $edge -target] -label]
        $graph set $node -label $s-$t
    }
}

Adjacent Nodes and Edges

The graph commands nodes and edges take several options which select a subset of the nodes and edges in the graph. For example, edges -adj n selects the edges that are adjacent to a node n :

proc degree {graph n} {
    return [llength [$graph edges -adj $n]]
}

The nodes command takes an identical option -adj. $graph nodes -adj $node returns all neighbors of a node:

proc degree1 {graph n} {
    return [llength [$graph nodes -adj $n]]
}

Furthermore, like most graph commands, nodes and edges can take lists of nodes or edges as parameters. The following example fills all nodes that are adjacent to a subgraph (given by a list of nodes) with black ink. This is more efficient and easier to write than a foreach loop.

proc show_neighbours {graph subgraph_nodes} {
    $graph set [$graph nodes -adj $subgraph_nodes] \
        -fill black
}

Incoming And Outgoing Edges

The commands nodes -adj and edges -adj work for both directed and undirected graphs. More precisely, edges -adj returns all incoming and outgoing edges in a directed graph. The graph commands edges -in and edges -out select incoming and outgoing edges :

array set color {
    in red
    out green
}

foreach edge [$graph edges $node -in] {
    $graph set $edge -fill $color(in)
}
foreach edge [$graph edges $node -out] {
    $graph set $edge -fill $color(out)
}

array set color {
    in red
    out green
}

foreach node [$graph nodes $node -in] {
    $graph set $node -fill $color(in)
}
foreach node [$graph nodes $node -out] {
    $graph set $node -fill $color(out)
}

Note: The options -in and -out are only valid for directed graphs; they return empty lists when used with undirected graphs.

Inner and outer Edges

The graph command command edges -adj $nodes returns the list of all edges adjacent to nodes. However, this is not the set of edges in the subgraph that is spawned by nodes. The graph command edges provides additional options -inner and -embedding to select edges within the spawned subgraph, an to select edges that connect the subgraph with the rest. edges -inner selects all edges between nodes of nodes. edges -embedding selects all edges to nodes with one endpoint in nodes and the other endpoint not in nodes.

foreach edge [$graph edges -inner $subgraph] {
    $graph set $edge -fill blue
}
foreach edge [$graph edges -embedding $subgraph] {
    $graph set $edge -fill green
}

Drawing Graphs

Graphlet's redrawing policy is simple: all graph commands, including configure and set do never update the on-screen graph. Instead, the programmer must redraw the graph explicitly with the command draw. The following example sets all node sizes to 16x16 and draws the graph :

foreach node [$g nodes] {
    $g configure $node -w 16 -h 16
}

$g draw

This strategy was chosen to avoid unneccessary drawing operations. For example, a two pass algorithm might move a node in x direction in the first pass, and in y direction in the second pass. Or, both endpoints of a node are moved separately. In both cases, immediate drawing would lead to an excessive amount of surplus drawing operations.

$graph draw [concat $changed_nodes $changed_edges]

This should be used only with large graphs and with exact knowledge which nodes and edges are changed. Otherwise, the overhead for checking which nodes and edges need to be redrawn is neglectible.