1`struct::graph::op(n) Tcl Data Structures struct::graph::op(n)`

2`3`

`4`

`5`

`______________________________________________________________________________`

6

## NAME

8`struct::graph::op - Operation for (un)directed graph objects`

9

## SYNOPSIS

11`package require Tcl 8.4`

12`13`

`package require struct::graph::op ?0.11.3?`

14`15`

`struct::graph::op::toAdjacencyMatrix g`

16`17`

`struct::graph::op::toAdjacencyList G ?options...?`

18`19`

`struct::graph::op::kruskal g`

20`21`

`struct::graph::op::prim g`

22`23`

`struct::graph::op::isBipartite? g ?bipartvar?`

24`25`

`struct::graph::op::tarjan g`

26`27`

`struct::graph::op::connectedComponents g`

28`29`

`struct::graph::op::connectedComponentOf g n`

30`31`

`struct::graph::op::isConnected? g`

32`33`

`struct::graph::op::isCutVertex? g n`

34`35`

`struct::graph::op::isBridge? g a`

36`37`

`struct::graph::op::isEulerian? g ?tourvar?`

38`39`

`struct::graph::op::isSemiEulerian? g ?pathvar?`

40`41`

`struct::graph::op::dijkstra g start ?options...?`

42`43`

`struct::graph::op::distance g origin destination ?options...?`

44`45`

`struct::graph::op::eccentricity g n ?options...?`

46`47`

`struct::graph::op::radius g ?options...?`

48`49`

`struct::graph::op::diameter g ?options...?`

50`51`

`struct::graph::op::BellmanFord G startnode`

52`53`

`struct::graph::op::Johnsons G ?options...?`

54`55`

`struct::graph::op::FloydWarshall G`

56`57`

`struct::graph::op::MetricTravellingSalesman G`

58`59`

`struct::graph::op::Christofides G`

60`61`

`struct::graph::op::GreedyMaxMatching G`

62`63`

`struct::graph::op::MaxCut G U V`

64`65`

`struct::graph::op::UnweightedKCenter G k`

66`67`

`struct::graph::op::WeightedKCenter G nodeWeights W`

68`69`

`struct::graph::op::GreedyMaxIndependentSet G`

70`71`

`struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights`

72`73`

`struct::graph::op::VerticesCover G`

74`75`

`struct::graph::op::EdmondsKarp G s t`

76`77`

`struct::graph::op::BusackerGowen G desiredFlow s t`

78`79`

`struct::graph::op::ShortestsPathsByBFS G s outputFormat`

80`81`

`struct::graph::op::BFS G s ?outputFormat...?`

82`83`

`struct::graph::op::MinimumDiameterSpanningTree G`

84`85`

`struct::graph::op::MinimumDegreeSpanningTree G`

86`87`

`struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg`

88`89`

`struct::graph::op::BlockingFlowByDinic G s t`

90`91`

`struct::graph::op::BlockingFlowByMKM G s t`

92`93`

`struct::graph::op::createResidualGraph G f`

94`95`

`struct::graph::op::createAugmentingNetwork G f path`

96`97`

`struct::graph::op::createLevelGraph Gf s`

98`99`

`struct::graph::op::TSPLocalSearching G C`

100`101`

`struct::graph::op::TSPLocalSearching3Approx G C`

102`103`

`struct::graph::op::createSquaredGraph G`

104`105`

`struct::graph::op::createCompleteGraph G originalEdges`

106`107`

`______________________________________________________________________________`

108

## DESCRIPTION

110`The package described by this document, struct::graph::op, is a compan‐`

111`ion to the package struct::graph. It provides a series of common opera‐`

112`tions and algorithms applicable to (un)directed graphs.`

113`114`

`Despite being a companion the package is not directly dependent on`

115`struct::graph, only on the API defined by that package. I.e. the opera‐`

116`tions of this package can be applied to any and all graph objects which`

117`provide the same API as the objects created through struct::graph.`

118

## OPERATIONS

120`struct::graph::op::toAdjacencyMatrix g`

121`This command takes the graph g and returns a nested list con‐`

122`taining the adjacency matrix of g.`

123`124`

`The elements of the outer list are the rows of the matrix, the`

125`inner elements are the column values in each row. The matrix has`

126`"n+1" rows and columns, with the first row and column (index 0)`

127`containing the name of the node the row/column is for. All other`

128`elements are boolean values, True if there is an arc between the`

129`2 nodes of the respective row and column, and False otherwise.`

130`131`

`Note that the matrix is symmetric. It does not represent the`

132`directionality of arcs, only their presence between nodes. It is`

133`also unable to represent parallel arcs in g.`

134`135`

`struct::graph::op::toAdjacencyList G ?options...?`

136`Procedure creates for input graph G, it's representation as`

137`Adjacency List. It handles both directed and undirected graphs`

138`(default is undirected). It returns dictionary that for each`

139`node (key) returns list of nodes adjacent to it. When consider‐`

140`ing weighted version, for each adjacent node there is also`

141`weight of the edge included.`

142`143`

`144`

`Arguments:`

145`146`

`Graph object G (input)`

147`A graph to convert into an Adjacency List.`

148`149`

`Options:`

150`151`

`-directed`

152`By default G is operated as if it were an Undi‐`

153`rected graph. Using this option tells the command`

154`to handle G as the directed graph it is.`

155`156`

`-weights`

157`By default any weight information the graph G may`

158`have is ignored. Using this option tells the com‐`

159`mand to put weight information into the result.`

160`In that case it is expected that all arcs have a`

161`proper weight, and an error is thrown if that is`

162`not the case.`

163`164`

`struct::graph::op::kruskal g`

165`This command takes the graph g and returns a list containing the`

166`names of the arcs in g which span up a minimum weight spanning`

167`tree (MST), or, in the case of an un-connected graph, a minimum`

168`weight spanning forest (except for the 1-vertex components).`

169`Kruskal's algorithm is used to compute the tree or forest. This`

170`algorithm has a time complexity of O(E*log E) or O(E* log V),`

171`where V is the number of vertices and E is the number of edges`

172`in graph g.`

173`174`

`The command will throw an error if one or more arcs in g have no`

175`weight associated with them.`

176`177`

`A note regarding the result, the command refrains from explic‐`

178`itly listing the nodes of the MST as this information is implic‐`

179`itly provided in the arcs already.`

180`181`

