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

NAME

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

SYNOPSIS

11       package require Tcl  8.4
12
13       package require struct::graph  ?2.4.1?
14
15       package require struct::list  ?1.5?
16
17       package require struct::set  ?2.2.3?
18
19       ::struct::graph ?graphName? ?=|:=|as|deserialize source?
20
21       graphName option ?arg arg ...?
22
23       graphName = sourcegraph
24
25       graphName --> destgraph
26
27       graphName append key value
28
29       graphName deserialize serialization
30
31       graphName destroy
32
33       graphName arc append arc key value
34
35       graphName arc attr key
36
37       graphName arc attr key -arcs list
38
39       graphName arc attr key -glob globpattern
40
41       graphName arc attr key -regexp repattern
42
43       graphName arc delete arc ?arc ...?
44
45       graphName arc exists arc
46
47       graphName arc flip arc
48
49       graphName arc get arc key
50
51       graphName arc getall arc ?pattern?
52
53       graphName arc getunweighted
54
55       graphName arc getweight arc
56
57       graphName arc keys arc ?pattern?
58
59       graphName arc keyexists arc key
60
61       graphName arc insert start end ?child?
62
63       graphName arc lappend arc key value
64
65       graphName arc rename arc newname
66
67       graphName arc set arc key ?value?
68
69       graphName arc setunweighted ?weight?
70
71       graphName arc setweight arc weight
72
73       graphName arc unsetweight arc
74
75       graphName arc hasweight arc
76
77       graphName arc source arc
78
79       graphName arc target arc
80
81       graphName arc nodes arc
82
83       graphName arc move-source arc newsource
84
85       graphName arc move-target arc newtarget
86
87       graphName arc move arc newsource newtarget
88
89       graphName arc unset arc key
90
91       graphName arc weights
92
93       graphName   arcs   ?-key   key?   ?-value  value?  ?-filter  cmdprefix?
94       ?-in|-out|-adj|-inner|-embedding node node...?
95
96       graphName lappend key value
97
98       graphName node append node key value
99
100       graphName node attr key
101
102       graphName node attr key -nodes list
103
104       graphName node attr key -glob globpattern
105
106       graphName node attr key -regexp repattern
107
108       graphName node degree ?-in|-out? node
109
110       graphName node delete node ?node...?
111
112       graphName node exists node
113
114       graphName node get node key
115
116       graphName node getall node ?pattern?
117
118       graphName node keys node ?pattern?
119
120       graphName node keyexists node key
121
122       graphName node insert ?node...?
123
124       graphName node lappend node key value
125
126       graphName node opposite node arc
127
128       graphName node rename node newname
129
130       graphName node set node key ?value?
131
132       graphName node unset node key
133
134       graphName  nodes  ?-key  key?  ?-value   value?   ?-filter   cmdprefix?
135       ?-in|-out|-adj|-inner|-embedding node node...?
136
137       graphName get key
138
139       graphName getall ?pattern?
140
141       graphName keys ?pattern?
142
143       graphName keyexists key
144
145       graphName serialize ?node...?
146
147       graphName set key ?value?
148
149       graphName swap node1 node2
150
151       graphName unset key
152
153       graphName  walk node ?-order order? ?-type type? ?-dir direction? -com‐
154       mand cmd
155
156______________________________________________________________________________
157

DESCRIPTION

