1[comment {-*- tcl -*-}] 2[manpage_begin {struct::graph v1} n 1.2.1] 3[copyright {2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>}] 4[moddesc {Tcl Data Structures}] 5[titledesc {Create and manipulate directed graph objects}] 6[category {Data structures}] 7[require Tcl 8.2] 8[require struct::graph [opt 1.2.1]] 9[description] 10[para] 11 12The [cmd ::struct::graph] command creates a new graph object with an 13associated global Tcl command whose name is [arg graphName]. This 14command may be used to invoke various operations on the graph. It has 15the following general form: 16 17[list_begin definitions] 18[call [cmd graphName] [arg option] [opt [arg "arg arg ..."]]] 19 20[arg Option] and the [arg arg]s determine the exact behavior of the 21command. 22 23[list_end] 24 25[para] 26 27A directed graph is a structure containing two collections of 28elements, called [emph nodes] and [emph arcs] respectively, together 29with a relation ("connectivity") that places a general structure upon 30the nodes and arcs. 31 32[para] 33 34Each arc is connected to two nodes, one of which is called the 35 36[emph source] and the other the [emph target]. This imposes a 37direction upon the arc, which is said to go from the source to the 38target. It is allowed that source and target of an arc are the same 39node. Such an arc is called a [emph loop]. Whenever a node is source 40or target of an arc both are said to be [emph adjacent]. This extends 41into a relation between nodes, i.e. if two nodes are connected through 42at least one arc they are said to be [emph adjacent] too. 43 44[para] 45 46Each node can be the source and target for any number of arcs. The 47former are called the [emph {outgoing arcs}] of the node, the latter 48the [emph {incoming arcs}] of the node. The number of edges in either 49set is called the [emph in-] resp. the [emph out-degree] of the node. 50 51[para] 52 53In addition to maintaining the node and arc relationships, this graph 54implementation allows any number of keyed values to be associated with 55each node and arc. 56 57[para] 58 59The following commands are possible for graph objects: 60 61[list_begin definitions] 62 63[call [arg graphName] [method destroy]] 64 65Destroy the graph, including its storage space and associated command. 66 67[call [arg graphName] [method {arc append}] [arg arc] [opt "-key [arg key]"] [arg value]] 68 69Appends a [arg value] to one of the keyed values associated with an 70[arg arc]. If no [arg key] is specified, the key [const data] is 71assumed. 72 73 74[call [arg graphName] [method {arc delete}] [arg arc] [opt "[arg arc] ..."]] 75 76Remove the specified arcs from the graph. 77 78 79[call [arg graphName] [method {arc exists}] [arg arc]] 80 81Return true if the specified [arg arc] exists in the graph. 82 83 84[call [arg graphName] [method {arc get}] [arg arc] [opt "-key [arg key]"]] 85 86Return the value associated with the key [arg key] for the [arg arc]. 87If no key is specified, the key [const data] is assumed. 88 89[call [arg graphName] [method {arc getall}] [arg arc]] 90 91Returns a serialized list of key/value pairs (suitable for use with 92[lb][cmd {array set}][rb]) for the [arg arc]. 93 94 95[call [arg graphName] [method {arc keys}] [arg arc]] 96 97Returns a list of keys for the [arg arc]. 98 99 100[call [arg graphName] [method {arc keyexists}] [arg arc] [opt "-key [arg key]"]] 101 102Return true if the specified [arg key] exists for the [arg arc]. If no 103[arg key] is specified, the key [const data] is assumed. 104 105 106[call [arg graphName] [method {arc insert}] [arg start] [arg end] [opt [arg child]]] 107 108Insert an arc named [arg child] into the graph beginning at the node 109[arg start] and ending at the node [arg end]. If the name of the new 110arc is not specified the system will generate a unique name of the 111form [emph arc][arg x]. 112 113 114[call [arg graphName] [method {arc lappend}] [arg arc] [opt "-key [arg key]"] [arg value]] 115 116Appends a [arg value] (as a list) to one of the keyed values 117associated with an [arg arc]. If no [arg key] is specified, the key 118[const data] is assumed. 119 120 121[call [arg graphName] [method {arc set}] [arg arc] [opt "-key [arg key]"] [opt [arg value]]] 122 123Set or get one of the keyed values associated with an arc. If no key 124is specified, the key [const data] is assumed. Each arc that is 125added to a graph has the empty string assigned to the key 126 127[const data] automatically. An arc may have any number of keyed 128values associated with it. If [arg value] is not specified, this 129command returns the current value assigned to the key; if [arg value] 130is specified, this command assigns that value to the key. 131 132 133[call [arg graphName] [method {arc source}] [arg arc]] 134 135Return the node the given [arg arc] begins at. 136 137 138[call [arg graphName] [method {arc target}] [arg arc]] 139 140Return the node the given [arg arc] ends at. 141 142 143[call [arg graphName] [method {arc unset}] [arg arc] [opt "-key [arg key]"]] 144 145Remove a keyed value from the arc [arg arc]. If no key is specified, 146the key [const data] is assumed. 147 148 149[call [arg graphName] [method arcs] [opt "-key [arg key]"] [opt "-value [arg value]"] [opt "-in|-out|-adj|-inner|-embedding [arg nodelist]"]] 150 151Return a list of arcs in the graph. If no restriction is specified a 152list containing all arcs is returned. Restrictions can limit the list 153of returned arcs based on the nodes that are connected by the arc, on 154the keyed values associated with the arc, or both. The restrictions 155that involve connected nodes have a list of nodes as argument, 156specified after the name of the restriction itself. 157 158[list_begin definitions] 159[def [option -in]] 160 161Return a list of all arcs whose target is one of the nodes in the 162[arg nodelist]. 163 164[def [option -out]] 165 166Return a list of all arcs whose source is one of the nodes in the 167[arg nodelist]. 168 169[def [option -adj]] 170 171Return a list of all arcs adjacent to at least one of the nodes in the 172[arg nodelist]. This is the union of the nodes returned by 173 174[option -in] and [option -out]. 175 176[def [option -inner]] 177 178Return a list of all arcs adjacent to two of the nodes in the 179 180[arg nodelist]. This is the set of arcs in the subgraph spawned by the 181specified nodes. 182 183[def [option -embedding]] 184 185Return a list of all arcs adjacent to exactly one of the nodes in the 186[arg nodelist]. This is the set of arcs connecting the subgraph 187spawned by the specified nodes to the rest of the graph. 188 189[def "[option -key] [arg key]"] 190 191Limit the list of arcs that are returned to those arcs that have an 192associated key [arg key]. 193 194[def "[option -value] [arg value]"] 195 196This restriction can only be used in combination with 197 198[option -key]. It limits the list of arcs that are returned to those 199arcs whose associated key [arg key] has the value [arg value]. 200 201[list_end] 202[para] 203 204The restrictions imposed by either [option -in], [option -out], 205[option -adj], [option -inner], or [option -embedded] are applied 206first. Specifying more than one of them is illegal. 207 208At last the restrictions set via [option -key] (and [option -value]) 209are applied. 210Specifying more than one [option -key] (and [option -value]) is 211illegal. 212 213 214[call [arg graphName] [method {node append}] [arg node] [opt "-key [arg key]"] [arg value]] 215 216Appends a [arg value] to one of the keyed values associated with an 217[arg node]. If no [arg key] is specified, the key [const data] is 218assumed. 219 220 221[call [arg graphName] [method {node degree}] [opt -in|-out] [arg node]] 222 223Return the number of arcs adjacent to the specified [arg node]. If one 224of the restrictions [option -in] or [option -out] is given only the 225incoming resp. outgoing arcs are counted. 226 227 228[call [arg graphName] [method {node delete}] [arg node] [opt "[arg node] ..."]] 229 230Remove the specified nodes from the graph. All of the nodes' arcs 231will be removed as well to prevent unconnected arcs. 232 233 234[call [arg graphName] [method {node exists}] [arg node]] 235 236Return true if the specified [arg node] exists in the graph. 237 238 239[call [arg graphName] [method {node get}] [arg node] [opt "-key [arg key]"]] 240 241Return the value associated with the key [arg key] for the [arg node]. 242If no key is specified, the key [const data] is assumed. 243 244[call [arg graphName] [method {node getall}] [arg node]] 245 246Returns a serialized list of key/value pairs (suitable for use with 247[lb][cmd {array set}][rb]) for the [arg node]. 248 249 250[call [arg graphName] [method {node keys}] [arg node]] 251 252Returns a list of keys for the [arg node]. 253 254 255[call [arg graphName] [method {node keyexists}] [arg node] [opt "-key [arg key]"]] 256 257Return true if the specified [arg key] exists for the [arg node]. If 258no [arg key] is specified, the key [const data] is assumed. 259 260 261[call [arg graphName] [method {node insert}] [opt [arg child]]] 262 263Insert a node named [arg child] into the graph. The nodes has no arcs 264connected to it. If the name of the new child is not specified the 265system will generate a unique name of the form [emph node][arg x]. 266 267[call [arg graphName] [method {node lappend}] [arg node] [opt "-key [arg key]"] [arg value]] 268 269Appends a [arg value] (as a list) to one of the keyed values 270associated with an [arg node]. If no [arg key] is specified, the key 271[const data] is assumed. 272 273 274[call [arg graphName] [method {node opposite}] [arg node] [arg arc]] 275 276Return the node at the other end of the specified [arg arc], which has 277to be adjacent to the given [arg node]. 278 279 280[call [arg graphName] [method {node set}] [arg node] [opt "-key [arg key]"] [opt [arg value]]] 281 282Set or get one of the keyed values associated with a node. If no key 283is specified, the key [const data] is assumed. Each node that is 284added to a graph has the empty string assigned to the key 285 286[const data] automatically. A node may have any number of keyed 287values associated with it. If [arg value] is not specified, this 288command returns the current value assigned to the key; if [arg value] 289is specified, this command assigns that value to the key. 290 291 292[call [arg graphName] [method {node unset}] [arg node] [opt "-key [arg key]"]] 293 294Remove a keyed value from the node [arg node]. If no key is 295specified, the key [method data] is assumed. 296 297[call [arg graphName] [method nodes] [opt "-key [arg key]"] [opt "-value [arg value]"] [opt "-in|-out|-adj|-inner|-embedding [arg nodelist]"]] 298 299Return a list of nodes in the graph. Restrictions can limit the list 300of returned nodes based on neighboring nodes, or based on the keyed 301values associated with the node. The restrictions that involve 302neighboring nodes have a list of nodes as argument, specified after 303the name of the restriction itself. 304 305[para] 306 307The possible restrictions are the same as for method 308 309[method arcs]. The set of nodes to return is computed as the union of 310all source and target nodes for all the arcs satisfying the 311restriction as defined for [method arcs]. 312 313 314[call [arg graphName] [method get] [opt "-key [arg key]"]] 315 316Return the value associated with the key [arg key] for the graph. If 317no key is specified, the key [const data] is assumed. 318 319 320[call [arg graphName] [method getall]] 321 322Returns a serialized list of key/value pairs (suitable for use with 323[lb][cmd {array set}][rb]) for the whole graph. 324 325 326[call [arg graphName] [method keys]] 327 328Returns a list of keys for the whole graph. 329 330 331[call [arg graphName] [method keyexists] [opt "-key [arg key]"]] 332 333Return true if the specified [arg key] exists for the whole graph. If no 334[arg key] is specified, the key [const data] is assumed. 335 336 337[call [arg graphName] [method set] [opt "-key [arg key]"] [opt [arg value]]] 338 339Set or get one of the keyed values associated with a graph. If no key 340is specified, the key [const data] is assumed. Each graph has the 341empty string assigned to the key [const data] automatically. A graph 342may have any number of keyed values associated with it. If [arg value] 343is not specified, this command returns the current value assigned to 344the key; if [arg value] is specified, this command assigns that value 345to the key. 346 347 348[call [arg graphName] [method swap] [arg node1] [arg node2]] 349 350Swap the position of [arg node1] and [arg node2] in the graph. 351 352 353[call [arg graphName] [method unset] [opt "-key [arg key]"]] 354 355Remove a keyed value from the graph. If no key is specified, the key 356[const data] is assumed. 357 358[call [arg graphName] [method walk] [arg node] [opt "-order [arg order]"] [opt "-type [arg type]"] [opt "-dir [arg direction]"] -command [arg cmd]] 359 360Perform a breadth-first or depth-first walk of the graph starting at 361the node [arg node] going in either the direction of outgoing or 362opposite to the incoming arcs. 363 364[para] 365 366The type of walk, breadth-first or depth-first, is determined by the 367value of [arg type]; [const bfs] indicates breadth-first, 368 369[const dfs] indicates depth-first. Depth-first is the default. 370 371[para] 372 373The order of the walk, pre-order, post-order or both-order is 374determined by the value of [arg order]; [const pre] indicates 375pre-order, [const post] indicates post-order, [const both] indicates 376both-order. Pre-order is the default. Pre-order walking means that a 377node is visited before any of its neighbors (as defined by the 378 379[arg direction], see below). Post-order walking means that a parent is 380visited after any of its neighbors. Both-order walking means that a 381node is visited before [emph and] after any of its neighbors. The 382combination of a bread-first walk with post- or both-order is illegal. 383 384[para] 385 386The direction of the walk is determined by the value of [arg dir]; 387[const backward] indicates the direction opposite to the incoming 388arcs, [const forward] indicates the direction of the outgoing arcs. 389 390[para] 391 392As the walk progresses, the command [arg cmd] will be evaluated at 393each node, with the mode of the call ([const enter] or 394[const leave]) and values [arg graphName] and the name of the current 395node appended. For a pre-order walk, all nodes are [const enter]ed, for a 396post-order all nodes are left. In a both-order walk the first visit of 397a node [const enter]s it, the second visit [const leave]s it. 398 399[list_end] 400 401[section {BUGS, IDEAS, FEEDBACK}] 402 403This document, and the package it describes, will undoubtedly contain 404bugs and other problems. 405 406Please report such in the category [emph {struct :: graph}] of the 407[uri {http://sourceforge.net/tracker/?group_id=12883} {Tcllib SF Trackers}]. 408 409Please also report any ideas for enhancements you may have for either 410package and/or documentation. 411 412 413[keywords graph cgraph] 414[manpage_end] 415