`struct::graph::op::prim g`

182`This command takes the graph g and returns a list containing the`

183`names of the arcs in g which span up a minimum weight spanning`

184`tree (MST), or, in the case of an un-connected graph, a minimum`

185`weight spanning forest (except for the 1-vertex components).`

186`Prim's algorithm is used to compute the tree or forest. This`

187`algorithm has a time complexity between O(E+V*log V) and O(V*V),`

188`depending on the implementation (Fibonacci heap + Adjacency list`

189`versus Adjacency Matrix). As usual V is the number of vertices`

190`and E the number of edges in graph g.`

191`192`

`The command will throw an error if one or more arcs in g have no`

193`weight associated with them.`

194`195`

`A note regarding the result, the command refrains from explic‐`

196`itly listing the nodes of the MST as this information is implic‐`

197`itly provided in the arcs already.`

198`199`

`struct::graph::op::isBipartite? g ?bipartvar?`

200`This command takes the graph g and returns a boolean value indi‐`

201`cating whether it is bipartite (true) or not (false). If the`

202`variable bipartvar is specified the two partitions of the graph`

203`are there as a list, if, and only if the graph is bipartit. If`

204`it is not the variable, if specified, is not touched.`

205`206`

`struct::graph::op::tarjan g`

207`This command computes the set of strongly connected components`

208`(SCCs) of the graph g. The result of the command is a list of`

209`sets, each of which contains the nodes for one of the SCCs of g.`

210`The union of all SCCs covers the whole graph, and no two SCCs`

211`intersect with each other.`

212`213`

`The graph g is acyclic if all SCCs in the result contain only a`

214`single node. The graph g is strongly connected if the result`

215`contains only a single SCC containing all nodes of g.`

216`217`

`struct::graph::op::connectedComponents g`

218`This command computes the set of connected components (CCs) of`

219`the graph g. The result of the command is a list of sets, each`

220`of which contains the nodes for one of the CCs of g. The union`

221`of all CCs covers the whole graph, and no two CCs intersect with`

222`each other.`

223`224`

`The graph g is connected if the result contains only a single`

225`SCC containing all nodes of g.`

226`227`

`struct::graph::op::connectedComponentOf g n`

228`This command computes the connected component (CC) of the graph`

229`g containing the node n. The result of the command is a sets`

230`which contains the nodes for the CC of n in g.`

231`232`

`The command will throw an error if n is not a node of the graph`

233`g.`

234`235`

`struct::graph::op::isConnected? g`

236`This is a convenience command determining whether the graph g is`

237`connected or not. The result is a boolean value, true if the`

238`graph is connected, and false otherwise.`

239`240`

`struct::graph::op::isCutVertex? g n`

241`This command determines whether the node n in the graph g is a`

242`cut vertex (aka articulation point). The result is a boolean`

243`value, true if the node is a cut vertex, and false otherwise.`

244`245`

`The command will throw an error if n is not a node of the graph`

246`g.`

247`248`

`struct::graph::op::isBridge? g a`

249`This command determines whether the arc a in the graph g is a`

250`bridge (aka cut edge, or isthmus). The result is a boolean`

251`value, true if the arc is a bridge, and false otherwise.`

252`253`

`The command will throw an error if a is not an arc of the graph`

254`g.`

255`256`

`struct::graph::op::isEulerian? g ?tourvar?`

257`This command determines whether the graph g is eulerian or not.`

258`The result is a boolean value, true if the graph is eulerian,`

259`and false otherwise.`

260`261`

`If the graph is eulerian and tourvar is specified then an euler`

262`tour is computed as well and stored in the named variable. The`

263`tour is represented by the list of arcs traversed, in the order`

264`of traversal.`

265`266`

`struct::graph::op::isSemiEulerian? g ?pathvar?`

267`This command determines whether the graph g is semi-eulerian or`

268`not. The result is a boolean value, true if the graph is semi-`

269`eulerian, and false otherwise.`

270`271`

`If the graph is semi-eulerian and pathvar is specified then an`

272`euler path is computed as well and stored in the named variable.`

273`The path is represented by the list of arcs traversed, in the`

274`order of traversal.`

275`276`

`struct::graph::op::dijkstra g start ?options...?`

277`This command determines distances in the weighted g from the`

278`node start to all other nodes in the graph. The options specify`

279`how to traverse graphs, and the format of the result.`

280`281`

`Two options are recognized`

282`283`

`-arcmode mode`

284`The accepted mode values are directed and undirected.`

285`For directed traversal all arcs are traversed from source`

286`to target. For undirected traversal all arcs are tra‐`

287`versed in the opposite direction as well. Undirected tra‐`

288`versal is the default.`

289`290`

`-outputformat format`

291`The accepted format values are distances and tree. In`

292`both cases the result is a dictionary keyed by the names`

293`of all nodes in the graph. For distances the value is the`

294`distance of the node to start, whereas for tree the value`

295`is the path from the node to start, excluding the node`

296`itself, but including start. Tree format is the default.`

297`298`

`struct::graph::op::distance g origin destination ?options...?`

299`This command determines the (un)directed distance between the`

300`two nodes origin and destination in the graph g. It accepts the`

301`option -arcmode of struct::graph::op::dijkstra.`

302`303`

`struct::graph::op::eccentricity g n ?options...?`

304`This command determines the (un)directed eccentricity of the`

305`node n in the graph g. It accepts the option -arcmode of`

306`struct::graph::op::dijkstra.`

307`308`

`The (un)directed eccentricity of a node is the maximal`

309`(un)directed distance between the node and any other node in the`

310`graph.`

311`312`

`struct::graph::op::radius g ?options...?`

313`This command determines the (un)directed radius of the graph g.`

314`It accepts the option -arcmode of struct::graph::op::dijkstra.`

315`316`

`The (un)directed radius of a graph is the minimal (un)directed`

317`eccentricity of all nodes in the graph.`

318`319`

`struct::graph::op::diameter g ?options...?`

320`This command determines the (un)directed diameter of the graph`

321`g. It accepts the option -arcmode of struct::graph::op::dijk‐`

322`stra.`

323`324`

`The (un)directed diameter of a graph is the maximal (un)directed`

325`eccentricity of all nodes in the graph.`

326`327`

`struct::graph::op::BellmanFord G startnode`

328`Searching for shortests paths between chosen node and all other`

329`nodes in graph G. Based on relaxation method. In comparison to`

