1struct::graph v1(n) Tcl Data Structures struct::graph v1(n)
2______________________________________________________________________________
6
8 struct::graph v1 - Create and manipulate directed graph objects
9
11 package require Tcl 8.2
12 package require struct::graph ?1.2.1?
14 graphName option ?arg arg ...?
16 graphName destroy
18 graphName arc append arc ?-key key? value
20 graphName arc delete arc ?arc ...?
22 graphName arc exists arc
24 graphName arc get arc ?-key key?
26 graphName arc getall arc
28 graphName arc keys arc
30 graphName arc keyexists arc ?-key key?
32 graphName arc insert start end ?child?
34 graphName arc lappend arc ?-key key? value
36 graphName arc set arc ?-key key? ?value?
38 graphName arc source arc
40 graphName arc target arc
42 graphName arc unset arc ?-key key?
44 graphName arcs ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embed‐
46 ding nodelist?
47 graphName node append node ?-key key? value
49 graphName node degree ?-in|-out? node
51 graphName node delete node ?node ...?
53 graphName node exists node
55 graphName node get node ?-key key?
57 graphName node getall node
59 graphName node keys node
61 graphName node keyexists node ?-key key?
63 graphName node insert ?child?
65 graphName node lappend node ?-key key? value
67 graphName node opposite node arc
69 graphName node set node ?-key key? ?value?
71 graphName node unset node ?-key key?
73 graphName nodes ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embed‐
75 ding nodelist?
76 graphName get ?-key key?
78 graphName getall
80 graphName keys
82 graphName keyexists ?-key key?
84 graphName set ?-key key? ?value?
86 graphName swap node1 node2
88 graphName unset ?-key key?
90 graphName walk node ?-order order? ?-type type? ?-dir direction? -com‐
92 mand cmd
93_________________________________________________________________
95
97 The ::struct::graph command creates a new graph object with an associ‐
98 ated global Tcl command whose name is graphName. This command may be
99 used to invoke various operations on the graph. It has the following
100 general form:
101 graphName option ?arg arg ...?
103 Option and the args determine the exact behavior of the command.
104 Note: A C-implementation of the command can be had from the location
106 http://www.purl.org/NET/schlenker/tcl/cgraph. See also
107 http://wiki.tcl.tk/cgraph. This implementation uses a bit less memory
108 than the tcl version provided here directly, and is faster.
109 A directed graph is a structure containing two collections of elements,
111 called nodes and arcs respectively, together with a relation ("connec‐
112 tivity") that places a general structure upon the nodes and arcs.
113 Each arc is connected to two nodes, one of which is called the source
115 and the other the target. This imposes a direction upon the arc, which
116 is said to go from the source to the target. It is allowed that source
117 and target of an arc are the same node. Such an arc is called a loop.
118 Whenever a node is source or target of an arc both are said to be adja‐
119 cent. This extends into a relation between nodes, i.e. if two nodes are
120 connected through at least one arc they are said to be adjacent too.
121 Each node can be the source and target for any number of arcs. The for‐
123 mer are called the outgoing arcs of the node, the latter the incoming
124 arcs of the node. The number of edges in either set is called the in-
125 resp. the out-degree of the node.
126 In addition to maintaining the node and arc relationships, this graph
128 implementation allows any number of keyed values to be associated with
129 each node and arc.
130 The following commands are possible for graph objects:
132 graphName destroy
134 Destroy the graph, including its storage space and associated
135 command.
136 graphName arc append arc ?-key key? value
138 Appends a value to one of the keyed values associated with an
139 arc. If no key is specified, the key data is assumed.
140 graphName arc delete arc ?arc ...?
142 Remove the specified arcs from the graph.
143 graphName arc exists arc
145 Return true if the specified arc exists in the graph.
146 graphName arc get arc ?-key key?
148 Return the value associated with the key key for the arc. If no
149 key is specified, the key data is assumed.
150 graphName arc getall arc
152 Returns a serialized list of key/value pairs (suitable for use
153 with [array set]) for the arc.
154 graphName arc keys arc
156 Returns a list of keys for the arc.
157 graphName arc keyexists arc ?-key key?
159 Return true if the specified key exists for the arc. If no key
160 is specified, the key data is assumed.
161 graphName arc insert start end ?child?
163 Insert an arc named child into the graph beginning at the node
164 start and ending at the node end. If the name of the new arc is
165 not specified the system will generate a unique name of the form
166 arcx.
167 graphName arc lappend arc ?-key key? value
169 Appends a value (as a list) to one of the keyed values associ‐
170 ated with an arc. If no key is specified, the key data is
171 assumed.
172 graphName arc set arc ?-key key? ?value?
174 Set or get one of the keyed values associated with an arc. If
175 no key is specified, the key data is assumed. Each arc that is
176 added to a graph has the empty string assigned to the key data
177 automatically. An arc may have any number of keyed values asso‐
178 ciated with it. If value is not specified, this command returns
179 the current value assigned to the key; if value is specified,
180 this command assigns that value to the key.
181 graphName arc source arc
183 Return the node the given arc begins at.
184 graphName arc target arc
186 Return the node the given arc ends at.
187 graphName arc unset arc ?-key key?
189 Remove a keyed value from the arc arc. If no key is specified,
190 the key data is assumed.
191 graphName arcs ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embed‐
193 ding nodelist?
194 Return a list of arcs in the graph. If no restriction is speci‐
195 fied a list containing all arcs is returned. Restrictions can
196 limit the list of returned arcs based on the nodes that are con‐
197 nected by the arc, on the keyed values associated with the arc,
198 or both. The restrictions that involve connected nodes have a
199 list of nodes as argument, specified after the name of the
200 restriction itself.
201 -in Return a list of all arcs whose target is one of the
203 nodes in the nodelist.
204 -out Return a list of all arcs whose source is one of the
206 nodes in the nodelist.
207 -adj Return a list of all arcs adjacent to at least one of the
209 nodes in the nodelist. This is the union of the nodes
210 returned by -in and -out.
211 -inner Return a list of all arcs adjacent to two of the nodes in
213 the nodelist. This is the set of arcs in the subgraph
214 spawned by the specified nodes.
215 -embedding
217 Return a list of all arcs adjacent to exactly one of the
218 nodes in the nodelist. This is the set of arcs connecting
219 the subgraph spawned by the specified nodes to the rest
220 of the graph.
221 -key key
223 Limit the list of arcs that are returned to those arcs
224 that have an associated key key.
225 -value value
227 This restriction can only be used in combination with
228 -key. It limits the list of arcs that are returned to
229 those arcs whose associated key key has the value value.
230 The restrictions imposed by either -in, -out, -adj, -inner, or -embed‐
232 ded are applied first. Specifying more than one of them is illegal. At
233 last the restrictions set via -key (and -value) are applied. Specify‐
234 ing more than one -key (and -value) is illegal.
235 graphName node append node ?-key key? value
237 Appends a value to one of the keyed values associated with an
238 node. If no key is specified, the key data is assumed.
239 graphName node degree ?-in|-out? node
241 Return the number of arcs adjacent to the specified node. If one
242 of the restrictions -in or -out is given only the incoming resp.
243 outgoing arcs are counted.
244 graphName node delete node ?node ...?
246 Remove the specified nodes from the graph. All of the nodes'
247 arcs will be removed as well to prevent unconnected arcs.
248 graphName node exists node
250 Return true if the specified node exists in the graph.
251 graphName node get node ?-key key?
253 Return the value associated with the key key for the node. If
254 no key is specified, the key data is assumed.
255 graphName node getall node
257 Returns a serialized list of key/value pairs (suitable for use
258 with [array set]) for the node.
259 graphName node keys node
261 Returns a list of keys for the node.
262 graphName node keyexists node ?-key key?
264 Return true if the specified key exists for the node. If no key
265 is specified, the key data is assumed.
266 graphName node insert ?child?
268 Insert a node named child into the graph. The nodes has no arcs
269 connected to it. If the name of the new child is not specified
270 the system will generate a unique name of the form nodex.
271 graphName node lappend node ?-key key? value
273 Appends a value (as a list) to one of the keyed values associ‐
274 ated with an node. If no key is specified, the key data is
275 assumed.
276 graphName node opposite node arc
278 Return the node at the other end of the specified arc, which has
279 to be adjacent to the given node.
280 graphName node set node ?-key key? ?value?
282 Set or get one of the keyed values associated with a node. If
283 no key is specified, the key data is assumed. Each node that is
284 added to a graph has the empty string assigned to the key data
285 automatically. A node may have any number of keyed values asso‐
286 ciated with it. If value is not specified, this command returns
287 the current value assigned to the key; if value is specified,
288 this command assigns that value to the key.
289 graphName node unset node ?-key key?
291 Remove a keyed value from the node node. If no key is speci‐
292 fied, the key data is assumed.
293 graphName nodes ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embed‐
295 ding nodelist?
296 Return a list of nodes in the graph. Restrictions can limit the
297 list of returned nodes based on neighboring nodes, or based on
298 the keyed values associated with the node. The restrictions that
299 involve neighboring nodes have a list of nodes as argument,
300 specified after the name of the restriction itself.
301 The possible restrictions are the same as for method arcs. The
303 set of nodes to return is computed as the union of all source
304 and target nodes for all the arcs satisfying the restriction as
305 defined for arcs.
306 graphName get ?-key key?
308 Return the value associated with the key key for the graph. If
309 no key is specified, the key data is assumed.
310 graphName getall
312 Returns a serialized list of key/value pairs (suitable for use
313 with [array set]) for the whole graph.
314 graphName keys
316 Returns a list of keys for the whole graph.
317 graphName keyexists ?-key key?
319 Return true if the specified key exists for the whole graph. If
320 no key is specified, the key data is assumed.
321 graphName set ?-key key? ?value?
323 Set or get one of the keyed values associated with a graph. If
324 no key is specified, the key data is assumed. Each graph has the
325 empty string assigned to the key data automatically. A graph may
326 have any number of keyed values associated with it. If value is
327 not specified, this command returns the current value assigned
328 to the key; if value is specified, this command assigns that
329 value to the key.
330 graphName swap node1 node2
332 Swap the position of node1 and node2 in the graph.
333 graphName unset ?-key key?
335 Remove a keyed value from the graph. If no key is specified, the
336 key data is assumed.
337 graphName walk node ?-order order? ?-type type? ?-dir direction? -com‐
339 mand cmd
340 Perform a breadth-first or depth-first walk of the graph start‐
341 ing at the node node going in either the direction of outgoing
342 or opposite to the incoming arcs.
343 The type of walk, breadth-first or depth-first, is determined by
345 the value of type; bfs indicates breadth-first, dfs indicates
346 depth-first. Depth-first is the default.
347 The order of the walk, pre-order, post-order or both-order is
349 determined by the value of order; pre indicates pre-order, post
350 indicates post-order, both indicates both-order. Pre-order is
351 the default. Pre-order walking means that a node is visited
352 before any of its neighbors (as defined by the direction, see
353 below). Post-order walking means that a parent is visited after
354 any of its neighbors. Both-order walking means that a node is
355 visited before and after any of its neighbors. The combination
356 of a bread-first walk with post- or both-order is illegal.
357 The direction of the walk is determined by the value of dir;
359 backward indicates the direction opposite to the incoming arcs,
360 forward indicates the direction of the outgoing arcs.
361 As the walk progresses, the command cmd will be evaluated at
363 each node, with the mode of the call (enter or leave) and values
364 graphName and the name of the current node appended. For a pre-
365 order walk, all nodes are entered, for a post-order all nodes
366 are left. In a both-order walk the first visit of a node enters
367 it, the second visit leaves it.
368
370 cgraph, graph
371
373 Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
374struct 1.2.1 struct::graph v1(n)