159       A directed graph is a structure containing two collections of elements,
160       called  nodes and arcs respectively, together with a relation ("connec‐
161       tivity") that places a general structure upon the nodes and arcs.
162
163       Each arc is connected to two nodes, one of which is called  the  source
164       and  the other the target. This imposes a direction upon the arc, which
165       is said to go from the source to the target. It is allowed that  source
166       and  target  of an arc are the same node. Such an arc is called a loop.
167       Whenever a node is either the source or target of an arc both are  said
168       to be adjacent. This extends into a relation between nodes, i.e. if two
169       nodes are connected through at least one arc they are said to be  adja‐
170       cent too.
171
172       Each node can be the source and target for any number of arcs. The for‐
173       mer are called the outgoing arcs of the node, the latter  the  incoming
174       arcs  of  the  node. The number of arcs in either set is called the in-
175       degree resp. the out-degree of the node.
176
177       In addition to maintaining the node and arc relationships,  this  graph
178       implementation  allows  any number of named attributes to be associated
179       with the graph itself, and each node or arc.
180
181       Note: The major version of the package struct has been changed to  ver‐
182       sion  2.0, due to backward incompatible changes in the API of this mod‐
183       ule. Please read the section Changes for 2.0 for a  full  list  of  all
184       changes, incompatible and otherwise.
185
186       Note:  A  C-implementation  of the command can be had from the location
187       http://www.purl.org/NET/schlenker/tcl/cgraph.         See          also
188       http://wiki.tcl.tk/cgraph.   This implementation uses a bit less memory
189       than the tcl version provided here directly, and is faster. Its support
190       is limited to versions of the package before 2.0.
191
192       As  of  version  2.2 of this package a critcl based C implementation is
193       available from here as well. This implementation however  requires  Tcl
194       8.4 to run.
195
196       The main command of the package is:
197
198       ::struct::graph ?graphName? ?=|:=|as|deserialize source?
199              The command creates a new graph object with an associated global
200              Tcl command whose name is graphName.  This command may  be  used
201              to invoke various operations on the graph.  It has the following
202              general form:
203
204              graphName option ?arg arg ...?
205                     Option and the args determine the exact behavior  of  the
206                     command.
207
208       If  graphName  is  not specified a unique name will be generated by the
209       package itself. If a source is specified the new graph will be initial‐
210       ized  to  it.  For  the  operators =, :=, and as the source argument is
211       interpreted as the name of another graph  object,  and  the  assignment
212       operator = will be executed. For the operator deserialize the source is
213       a serialized graph object and deserialize will be executed.
214
215       In other words
216
217
218
219                  ::struct::graph mygraph = b
220
221
222       is equivalent to
223
224
225
226                  ::struct::graph mygraph
227                  mygraph = b
228
229
230       and
231
232
233
234                  ::struct::graph mygraph deserialize $b
235
236
237       is equivalent to
238
239
240
241                  ::struct::graph mygraph
242                  mygraph deserialize $b
243
244
245       The following commands are possible for graph objects:
246
247       graphName = sourcegraph
248              This is the assignment operator for graph objects. It copies the
249              graph  contained  in the graph object sourcegraph over the graph
250              data in graphName. The old contents of graphName are deleted  by
251              this operation.
252
253              This operation is in effect equivalent to
254
255
256
257                  graphName deserialize [sourcegraph serialize]
258
259
260       The  operation assumes that the sourcegraph provides the method serial‐
261       ize and that this method returns a valid graph serialization.
262
263       graphName --> destgraph
264              This is the reverse assignment operator for  graph  objects.  It
265              copies  the  graph  contained in the graph object graphName over
266              the graph data in the object destgraph.   The  old  contents  of
267              destgraph are deleted by this operation.
268
269              This operation is in effect equivalent to
270
271
272
273                  destgraph deserialize [graphName serialize]
274
275
276       The  operation assumes that the destgraph provides the method deserial‐
277       ize and that this method takes a graph serialization.
278
279       graphName append key value
280              Appends a value to one of the keyed values associated  with  the
281              graph.  Returns the new value given to the attribute key.
282
283       graphName deserialize serialization
284              This  is the complement to serialize. It replaces the graph data
285              in graphName with  the  graph  described  by  the  serialization
286              value.  The old contents of graphName are deleted by this opera‐
287              tion.
288
289       graphName destroy
290              Destroys the graph, including its storage space  and  associated
291              command.
292
293       graphName arc append arc key value
294              Appends  a  value  to one of the keyed values associated with an
295              arc. Returns the new value given to the attribute key.
296
297       graphName arc attr key
298
299       graphName arc attr key -arcs list
300
301       graphName arc attr key -glob globpattern
302
303       graphName arc attr key -regexp repattern
304              This method retrieves the value of the attribute named key,  for
305              all  arcs  in  the graph (matching the restriction specified via
306              one of the possible options) and having the specified attribute.
307
308              The result is a dictionary mapping from arc names to  the  value
309              of  attribute  key  at  that arc.  Arcs not having the attribute
310              key, or not passing a specified restriction, are not  listed  in
311              the result.
312
313              The possible restrictions are:
314
315              -arcs  The  value  is a list of arcs. Only the arcs mentioned in
316                     this list are searched for the attribute.
317
318              -glob  The value is a glob pattern. Only the arcs in  the  graph
319                     whose  names  match  this  pattern  are  searched for the
320                     attribute.
321
322              -regexp
323                     The value is a regular expression. Only the arcs  in  the
324                     graph whose names match this pattern are searched for the
325                     attribute.
326
327
328       graphName arc delete arc ?arc ...?
329              Remove the specified arcs from the graph.
330
331       graphName arc exists arc
332              Return true if the specified arc exists in the graph.
333
334       graphName arc flip arc
335              Reverses the direction of the named arc,  i.e.  the  source  and
336              target nodes of the arc are exchanged with each other.
337
338       graphName arc get arc key
339              Returns the value associated with the key key for the arc.
340
341       graphName arc getall arc ?pattern?
342              Returns a dictionary (suitable for use with [array set]) for the
343              arc.  If the pattern is  specified  only  the  attributes  whose
344              names match the pattern will be part of the returned dictionary.
345              The pattern is a glob pattern.
346
347       graphName arc getunweighted
348              Returns a list containing the names of all  arcs  in  the  graph
349              which have no weight associated with them.
350
351       graphName arc getweight arc
352              Returns  the  weight associated with the arc. Throws an error if
353              the arc has no weight associated with it.
354
355       graphName arc keys arc ?pattern?
356              Returns a list of keys for the arc.  If the pattern is specified
357              only  the  attributes whose names match the pattern will be part
358              of the returned list. The pattern is a glob pattern.
359
360       graphName arc keyexists arc key
361              Return true if the specified key exists for the arc.
362
363       graphName arc insert start end ?child?
364              Insert an arc named child into the graph beginning at  the  node
365              start  and ending at the node end. If the name of the new arc is
366              not specified the system will generate a unique name of the form
367              arcx.
368
369       graphName arc lappend arc key value
370              Appends  a  value (as a list) to one of the keyed values associ‐
371              ated with an arc. Returns the new value given to  the  attribute
372              key.
373
374       graphName arc rename arc newname
375              Renames the arc arc to newname. An error is thrown if either the
376              arc does not exist, or a arc with name newname does  exist.  The
377              result of the command is the new name of the arc.
378
379       graphName arc set arc key ?value?
380              Set  or  get one of the keyed values associated with an arc.  An
381              arc may have any number of keyed values associated with it.   If
382              value  is  not specified, this command returns the current value
383              assigned to the key; if value is specified, this command assigns
384              that value to the key, and returns that value.
385
386       graphName arc setunweighted ?weight?
387              Sets  the weight of all arcs without a weight to weight. Returns
388              the empty string as its result. If not present  weight  defaults
389              to 0.
390
391       graphName arc setweight arc weight
392              Sets the weight of the arc to weight. Returns weight.
393
394       graphName arc unsetweight arc
395              Removes  the  weight of the arc, if present. Does nothing other‐
396              wise. Returns the empty string.
397
398       graphName arc hasweight arc
399              Determines if the arc has a  weight  associated  with  it.   The
400              result  is  a  boolean  value,  True if a weight is defined, and
401              False otherwise.
402
403       graphName arc source arc
404              Return the node the given arc begins at.
405
406       graphName arc target arc
407              Return the node the given arc ends at.
408
409       graphName arc nodes arc
410              Return the nodes the given arc begins and ends at, as a two-ele‐
411              ment list.
412
413       graphName arc move-source arc newsource
414              Changes  the source node of the arc to newsource. It can be said
415              that the arc rotates around its target node.
416
417       graphName arc move-target arc newtarget
418              Changes the target node of the arc to newtarget. It can be  said
419              that the arc rotates around its source node.
420
421       graphName arc move arc newsource newtarget
422              Changes  both  source  and target nodes of the arc to newsource,
423              and newtarget resp.
424
425       graphName arc unset arc key
426              Remove a keyed value from the arc arc. The method will do  noth‐
427              ing if the key does not exist.
428
429       graphName arc weights
430              Returns  a dictionary whose keys are the names of all arcs which
431              have a weight associated with them, and  the  values  are  these
432              weights.
433
434       graphName   arcs   ?-key   key?   ?-value  value?  ?-filter  cmdprefix?
435       ?-in|-out|-adj|-inner|-embedding node node...?
436              Returns a list of arcs in the graph. If no restriction is speci‐
437              fied  a  list  containing all arcs is returned. Restrictions can
438              limit the list of returned arcs based on the nodes that are con‐
439              nected  by the arc, on the keyed values associated with the arc,
440              or both. A general filter command  can  be  used  as  well.  The
441              restrictions that involve connected nodes take a variable number
442              of nodes as argument, specified after the name of  the  restric‐
443              tion itself.
444
445              The  restrictions  imposed by either -in, -out, -adj, -inner, or
446              -embedded are applied first. Specifying more than one of them is
447              illegal.
448
449              After  that  the  restrictions  set  via  -key  (and -value) are
450              applied. Specifying more than one -key (and -value) is  illegal.
451              Specifying -value alone, without -key is illegal as well.
452
453              Any  restriction set through -filter is applied last. Specifying
454              more than one -filter is illegal.
455
456              Coming back to the restrictions based on a  set  of  nodes,  the
457              command recognizes the following switches:
458
459              -in    Return  a  list  of  all  arcs whose target is one of the
460                     nodes in the set of nodes. I.e. it computes the union  of
461                     all incoming arcs of the nodes in the set.
462
463              -out   Return  a  list  of  all  arcs whose source is one of the
464                     nodes in the set of nodes. I.e. it computes the union  of
465                     all outgoing arcs of the nodes in the set.
466
467              -adj   Return a list of all arcs adjacent to at least one of the
468                     nodes in the set. This is the union of the nodes returned
469                     by -in and -out.
470
471              -inner Return  a  list  of all arcs which are adjacent to two of
472                     the nodes in the set. This is the set of arcs in the sub‐
473                     graph spawned by the specified nodes.
474
475              -embedding
476                     Return  a list of all arcs adjacent to exactly one of the
477                     nodes in the set. This is the set of arcs connecting  the
478                     subgraph  spawned  by  the specified nodes to the rest of
479                     the graph.
480
481              -key key
482                     Limit the list of arcs that are returned  to  those  arcs
483                     that have an associated key key.
484
485              -value value
486                     This  restriction  can  only  be used in combination with
487                     -key. It limits the list of arcs  that  are  returned  to
488                     those arcs whose associated key key has the value value.
489
490              -filter cmdrefix
491                     Limit  the  list  of arcs that are returned to those arcs
492                     that pass the test. The command in  cmdprefix  is  called
493                     with two arguments, the name of the graph object, and the
494                     name of the arc in question. It is executed in  the  con‐
495                     text  of  the  caller  and has to return a boolean value.
496                     Arcs for which the command returns false are removed from
497                     the result list before it is returned to the caller.
498
499       graphName lappend key value
500              Appends  a  value (as a list) to one of the keyed values associ‐
501              ated with  the  graph.  Returns  the  new  value  given  to  the
502              attribute key.
503
504       graphName node append node key value
505              Appends  a  value  to one of the keyed values associated with an
506              node. Returns the new value given to the attribute key.
507
508       graphName node attr key
509
510       graphName node attr key -nodes list
511
512       graphName node attr key -glob globpattern
513
514       graphName node attr key -regexp repattern
515              This method retrieves the value of the attribute named key,  for
516              all  nodes  in the graph (matching the restriction specified via
517              one of the possible options) and having the specified attribute.
518
519              The result is a dictionary mapping from node names to the  value
520              of  attribute  key at that node.  Nodes not having the attribute
521              key, or not passing a specified restriction, are not  listed  in
522              the result.
523
524              The possible restrictions are:
525
526              -nodes The value is a list of nodes. Only the nodes mentioned in
527                     this list are searched for the attribute.
528
529              -glob  The value is a glob pattern. Only the nodes in the  graph
530                     whose  names  match  this  pattern  are  searched for the
531                     attribute.
532
533              -regexp
534                     The value is a regular expression. Only the nodes in  the
535                     graph whose names match this pattern are searched for the
536                     attribute.
537
538
539       graphName node degree ?-in|-out? node
540              Return the number of arcs adjacent to the specified node. If one
541              of the restrictions -in or -out is given only the incoming resp.
542              outgoing arcs are counted.
543
544       graphName node delete node ?node...?
545              Remove the specified nodes from the graph.  All  of  the  nodes'
546              arcs will be removed as well to prevent unconnected arcs.
547
548       graphName node exists node
549              Return true if the specified node exists in the graph.
550
551       graphName node get node key
552              Return the value associated with the key key for the node.
553
554       graphName node getall node ?pattern?
555              Returns a dictionary (suitable for use with [array set]) for the
556              node.  If the pattern is specified  only  the  attributes  whose
557              names match the pattern will be part of the returned dictionary.
558              The pattern is a glob pattern.
559
560       graphName node keys node ?pattern?
561              Returns a list of keys for the node.  If the pattern  is  speci‐
562              fied  only  the attributes whose names match the pattern will be
563              part of the returned list. The pattern is a glob pattern.
564
565       graphName node keyexists node key
566              Return true if the specified key exists for the node.
567
568       graphName node insert ?node...?
569              Insert one or more nodes into the graph. The new nodes  have  no
570              arcs connected to them. If no node is specified one node will be
571              inserted, and the system will generate a unique name of the form
572              nodex for it.
573
574       graphName node lappend node key value
575              Appends  a  value (as a list) to one of the keyed values associ‐
576              ated with an node. Returns the new value given to the  attribute
577              key.
578
579       graphName node opposite node arc
580              Return the node at the other end of the specified arc, which has
581              to be adjacent to the given node.
582
583       graphName node rename node newname
584              Renames the node node to newname. An error is thrown  if  either
585              the node does not exist, or a node with name newname does exist.
586              The result of the command is the new name of the node.
587
588       graphName node set node key ?value?
589              Set or get one of the keyed values associated  with  a  node.  A
590              node may have any number of keyed values associated with it.  If
591              value is not specified, this command returns the  current  value
592              assigned to the key; if value is specified, this command assigns
593              that value to the key.
594
595       graphName node unset node key
596              Remove a keyed value from the node  node.  The  method  will  do
597              nothing if the key does not exist.
598
599       graphName   nodes   ?-key   key?  ?-value  value?  ?-filter  cmdprefix?
600       ?-in|-out|-adj|-inner|-embedding node node...?
601              Return a list of nodes in the graph. Restrictions can limit  the
602              list  of  returned nodes based on neighboring nodes, or based on
603              the keyed values associated with the node. The restrictions that
604              involve  neighboring  nodes  have  a  list of nodes as argument,
605              specified after the name of the restriction itself.
606
607              The possible restrictions are the same as for method  arcs.  The
608              exact meanings change slightly, as they operate on nodes instead
609              of arcs. The command recognizes:
610
611              -in    Return a list of all nodes with at least one outgoing arc
612                     ending  in  a  node  found in the specified set of nodes.
613                     Alternatively specified as the set of  source  nodes  for
614                     the -in arcs of the node set. The incoming neighbours.
615
616              -out   Return a list of all nodes with at least one incoming arc
617                     starting in a node found in the specified set  of  nodes.
618                     Alternatively  specified  as  the set of target nodes for
619                     the -out arcs of the node set. The outgoing neighbours.
620
621              -adj   This is the union of the nodes returned by -in and  -out.
622                     The neighbours.
623
624              -inner The  set of neighbours (see -adj above) which are also in
625                     the set of nodes. I.e. the intersection between  the  set
626                     of nodes and the neighbours per -adj.
627
628              -embedding
629                     The  set  of neighbours (see -adj above) which are not in
630                     the set of nodes. I.e. the difference between the  neigh‐
631                     bours as per -adj, and the set of nodes.
632
633              -key key
634                     Limit  the list of nodes that are returned to those nodes
635                     that have an associated key key.
636
637              -value value
638                     This restriction can only be  used  in  combination  with
639                     -key.  It  limits  the list of nodes that are returned to
640                     those nodes whose associated key key has the value value.
641
642              -filter cmdrefix
643                     Limit the list of nodes that are returned to those  nodes
644                     that  pass  the  test. The command in cmdprefix is called
645                     with two arguments, the name of the graph object, and the
646                     name  of the node in question. It is executed in the con‐
647                     text of the caller and has to  return  a  boolean  value.
648                     Nodes  for  which  the  command returns false are removed
649                     from the result list before it is returned to the caller.
650
651       graphName get key
652              Return the value associated with the key key for the graph.
653
654       graphName getall ?pattern?
655              Returns a dictionary (suitable for use with [array set]) for the
656              whole  graph.   If  the pattern is specified only the attributes
657              whose names match the pattern will be part of the returned  dic‐
658              tionary. The pattern is a glob pattern.
659
660       graphName keys ?pattern?
661              Returns  a  list of keys for the whole graph.  If the pattern is
662              specified only the attributes whose names match the pattern will
663              be part of the returned list. The pattern is a glob pattern.
664
665       graphName keyexists key
666              Return true if the specified key exists for the whole graph.
667
668       graphName serialize ?node...?
669              This method serializes the sub-graph spanned up by the nodes. In
670              other words it returns a tcl value  completely  describing  that
671              graph. If no nodes are specified the whole graph will be serial‐
672              ized.  This allows, for example, the transfer of  graph  objects
673              (or  parts  thereof)  over arbitrary channels, persistence, etc.
674              This method is also the basis for both the copy constructor  and
675              the assignment operator.
676
677              The  result of this method has to be semantically identical over
678              all implementations of the graph interface. This  is  what  will
679              enable  us  to copy graph data between different implementations
680              of the same interface.
681
682              The result is a list containing a multiple of three items,  plus
683              one!  In other words, '[llength $serial] % 3 == 1'. Valid values
684              include 1, 4, 7, ...
685
686              The last element of the list  is  a  dictionary  containing  the
687              attributes associated with the whole graph.  Regarding the other
688              elements; each triple consists of
689
690              [1]    The name of the node to be described,
691
692              [2]    A dictionary containing the  attributes  associated  with
693                     the node,
694
695              [3]    And a list describing all the arcs starting at that node.
696
697       The  elements  of  the arc list are lists containing three or four ele‐
698       ments each, i.e.
699
700              [1]    The name of the arc described by the element,
701
702              [2]    A reference to the destination node of the arc. This ref‐
703                     erence  is an integer number given the index of that node
704                     in the main serialization list. As  that  it  is  greater
705                     than  or equal to zero, less than the length of the seri‐
706                     alization, and a multiple of three.  Note:  For  internal
707                     consistency no arc name may be used twice, whether in the
708                     same node, or at some other node. This is a  global  con‐
709                     sistency requirement for the serialization.
710
711              [3]    And  a  dictionary  containing  the attributes associated
712                     with the arc.
713
714              [4]    The  weight  associated  with  the  arc.  This  value  is
715                     optional. Its non-presence means that the arc in question
716                     has no weight associated with it.
717
718                     Note: This information is new, compared to the serializa‐
719                     tion  of  graph 2.3 and earlier. By making it an optional
720                     element the new format is maximally compatible  with  the
721                     old.  This  means  that  any graph not using weights will
722                     generate a serialization which is still understood by the
723                     older  graph  package. A serialization will not be under‐
724                     stood any longer by the older packages if,  and  only  if
725                     the  graph  it  was generated from actually has arcs with
726                     weights.
727
728       For  all  attribute  dictionaries  they  keys  are  the  names  of  the
729       attributes, and the values are the values for each name.
730
731       Note: The order of the nodes in the serialization has no relevance, nor
732       has the order of the arcs per node.
733
734
735                  # A possible serialization for the graph structure
736                  #
737                  #        d -----> %2
738                  #       /         ^ \\
739                  #      /         /   \\
740                  #     /         b     \\
741                  #    /         /       \\
742                  #  %1 <- a - %0         e
743                  #    ^         \\      /
744                  #     \\        c     /
745                  #      \\        \\  /
746                  #       \\        v v
747                  #        f ------ %3
748                  # is
749                  #
750                  # %3 {} {{f 6 {}}} %0 {} {{a 6 {}} {b 9 {}} {c 0 {}}} %1 {} {{d 9 {}}} %2 {} {{e 0 {}}} {}
751                  #
752                  # This assumes that the graph has neither attribute data nor weighted arcs.
753
754
755
756       graphName set key ?value?
757              Set or get one of the keyed values associated with  a  graph.  A
758              graph may have any number of keyed values associated with it. If
759              value is not specified, this command returns the  current  value
760              assigned to the key; if value is specified, this command assigns
761              that value to the key.
762
763       graphName swap node1 node2
764              Swap the position of node1 and node2 in the graph.
765
766       graphName unset key
767              Remove a keyed value from the graph. The method will do  nothing
768              if the key does not exist.
769
770       graphName  walk node ?-order order? ?-type type? ?-dir direction? -com‐
771       mand cmd
772              Perform a breadth-first or depth-first walk of the graph  start‐
773              ing  at  the node node going in either the direction of outgoing
774              or opposite to the incoming arcs.
775
776              The type of walk, breadth-first or depth-first, is determined by
777              the  value  of  type; bfs indicates breadth-first, dfs indicates
778              depth-first.  Depth-first is the default.
779
780              The order of the walk, pre-order, post-order  or  both-order  is
781              determined  by the value of order; pre indicates pre-order, post
782              indicates post-order, both indicates  both-order.  Pre-order  is
783              the  default.  Pre-order  walking  means  that a node is visited
784              before any of its neighbors (as defined by  the  direction,  see
785              below).  Post-order walking means that a parent is visited after
786              any of its neighbors. Both-order walking means that  a  node  is
787              visited  before  and after any of its neighbors. The combination
788              of a breadth-first walk with post- or both-order is illegal.
789
790              The direction of the walk is determined by  the  value  of  dir;
791              backward  indicates the direction opposite to the incoming arcs,
792              forward indicates the direction of the outgoing arcs.
793
794              As the walk progresses, the command cmd  will  be  evaluated  at
795              each node, with the mode of the call (enter or leave) and values
796              graphName and the name of the current node appended. For a  pre-
797              order  walk,  all  nodes are entered, for a post-order all nodes
798              are left. In a both-order walk the first visit of a node  enters
799              it, the second visit leaves it.
800

CHANGES FOR 2.0

802       The following noteworthy changes have occurred:
803
804       [1]    The  API for accessing attributes and their values has been sim‐
805              plified.
806
807              All functionality regarding the  default  attribute  "data"  has
808              been removed. This default attribute does not exist anymore. All
809              accesses to attributes have to specify the name of the attribute
810              in  question.  This  backward  incompatible change allowed us to
811              simplify the signature of all methods handling attributes.
812
813              Especially the flag -key is not required anymore, even more, its
814              use  is now forbidden. Please read the documentation for the arc
815              and node methods  set,  get,  getall,  unset,  append,  lappend,
816              keyexists and keys for a description of the new API's.
817
818       [2]    The  methods  keys and getall now take an optional pattern argu‐
819              ment and will return only attribute data for keys matching  this
820              pattern.
821
822       [3]    Arcs and nodes can now be renamed. See the documentation for the
823              methods arc rename and node rename.
824
825       [4]    The structure has been extended with API's for the serialization
826              and deserialization of graph objects, and a number of operations
827              based on them (graph assignment, copy construction).
828
829              Please read the documentation for the methods serialize, deseri‐
830              alize,  =, and -->, and the documentation on the construction of
831              graph objects.
832
833              Beyond the copying of whole graph objects these new  API's  also
834              enable the transfer of graph objects over arbitrary channels and
835              for easy persistence.
836
837       [5]    A new method, attr, was added to both arc and node allowing  the
838              query  and retrieval of attribute data without regard to arc and
839              node relationships.
840
841       [6]    Both methods arcs and nodes have been extended with the  ability
842              to  select  arcs  and nodes based on an arbitrary filtering cri‐
843              terium.
844

BUGS, IDEAS, FEEDBACK

846       This document, and the package it describes, will  undoubtedly  contain
847       bugs  and other problems.  Please report such in the category struct ::
848       graph of the  Tcllib  Trackers  [http://core.tcl.tk/tcllib/reportlist].
849       Please  also  report any ideas for enhancements you may have for either
850       package and/or documentation.
851
852       When proposing code changes, please provide unified diffs, i.e the out‐
853       put of diff -u.
854
855       Note  further  that  attachments  are  strongly  preferred over inlined
856       patches. Attachments can be made by going  to  the  Edit  form  of  the
857       ticket  immediately  after  its  creation, and then using the left-most
858       button in the secondary navigation bar.
859

KEYWORDS

861       adjacent, arc, cgraph, degree,  edge,  graph,  loop,  neighbour,  node,
862       serialization, subgraph, vertex
863

CATEGORY

865       Data structures
866
868       Copyright (c) 2002-2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>
869
870
871
872
873tcllib                               2.4.1                    struct::graph(n)
Impressum