330`struct::graph::op::dijkstra it doesn't need assumption that all`

331`weights on edges in input graph G have to be positive.`

332`333`

`That generality sets the complexity of algorithm to - O(V*E),`

334`where V is the number of vertices and E is number of edges in`

335`graph G.`

336`337`

`338`

`Arguments:`

339`340`

`Graph object G (input)`

341`Directed, connected and edge weighted graph G,`

342`without any negative cycles ( presence of cycles`

343`with the negative sum of weight means that there`

344`is no shortest path, since the total weight`

345`becomes lower each time the cycle is traversed ).`

346`Negative weights on edges are allowed.`

347`348`

`Node startnode (input)`

349`The node for which we find all shortest paths to`

350`each other node in graph G.`

351`352`

`Result:`

353`Dictionary containing for each node (key) distances to`

354`each other node in graph G.`

355`356`

`Note: If algorithm finds a negative cycle, it will return error mes‐`

357`sage.`

358`359`

`struct::graph::op::Johnsons G ?options...?`

360`Searching for shortest paths between all pairs of vertices in`

361`graph. For sparse graphs asymptotically quicker than`

362`struct::graph::op::FloydWarshall algorithm. Johnson's algorithm`

363`uses struct::graph::op::BellmanFord and struct::graph::op::dijk‐`

364`stra as subprocedures.`

365`366`

`Time complexity: O(n**2*log(n) +n*m), where n is the number of`

367`nodes and m is the number of edges in graph G.`

368`369`

`370`

`Arguments:`

371`372`

`Graph object G (input)`

373`Directed graph G, weighted on edges and not con‐`

374`taining any cycles with negative sum of weights (`

375`the presence of such cycles means there is no`

376`shortest path, since the total weight becomes`

377`lower each time the cycle is traversed ). Negative`

378`weights on edges are allowed.`

379`380`

`Options:`

381`382`

`-filter`

383`Returns only existing distances, cuts all Inf val‐`

384`ues for non-existing connections between pairs of`

385`nodes.`

386`387`

`Result:`

388`Dictionary containing distances between all pairs of ver‐`

389`tices.`

390`391`

`struct::graph::op::FloydWarshall G`

392`Searching for shortest paths between all pairs of edges in`

393`weighted graphs.`

394`395`

`Time complexity: O(V^3) - where V is number of vertices.`

396`397`

`Memory complexity: O(V^2).`

398`399`

`400`

`Arguments:`

401`402`

`Graph object G (input)`

403`Directed and weighted graph G.`

404`405`

`Result:`

406`Dictionary containing shortest distances to each node`

407`from each node.`

408`409`

`Note: Algorithm finds solutions dynamically. It compares all`

410`possible paths through the graph between each pair of vertices.`

411`Graph shouldn't possess any cycle with negative sum of weights`

412`(the presence of such cycles means there is no shortest path,`

413`since the total weight becomes lower each time the cycle is tra‐`

414`versed).`

415`416`

`On the other hand algorithm can be used to find those cycles -`

417`if any shortest distance found by algorithm for any nodes v and`

418`u (when v is the same node as u) is negative, that node surely`

419`belong to at least one negative cycle.`

420`421`

`struct::graph::op::MetricTravellingSalesman G`

422`Algorithm for solving a metric variation of Travelling salesman`

423`problem. TSP problem is NP-Complete, so there is no efficient`

424`algorithm to solve it. Greedy methods are getting extremely`

425`slow, with the increase in the set of nodes.`

426`427`

`428`

`Arguments:`

429`430`

`Graph object G (input)`

431`Undirected, weighted graph G.`

432`433`

`Result:`

434`Approximated solution of minimum Hamilton Cycle - closed`

435`path visiting all nodes, each exactly one time.`

436`437`

`Note: It's 2-approximation algorithm.`

438`439`

`struct::graph::op::Christofides G`

440`Another algorithm for solving metric TSP problem. Christofides`

441`implementation uses Max Matching for reaching better approxima‐`

442`tion factor.`

443`444`

`445`

`Arguments:`

446`447`

`Graph Object G (input)`

448`Undirected, weighted graph G.`

449`450`

`Result:`

451`Approximated solution of minimum Hamilton Cycle - closed`

452`path visiting all nodes, each exactly one time.`

453`454`

`Note: It's is a 3/2 approximation algorithm.`

455`456`

`struct::graph::op::GreedyMaxMatching G`

457`Greedy Max Matching procedure, which finds maximal matching (not`

458`maximum) for given graph G. It adds edges to solution, beginning`

459`from edges with the lowest cost.`

460`461`

`462`

`Arguments:`

463`464`

`Graph Object G (input)`

465`Undirected graph G.`

466`467`

`Result:`

468`Set of edges - the max matching for graph G.`

469`470`

`struct::graph::op::MaxCut G U V`

471`Algorithm solving a Maximum Cut Problem.`

472`473`

`474`

`Arguments:`

475`476`

`Graph Object G (input)`

477`The graph to cut.`

478`479`

`List U (output)`

480`Variable storing first set of nodes (cut) given by`

481`solution.`

482`483`

`List V (output)`

484`Variable storing second set of nodes (cut) given`

485`by solution.`

486`487`

`Result:`

488`Algorithm returns number of edges between found two sets`

489`of nodes.`

490`491`

`Note: MaxCut is a 2-approximation algorithm.`

492`493`

`struct::graph::op::UnweightedKCenter G k`

494`Approximation algorithm that solves a k-center problem.`

495`496`

`497`

`Arguments:`

498`499`

`Graph Object G (input)`

500`Undirected complete graph G, which satisfies tri‐`

501`angle inequality.`

502`503`

`504`

`Integer k (input)`

505`Positive integer that sets the number of nodes`

506`that will be included in k-center.`

507`508`

`Result:`

509`Set of nodes - k center for graph G.`

510`511`

`Note: UnweightedKCenter is a 2-approximation algorithm.`

512`513`

`struct::graph::op::WeightedKCenter G nodeWeights W`

514`Approximation algorithm that solves a weighted version of k-cen‐`

515`ter problem.`

516`517`

`518`

`Arguments:`

519`520`

`Graph Object G (input)`

521`Undirected complete graph G, which satisfies tri‐`

522`angle inequality.`

523`524`

`Integer W (input)`

525`Positive integer that sets the maximum possible`

526`weight of k-center found by algorithm.`

