1 2[//000000001]: # (struct::graph\_v1 \- Tcl Data Structures) 3[//000000002]: # (Generated from file 'graph1\.man' by tcllib/doctools with format 'markdown') 4[//000000003]: # (Copyright © 2002 Andreas Kupries <andreas\_kupries@users\.sourceforge\.net>) 5[//000000004]: # (struct::graph\_v1\(n\) 1\.2\.1 tcllib "Tcl Data Structures") 6 7<hr> [ <a href="../../../../toc.md">Main Table Of Contents</a> | <a 8href="../../../toc.md">Table Of Contents</a> | <a 9href="../../../../index.md">Keyword Index</a> | <a 10href="../../../../toc0.md">Categories</a> | <a 11href="../../../../toc1.md">Modules</a> | <a 12href="../../../../toc2.md">Applications</a> ] <hr> 13 14# NAME 15 16struct::graph\_v1 \- Create and manipulate directed graph objects 17 18# <a name='toc'></a>Table Of Contents 19 20 - [Table Of Contents](#toc) 21 22 - [Synopsis](#synopsis) 23 24 - [Description](#section1) 25 26 - [Bugs, Ideas, Feedback](#section2) 27 28 - [Keywords](#keywords) 29 30 - [Category](#category) 31 32 - [Copyright](#copyright) 33 34# <a name='synopsis'></a>SYNOPSIS 35 36package require Tcl 8\.2 37package require struct::graph ?1\.2\.1? 38 39[__graphName__ *option* ?*arg arg \.\.\.*?](#1) 40[*graphName* __destroy__](#2) 41[*graphName* __arc append__ *arc* ?\-key *key*? *value*](#3) 42[*graphName* __arc delete__ *arc* ?*arc* \.\.\.?](#4) 43[*graphName* __arc exists__ *arc*](#5) 44[*graphName* __arc get__ *arc* ?\-key *key*?](#6) 45[*graphName* __arc getall__ *arc*](#7) 46[*graphName* __arc keys__ *arc*](#8) 47[*graphName* __arc keyexists__ *arc* ?\-key *key*?](#9) 48[*graphName* __arc insert__ *start* *end* ?*child*?](#10) 49[*graphName* __arc lappend__ *arc* ?\-key *key*? *value*](#11) 50[*graphName* __arc set__ *arc* ?\-key *key*? ?*value*?](#12) 51[*graphName* __arc source__ *arc*](#13) 52[*graphName* __arc target__ *arc*](#14) 53[*graphName* __arc unset__ *arc* ?\-key *key*?](#15) 54[*graphName* __arcs__ ?\-key *key*? ?\-value *value*? ?\-in|\-out|\-adj|\-inner|\-embedding *nodelist*?](#16) 55[*graphName* __node append__ *node* ?\-key *key*? *value*](#17) 56[*graphName* __node degree__ ?\-in|\-out? *node*](#18) 57[*graphName* __node delete__ *node* ?*node* \.\.\.?](#19) 58[*graphName* __node exists__ *node*](#20) 59[*graphName* __node get__ *node* ?\-key *key*?](#21) 60[*graphName* __node getall__ *node*](#22) 61[*graphName* __node keys__ *node*](#23) 62[*graphName* __node keyexists__ *node* ?\-key *key*?](#24) 63[*graphName* __node insert__ ?*child*?](#25) 64[*graphName* __node lappend__ *node* ?\-key *key*? *value*](#26) 65[*graphName* __node opposite__ *node* *arc*](#27) 66[*graphName* __node set__ *node* ?\-key *key*? ?*value*?](#28) 67[*graphName* __node unset__ *node* ?\-key *key*?](#29) 68[*graphName* __nodes__ ?\-key *key*? ?\-value *value*? ?\-in|\-out|\-adj|\-inner|\-embedding *nodelist*?](#30) 69[*graphName* __get__ ?\-key *key*?](#31) 70[*graphName* __getall__](#32) 71[*graphName* __keys__](#33) 72[*graphName* __keyexists__ ?\-key *key*?](#34) 73[*graphName* __set__ ?\-key *key*? ?*value*?](#35) 74[*graphName* __swap__ *node1* *node2*](#36) 75[*graphName* __unset__ ?\-key *key*?](#37) 76[*graphName* __walk__ *node* ?\-order *order*? ?\-type *type*? ?\-dir *direction*? \-command *cmd*](#38) 77 78# <a name='description'></a>DESCRIPTION 79 80The __::struct::graph__ command creates a new graph object with an 81associated global Tcl command whose name is *graphName*\. This command may be 82used to invoke various operations on the graph\. It has the following general 83form: 84 85 - <a name='1'></a>__graphName__ *option* ?*arg arg \.\.\.*? 86 87 *Option* and the *arg*s determine the exact behavior of the command\. 88 89A directed graph is a structure containing two collections of elements, called 90*nodes* and *arcs* respectively, together with a relation \("connectivity"\) 91that places a general structure upon the nodes and arcs\. 92 93Each arc is connected to two nodes, one of which is called the *source* and 94the other the *target*\. This imposes a direction upon the arc, which is said 95to go from the source to the target\. It is allowed that source and target of an 96arc are the same node\. Such an arc is called a *loop*\. Whenever a node is 97source or target of an arc both are said to be *adjacent*\. This extends into a 98relation between nodes, i\.e\. if two nodes are connected through at least one arc 99they are said to be *adjacent* too\. 100 101Each node can be the source and target for any number of arcs\. The former are 102called the *outgoing arcs* of the node, the latter the *incoming arcs* of 103the node\. The number of edges in either set is called the *in\-* resp\. the 104*out\-degree* of the node\. 105 106In addition to maintaining the node and arc relationships, this graph 107implementation allows any number of keyed values to be associated with each node 108and arc\. 109 110The following commands are possible for graph objects: 111 112 - <a name='2'></a>*graphName* __destroy__ 113 114 Destroy the graph, including its storage space and associated command\. 115 116 - <a name='3'></a>*graphName* __arc append__ *arc* ?\-key *key*? *value* 117 118 Appends a *value* to one of the keyed values associated with an *arc*\. 119 If no *key* is specified, the key __data__ is assumed\. 120 121 - <a name='4'></a>*graphName* __arc delete__ *arc* ?*arc* \.\.\.? 122 123 Remove the specified arcs from the graph\. 124 125 - <a name='5'></a>*graphName* __arc exists__ *arc* 126 127 Return true if the specified *arc* exists in the graph\. 128 129 - <a name='6'></a>*graphName* __arc get__ *arc* ?\-key *key*? 130 131 Return the value associated with the key *key* for the *arc*\. If no key 132 is specified, the key __data__ is assumed\. 133 134 - <a name='7'></a>*graphName* __arc getall__ *arc* 135 136 Returns a serialized list of key/value pairs \(suitable for use with 137 \[__array set__\]\) for the *arc*\. 138 139 - <a name='8'></a>*graphName* __arc keys__ *arc* 140 141 Returns a list of keys for the *arc*\. 142 143 - <a name='9'></a>*graphName* __arc keyexists__ *arc* ?\-key *key*? 144 145 Return true if the specified *key* exists for the *arc*\. If no *key* 146 is specified, the key __data__ is assumed\. 147 148 - <a name='10'></a>*graphName* __arc insert__ *start* *end* ?*child*? 149 150 Insert an arc named *child* into the graph beginning at the node *start* 151 and ending at the node *end*\. If the name of the new arc is not specified 152 the system will generate a unique name of the form *arc**x*\. 153 154 - <a name='11'></a>*graphName* __arc lappend__ *arc* ?\-key *key*? *value* 155 156 Appends a *value* \(as a list\) to one of the keyed values associated with 157 an *arc*\. If no *key* is specified, the key __data__ is assumed\. 158 159 - <a name='12'></a>*graphName* __arc set__ *arc* ?\-key *key*? ?*value*? 160 161 Set or get one of the keyed values associated with an arc\. If no key is 162 specified, the key __data__ is assumed\. Each arc that is added to a 163 graph has the empty string assigned to the key __data__ automatically\. 164 An arc may have any number of keyed values associated with it\. If *value* 165 is not specified, this command returns the current value assigned to the 166 key; if *value* is specified, this command assigns that value to the key\. 167 168 - <a name='13'></a>*graphName* __arc source__ *arc* 169 170 Return the node the given *arc* begins at\. 171 172 - <a name='14'></a>*graphName* __arc target__ *arc* 173 174 Return the node the given *arc* ends at\. 175 176 - <a name='15'></a>*graphName* __arc unset__ *arc* ?\-key *key*? 177 178 Remove a keyed value from the arc *arc*\. If no key is specified, the key 179 __data__ is assumed\. 180 181 - <a name='16'></a>*graphName* __arcs__ ?\-key *key*? ?\-value *value*? ?\-in|\-out|\-adj|\-inner|\-embedding *nodelist*? 182 183 Return a list of arcs in the graph\. If no restriction is specified a list 184 containing all arcs is returned\. Restrictions can limit the list of returned 185 arcs based on the nodes that are connected by the arc, on the keyed values 186 associated with the arc, or both\. The restrictions that involve connected 187 nodes have a list of nodes as argument, specified after the name of the 188 restriction itself\. 189 190 * __\-in__ 191 192 Return a list of all arcs whose target is one of the nodes in the 193 *nodelist*\. 194 195 * __\-out__ 196 197 Return a list of all arcs whose source is one of the nodes in the 198 *nodelist*\. 199 200 * __\-adj__ 201 202 Return a list of all arcs adjacent to at least one of the nodes in the 203 *nodelist*\. This is the union of the nodes returned by __\-in__ and 204 __\-out__\. 205 206 * __\-inner__ 207 208 Return a list of all arcs adjacent to two of the nodes in the 209 *nodelist*\. This is the set of arcs in the subgraph spawned by the 210 specified nodes\. 211 212 * __\-embedding__ 213 214 Return a list of all arcs adjacent to exactly one of the nodes in the 215 *nodelist*\. This is the set of arcs connecting the subgraph spawned by 216 the specified nodes to the rest of the graph\. 217 218 * __\-key__ *key* 219 220 Limit the list of arcs that are returned to those arcs that have an 221 associated key *key*\. 222 223 * __\-value__ *value* 224 225 This restriction can only be used in combination with __\-key__\. It 226 limits the list of arcs that are returned to those arcs whose associated 227 key *key* has the value *value*\. 228 229 The restrictions imposed by either __\-in__, __\-out__, __\-adj__, 230 __\-inner__, or __\-embedded__ are applied first\. Specifying more than 231 one of them is illegal\. At last the restrictions set via __\-key__ \(and 232 __\-value__\) are applied\. Specifying more than one __\-key__ \(and 233 __\-value__\) is illegal\. 234 235 - <a name='17'></a>*graphName* __node append__ *node* ?\-key *key*? *value* 236 237 Appends a *value* to one of the keyed values associated with an *node*\. 238 If no *key* is specified, the key __data__ is assumed\. 239 240 - <a name='18'></a>*graphName* __node degree__ ?\-in|\-out? *node* 241 242 Return the number of arcs adjacent to the specified *node*\. If one of the 243 restrictions __\-in__ or __\-out__ is given only the incoming resp\. 244 outgoing arcs are counted\. 245 246 - <a name='19'></a>*graphName* __node delete__ *node* ?*node* \.\.\.? 247 248 Remove the specified nodes from the graph\. All of the nodes' arcs will be 249 removed as well to prevent unconnected arcs\. 250 251 - <a name='20'></a>*graphName* __node exists__ *node* 252 253 Return true if the specified *node* exists in the graph\. 254 255 - <a name='21'></a>*graphName* __node get__ *node* ?\-key *key*? 256 257 Return the value associated with the key *key* for the *node*\. If no key 258 is specified, the key __data__ is assumed\. 259 260 - <a name='22'></a>*graphName* __node getall__ *node* 261 262 Returns a serialized list of key/value pairs \(suitable for use with 263 \[__array set__\]\) for the *node*\. 264 265 - <a name='23'></a>*graphName* __node keys__ *node* 266 267 Returns a list of keys for the *node*\. 268 269 - <a name='24'></a>*graphName* __node keyexists__ *node* ?\-key *key*? 270 271 Return true if the specified *key* exists for the *node*\. If no *key* 272 is specified, the key __data__ is assumed\. 273 274 - <a name='25'></a>*graphName* __node insert__ ?*child*? 275 276 Insert a node named *child* into the graph\. The nodes has no arcs 277 connected to it\. If the name of the new child is not specified the system 278 will generate a unique name of the form *node**x*\. 279 280 - <a name='26'></a>*graphName* __node lappend__ *node* ?\-key *key*? *value* 281 282 Appends a *value* \(as a list\) to one of the keyed values associated with 283 an *node*\. If no *key* is specified, the key __data__ is assumed\. 284 285 - <a name='27'></a>*graphName* __node opposite__ *node* *arc* 286 287 Return the node at the other end of the specified *arc*, which has to be 288 adjacent to the given *node*\. 289 290 - <a name='28'></a>*graphName* __node set__ *node* ?\-key *key*? ?*value*? 291 292 Set or get one of the keyed values associated with a node\. If no key is 293 specified, the key __data__ is assumed\. Each node that is added to a 294 graph has the empty string assigned to the key __data__ automatically\. A 295 node may have any number of keyed values associated with it\. If *value* is 296 not specified, this command returns the current value assigned to the key; 297 if *value* is specified, this command assigns that value to the key\. 298 299 - <a name='29'></a>*graphName* __node unset__ *node* ?\-key *key*? 300 301 Remove a keyed value from the node *node*\. If no key is specified, the key 302 __data__ is assumed\. 303 304 - <a name='30'></a>*graphName* __nodes__ ?\-key *key*? ?\-value *value*? ?\-in|\-out|\-adj|\-inner|\-embedding *nodelist*? 305 306 Return a list of nodes in the graph\. Restrictions can limit the list of 307 returned nodes based on neighboring nodes, or based on the keyed values 308 associated with the node\. The restrictions that involve neighboring nodes 309 have a list of nodes as argument, specified after the name of the 310 restriction itself\. 311 312 The possible restrictions are the same as for method __arcs__\. The set 313 of nodes to return is computed as the union of all source and target nodes 314 for all the arcs satisfying the restriction as defined for __arcs__\. 315 316 - <a name='31'></a>*graphName* __get__ ?\-key *key*? 317 318 Return the value associated with the key *key* for the graph\. If no key is 319 specified, the key __data__ is assumed\. 320 321 - <a name='32'></a>*graphName* __getall__ 322 323 Returns a serialized list of key/value pairs \(suitable for use with 324 \[__array set__\]\) for the whole graph\. 325 326 - <a name='33'></a>*graphName* __keys__ 327 328 Returns a list of keys for the whole graph\. 329 330 - <a name='34'></a>*graphName* __keyexists__ ?\-key *key*? 331 332 Return true if the specified *key* exists for the whole graph\. If no 333 *key* is specified, the key __data__ is assumed\. 334 335 - <a name='35'></a>*graphName* __set__ ?\-key *key*? ?*value*? 336 337 Set or get one of the keyed values associated with a graph\. If no key is 338 specified, the key __data__ is assumed\. Each graph has the empty string 339 assigned to the key __data__ automatically\. A graph may have any number 340 of keyed values associated with it\. If *value* is not specified, this 341 command returns the current value assigned to the key; if *value* is 342 specified, this command assigns that value to the key\. 343 344 - <a name='36'></a>*graphName* __swap__ *node1* *node2* 345 346 Swap the position of *node1* and *node2* in the graph\. 347 348 - <a name='37'></a>*graphName* __unset__ ?\-key *key*? 349 350 Remove a keyed value from the graph\. If no key is specified, the key 351 __data__ is assumed\. 352 353 - <a name='38'></a>*graphName* __walk__ *node* ?\-order *order*? ?\-type *type*? ?\-dir *direction*? \-command *cmd* 354 355 Perform a breadth\-first or depth\-first walk of the graph starting at the 356 node *node* going in either the direction of outgoing or opposite to the 357 incoming arcs\. 358 359 The type of walk, breadth\-first or depth\-first, is determined by the value 360 of *type*; __bfs__ indicates breadth\-first, __dfs__ indicates 361 depth\-first\. Depth\-first is the default\. 362 363 The order of the walk, pre\-order, post\-order or both\-order is determined by 364 the value of *order*; __pre__ indicates pre\-order, __post__ 365 indicates post\-order, __both__ indicates both\-order\. Pre\-order is the 366 default\. Pre\-order walking means that a node is visited before any of its 367 neighbors \(as defined by the *direction*, see below\)\. Post\-order walking 368 means that a parent is visited after any of its neighbors\. Both\-order 369 walking means that a node is visited before *and* after any of its 370 neighbors\. The combination of a bread\-first walk with post\- or both\-order is 371 illegal\. 372 373 The direction of the walk is determined by the value of *dir*; 374 __backward__ indicates the direction opposite to the incoming arcs, 375 __forward__ indicates the direction of the outgoing arcs\. 376 377 As the walk progresses, the command *cmd* will be evaluated at each node, 378 with the mode of the call \(__enter__ or __leave__\) and values 379 *graphName* and the name of the current node appended\. For a pre\-order 380 walk, all nodes are __enter__ed, for a post\-order all nodes are left\. In 381 a both\-order walk the first visit of a node __enter__s it, the second 382 visit __leave__s it\. 383 384# <a name='section2'></a>Bugs, Ideas, Feedback 385 386This document, and the package it describes, will undoubtedly contain bugs and 387other problems\. Please report such in the category *struct :: graph* of the 388[Tcllib Trackers](http://core\.tcl\.tk/tcllib/reportlist)\. Please also report 389any ideas for enhancements you may have for either package and/or documentation\. 390 391When proposing code changes, please provide *unified diffs*, i\.e the output of 392__diff \-u__\. 393 394Note further that *attachments* are strongly preferred over inlined patches\. 395Attachments can be made by going to the __Edit__ form of the ticket 396immediately after its creation, and then using the left\-most button in the 397secondary navigation bar\. 398 399# <a name='keywords'></a>KEYWORDS 400 401[cgraph](\.\./\.\./\.\./\.\./index\.md\#cgraph), 402[graph](\.\./\.\./\.\./\.\./index\.md\#graph) 403 404# <a name='category'></a>CATEGORY 405 406Data structures 407 408# <a name='copyright'></a>COPYRIGHT 409 410Copyright © 2002 Andreas Kupries <andreas\_kupries@users\.sourceforge\.net> 411