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

DESCRIPTION

139       A directed graph is a structure containing two collections of elements,
140       called  nodes and arcs respectively, together with a relation ("connec‐
141       tivity") that places a general structure upon the nodes and arcs.
142
143       Each arc is connected to two nodes, one of which is called  the  source
144       and  the other the target. This imposes a direction upon the arc, which
145       is said to go from the source to the target. It is allowed that  source
146       and  target  of an arc are the same node. Such an arc is called a loop.
147       Whenever a node is source or target of an arc both are said to be adja‐
148       cent. This extends into a relation between nodes, i.e. if two nodes are
149       connected through at least one arc they are said to be adjacent too.
150
151       Each node can be the source and target for any number of arcs. The for‐
152       mer  are  called the outgoing arcs of the node, the latter the incoming
153       arcs of the node. The number of edges in either set is called  the  in-
154       resp. the out-degree of the node.
155
156       In  addition  to maintaining the node and arc relationships, this graph
157       implementation allows any number of keyed values to be associated  with
158       each node and arc.
159
160       Note:  The major version of the package struct has been changed to ver‐
161       sion 2.0, due to backward incompatible changes in the API of this  mod‐
162       ule.  Please  read  the  section Changes for 2.0 for a full list of all
163       changes, incompatible and otherwise.
164
165       Note: A C-implementation of the command can be had  from  the  location
166       http://www.purl.org/NET/schlenker/tcl/cgraph.          See         also
167       http://wiki.tcl.tk/cgraph.  This implementation uses a bit less  memory
168       than the tcl version provided here directly, and is faster.
169
170       The main command of the package is:
171
172       ::struct::graph ?graphName? ?=|:=|as|deserialize source?
173              The command creates a new graph object with an associated global
174              Tcl command whose name is graphName.  This command may  be  used
175              to invoke various operations on the graph.  It has the following
176              general form:
177
178              graphName option ?arg arg ...?
179                     Option and the args determine the exact behavior  of  the
180                     command.
181
182       If  graphName  is  not specified a unique name will be generated by the
183       package itself. If a source is specified the new graph will be initial‐
184       ized  to  it.  For the operators =, :=, and as source is interpreted as
185       the name of another graph object, and the assignment operator = will be
186       executed.  For  deserialize the source is a serialized graph object and
187       deserialize will be executed.
188
189       In other words
190
191
192           ::struct::graph mygraph = b
193
194
195       is equivalent to
196
197
198           ::struct::graph mygraph
199           mygraph = b
200
201
202       and
203
204
205           ::struct::graph mygraph deserialize $b
206
207
208       is equivalent to
209
210
211           ::struct::graph mygraph
212           mygraph deserialize $b
213
214
215       The following commands are possible for graph objects:
216
217       graphName = sourcegraph
218              This is the assignment operator for graph objects. It copies the
219              graph  contained  in the graph object sourcegraph over the graph
220              data in graphName. The old contents of graphName are deleted  by
221              this operation.
222
223              This operation is in effect equivalent to
224
225
226                  graphName deserialize [sourcegraph serialize]
227
228
229       graphName --> destgraph
230              This  is  the  reverse assignment operator for graph objects. It
231              copies the graph contained in the graph  object  graphName  over
232              the  graph  data  in  the object destgraph.  The old contents of
233              destgraph are deleted by this operation.
234
235              This operation is in effect equivalent to
236
237
238                  destgraph deserialize [graphName serialize]
239
240
241       graphName append key value
242              Appends a value to one of the keyed values associated  with  the
243              graph.  Returns the new value given to the attribute key.
244
245       graphName deserialize serialization
246              This  is  the complement to serialize. It replaces graph data in
247              graphName with the graph described by the  serialization  value.
248              The old contents of graphName are deleted by this operation.
249
250       graphName destroy
251              Destroy  the  graph,  including its storage space and associated
252              command.
253
254       graphName arc append arc key value
255              Appends a value to one of the keyed values  associated  with  an
256              arc. Returns the new value given to the attribute key.
257
258       graphName arc attr key
259
260       graphName arc attr key -arcs list
261
262       graphName arc attr key -glob globpattern
263
264       graphName arc attr key -regexp repattern
265              This  method retrieves the value of the attribute named key, for
266              all arcs in the graph (matching the  restriction  specified  via
267              one of the possible options) and having the specified attribute.
268
269              The  result  is a dictionary mapping from arc names to the value
270              of attribute key at that arc.  Arcs  not  having  the  attribute
271              key,  or  not passing a specified restriction, are not listed in
272              the result.
273
274              The possible restrictions are:
275
276              -arcs  The value is a list of arcs. Only the arcs  mentioned  in
277                     this list are searched for the attribute.
278
279              -glob  The  value  is a glob pattern. Only the arcs in the graph
280                     whose names match  this  pattern  are  searched  for  the
281                     attribute.
282
283              -regexp
284                     The  value  is a regular expression. Only the arcs in the
285                     graph whose names match this pattern are searched for the
286                     attribute.
287
288
289       graphName arc delete arc ?arc ...?
290              Remove the specified arcs from the graph.
291
292       graphName arc exists arc
293              Return true if the specified arc exists in the graph.
294
295       graphName arc get arc key
296              Return the value associated with the key key for the arc.
297
298       graphName arc getall arc ?pattern?
299              Returns a dictionary (suitable for use with [array set]) for the
300              arc.  If the pattern is  specified  only  the  attributes  whose
301              names match the pattern will be part of the returned dictionary.
302              The pattern is a glob pattern.
303
304       graphName arc keys arc ?pattern?
305              Returns a list of keys for the arc.  If the pattern is specified
306              only  the  attributes whose names match the pattern will be part
307              of the returned list. The pattern is a glob pattern.
308
309       graphName arc keyexists arc key
310              Return true if the specified key exists for the arc.
311
312       graphName arc insert start end ?child?
313              Insert an arc named child into the graph beginning at  the  node
314              start  and ending at the node end. If the name of the new arc is
315              not specified the system will generate a unique name of the form
316              arcx.
317
318       graphName arc lappend arc key value
319              Appends  a  value (as a list) to one of the keyed values associ‐
320              ated with an arc. Returns the new value given to  the  attribute
321              key.
322
323       graphName arc rename arc newname
324              Renames the arc arc to newname. An error is thrown if either the
325              arc does not exist, or a arc with name newname does  exist.  The
326              result of the command is the new name of the arc.
327
328       graphName arc set arc key ?value?
329              Set  or  get one of the keyed values associated with an arc.  An
330              arc may have any number of keyed values associated with it.   If
331              value  is  not specified, this command returns the current value
332              assigned to the key; if value is specified, this command assigns
333              that value to the key, and returns that value.
334
335       graphName arc source arc
336              Return the node the given arc begins at.
337
338       graphName arc target arc
339              Return the node the given arc ends at.
340
341       graphName arc move-source arc newsource
342              Changes the source node of the arc to newsource.
343
344       graphName arc move-target arc newtarget
345              Changes the target node of the arc to newtarget.
346
347       graphName arc move arc newsource newtarget
348              Changes  both  source  and target nodes of the arc to newsource,
349              and newtarget resp.
350
351       graphName arc unset arc key
352              Remove a keyed value from the arc arc. The method will do  noth‐
353              ing if the key does not exist.
354
355       graphName   arcs   ?-key   key?   ?-value  value?  ?-filter  cmdprefix?
356       ?-in|-out|-adj|-inner|-embedding nodelist?
357              Return a list of arcs in the graph. If no restriction is  speci‐
358              fied  a  list  containing all arcs is returned. Restrictions can
359              limit the list of returned arcs based on the nodes that are con‐
360              nected  by the arc, on the keyed values associated with the arc,
361              or both. A general filter command  can  be  used  as  well.  The
362              restrictions  that  involve connected nodes have a list of nodes
363              as argument, specified after the name of the restriction itself.
364
365              -in    Return a list of all arcs whose  target  is  one  of  the
366                     nodes in the nodelist.
367
368              -out   Return  a  list  of  all  arcs whose source is one of the
369                     nodes in the nodelist.
370
371              -adj   Return a list of all arcs adjacent to at least one of the
372                     nodes  in  the  nodelist.  This is the union of the nodes
373                     returned by -in and -out.
374
375              -inner Return a list of all arcs adjacent to two of the nodes in
376                     the  nodelist.  This  is  the set of arcs in the subgraph
377                     spawned by the specified nodes.
378
379              -embedding
380                     Return a list of all arcs adjacent to exactly one of  the
381                     nodes in the nodelist. This is the set of arcs connecting
382                     the subgraph spawned by the specified nodes to  the  rest
383                     of the graph.
384
385              -key key
386                     Limit  the  list  of arcs that are returned to those arcs
387                     that have an associated key key.
388
389              -value value
390                     This restriction can only be  used  in  combination  with
391                     -key.  It  limits  the  list of arcs that are returned to
392                     those arcs whose associated key key has the value value.
393
394              -filter cmdrefix
395                     Limit the list of arcs that are returned  to  those  arcs
396                     that  pass  the  test. The command in cmdprefix is called
397                     with two arguments, the name of the graph object, and the
398                     name  of  the arc in question. It is executed in the con‐
399                     text of the caller and has to  return  a  boolean  value.
400                     Arcs for which the command returns false are removed from
401                     the result list before it is returned to the caller.
402
403       The restrictions imposed by either -in, -out, -adj, -inner, or  -embed‐
404       ded  are  applied  first.  Specifying more than one of them is illegal.
405       After that the restrictions set via  -key  (and  -value)  are  applied.
406       Specifying more than one -key (and -value) is illegal.  Any restriction
407       set through -filter is applied last. Specifying more than  one  -filter
408       is illegal.
409
410       graphName lappend key value
411              Appends  a  value (as a list) to one of the keyed values associ‐
412              ated with  the  graph.  Returns  the  new  value  given  to  the
413              attribute key.
414
415       graphName node append node key value
416              Appends  a  value  to one of the keyed values associated with an
417              node. Returns the new value given to the attribute key.
418
419       graphName node attr key
420
421       graphName node attr key -nodes list
422
423       graphName node attr key -glob globpattern
424
425       graphName node attr key -regexp repattern
426              This method retrieves the value of the attribute named key,  for
427              all  nodes  in the graph (matching the restriction specified via
428              one of the possible options) and having the specified attribute.
429
430              The result is a dictionary mapping from node names to the  value
431              of  attribute  key at that node.  Nodes not having the attribute
432              key, or not passing a specified restriction, are not  listed  in
433              the result.
434
435              The possible restrictions are:
436
437              -nodes The value is a list of nodes. Only the nodes mentioned in
438                     this list are searched for the attribute.
439
440              -glob  The value is a glob pattern. Only the nodes in the  graph
441                     whose  names  match  this  pattern  are  searched for the
442                     attribute.
443
444              -regexp
445                     The value is a regular expression. Only the nodes in  the
446                     graph whose names match this pattern are searched for the
447                     attribute.
448
449
450       graphName node degree ?-in|-out? node
451              Return the number of arcs adjacent to the specified node. If one
452              of the restrictions -in or -out is given only the incoming resp.
453              outgoing arcs are counted.
454
455       graphName node delete node ?node ...?
456              Remove the specified nodes from the graph.  All  of  the  nodes'
457              arcs will be removed as well to prevent unconnected arcs.
458
459       graphName node exists node
460              Return true if the specified node exists in the graph.
461
462       graphName node get node key
463              Return the value associated with the key key for the node.
464
465       graphName node getall node ?pattern?
466              Returns a dictionary (suitable for use with [array set]) for the
467              node.  If the pattern is specified  only  the  attributes  whose
468              names match the pattern will be part of the returned dictionary.
469              The pattern is a glob pattern.
470
471       graphName node keys node ?pattern?
472              Returns a list of keys for the node.  If the pattern  is  speci‐
473              fied  only  the attributes whose names match the pattern will be
474              part of the returned list. The pattern is a glob pattern.
475
476       graphName node keyexists node key
477              Return true if the specified key exists for the node.
478
479       graphName node insert ?child?
480              Insert a node named child into the graph. The nodes has no  arcs
481              connected  to  it. If the name of the new child is not specified
482              the system will generate a unique name of the form nodex.
483
484       graphName node lappend node key value
485              Appends a value (as a list) to one of the keyed  values  associ‐
486              ated  with an node. Returns the new value given to the attribute
487              key.
488
489       graphName node opposite node arc
490              Return the node at the other end of the specified arc, which has
491              to be adjacent to the given node.
492
493       graphName node rename node newname
494              Renames  the  node node to newname. An error is thrown if either
495              the node does not exist, or a node with name newname does exist.
496              The result of the command is the new name of the node.
497
498       graphName node set node key ?value?
499              Set  or  get  one  of the keyed values associated with a node. A
500              node may have any number of keyed values associated with it.  If
501              value  is  not specified, this command returns the current value
502              assigned to the key; if value is specified, this command assigns
503              that value to the key.
504
505       graphName node unset node key
506              Remove  a  keyed  value  from  the node node. The method will do
507              nothing if the key does not exist.
508
509       graphName  nodes  ?-key  key?  ?-value   value?   ?-filter   cmdprefix?
510       ?-in|-out|-adj|-inner|-embedding nodelist?
511              Return  a list of nodes in the graph. Restrictions can limit the
512              list of returned nodes based on neighboring nodes, or  based  on
513              the keyed values associated with the node. The restrictions that
514              involve neighboring nodes have a  list  of  nodes  as  argument,
515              specified after the name of the restriction itself.
516
517              The  possible  restrictions are the same as for method arcs. The
518              set of nodes to return is computed as the union  of  all  source
519              and target nodes for all the arcs satisfying the restrictions as
520              defined for arcs.
521
522              Note that here the -filter command is applied  to  the  list  of
523              nodes, not arcs.
524
525       graphName get key
526              Return the value associated with the key key for the graph.
527
528       graphName getall ?pattern?
529              Returns a dictionary (suitable for use with [array set]) for the
530              whole graph.  If the pattern is specified  only  the  attributes
531              whose  names match the pattern will be part of the returned dic‐
532              tionary. The pattern is a glob pattern.
533
534       graphName keys ?pattern?
535              Returns a list of keys for the whole graph.  If the  pattern  is
536              specified only the attributes whose names match the pattern will
537              be part of the returned list. The pattern is a glob pattern.
538
539       graphName keyexists key
540              Return true if the specified key exists for the whole graph.
541
542       graphName serialize ?node...?
543              This method serializes the sub-graph spanned up by the nodes. In
544              other  words  it  returns a tcl value completely describing that
545              graph. If no nodes are specified the whole graph will be serial‐
546              ized.   This  allows, for example, the transfer of graph objects
547              (or parts thereof) over arbitrary  channels,  persistence,  etc.
548              This  method is also the basis for both the copy constructor and
549              the assignment operator.
550
551              The result of this method has to be semantically identical  over
552              all  implementations  of  the graph interface. This is what will
553              enable us to copy graph data between  different  implementations
554              of the same interface.
555
556              The  result is a list containing a multiple of three items, plus
557              one!  In other words, '[llength $serial] % 3 == 1'. Valid values
558              include 1, 4, 7, ...
559
560              The  last  element  of  the  list is a dictionary containing the
561              attributes associated with the whole graph.  Regarding the other
562              elements; each triple consists of
563
564              [1]    The name of the node to be described,
565
566              [2]    A  dictionary  containing  the attributes associated with
567                     the node,
568
569              [3]    And a list describing all the arcs starting at that node.
570
571       The elements of the arc list are lists containing three elements  each,
572       i.e.
573
574              [1]    The name of the arc described by the element,
575
576              [2]    A reference to the destination node of the arc. This ref‐
577                     erence is an integer number given the index of that  node
578                     in  the  main  serialization  list. As that it is greater
579                     than or equal to zero, less than the length of the  seri‐
580                     alization,  and  a multiple of three.  Note: For internal
581                     consistency no arc name may be used twice, whether in the
582                     same  node,  or at some other node. This is a global con‐
583                     sistency requirement for the serialization.
584
585              [3]    And a dictionary  containing  the  attributes  associated
586                     with the arc.
587
588       For  all  attribute  dictionaries  they  keys  are  the  names  of  the
589       attributes, and the values are the values for each name.
590
591       Note: The order of the nodes in the serialization has no relevance, nor
592       has the order of the arcs per node.
593
594           # A possible serialization for the graph structure
595           #
596           #        d -----> %2
597           #       /         ^ \\
598           #      /         /   \\
599           #     /         b     \\
600           #    /         /       \\
601           #  %1 <- a - %0         e
602           #    ^         \\      /
603           #     \\        c     /
604           #      \\        \\  /
605           #       \\        v v
606           #        f ------ %3
607           # is
608           #
609           # %3 {} {{f 6 {}}} %0 {} {{a 6 {}} {b 9 {}} {c 0 {}}} %1 {} {{d 9 {}}} %2 {} {{e 0 {}}} {}
610           #
611           # This assumes that the graph has no attribute data.
612
613
614
615       graphName set key ?value?
616              Set  or  get  one of the keyed values associated with a graph. A
617              graph may have any number of keyed values associated with it. If
618              value  is  not specified, this command returns the current value
619              assigned to the key; if value is specified, this command assigns
620              that value to the key.
621
622       graphName swap node1 node2
623              Swap the position of node1 and node2 in the graph.
624
625       graphName unset key
626              Remove  a keyed value from the graph. The method will do nothing
627              if the key does not exist.
628
629       graphName walk node ?-order order? ?-type type? ?-dir direction?  -com‐
630       mand cmd
631              Perform  a breadth-first or depth-first walk of the graph start‐
632              ing at the node node going in either the direction  of  outgoing
633              or opposite to the incoming arcs.
634
635              The type of walk, breadth-first or depth-first, is determined by
636              the value of type; bfs indicates  breadth-first,  dfs  indicates
637              depth-first.  Depth-first is the default.
638
639              The  order  of  the walk, pre-order, post-order or both-order is
640              determined by the value of order; pre indicates pre-order,  post
641              indicates  post-order,  both  indicates both-order. Pre-order is
642              the default. Pre-order walking means  that  a  node  is  visited
643              before  any  of  its neighbors (as defined by the direction, see
644              below). Post-order walking means that a parent is visited  after
645              any  of  its  neighbors. Both-order walking means that a node is
646              visited before and after any of its neighbors.  The  combination
647              of a bread-first walk with post- or both-order is illegal.
648
649              The  direction  of  the  walk is determined by the value of dir;
650              backward indicates the direction opposite to the incoming  arcs,
651              forward indicates the direction of the outgoing arcs.
652
653              As  the  walk  progresses,  the command cmd will be evaluated at
654              each node, with the mode of the call (enter or leave) and values
655              graphName  and the name of the current node appended. For a pre-
656              order walk, all nodes are entered, for a  post-order  all  nodes
657              are  left. In a both-order walk the first visit of a node enters
658              it, the second visit leaves it.
659

Changes for 2.0

661       The following noteworthy changes have occurred:
662
663       [1]    The API for accessing attributes and their values has been  sim‐
664              plified.
665
666              All  functionality  regarding  the  default attribute "data" has
667              been removed. This default attribute does not exist anymore. All
668              accesses to attributes have to specify the name of the attribute
669              in question. This backward incompatible  change  allowed  us  to
670              simplify the signature of all methods handling attributes.
671
672              Especially the flag -key is not required anymore, even more, its
673              use is now forbidden. Please read the documentation for the  arc
674              and  node  methods  set,  get,  getall,  unset, append, lappend,
675              keyexists and keys for a description of the new API's.
676
677       [2]    The methods keys and getall now take an optional  pattern  argu‐
678              ment  and will return only attribute data for keys matching this
679              pattern.
680
681       [3]    Arcs and nodes can now be renamed. See the documentation for the
682              methods arc rename and node rename.
683
684       [4]    The structure has been extended with API's for the serialization
685              and deserialization of graph objects, and a number of operations
686              based on them (graph assignment, copy construction).
687
688              Please read the documentation for the methods serialize, deseri‐
689              alize, =, and -->, and the documentation on the construction  of
690              graph objects.
691
692              Beyond  the  copying of whole graph objects these new API's also
693              enable the transfer of graph objects over arbitrary channels and
694              for easy persistence.
695
696       [5]    A  new method, attr, was added to both arc and node allowing the
697              query and retrieval of attribute data without regard to arc  and
698              node relationships.
699
700       [6]    Both  methods arcs and nodes have been extended with the ability
701              to select arcs and nodes based on an  arbitrary  filtering  cri‐
702              terium.
703

KEYWORDS

705       cgraph, graph, serialization
706
708       Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
709
710
711
712
713struct                                2.1                     struct::graph(n)
Impressum