1struct::graph(n) Tcl Data Structures struct::graph(n)
2______________________________________________________________________________
6
8 struct::graph - Create and manipulate directed graph objects
9
11 package require Tcl 8.2
12 package require struct::graph ?2.1?
14 package require struct::list ?1.5?
16 ::struct::graph ?graphName? ?=|:=|as|deserialize source?
18 graphName option ?arg arg ...?
20 graphName = sourcegraph
22 graphName --> destgraph
24 graphName append key value
26 graphName deserialize serialization
28 graphName destroy
30 graphName arc append arc key value
32 graphName arc attr key
34 graphName arc attr key -arcs list
36 graphName arc attr key -glob globpattern
38 graphName arc attr key -regexp repattern
40 graphName arc delete arc ?arc ...?
42 graphName arc exists arc
44 graphName arc get arc key
46 graphName arc getall arc ?pattern?
48 graphName arc keys arc ?pattern?
50 graphName arc keyexists arc key
52 graphName arc insert start end ?child?
54 graphName arc lappend arc key value
56 graphName arc rename arc newname
58 graphName arc set arc key ?value?
60 graphName arc source arc
62 graphName arc target arc
64 graphName arc move-source arc newsource
66 graphName arc move-target arc newtarget
68 graphName arc move arc newsource newtarget
70 graphName arc unset arc key
72 graphName arcs ?-key key? ?-value value? ?-filter cmdprefix?
74 ?-in|-out|-adj|-inner|-embedding nodelist?
75 graphName lappend key value
77 graphName node append node key value
79 graphName node attr key
81 graphName node attr key -nodes list
83 graphName node attr key -glob globpattern
85 graphName node attr key -regexp repattern
87 graphName node degree ?-in|-out? node
89 graphName node delete node ?node ...?
91 graphName node exists node
93 graphName node get node key
95 graphName node getall node ?pattern?
97 graphName node keys node ?pattern?
99 graphName node keyexists node key
101 graphName node insert ?child?
103 graphName node lappend node key value
105 graphName node opposite node arc
107 graphName node rename node newname
109 graphName node set node key ?value?
111 graphName node unset node key
113 graphName nodes ?-key key? ?-value value? ?-filter cmdprefix?
115 ?-in|-out|-adj|-inner|-embedding nodelist?
116 graphName get key
118 graphName getall ?pattern?
120 graphName keys ?pattern?
122 graphName keyexists key
124 graphName serialize ?node...?
126 graphName set key ?value?
128 graphName swap node1 node2
130 graphName unset key
132 graphName walk node ?-order order? ?-type type? ?-dir direction? -com‐
134 mand cmd
135_________________________________________________________________
137
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 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 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 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 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 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 The main command of the package is:
171 ::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 graphName option ?arg arg ...?
179 Option and the args determine the exact behavior of the
180 command.
181 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 In other words
190 ::struct::graph mygraph = b
193 is equivalent to
196 ::struct::graph mygraph
199 mygraph = b
200 and
203 ::struct::graph mygraph deserialize $b
206 is equivalent to
209 ::struct::graph mygraph
212 mygraph deserialize $b
213 The following commands are possible for graph objects:
216 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 This operation is in effect equivalent to
224 graphName deserialize [sourcegraph serialize]
227 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 This operation is in effect equivalent to
236 destgraph deserialize [graphName serialize]
239 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 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 graphName destroy
251 Destroy the graph, including its storage space and associated
252 command.
253 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 graphName arc attr key
259 graphName arc attr key -arcs list
261 graphName arc attr key -glob globpattern
263 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 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 The possible restrictions are:
275 -arcs The value is a list of arcs. Only the arcs mentioned in
277 this list are searched for the attribute.
278 -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 -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 graphName arc delete arc ?arc ...?
290 Remove the specified arcs from the graph.
291 graphName arc exists arc
293 Return true if the specified arc exists in the graph.
294 graphName arc get arc key
296 Return the value associated with the key key for the arc.
297 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 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 graphName arc keyexists arc key
310 Return true if the specified key exists for the arc.
311 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 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 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 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 graphName arc source arc
336 Return the node the given arc begins at.
337 graphName arc target arc
339 Return the node the given arc ends at.
340 graphName arc move-source arc newsource
342 Changes the source node of the arc to newsource.
343 graphName arc move-target arc newtarget
345 Changes the target node of the arc to newtarget.
346 graphName arc move arc newsource newtarget
348 Changes both source and target nodes of the arc to newsource,
349 and newtarget resp.
350 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 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 -in Return a list of all arcs whose target is one of the
366 nodes in the nodelist.
367 -out Return a list of all arcs whose source is one of the
369 nodes in the nodelist.
370 -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 -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 -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 -key key
386 Limit the list of arcs that are returned to those arcs
387 that have an associated key key.
388 -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 -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 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 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 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 graphName node attr key
420 graphName node attr key -nodes list
422 graphName node attr key -glob globpattern
424 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 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 The possible restrictions are:
436 -nodes The value is a list of nodes. Only the nodes mentioned in
438 this list are searched for the attribute.
439 -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 -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 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 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 graphName node exists node
460 Return true if the specified node exists in the graph.
461 graphName node get node key
463 Return the value associated with the key key for the node.
464 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 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 graphName node keyexists node key
477 Return true if the specified key exists for the node.
478 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 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 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 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 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 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 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 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 Note that here the -filter command is applied to the list of
523 nodes, not arcs.
524 graphName get key
526 Return the value associated with the key key for the graph.
527 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 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 graphName keyexists key
540 Return true if the specified key exists for the whole graph.
541 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 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 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 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 [1] The name of the node to be described,
565 [2] A dictionary containing the attributes associated with
567 the node,
568 [3] And a list describing all the arcs starting at that node.
570 The elements of the arc list are lists containing three elements each,
572 i.e.
573 [1] The name of the arc described by the element,
575 [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 [3] And a dictionary containing the attributes associated
586 with the arc.
587 For all attribute dictionaries they keys are the names of the
589 attributes, and the values are the values for each name.
590 Note: The order of the nodes in the serialization has no relevance, nor
592 has the order of the arcs per node.
593 # 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 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 graphName swap node1 node2
623 Swap the position of node1 and node2 in the graph.
624 graphName unset key
626 Remove a keyed value from the graph. The method will do nothing
627 if the key does not exist.
628 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 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 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 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 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
661 The following noteworthy changes have occurred:
662 [1] The API for accessing attributes and their values has been sim‐
664 plified.
665 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 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 [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 [3] Arcs and nodes can now be renamed. See the documentation for the
682 methods arc rename and node rename.
683 [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 Please read the documentation for the methods serialize, deseri‐
689 alize, =, and -->, and the documentation on the construction of
690 graph objects.
691 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 [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 [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
705 cgraph, graph, serialization
706
708 Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
709struct 2.1 struct::graph(n)