 |
ActiveTcl User Guide
|
 |
|
[ Main table Of Contents | Tcllib Table Of Contents | Tcllib Index ]
graph(n) 1.2.1 "Tcl Data Structures"
graph - Create and manipulate directed graph objects
package require Tcl 8.2
package require struct ?1.3?
The ::struct::graph command creates a new
graph object with an associated global Tcl command whose name is graphName. This command may be used to invoke
various operations on the graph. It has the following general
form:
- graphName option ?arg arg ...?
- Option and the args
determine the exact behavior of the command.
Note: A C-implementation of the command can be had from
the location http://www.purl.org/NET/schlenker/tcl/cgraph.
See also http://wiki.tcl.tk/cgraph. This
implementation uses a bit less memory than the tcl version provided
here directly, and is faster.
A directed graph is a structure containing two collections of
elements, called nodes and arcs respectively,
together with a relation ("connectivity") that places a general
structure upon the nodes and arcs.
Each arc is connected to two nodes, one of which is called the
source and the other the target. This imposes a
direction upon the arc, which is said to go from the source to the
target. It is allowed that source and target of an arc are the same
node. Such an arc is called a loop. Whenever a node is
source or target of an arc both are said to be adjacent.
This extends into a relation between nodes, i.e. if two nodes are
connected through at least one arc they are said to be
adjacent too.
Each node can be the source and target for any number of arcs.
The former are called the outgoing arcs of the node, the
latter the incoming arcs of the node. The number of edges
in either set is called the in- resp. the
out-degree of the node.
In addition to maintaining the node and arc relationships, this
graph implementation allows any number of keyed values to be
associated with each node and arc.
The following commands are possible for graph objects:
- graphName
destroy
- Destroy the graph, including its storage space and associated
command.
- graphName arc
append arc ?-key key? value
- Appends a value to one of the keyed values
associated with an arc. If no key is specified, the key data is
assumed.
- graphName arc
delete arc ?arc
...?
- Remove the specified arcs from the graph.
- graphName arc
exists arc
- Return true if the specified arc exists in
the graph.
- graphName arc
get arc ?-key key?
- Return the value associated with the key key
for the arc. If no key is specified, the key
data is assumed.
- graphName arc
getall arc
- Returns a serialized list of key/value pairs (suitable for use
with [array set]) for the arc.
- graphName arc
keys arc
- Returns a list of keys for the arc.
- graphName arc
keyexists arc ?-key key?
- Return true if the specified key exists for
the arc. If no key is
specified, the key data is assumed.
- graphName arc
insert start end ?child?
- Insert an arc named child into the graph
beginning at the node start and ending at the
node end. If the name of the new arc is not
specified the system will generate a unique name of the form
arcx.
- graphName arc
lappend arc ?-key key? value
- Appends a value (as a list) to one of the
keyed values associated with an arc. If no key is specified, the key data is
assumed.
- graphName arc
set arc ?-key key?
?value?
- Set or get one of the keyed values associated with an arc. If
no key is specified, the key data is assumed. Each
arc that is added to a graph has the empty string assigned to the
key data automatically. An arc may have any number
of keyed values associated with it. If value is
not specified, this command returns the current value assigned to
the key; if value is specified, this command
assigns that value to the key.
- graphName arc
source arc
- Return the node the given arc begins at.
- graphName arc
target arc
- Return the node the given arc ends at.
- graphName arc
unset arc ?-key key?
- Remove a keyed value from the arc arc. If no
key is specified, the key data is assumed.
- graphName arcs
?-key key? ?-value value?
?-in|-out|-adj|-inner|-embedding nodelist?
- Return a list of arcs in the graph. If no restriction is
specified a list containing all arcs is returned. Restrictions can
limit the list of returned arcs based on the nodes that are
connected by the arc, on the keyed values associated with the arc,
or both. The restrictions that involve connected nodes have a list
of nodes as argument, specified after the name of the restriction
itself.
- -in
- Return a list of all arcs whose target is one of the nodes in
the nodelist.
- -out
- Return a list of all arcs whose source is one of the nodes in
the nodelist.
- -adj
- Return a list of all arcs adjacent to at least one of the nodes
in the nodelist. This is the union of the nodes
returned by -in and -out.
- -inner
- Return a list of all arcs adjacent to two of the nodes in the
nodelist. This is the set of arcs in the
subgraph spawned by the specified nodes.
- -embedding
- Return a list of all arcs adjacent to exactly one of the nodes
in the nodelist. This is the set of arcs
connecting the subgraph spawned by the specified nodes to the rest
of the graph.
- -key key
- Limit the list of arcs that are returned to those arcs that
have an associated key key.
- -value value
- This restriction can only be used in combination with
-key. It limits the list of arcs that are returned
to those arcs whose associated key key has the
value value.
- graphName node
append node ?-key key? value
- Appends a value to one of the keyed values
associated with an node. If no key is specified, the key data is
assumed.
- graphName node
degree ?-in|-out? node
- Return the number of arcs adjacent to the specified node. If one of the restrictions -in or
-out is given only the incoming resp. outgoing
arcs are counted.
- graphName node
delete node ?node
...?
- Remove the specified nodes from the graph. All of the nodes'
arcs will be removed as well to prevent unconnected arcs.
- graphName node
exists node
- Return true if the specified node exists in
the graph.
- graphName node
get node ?-key key?
- Return the value associated with the key key
for the node. If no key is specified, the key
data is assumed.
- graphName node
getall node
- Returns a serialized list of key/value pairs (suitable for use
with [array set]) for the node.
- graphName node
keys node
- Returns a list of keys for the node.
- graphName node
keyexists node ?-key key?
- Return true if the specified key exists for
the node. If no key is
specified, the key data is assumed.
- graphName node
insert ?child?
- Insert a node named child into the graph.
The nodes has no arcs connected to it. If the name of the new child
is not specified the system will generate a unique name of the form
nodex.
- graphName node
lappend node ?-key key? value
- Appends a value (as a list) to one of the
keyed values associated with an node. If no key is specified, the key data is
assumed.
- graphName node
opposite node arc
- Return the node at the other end of the specified arc, which has to be adjacent to the given node.
- graphName node
set node ?-key key?
?value?
- Set or get one of the keyed values associated with a node. If
no key is specified, the key data is assumed. Each
node that is added to a graph has the empty string assigned to the
key data automatically. A node may have any number
of keyed values associated with it. If value is
not specified, this command returns the current value assigned to
the key; if value is specified, this command
assigns that value to the key.
- graphName node
unset node ?-key key?
- Remove a keyed value from the node node. If
no key is specified, the key data is assumed.
- graphName
nodes ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embedding nodelist?
- Return a list of nodes in the graph. Restrictions can limit the
list of returned nodes based on neighboring nodes, or based on the
keyed values associated with the node. The restrictions that
involve neighboring nodes have a list of nodes as argument,
specified after the name of the restriction itself.
The possible restrictions are the same as for method
arcs. The set of nodes to return is computed as
the union of all source and target nodes for all the arcs
satisfying the restriction as defined for
arcs.
- graphName get
?-key key?
- Return the value associated with the key key
for the graph. If no key is specified, the key
data is assumed.
- graphName
getall
- Returns a serialized list of key/value pairs (suitable for use
with [array set]) for the whole graph.
- graphName
keys
- Returns a list of keys for the whole graph.
- graphName
keyexists ?-key key?
- Return true if the specified key exists for
the whole graph. If no key is specified, the key
data is assumed.
- graphName set
?-key key? ?value?
- Set or get one of the keyed values associated with a graph. If
no key is specified, the key data is assumed. Each
graph has the empty string assigned to the key
data automatically. A graph may have any number of
keyed values associated with it. If value is not
specified, this command returns the current value assigned to the
key; if value is specified, this command assigns
that value to the key.
- graphName swap
node1 node2
- Swap the position of node1 and node2 in the graph.
- graphName
unset ?-key key?
- Remove a keyed value from the graph. If no key is specified,
the key data is assumed.
- graphName walk
node ?-order order? ?-type type? ?-dir direction? -command
cmd
- Perform a breadth-first or depth-first walk of the graph
starting at the node node going in either the
direction of outgoing or opposite to the incoming arcs.
The type of walk, breadth-first or depth-first, is determined by
the value of type; bfs
indicates breadth-first, dfs indicates
depth-first. Depth-first is the default.
The order of the walk, pre-order, post-order or both-order is
determined by the value of order;
pre indicates pre-order, post
indicates post-order, both indicates both-order.
Pre-order is the default. Pre-order walking means that a node is
visited before any of its neighbors (as defined by the direction, see below). Post-order walking means that a
parent is visited after any of its neighbors. Both-order walking
means that a node is visited before and after any of its
neighbors. The combination of a bread-first walk with post- or
both-order is illegal.
The direction of the walk is determined by the value of dir; backward indicates the direction
opposite to the incoming arcs, forward indicates
the direction of the outgoing arcs.
As the walk progresses, the command cmd will be
evaluated at each node, with the mode of the call
(enter or leave) and values graphName and the name of the current node
appended. For a pre-order walk, all nodes are
entered, for a post-order all nodes are left. In a
both-order walk the first visit of a node enters
it, the second visit leaves it.
cgraph , graph
Copyright © 2002 Andreas Kupries
<andreas_kupries@users.sourceforge.net>