1struct::graph_v1(n)           Tcl Data Structures          struct::graph_v1(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       struct::graph_v1 - Create and manipulate directed graph objects
9

SYNOPSIS

11       package require Tcl  8.2
12
13       package require struct::graph  ?1.2.1?
14
15       graphName option ?arg arg ...?
16
17       graphName destroy
18
19       graphName arc append arc ?-key key? value
20
21       graphName arc delete arc ?arc ...?
22
23       graphName arc exists arc
24
25       graphName arc get arc ?-key key?
26
27       graphName arc getall arc
28
29       graphName arc keys arc
30
31       graphName arc keyexists arc ?-key key?
32
33       graphName arc insert start end ?child?
34
35       graphName arc lappend arc ?-key key? value
36
37       graphName arc set arc ?-key key? ?value?
38
39       graphName arc source arc
40
41       graphName arc target arc
42
43       graphName arc unset arc ?-key key?
44
45       graphName  arcs ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embed‐
46       ding nodelist?
47
48       graphName node append node ?-key key? value
49
50       graphName node degree ?-in|-out? node
51
52       graphName node delete node ?node ...?
53
54       graphName node exists node
55
56       graphName node get node ?-key key?
57
58       graphName node getall node
59
60       graphName node keys node
61
62       graphName node keyexists node ?-key key?
63
64       graphName node insert ?child?
65
66       graphName node lappend node ?-key key? value
67
68       graphName node opposite node arc
69
70       graphName node set node ?-key key? ?value?
71
72       graphName node unset node ?-key key?
73
74       graphName nodes ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embed‐
75       ding nodelist?
76
77       graphName get ?-key key?
78
79       graphName getall
80
81       graphName keys
82
83       graphName keyexists ?-key key?
84
85       graphName set ?-key key? ?value?
86
87       graphName swap node1 node2
88
89       graphName unset ?-key key?
90
91       graphName  walk node ?-order order? ?-type type? ?-dir direction? -com‐
92       mand cmd
93
94______________________________________________________________________________
95

DESCRIPTION

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
102       graphName option ?arg arg ...?
103              Option and the args determine the exact behavior of the command.
104
105       A directed graph is a structure containing two collections of elements,
106       called nodes and arcs respectively, together with a relation  ("connec‐
107       tivity") that places a general structure upon the nodes and arcs.
108
109       Each  arc  is connected to two nodes, one of which is called the source
110       and the other the target. This imposes a direction upon the arc,  which
111       is  said to go from the source to the target. It is allowed that source
112       and target of an arc are the same node. Such an arc is called  a  loop.
113       Whenever a node is source or target of an arc both are said to be adja‐
114       cent. This extends into a relation between nodes, i.e. if two nodes are
115       connected through at least one arc they are said to be adjacent too.
116
117       Each node can be the source and target for any number of arcs. The for‐
118       mer are called the outgoing arcs of the node, the latter  the  incoming
119       arcs  of  the node. The number of edges in either set is called the in-
120       resp. the out-degree of the node.
121
122       In addition to maintaining the node and arc relationships,  this  graph
123       implementation  allows any number of keyed values to be associated with
124       each node and arc.
125
126       The following commands are possible for graph objects:
127
128       graphName destroy
129              Destroy the graph, including its storage  space  and  associated
130              command.
131
132       graphName arc append arc ?-key key? value
133              Appends  a  value  to one of the keyed values associated with an
134              arc. If no key is specified, the key data is assumed.
135
136       graphName arc delete arc ?arc ...?
137              Remove the specified arcs from the graph.
138
139       graphName arc exists arc
140              Return true if the specified arc exists in the graph.
141
142       graphName arc get arc ?-key key?
143              Return the value associated with the key key for the arc.  If no
144              key is specified, the key data is assumed.
145
146       graphName arc getall arc
147              Returns  a  serialized list of key/value pairs (suitable for use
148              with [array set]) for the arc.
149
150       graphName arc keys arc
151              Returns a list of keys for the arc.
152
153       graphName arc keyexists arc ?-key key?
154              Return true if the specified key exists for the arc. If  no  key
155              is specified, the key data is assumed.
156
157       graphName arc insert start end ?child?
158              Insert  an  arc named child into the graph beginning at the node
159              start and ending at the node end. If the name of the new arc  is
160              not specified the system will generate a unique name of the form
161              arcx.
162
163       graphName arc lappend arc ?-key key? value
164              Appends a value (as a list) to one of the keyed  values  associ‐
165              ated  with  an  arc.   If  no  key is specified, the key data is
166              assumed.
167
168       graphName arc set arc ?-key key? ?value?
169              Set or get one of the keyed values associated with an  arc.   If
170              no  key is specified, the key data is assumed.  Each arc that is
171              added to a graph has the empty string assigned to the  key  data
172              automatically.  An arc may have any number of keyed values asso‐
173              ciated with it.  If value is not specified, this command returns
174              the  current  value  assigned to the key; if value is specified,
175              this command assigns that value to the key.
176
177       graphName arc source arc
178              Return the node the given arc begins at.
179
180       graphName arc target arc
181              Return the node the given arc ends at.
182
183       graphName arc unset arc ?-key key?
184              Remove a keyed value from the arc arc.  If no key is  specified,
185              the key data is assumed.
186
187       graphName  arcs ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embed‐
188       ding nodelist?
189              Return a list of arcs in the graph. If no restriction is  speci‐
190              fied  a  list  containing all arcs is returned. Restrictions can
191              limit the list of returned arcs based on the nodes that are con‐
192              nected  by the arc, on the keyed values associated with the arc,
193              or both. The restrictions that involve connected  nodes  have  a
194              list  of  nodes  as  argument,  specified  after the name of the
195              restriction itself.
196
197              -in    Return a list of all arcs whose  target  is  one  of  the
198                     nodes in the nodelist.
199
200              -out   Return  a  list  of  all  arcs whose source is one of the
201                     nodes in the nodelist.
202
203              -adj   Return a list of all arcs adjacent to at least one of the
204                     nodes  in  the  nodelist.  This is the union of the nodes
205                     returned by -in and -out.
206
207              -inner Return a list of all arcs adjacent to two of the nodes in
208                     the  nodelist.  This  is  the set of arcs in the subgraph
209                     spawned by the specified nodes.
210
211              -embedding
212                     Return a list of all arcs adjacent to exactly one of  the
213                     nodes in the nodelist. This is the set of arcs connecting
214                     the subgraph spawned by the specified nodes to  the  rest
215                     of the graph.
216
217              -key key
218                     Limit  the  list  of arcs that are returned to those arcs
219                     that have an associated key key.
220
221              -value value
222                     This restriction can only be  used  in  combination  with
223                     -key.  It  limits  the  list of arcs that are returned to
224                     those arcs whose associated key key has the value value.
225
226       The restrictions imposed by either -in, -out, -adj, -inner, or  -embed‐
227       ded are applied first. Specifying more than one of them is illegal.  At
228       last the restrictions set via -key (and -value) are applied.   Specify‐
229       ing more than one -key (and -value) is illegal.
230
231       graphName node append node ?-key key? value
232              Appends  a  value  to one of the keyed values associated with an
233              node. If no key is specified, the key data is assumed.
234
235       graphName node degree ?-in|-out? node
236              Return the number of arcs adjacent to the specified node. If one
237              of the restrictions -in or -out is given only the incoming resp.
238              outgoing arcs are counted.
239
240       graphName node delete node ?node ...?
241              Remove the specified nodes from the graph.  All  of  the  nodes'
242              arcs will be removed as well to prevent unconnected arcs.
243
244       graphName node exists node
245              Return true if the specified node exists in the graph.
246
247       graphName node get node ?-key key?
248              Return  the  value associated with the key key for the node.  If
249              no key is specified, the key data is assumed.
250
251       graphName node getall node
252              Returns a serialized list of key/value pairs (suitable  for  use
253              with [array set]) for the node.
254
255       graphName node keys node
256              Returns a list of keys for the node.
257
258       graphName node keyexists node ?-key key?
259              Return  true if the specified key exists for the node. If no key
260              is specified, the key data is assumed.
261
262       graphName node insert ?child?
263              Insert a node named child into the graph. The nodes has no  arcs
264              connected  to  it. If the name of the new child is not specified
265              the system will generate a unique name of the form nodex.
266
267       graphName node lappend node ?-key key? value
268              Appends a value (as a list) to one of the keyed  values  associ‐
269              ated  with  an  node.  If  no  key is specified, the key data is
270              assumed.
271
272       graphName node opposite node arc
273              Return the node at the other end of the specified arc, which has
274              to be adjacent to the given node.
275
276       graphName node set node ?-key key? ?value?
277              Set  or  get one of the keyed values associated with a node.  If
278              no key is specified, the key data is assumed.  Each node that is
279              added  to  a graph has the empty string assigned to the key data
280              automatically.  A node may have any number of keyed values asso‐
281              ciated with it.  If value is not specified, this command returns
282              the current value assigned to the key; if  value  is  specified,
283              this command assigns that value to the key.
284
285       graphName node unset node ?-key key?
286              Remove  a  keyed  value from the node node.  If no key is speci‐
287              fied, the key data is assumed.
288
289       graphName nodes ?-key key? ?-value value? ?-in|-out|-adj|-inner|-embed‐
290       ding nodelist?
291              Return  a list of nodes in the graph. Restrictions can limit the
292              list of returned nodes based on neighboring nodes, or  based  on
293              the keyed values associated with the node. The restrictions that
294              involve neighboring nodes have a  list  of  nodes  as  argument,
295              specified after the name of the restriction itself.
296
297              The  possible  restrictions are the same as for method arcs. The
298              set of nodes to return is computed as the union  of  all  source
299              and  target nodes for all the arcs satisfying the restriction as
300              defined for arcs.
301
302       graphName get ?-key key?
303              Return the value associated with the key key for the  graph.  If
304              no key is specified, the key data is assumed.
305
306       graphName getall
307              Returns  a  serialized list of key/value pairs (suitable for use
308              with [array set]) for the whole graph.
309
310       graphName keys
311              Returns a list of keys for the whole graph.
312
313       graphName keyexists ?-key key?
314              Return true if the specified key exists for the whole graph.  If
315              no key is specified, the key data is assumed.
316
317       graphName set ?-key key? ?value?
318              Set  or  get one of the keyed values associated with a graph. If
319              no key is specified, the key data is assumed. Each graph has the
320              empty string assigned to the key data automatically. A graph may
321              have any number of keyed values associated with it. If value  is
322              not  specified,  this command returns the current value assigned
323              to the key; if value is specified,  this  command  assigns  that
324              value to the key.
325
326       graphName swap node1 node2
327              Swap the position of node1 and node2 in the graph.
328
329       graphName unset ?-key key?
330              Remove a keyed value from the graph. If no key is specified, the
331              key data is assumed.
332
333       graphName walk node ?-order order? ?-type type? ?-dir direction?  -com‐
334       mand cmd
335              Perform  a breadth-first or depth-first walk of the graph start‐
336              ing at the node node going in either the direction  of  outgoing
337              or opposite to the incoming arcs.
338
339              The type of walk, breadth-first or depth-first, is determined by
340              the value of type; bfs indicates  breadth-first,  dfs  indicates
341              depth-first.  Depth-first is the default.
342
343              The  order  of  the walk, pre-order, post-order or both-order is
344              determined by the value of order; pre indicates pre-order,  post
345              indicates  post-order,  both  indicates both-order. Pre-order is
346              the default. Pre-order walking means  that  a  node  is  visited
347              before  any  of  its neighbors (as defined by the direction, see
348              below). Post-order walking means that a parent is visited  after
349              any  of  its  neighbors. Both-order walking means that a node is
350              visited before and after any of its neighbors.  The  combination
351              of a bread-first walk with post- or both-order is illegal.
352
353              The  direction  of  the  walk is determined by the value of dir;
354              backward indicates the direction opposite to the incoming  arcs,
355              forward indicates the direction of the outgoing arcs.
356
357              As  the  walk  progresses,  the command cmd will be evaluated at
358              each node, with the mode of the call (enter or leave) and values
359              graphName  and the name of the current node appended. For a pre-
360              order walk, all nodes are entered, for a  post-order  all  nodes
361              are  left. In a both-order walk the first visit of a node enters
362              it, the second visit leaves it.
363

BUGS, IDEAS, FEEDBACK

365       This document, and the package it describes, will  undoubtedly  contain
366       bugs  and other problems.  Please report such in the category struct ::
367       graph of the  Tcllib  Trackers  [http://core.tcl.tk/tcllib/reportlist].
368       Please  also  report any ideas for enhancements you may have for either
369       package and/or documentation.
370
371       When proposing code changes, please provide unified diffs, i.e the out‐
372       put of diff -u.
373
374       Note  further  that  attachments  are  strongly  preferred over inlined
375       patches. Attachments can be made by going  to  the  Edit  form  of  the
376       ticket  immediately  after  its  creation, and then using the left-most
377       button in the secondary navigation bar.
378

KEYWORDS

380       cgraph, graph
381

CATEGORY

383       Data structures
384
386       Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
387
388
389
390
391tcllib                               1.2.1                 struct::graph_v1(n)
Impressum