527`528`

`List nodeWeights (input)`

529`List of nodes and its weights in graph G.`

530`531`

`Result:`

532`Set of nodes, which is solution found by algorithm.`

533`534`

`Note:WeightedKCenter is a 3-approximation algorithm.`

535`536`

`struct::graph::op::GreedyMaxIndependentSet G`

537`A maximal independent set is an independent set such that adding`

538`any other node to the set forces the set to contain an edge.`

539`540`

`Algorithm for input graph G returns set of nodes (list), which`

541`are contained in Max Independent Set found by algorithm.`

542`543`

`struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights`

544`Weighted variation of Maximal Independent Set. It takes as an`

545`input argument not only graph G but also set of weights for all`

546`vertices in graph G.`

547`548`

`Note: Read also Maximal Independent Set description for more`

549`info.`

550`551`

`struct::graph::op::VerticesCover G`

552`Vertices cover is a set of vertices such that each edge of the`

553`graph is incident to at least one vertex of the set. This`

554`2-approximation algorithm searches for minimum vertices cover,`

555`which is a classical optimization problem in computer science`

556`and is a typical example of an NP-hard optimization problem that`

557`has an approximation algorithm. For input graph G algorithm`

558`returns the set of edges (list), which is Vertex Cover found by`

559`algorithm.`

560`561`

`struct::graph::op::EdmondsKarp G s t`

562`Improved Ford-Fulkerson's algorithm, computing the maximum flow`

563`in given flow network G.`

564`565`

`566`

`Arguments:`

567`568`

`Graph Object G (input)`

569`Weighted and directed graph. Each edge should have`

570`set integer attribute considered as maximum`

571`throughputs that can be carried by that link`

572`(edge).`

573`574`

`Node s (input)`

575`The node that is a source for graph G.`

576`577`

`Node t (input)`

578`The node that is a sink for graph G.`

579`580`

`Result:`

581`Procedure returns the dictionary containing throughputs`

582`for all edges. For each key ( the edge between nodes u`

583`and v in the form of list u v ) there is a value that is`

584`a throughput for that key. Edges where throughput values`

585`are equal to 0 are not returned ( it is like there was no`

586`link in the flow network between nodes connected by such`

587`edge).`

588`589`

`The general idea of algorithm is finding the shortest augumenting paths`

590`in graph G, as long as they exist, and for each path updating the`

591`edge's weights along that path, with maximum possible throughput. The`

592`final (maximum) flow is found when there is no other augumenting path`

593`from source to sink.`

594`595`

`Note: Algorithm complexity : O(V*E), where V is the number of nodes and`

596`E is the number of edges in graph G.`

597`598`

`struct::graph::op::BusackerGowen G desiredFlow s t`

599`Algorithm finds solution for a minimum cost flow problem. So,`

600`the goal is to find a flow, whose max value can be desiredFlow,`

601`from source node s to sink node t in given flow network G. That`

602`network except throughputs at edges has also defined a non-nega‐`

603`tive cost on each edge - cost of using that edge when directing`

604`flow with that edge ( it can illustrate e.g. fuel usage, time or`

605`any other measure dependent on usages ).`

606`607`

`608`

`Arguments:`

609`610`

`Graph Object G (input)`

611`Flow network (directed graph), each edge in graph`

612`should have two integer attributes: cost and`

613`throughput.`

614`615`

`Integer desiredFlow (input)`

616`Max value of the flow for that network.`

617`618`

`Node s (input)`

619`The source node for graph G.`

620`621`

`Node t (input)`

622`The sink node for graph G.`

623`624`

`Result:`

625`Dictionary containing values of used throughputs for each`

626`edge ( key ). found by algorithm.`

627`628`

`Note: Algorithm complexity : O(V**2*desiredFlow), where V is the`

629`number of nodes in graph G.`

630`631`

`struct::graph::op::ShortestsPathsByBFS G s outputFormat`

632`Shortest pathfinding algorithm using BFS method. In comparison`

633`to struct::graph::op::dijkstra it can work with negative weights`

634`on edges. Of course negative cycles are not allowed. Algorithm`

635`is better than dijkstra for sparse graphs, but also there exist`

636`some pathological cases (those cases generally don't appear in`

637`practise) that make time complexity increase exponentially with`

638`the growth of the number of nodes.`

639`640`

`641`

`Arguments:`

642`643`

`Graph Object G (input)`

644`Input graph.`

645`646`

`Node s (input)`

647`Source node for which all distances to each other`

648`node in graph G are computed.`

649`650`

`Options and result:`

651`652`

`distances`

653`When selected outputFormat is distances - proce‐`

654`dure returns dictionary containing distances`

655`between source node s and each other node in graph`

656`G.`

657`658`

`paths When selected outputFormat is paths - procedure`

659`returns dictionary containing for each node v, a`

660`list of nodes, which is a path between source node`

661`s and node v.`

662`663`

`struct::graph::op::BFS G s ?outputFormat...?`

664`Breadth-First Search - algorithm creates the BFS Tree. Memory`

665`and time complexity: O(V + E), where V is the number of nodes`

666`and E is number of edges.`

667`668`

`669`

`Arguments:`

670`671`

`Graph Object G (input)`

672`Input graph.`

673`674`

`Node s (input)`

675`Source node for BFS procedure.`

676`677`

`Options and result:`

678`679`

`graph When selected outputFormat is graph - procedure`

680`returns a graph structure (struct::graph), which`

681`is equivalent to BFS tree found by algorithm.`

682`683`

`tree When selected outputFormat is tree - procedure`

684`returns a tree structure (struct::tree), which is`

685`equivalent to BFS tree found by algorithm.`

686`687`

`struct::graph::op::MinimumDiameterSpanningTree G`

688`The goal is to find for input graph G, the spanning tree that`

689`has the minimum diameter value.`

690`691`

`General idea of algorithm is to run BFS over all vertices in`

692`graph G. If the diameter d of the tree is odd, then we are sure`

693`that tree given by BFS is minimum (considering diameter value).`

694`When, diameter d is even, then optimal tree can have minimum`

695`diameter equal to d or d-1.`

696`697`

`In that case, what algorithm does is rebuilding the tree given`

698`by BFS, by adding a vertice between root node and root's child`

699`node (nodes), such that subtree created with child node as root`

700`node is the greatest one (has the greatests height). In the next`

