1struct::graph::op(n) Tcl Data Structures struct::graph::op(n)
2______________________________________________________________________________
6
8 struct::graph::op - Operation for (un)directed graph objects
9
11 package require Tcl 8.4
12 package require struct::graph::op ?0.9?
14 struct::graph:op::toAdjacencyMatrix g
16 struct::graph:op::kruskal g
18 struct::graph:op::prim g
20 struct::graph:op::isBipartite? g ?bipartvar?
22 struct::graph:op::tarjan g
24 struct::graph:op::connectedComponents g
26 struct::graph:op::connectedComponentOf g n
28 struct::graph:op::isConnected? g
30 struct::graph:op::isCutVertex? g n
32 struct::graph:op::isBridge? g a
34 struct::graph:op::isEulerian? g ?tourvar?
36 struct::graph:op::isSemiEulerian? g ?pathvar?
38 struct::graph:op::dijkstra g start ?options...?
40 struct::graph:op::distance g origin destination ?options...?
42 struct::graph:op::eccentricity g n ?options...?
44 struct::graph:op::radius g ?options...?
46 struct::graph:op::diameter g ?options...?
48_________________________________________________________________
50
52 The package described by this document, struct::graph::op, is a compan‐
53 ion to the package struct::graph. It provides a series of common opera‐
54 tions and algorithms applicable to (un)directed graphs.
55 Despite being a companion the package is not directly dependent on
57 struct::graph, only on the API defined by that package. I.e. the opera‐
58 tions of this package can be applied to any and all graph objects which
59 provide the same API as the objects created through struct::graph.
60
62 struct::graph:op::toAdjacencyMatrix g
63 This command takes the graph g and returns a nested list con‐
64 taining the adjacency matrix of g.
65 The elements of the outer list are the rows of the matrix, the
67 inner elements are the column values in each row. The matrix has
68 "n+1" rows and columns, with the first row and column (index 0)
69 containing the name of the node the row/column is for. All other
70 elements are boolean values, True if there is an arc between the
71 2 nodes of the respective row and column, and False otherwise.
72 Note that the matrix is symmetric. It does not represent the
74 directionality of arcs, only their presence between nodes. It is
75 also unable to represent parallel arcs in g.
76 struct::graph:op::kruskal g
78 This command takes the graph g and returns a list containing the
79 names of the arcs in g which span up a minimum spanning tree
80 (MST), or, in the case of an un-connected graph, a minimum span‐
81 ning forest. Kruskal's algorithm is used to compute the tree or
82 forest.
83 The command will throw an error if one or more arcs in g have no
85 weight associated with them.
86 A note regarding the result, the command refrains from explic‐
88 itly listing the nodes of the MST as this information is implic‐
89 itly provided in the arcs already.
90 struct::graph:op::prim g
92 This command takes the graph g and returns a list containing the
93 names of the arcs in g which span up a minimum spanning tree
94 (MST), or, in the case of an un-connected graph, a minimum span‐
95 ning forest. Prim's algorithm is used to compute the tree or
96 forest.
97 The command will throw an error if one or more arcs in g have no
99 weight associated with them.
100 A note regarding the result, the command refrains from explic‐
102 itly listing the nodes of the MST as this information is implic‐
103 itly provided in the arcs already.
104 struct::graph:op::isBipartite? g ?bipartvar?
106 This command takes the graph g and returns a boolean value indi‐
107 cating whether it is bipartite (true) or not (false). If the
108 variable bipartvar is specified the two partitions of the graph
109 are there as a list, if, and only if the graph is bipartit. If
110 it is not the variable, if specified, is not touched.
111 struct::graph:op::tarjan g
113 This command computes the set of strongly connected components
114 (SCCs) of the graph g. The result of the command is a list of
115 sets, each of which contains the nodes for one of the SCCs of g.
116 The union of all SCCs covers the whole graph, and no two SCCs
117 intersect with each other.
118 The graph g is acyclic if all SCCs in the result contain only a
120 single node. The graph g is strongly connected if the result
121 contains only a single SCC containing all nodes of g.
122 struct::graph:op::connectedComponents g
124 This command computes the set of connected components (CCs) of
125 the graph g. The result of the command is a list of sets, each
126 of which contains the nodes for one of the CCs of g. The union
127 of all CCs covers the whole graph, and no two CCs intersect with
128 each other.
129 The graph g is connected if the result contains only a single
131 SCC containing all nodes of g.
132 struct::graph:op::connectedComponentOf g n
134 This command computes the connected component (CC) of the graph
135 g containing the node n. The result of the command is a sets
136 which contains the nodes for the CC of n in g.
137 The command will throw an error if n is not a node of the graph
139 g.
140 struct::graph:op::isConnected? g
142 This is a convenience command determining whether the graph g is
143 connected or not. The result is a boolean value, true if the
144 graph is connected, and false otherwise.
145 struct::graph:op::isCutVertex? g n
147 This command determines whether the node n in the graph g is a
148 cut vertex (aka articulation point). The result is a boolean
149 value, true if the node is a cut vertex, and false otherwise.
150 The command will throw an error if n is not a node of the graph
152 g.
153 struct::graph:op::isBridge? g a
155 This command determines whether the arc a in the graph g is a
156 bridge (aka cut edge, or isthmus). The result is a boolean
157 value, true if the arc is a bridge, and false otherwise.
158 The command will throw an error if a is not an arc of the graph
160 g.
161 struct::graph:op::isEulerian? g ?tourvar?
163 This command determines whether the graph g is eulerian or not.
164 The result is a boolean value, true if the graph is eulerian,
165 and false otherwise.
166 If the graph is eulerian and tourvar is specified then an euler
168 tour is computed as well and stored in the named variable. The
169 tour is represented by the list of arcs traversed, in the order
170 of traversal.
171 struct::graph:op::isSemiEulerian? g ?pathvar?
173 This command determines whether the graph g is semi-eulerian or
174 not. The result is a boolean value, true if the graph is semi-
175 eulerian, and false otherwise.
176 If the graph is semi-eulerian and pathvar is specified then an
178 euler path is computed as well and stored in the named variable.
179 The path is represented by the list of arcs traversed, in the
180 order of traversal.
181 struct::graph:op::dijkstra g start ?options...?
183 This command determines distances in the weighted g from the
184 node start to all other nodes in the graph. The options specify
185 how to traverse graphs, and the format of the result.
186 Two options are recognized
188 -arcmode mode
190 The accepted mode values are directed and undirected.
191 For directed traversal all arcs are traversed from source
192 to target. For undirected traversal all arcs are tra‐
193 versed in the opposite direction as well. Undirected tra‐
194 versal is the default.
195 -outputformat format
197 The accepted format values are distances and tree. In
198 both cases the result is a dictionary keyed by the names
199 of all nodes in the graph. For distances the value is the
200 distance of the node to start, whereas for tree the value
201 is the path from the node to start, excluding the node
202 itself, but including start. Tree format is the default.
203 struct::graph:op::distance g origin destination ?options...?
205 This command determines the (un)directed distance between the
206 two nodes origin and destination in the graph g. It accepts the
207 option -arcmode of struct::graph:op::dijkstra.
208 struct::graph:op::eccentricity g n ?options...?
210 This command determines the (un)directed eccentricity of the
211 node n in the graph g. It accepts the option -arcmode of
212 struct::graph:op::dijkstra.
213 The (un)directed eccentricity of a node is the maximal
215 (un)directed distance between the node and any other node in the
216 graph.
217 struct::graph:op::radius g ?options...?
219 This command determines the (un)directed radius of the graph g.
220 It accepts the option -arcmode of struct::graph:op::dijkstra.
221 The (un)directed radius of a graph is the minimal (un)directed
223 eccentricity of all nodes in the graph.
224 struct::graph:op::diameter g ?options...?
226 This command determines the (un)directed diameter of the graph
227 g. It accepts the option -arcmode of struct::graph:op::dijkstra.
228 The (un)directed diameter of a graph is the maximal (un)directed
230 eccentricity of all nodes in the graph.
231
233 [1] Adjacency matrix [http://en.wikipedia.org/wiki/Adjacency_matrix]
234 [2] Kruskal's algorithm
236 [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]
237 [3] Prim's algorithm [http://en.wikipedia.org/wiki/Prim%27s_algo‐
239 rithm]
240 [4] Bipartite graph [http://en.wikipedia.org/wiki/Bipartite_graph]
242 [5] Strongly connected components
244 [http://en.wikipedia.org/wiki/Strongly_connected_components]
245 [6] Tarjan's strongly connected components algorithm
247 [http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_com‐
248 ponents_algorithm]
249 [7] Cut vertex [http://en.wikipedia.org/wiki/Cut_vertex]
251 [8] Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)]
253
255 This document, and the package it describes, will undoubtedly contain
256 bugs and other problems. Please report such in the category struct ::
257 graph of the Tcllib SF Trackers [http://source‐
258 forge.net/tracker/?group_id=12883]. Please also report any ideas for
259 enhancements you may have for either package and/or documentation.
260
262 adjacency matrix, adjacent, arc, articulation point, bipartite, bridge,
263 connected component, cut edge, cut vertex, degree, diameter, dijkstra,
264 distance, eccentricity, edge, graph, isthmus, loop, minimal spanning
265 tree, neighbour, node, radius, strongly connected component, subgraph,
266 vertex
267
269 Copyright (c) 2008 Alejandro Paz <vidriloco@gmail.com>
270 Copyright (c) 2008 (docs) Andreas Kupries <andreas_kupries@users.sourceforge.net>
271struct 0.9 struct::graph::op(n)