701`step for such rebuilded tree, we run again BFS with new node as`

702`root node. If the height of the tree didn't changed, we have`

703`found a better solution.`

704`705`

`For input graph G algorithm returns the graph structure`

706`(struct::graph) that is a spanning tree with minimum diameter`

707`found by algorithm.`

708`709`

`struct::graph::op::MinimumDegreeSpanningTree G`

710`Algorithm finds for input graph G, a spanning tree T with the`

711`minimum possible degree. That problem is NP-hard, so algorithm`

712`is an approximation algorithm.`

713`714`

`Let V be the set of nodes for graph G and let W be any subset of`

715`V. Lets assume also that OPT is optimal solution and ALG is`

716`solution found by algorithm for input graph G.`

717`718`

`It can be proven that solution found with the algorithm must`

719`fulfil inequality:`

720`721`

`((|W| + k - 1) / |W|) <= ALG <= 2*OPT + log2(n) + 1.`

722`723`

`724`

`Arguments:`

725`726`

`Graph Object G (input)`

727`Undirected simple graph.`

728`729`

`Result:`

730`Algorithm returns graph structure, which is equivalent to`

731`spanning tree T found by algorithm.`

732`733`

`struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg`

734`Algorithm finds maximum flow for the flow network represented by`

735`graph G. It is based on the blocking-flow finding methods, which`

736`give us different complexities what makes a better fit for dif‐`

737`ferent graphs.`

738`739`

`740`

`Arguments:`

741`742`

`Graph Object G (input)`

743`Directed graph G representing the flow network.`

744`Each edge should have attribute throughput set`

745`with integer value.`

746`747`

`Node s (input)`

748`The source node for the flow network G.`

749`750`

`Node t (input)`

751`The sink node for the flow network G.`

752`753`

`Options:`

754`755`

`dinic Procedure will find maximum flow for flow network`

756`G using Dinic's algorithm`

757`(struct::graph::op::BlockingFlowByDinic) for`

758`blocking flow computation.`

759`760`

`mkm Procedure will find maximum flow for flow network`

761`G using Malhotra, Kumar and Maheshwari's algorithm`

762`(struct::graph::op::BlockingFlowByMKM) for block‐`

763`ing flow computation.`

764`765`

`Result:`

766`Algorithm returns dictionary containing it's flow value`

767`for each edge (key) in network G.`

768`769`

`Note: struct::graph::op::BlockingFlowByDinic gives O(m*n^2) complexity`

770`and struct::graph::op::BlockingFlowByMKM gives O(n^3) complexity, where`

771`n is the number of nodes and m is the number of edges in flow network`

772`G.`

773`774`

`struct::graph::op::BlockingFlowByDinic G s t`

775`Algorithm for given network G with source s and sink t, finds a`

776`blocking flow, which can be used to obtain a maximum flow for`

777`that network G.`

778`779`

`780`

`Arguments:`

781`782`

`Graph Object G (input)`

783`Directed graph G representing the flow network.`

784`Each edge should have attribute throughput set`

785`with integer value.`

786`787`

`Node s (input)`

788`The source node for the flow network G.`

789`790`

`Node t (input)`

791`The sink node for the flow network G.`

792`793`

`Result:`

794`Algorithm returns dictionary containing it's blocking`

795`flow value for each edge (key) in network G.`

796`797`

`Note: Algorithm's complexity is O(n*m), where n is the number of`

798`nodes and m is the number of edges in flow network G.`

799`800`

`struct::graph::op::BlockingFlowByMKM G s t`

801`Algorithm for given network G with source s and sink t, finds a`

802`blocking flow, which can be used to obtain a maximum flow for`

803`that network G.`

804`805`

`806`

`Arguments:`

807`808`

`Graph Object G (input)`

809`Directed graph G representing the flow network.`

810`Each edge should have attribute throughput set`

811`with integer value.`

812`813`

`Node s (input)`

814`The source node for the flow network G.`

815`816`

`Node t (input)`

817`The sink node for the flow network G.`

818`819`

`Result:`

820`Algorithm returns dictionary containing it's blocking`

821`flow value for each edge (key) in network G.`

822`823`

`Note: Algorithm's complexity is O(n^2), where n is the number of`

824`nodes in flow network G.`

825`826`

`struct::graph::op::createResidualGraph G f`

827`Procedure creates a residual graph (or residual network ) for`

828`network G and given flow f.`

829`830`

`831`

`Arguments:`

832`833`

`Graph Object G (input)`

834`Flow network (directed graph where each edge has`

835`set attribute: throughput ).`

836`837`

`dictionary f (input)`

838`Current flows in flow network G.`

839`840`

`Result:`

841`Procedure returns graph structure that is a residual`

842`graph created from input flow network G.`

843`844`

`struct::graph::op::createAugmentingNetwork G f path`

845`Procedure creates an augmenting network for a given residual`

846`network G , flow f and augmenting path path.`

847`848`

`849`

`Arguments:`

850`851`

`Graph Object G (input)`

852`Residual network (directed graph), where for every`

853`edge there are set two attributes: throughput and`

854`cost.`

855`856`

`Dictionary f (input)`

857`Dictionary which contains for every edge (key),`

858`current value of the flow on that edge.`

859`860`

`List path (input)`

861`Augmenting path, set of edges (list) for which we`

862`create the network modification.`

863`864`

`Result:`

865`Algorithm returns graph structure containing the modified`

866`augmenting network.`

867`868`

`struct::graph::op::createLevelGraph Gf s`

869`For given residual graph Gf procedure finds the level graph.`

870`871`

`872`

`Arguments:`

873`874`

`Graph Object Gf (input)`

875`Residual network, where each edge has it's`

876`attribute throughput set with certain value.`

877`878`

`Node s (input)`

879`The source node for the residual network Gf.`

880`881`

`Result:`

882`Procedure returns a level graph created from input resid‐`

883`ual network.`

884`885`

`struct::graph::op::TSPLocalSearching G C`

886`Algorithm is a heuristic of local searching for Travelling`

887`Salesman Problem. For some solution of TSP problem, it checks if`

888`it's possible to find a better solution. As TSP is well known`

889`NP-Complete problem, so algorithm is a approximation algorithm`

890`(with 2 approximation factor).`

891`892`

`893`

`Arguments:`

894`895`

`Graph Object G (input)`

896`Undirected and complete graph with attributes`

897`"weight" set on each single edge.`

898`899`

`List C (input)`

900`A list of edges being Hamiltonian cycle, which is`

901`solution of TSP Problem for graph G.`

902`903`

`Result:`

904`Algorithm returns the best solution for TSP problem, it`

905`was able to find.`

906`907`

`Note: The solution depends on the choosing of the beginning`

908`cycle C. It's not true that better cycle assures that better`

909`solution will be found, but practise shows that we should give`

910`starting cycle with as small sum of weights as possible.`

911`912`

`struct::graph::op::TSPLocalSearching3Approx G C`

913`Algorithm is a heuristic of local searching for Travelling`

914`Salesman Problem. For some solution of TSP problem, it checks if`

915`it's possible to find a better solution. As TSP is well known`

916`NP-Complete problem, so algorithm is a approximation algorithm`

917`(with 3 approximation factor).`

918`919`

`920`

`Arguments:`

921`922`

`Graph Object G (input)`

923`Undirected and complete graph with attributes`

924`"weight" set on each single edge.`

925`926`

`List C (input)`

927`A list of edges being Hamiltonian cycle, which is`

928`solution of TSP Problem for graph G.`

929`930`

`Result:`

931`Algorithm returns the best solution for TSP problem, it`

932`was able to find.`

933`934`

`Note: In practise 3-approximation algorithm turns out to be far`

935`more effective than 2-approximation, but it gives worser approx‐`

936`imation factor. Further heuristics of local searching (e.g.`

937`4-approximation) doesn't give enough boost to square the`

938`increase of approximation factor, so 2 and 3 approximations are`

939`mainly used.`

940`941`

`struct::graph::op::createSquaredGraph G`

942`X-Squared graph is a graph with the same set of nodes as input`

943`graph G, but a different set of edges. X-Squared graph has edge`

944`(u,v), if and only if, the distance between u and v nodes is not`

945`greater than X and u != v.`

946`947`

`Procedure for input graph G, returns its two-squared graph.`

948`949`

`Note: Distances used in choosing new set of edges are consider‐`

950`ing the number of edges, not the sum of weights at edges.`

951`952`

`struct::graph::op::createCompleteGraph G originalEdges`

953`For input graph G procedure adds missing arcs to make it a com‐`

954`plete graph. It also holds in variable originalEdges the set of`

955`arcs that graph G possessed before that operation.`

956

## BACKGROUND THEORY AND TERMS

958`SHORTEST PATH PROBLEM`

959`Definition (single-pair shortest path problem):`

960`Formally, given a weighted graph (let V be the set of vertices,`

961`and E a set of edges), and one vertice v of V, find a path P`

962`from v to a v' of V so that the sum of weights on edges along`

963`the path is minimal among all paths connecting v to v'.`

964`965`

`Generalizations:`

966`967`

`· The single-source shortest path problem, in which we have`

968`to find shortest paths from a source vertex v to all`

969`other vertices in the graph.`

970`971`

`· The single-destination shortest path problem, in which we`

972`have to find shortest paths from all vertices in the`

973`graph to a single destination vertex v. This can be`

974`reduced to the single-source shortest path problem by`

975`reversing the edges in the graph.`

976`977`

`· The all-pairs shortest path problem, in which we have to`

978`find shortest paths between every pair of vertices v, v'`

979`in the graph.`

980`981`

`Note: The result of Shortest Path problem can be Shortest Path`

982`tree, which is a subgraph of a given (possibly weighted) graph`

983`constructed so that the distance between a selected root node`

984`and all other nodes is minimal. It is a tree because if there`

985`are two paths between the root node and some vertex v (i.e. a`

986`cycle), we can delete the last edge of the longer path without`

987`increasing the distance from the root node to any node in the`

988`subgraph.`

989`990`

`TRAVELLING SALESMAN PROBLEM`

991`Definition:`

992`For given edge-weighted (weights on edges should be positive)`

993`graph the goal is to find the cycle that visits each node in`

994`graph exactly once (Hamiltonian cycle).`

995`996`

`Generalizations:`

997`998`

`· Metric TSP - A very natural restriction of the TSP is to`

999`require that the distances between cities form a metric,`

1000`i.e., they satisfy the triangle inequality. That is, for`

1001`any 3 cities A, B and C, the distance between A and C`

1002`must be at most the distance from A to B plus the dis‐`

1003`tance from B to C. Most natural instances of TSP satisfy`

1004`this constraint.`

1005`1006`

`· Euclidean TSP - Euclidean TSP, or planar TSP, is the TSP`

1007`with the distance being the ordinary Euclidean distance.`

1008`Euclidean TSP is a particular case of TSP with triangle`

1009`inequality, since distances in plane obey triangle`

1010`inequality. However, it seems to be easier than general`

1011`TSP with triangle inequality. For example, the minimum`

1012`spanning tree of the graph associated with an instance of`

1013`Euclidean TSP is a Euclidean minimum spanning tree, and`

1014`so can be computed in expected O(n log n) time for n`

1015`points (considerably less than the number of edges). This`

1016`enables the simple 2-approximation algorithm for TSP with`

1017`triangle inequality above to operate more quickly.`

1018`1019`

`· Asymmetric TSP - In most cases, the distance between two`

1020`nodes in the TSP network is the same in both directions.`

1021`The case where the distance from A to B is not equal to`

1022`the distance from B to A is called asymmetric TSP. A`

1023`practical application of an asymmetric TSP is route opti‐`

1024`misation using street-level routing (asymmetric due to`

1025`one-way streets, slip-roads and motorways).`

1026`1027`

`MATCHING PROBLEM`

1028`Definition:`

1029`Given a graph G = (V,E), a matching or edge-independent set M in`

1030`G is a set of pairwise non-adjacent edges, that is, no two edges`

1031`share a common vertex. A vertex is matched if it is incident to`

1032`an edge in the matching M. Otherwise the vertex is unmatched.`

1033`1034`

`Generalizations:`

1035`1036`

`· Maximal matching - a matching M of a graph G with the`

1037`property that if any edge not in M is added to M, it is`

1038`no longer a matching, that is, M is maximal if it is not`

1039`a proper subset of any other matching in graph G. In`

1040`other words, a matching M of a graph G is maximal if`

1041`every edge in G has a non-empty intersection with at`

1042`least one edge in M.`

1043`1044`

`· Maximum matching - a matching that contains the largest`

1045`possible number of edges. There may be many maximum`

1046`matchings. The matching number of a graph G is the size`

1047`of a maximum matching. Note that every maximum matching`

1048`is maximal, but not every maximal matching is a maximum`

1049`matching.`

1050`1051`

`· Perfect matching - a matching which matches all vertices`

1052`of the graph. That is, every vertex of the graph is inci‐`

1053`dent to exactly one edge of the matching. Every perfect`

1054`matching is maximum and hence maximal. In some litera‐`

1055`ture, the term complete matching is used. A perfect`

1056`matching is also a minimum-size edge cover. Moreover, the`

1057`size of a maximum matching is no larger than the size of`

1058`a minimum edge cover.`

1059`1060`

`· Near-perfect matching - a matching in which exactly one`

1061`vertex is unmatched. This can only occur when the graph`

1062`has an odd number of vertices, and such a matching must`

1063`be maximum. If, for every vertex in a graph, there is a`

1064`near-perfect matching that omits only that vertex, the`

1065`graph is also called factor-critical.`

1066`1067`

`Related terms:`

1068`1069`

`· Alternating path - given a matching M, an alternating`

1070`path is a path in which the edges belong alternatively to`

1071`the matching and not to the matching.`

1072`1073`

`· Augmenting path - given a matching M, an augmenting path`

1074`is an alternating path that starts from and ends on free`

1075`(unmatched) vertices.`

1076`1077`

`CUT PROBLEMS`

1078`Definition:`

1079`A cut is a partition of the vertices of a graph into two dis‐`

1080`joint subsets. The cut-set of the cut is the set of edges whose`

1081`end points are in different subsets of the partition. Edges are`

1082`said to be crossing the cut if they are in its cut-set.`

1083`1084`

`Formally:`

1085`1086`

`· a cut C = (S,T) is a partition of V of a graph G = (V,`

1087`E).`

1088`1089`

`· an s-t cut C = (S,T) of a flow network N = (V, E) is a`

1090`cut of N such that s is included in S and t is included`

1091`in T, where s and t are the source and the sink of N`

1092`respectively.`

1093`1094`

`· The cut-set of a cut C = (S,T) is such set of edges from`

1095`graph G = (V, E) that each edge (u, v) satisfies condi‐`

1096`tion that u is included in S and v is included in T.`

1097`1098`

`In an unweighted undirected graph, the size or weight of a cut is the`

1099`number of edges crossing the cut. In a weighted graph, the same term is`

1100`defined by the sum of the weights of the edges crossing the cut.`

1101`1102`

`In a flow network, an s-t cut is a cut that requires the source and the`

1103`sink to be in different subsets, and its cut-set only consists of edges`

1104`going from the source's side to the sink's side. The capacity of an s-t`

1105`cut is defined by the sum of capacity of each edge in the cut-set.`

1106`1107`

`The cut of a graph can sometimes refer to its cut-set instead of the`

1108`partition.`

1109`1110`

`Generalizations:`

1111`1112`

`· Minimum cut - A cut is minimum if the size of the cut is`

1113`not larger than the size of any other cut.`

1114`1115`

`· Maximum cut - A cut is maximum if the size of the cut is`

1116`not smaller than the size of any other cut.`

1117`1118`

`· Sparsest cut - The Sparsest cut problem is to bipartition`

1119`the vertices so as to minimize the ratio of the number of`

1120`edges across the cut divided by the number of vertices in`

1121`the smaller half of the partition.`

1122`1123`

`K-CENTER PROBLEM`

1124`Definitions:`

1125`1126`

`Unweighted K-Center`

1127`For any set S ( which is subset of V ) and node v, let`

1128`the connect(v,S) be the cost of cheapest edge connecting`

1129`v with any node in S. The goal is to find such S, that`

1130`|S| = k and max_v{connect(v,S)} is possibly small.`

1131`1132`

`In other words, we can use it i.e. for finding best loca‐`

1133`tions in the city ( nodes of input graph ) for placing k`

1134`buildings, such that those buildings will be as close as`

1135`possible to all other locations in town.`

1136`1137`

`1138`

`Weighted K-Center`

1139`The variation of unweighted k-center problem. Besides the`

1140`fact graph is edge-weighted, there are also weights on`

1141`vertices of input graph G. We've got also restriction W.`

1142`The goal is to choose such set of nodes S ( which is a`

1143`subset of V ), that it's total weight is not greater than`

1144`W and also function: max_v { min_u { cost(u,v) }} has the`

1145`smallest possible worth ( v is a node in V and u is a`

1146`node in S ).`

1147`1148`

`FLOW PROBLEMS`

1149`Definitions:`

1150`1151`

`· the maximum flow problem - the goal is to find a feasible`

1152`flow through a single-source, single-sink flow network`

1153`that is maximum. The maximum flow problem can be seen as`

1154`a special case of more complex network flow problems,`

1155`such as the circulation problem. The maximum value of an`

1156`s-t flow is equal to the minimum capacity of an s-t cut`

1157`in the network, as stated in the max-flow min-cut theo‐`

1158`rem.`

1159`1160`

`More formally for flow network G = (V,E), where for each`

1161`edge (u, v) we have its throuhgput c(u,v) defined. As`

1162`flow F we define set of non-negative integer attributes`

1163`f(u,v) assigned to edges, satisfying such conditions:`

1164`1165`

`[1] for each edge (u, v) in G such condition should be`

1166`satisfied: 0 <= f(u,v) <= c(u,v)`

1167`1168`

`[2] Network G has source node s such that the flow F`

1169`is equal to the sum of outcoming flow decreased by`

1170`the sum of incoming flow from that source node s.`

1171`1172`

`[3] Network G has sink node t such that the the -F`

1173`value is equal to the sum of the incoming flow`

1174`decreased by the sum of outcoming flow from that`

1175`sink node t.`

1176`1177`

`[4] For each node that is not a source or sink the sum`

1178`of incoming flow and sum of outcoming flow should`

1179`be equal.`

1180`1181`

`· the minimum cost flow problem - the goal is finding the`

1182`cheapest possible way of sending a certain amount of flow`

1183`through a flow network.`

1184`1185`

`· blocking flow - a blocking flow for a residual network Gf`

1186`we name such flow b in Gf that:`

1187`1188`

`[1] Each path from sink to source is the shortest path`

1189`in Gf.`

1190`1191`

`[2] Each shortest path in Gf contains an edge with`

1192`fully used throughput in Gf+b.`

1193`1194`

`· residual network - for a flow network G and flow f resid‐`

1195`ual network is built with those edges, which can send`

1196`larger flow. It contains only those edges, which can send`

1197`flow larger than 0.`

1198`1199`

`· level network - it has the same set of nodes as residual`

1200`graph, but has only those edges (u,v) from Gf for which`

1201`such equality is satisfied: distance(s,u)+1 = dis‐`

1202`tance(s,v).`

1203`1204`

`· augmenting network - it is a modification of residual`

1205`network considering the new flow values. Structure stays`

1206`unchanged but values of throughputs and costs at edges`

1207`are different.`

1208`1209`

`APPROXIMATION ALGORITHM`

1210`k-approximation algorithm:`

1211`Algorithm is a k-approximation, when for ALG (solution returned`

1212`by algorithm) and OPT (optimal solution), such inequality is`

1213`true:`

1214`1215`

`· for minimalization problems: ALG/OPT <= k`

1216`1217`

`· for maximalization problems: OPT/ALG <= k`

1218

## REFERENCES

1220`[1] Adjacency matrix [http://en.wikipedia.org/wiki/Adjacency_matrix]`

1221`1222`

`[2] Adjacency list [http://en.wikipedia.org/wiki/Adjacency_list]`

1223`1224`

`[3] Kruskal's algorithm`

1225`[http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]`

1226`1227`

`[4] Prim's algorithm [http://en.wikipedia.org/wiki/Prim%27s_algo‐`

1228`rithm]`

1229`1230`

`[5] Bipartite graph [http://en.wikipedia.org/wiki/Bipartite_graph]`

1231`1232`

`[6] Strongly connected components`

1233`[http://en.wikipedia.org/wiki/Strongly_connected_components]`

1234`1235`

`[7] Tarjan's strongly connected components algorithm`

1236`[http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_com‐`

1237`ponents_algorithm]`

1238`1239`

`[8] Cut vertex [http://en.wikipedia.org/wiki/Cut_vertex]`

1240`1241`

`[9] Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)]`

1242`1243`

`[10] Bellman-Ford's algorithm [http://en.wikipedia.org/wiki/Bellman-`

1244`Ford_algorithm]`

1245`1246`

`[11] Johnson's algorithm [http://en.wikipedia.org/wiki/Johnson_algo‐`

1247`rithm]`

1248`1249`

`[12] Floyd-Warshall's algorithm [http://en.wikipedia.org/wiki/Floyd-`

1250`Warshall_algorithm]`

1251`1252`

`[13] Travelling Salesman Problem [http://en.wikipedia.org/wiki/Trav‐`

1253`elling_salesman_problem]`

1254`1255`

`[14] Christofides Algorithm`

1256`[http://en.wikipedia.org/wiki/Christofides_algorithm]`

1257`1258`

`[15] Max Cut [http://en.wikipedia.org/wiki/Maxcut]`

1259`1260`

`[16] Matching [http://en.wikipedia.org/wiki/Matching]`

1261`1262`

`[17] Max Independent Set [http://en.wikipedia.org/wiki/Maximal_inde‐`

1263`pendent_set]`

1264`1265`

`[18] Vertex Cover [http://en.wikipedia.org/wiki/Vertex_cover_problem]`

1266`1267`

`[19] Ford-Fulkerson's algorithm [http://en.wikipedia.org/wiki/Ford-`

1268`Fulkerson_algorithm]`

1269`1270`

`[20] Maximum Flow problem [http://en.wikipedia.org/wiki/Maxi‐`

1271`mum_flow_problem]`

1272`1273`

`[21] Busacker-Gowen's algorithm [http://en.wikipedia.org/wiki/Mini‐`

1274`mum_cost_flow_problem]`

1275`1276`

`[22] Dinic's algorithm [http://en.wikipedia.org/wiki/Dinic's_algo‐`

1277`rithm]`

1278`1279`

`[23] K-Center problem [http://www.csc.kth.se/~viggo/wwwcom‐`

1280`pendium/node128.html]`

1281`1282`

`[24] BFS [http://en.wikipedia.org/wiki/Breadth-first_search]`

1283`1284`

`[25] Minimum Degree Spanning Tree`

1285`[http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree]`

1286`1287`

`[26] Approximation algorithm [http://en.wikipedia.org/wiki/Approxima‐`

1288`tion_algorithm]`

1289

## BUGS, IDEAS, FEEDBACK

1291`This document, and the package it describes, will undoubtedly contain`

1292`bugs and other problems. Please report such in the category struct ::`

1293`graph of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].`

1294`Please also report any ideas for enhancements you may have for either`

1295`package and/or documentation.`

1296`1297`

`When proposing code changes, please provide unified diffs, i.e the out‐`

1298`put of diff -u.`

1299`1300`

`Note further that attachments are strongly preferred over inlined`

1301`patches. Attachments can be made by going to the Edit form of the`

1302`ticket immediately after its creation, and then using the left-most`

1303`button in the secondary navigation bar.`

1304

## KEYWORDS

1306`adjacency list, adjacency matrix, adjacent, approximation algorithm,`

1307`arc, articulation point, augmenting network, augmenting path, bfs,`

1308`bipartite, blocking flow, bridge, complete graph, connected component,`

1309`cut edge, cut vertex, degree, degree constrained spanning tree, diame‐`

1310`ter, dijkstra, distance, eccentricity, edge, flow network, graph,`

1311`heuristic, independent set, isthmus, level graph, local searching,`

1312`loop, matching, max cut, maximum flow, minimal spanning tree, minimum`

1313`cost flow, minimum degree spanning tree, minimum diameter spanning`

1314`tree, neighbour, node, radius, residual graph, shortest path, squared`

1315`graph, strongly connected component, subgraph, travelling salesman,`

1316`vertex, vertex cover`

1317

## CATEGORY

1319`Data structures`

1320

## COPYRIGHT

1322`Copyright (c) 2008 Alejandro Paz <vidriloco@gmail.com>`

1323`Copyright (c) 2008 (docs) Andreas Kupries <andreas_kupries@users.sourceforge.net>`

1324`Copyright (c) 2009 Michal Antoniewski <antoniewski.m@gmail.com>`

1325`1326`

`1327`

`1328`

`1329`

`tcllib 0.11.3 struct::graph::op(n)`