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.11.3?
14 struct::graph::op::toAdjacencyMatrix g
16 struct::graph::op::toAdjacencyList G ?options...?
18 struct::graph::op::kruskal g
20 struct::graph::op::prim g
22 struct::graph::op::isBipartite? g ?bipartvar?
24 struct::graph::op::tarjan g
26 struct::graph::op::connectedComponents g
28 struct::graph::op::connectedComponentOf g n
30 struct::graph::op::isConnected? g
32 struct::graph::op::isCutVertex? g n
34 struct::graph::op::isBridge? g a
36 struct::graph::op::isEulerian? g ?tourvar?
38 struct::graph::op::isSemiEulerian? g ?pathvar?
40 struct::graph::op::dijkstra g start ?options...?
42 struct::graph::op::distance g origin destination ?options...?
44 struct::graph::op::eccentricity g n ?options...?
46 struct::graph::op::radius g ?options...?
48 struct::graph::op::diameter g ?options...?
50 struct::graph::op::BellmanFord G startnode
52 struct::graph::op::Johnsons G ?options...?
54 struct::graph::op::FloydWarshall G
56 struct::graph::op::MetricTravellingSalesman G
58 struct::graph::op::Christofides G
60 struct::graph::op::GreedyMaxMatching G
62 struct::graph::op::MaxCut G U V
64 struct::graph::op::UnweightedKCenter G k
66 struct::graph::op::WeightedKCenter G nodeWeights W
68 struct::graph::op::GreedyMaxIndependentSet G
70 struct::graph::op::GreedyWeightedMaxIndependentSet G nodeWeights
72 struct::graph::op::VerticesCover G
74 struct::graph::op::EdmondsKarp G s t
76 struct::graph::op::BusackerGowen G desiredFlow s t
78 struct::graph::op::ShortestsPathsByBFS G s outputFormat
80 struct::graph::op::BFS G s ?outputFormat...?
82 struct::graph::op::MinimumDiameterSpanningTree G
84 struct::graph::op::MinimumDegreeSpanningTree G
86 struct::graph::op::MaximumFlowByDinic G s t blockingFlowAlg
88 struct::graph::op::BlockingFlowByDinic G s t
90 struct::graph::op::BlockingFlowByMKM G s t
92 struct::graph::op::createResidualGraph G f
94 struct::graph::op::createAugmentingNetwork G f path
96 struct::graph::op::createLevelGraph Gf s
98 struct::graph::op::TSPLocalSearching G C
100 struct::graph::op::TSPLocalSearching3Approx G C
102 struct::graph::op::createSquaredGraph G
104 struct::graph::op::createCompleteGraph G originalEdges
106______________________________________________________________________________
108
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 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
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 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 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 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 Arguments:
145 Graph object G (input)
147 A graph to convert into an Adjacency List.
148 Options:
150 -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 -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 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 The command will throw an error if one or more arcs in g have no
175 weight associated with them.
176 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 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 The command will throw an error if one or more arcs in g have no
193 weight associated with them.
194 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 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 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 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 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 The graph g is connected if the result contains only a single
225 SCC containing all nodes of g.
226 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 The command will throw an error if n is not a node of the graph
233 g.
234 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 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 The command will throw an error if n is not a node of the graph
246 g.
247 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 The command will throw an error if a is not an arc of the graph
254 g.
255 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 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 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 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 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 Two options are recognized
282 -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 -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 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 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 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 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 The (un)directed radius of a graph is the minimal (un)directed
317 eccentricity of all nodes in the graph.
318 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 The (un)directed diameter of a graph is the maximal (un)directed
325 eccentricity of all nodes in the graph.
326 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 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 Arguments:
339 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 Node startnode (input)
349 The node for which we find all shortest paths to
350 each other node in graph G.
351 Result:
353 Dictionary containing for each node (key) distances to
354 each other node in graph G.
355 Note: If algorithm finds a negative cycle, it will return error mes‐
357 sage.
358 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 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 Arguments:
371 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 Options:
381 -filter
383 Returns only existing distances, cuts all Inf val‐
384 ues for non-existing connections between pairs of
385 nodes.
386 Result:
388 Dictionary containing distances between all pairs of ver‐
389 tices.
390 struct::graph::op::FloydWarshall G
392 Searching for shortest paths between all pairs of edges in
393 weighted graphs.
394 Time complexity: O(V^3) - where V is number of vertices.
396 Memory complexity: O(V^2).
398 Arguments:
401 Graph object G (input)
403 Directed and weighted graph G.
404 Result:
406 Dictionary containing shortest distances to each node
407 from each node.
408 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 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 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 Arguments:
429 Graph object G (input)
431 Undirected, weighted graph G.
432 Result:
434 Approximated solution of minimum Hamilton Cycle - closed
435 path visiting all nodes, each exactly one time.
436 Note: It's 2-approximation algorithm.
438 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 Arguments:
446 Graph Object G (input)
448 Undirected, weighted graph G.
449 Result:
451 Approximated solution of minimum Hamilton Cycle - closed
452 path visiting all nodes, each exactly one time.
453 Note: It's is a 3/2 approximation algorithm.
455 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 Arguments:
463 Graph Object G (input)
465 Undirected graph G.
466 Result:
468 Set of edges - the max matching for graph G.
469 struct::graph::op::MaxCut G U V
471 Algorithm solving a Maximum Cut Problem.
472 Arguments:
475 Graph Object G (input)
477 The graph to cut.
478 List U (output)
480 Variable storing first set of nodes (cut) given by
481 solution.
482 List V (output)
484 Variable storing second set of nodes (cut) given
485 by solution.
486 Result:
488 Algorithm returns number of edges between found two sets
489 of nodes.
490 Note: MaxCut is a 2-approximation algorithm.
492 struct::graph::op::UnweightedKCenter G k
494 Approximation algorithm that solves a k-center problem.
495 Arguments:
498 Graph Object G (input)
500 Undirected complete graph G, which satisfies tri‐
501 angle inequality.
502 Integer k (input)
505 Positive integer that sets the number of nodes
506 that will be included in k-center.
507 Result:
509 Set of nodes - k center for graph G.
510 Note: UnweightedKCenter is a 2-approximation algorithm.
512 struct::graph::op::WeightedKCenter G nodeWeights W
514 Approximation algorithm that solves a weighted version of k-cen‐
515 ter problem.
516 Arguments:
519 Graph Object G (input)
521 Undirected complete graph G, which satisfies tri‐
522 angle inequality.
523 Integer W (input)
525 Positive integer that sets the maximum possible
526 weight of k-center found by algorithm.
527 List nodeWeights (input)
529 List of nodes and its weights in graph G.
530 Result:
532 Set of nodes, which is solution found by algorithm.
533 Note:WeightedKCenter is a 3-approximation algorithm.
535 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 Algorithm for input graph G returns set of nodes (list), which
541 are contained in Max Independent Set found by algorithm.
542 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 Note: Read also Maximal Independent Set description for more
549 info.
550 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 struct::graph::op::EdmondsKarp G s t
562 Improved Ford-Fulkerson's algorithm, computing the maximum flow
563 in given flow network G.
564 Arguments:
567 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 Node s (input)
575 The node that is a source for graph G.
576 Node t (input)
578 The node that is a sink for graph G.
579 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 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 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 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 Arguments:
609 Graph Object G (input)
611 Flow network (directed graph), each edge in graph
612 should have two integer attributes: cost and
613 throughput.
614 Integer desiredFlow (input)
616 Max value of the flow for that network.
617 Node s (input)
619 The source node for graph G.
620 Node t (input)
622 The sink node for graph G.
623 Result:
625 Dictionary containing values of used throughputs for each
626 edge ( key ). found by algorithm.
627 Note: Algorithm complexity : O(V**2*desiredFlow), where V is the
629 number of nodes in graph G.
630 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 Arguments:
642 Graph Object G (input)
644 Input graph.
645 Node s (input)
647 Source node for which all distances to each other
648 node in graph G are computed.
649 Options and result:
651 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 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 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 Arguments:
670 Graph Object G (input)
672 Input graph.
673 Node s (input)
675 Source node for BFS procedure.
676 Options and result:
678 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 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 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 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 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 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 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 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 It can be proven that solution found with the algorithm must
719 fulfil inequality:
720 ((|W| + k - 1) / |W|) <= ALG <= 2*OPT + log2(n) + 1.
722 Arguments:
725 Graph Object G (input)
727 Undirected simple graph.
728 Result:
730 Algorithm returns graph structure, which is equivalent to
731 spanning tree T found by algorithm.
732 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 Arguments:
741 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 Node s (input)
748 The source node for the flow network G.
749 Node t (input)
751 The sink node for the flow network G.
752 Options:
754 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 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 Result:
766 Algorithm returns dictionary containing it's flow value
767 for each edge (key) in network G.
768 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 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 Arguments:
781 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 Node s (input)
788 The source node for the flow network G.
789 Node t (input)
791 The sink node for the flow network G.
792 Result:
794 Algorithm returns dictionary containing it's blocking
795 flow value for each edge (key) in network G.
796 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 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 Arguments:
807 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 Node s (input)
814 The source node for the flow network G.
815 Node t (input)
817 The sink node for the flow network G.
818 Result:
820 Algorithm returns dictionary containing it's blocking
821 flow value for each edge (key) in network G.
822 Note: Algorithm's complexity is O(n^2), where n is the number of
824 nodes in flow network G.
825 struct::graph::op::createResidualGraph G f
827 Procedure creates a residual graph (or residual network ) for
828 network G and given flow f.
829 Arguments:
832 Graph Object G (input)
834 Flow network (directed graph where each edge has
835 set attribute: throughput ).
836 dictionary f (input)
838 Current flows in flow network G.
839 Result:
841 Procedure returns graph structure that is a residual
842 graph created from input flow network G.
843 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 Arguments:
850 Graph Object G (input)
852 Residual network (directed graph), where for every
853 edge there are set two attributes: throughput and
854 cost.
855 Dictionary f (input)
857 Dictionary which contains for every edge (key),
858 current value of the flow on that edge.
859 List path (input)
861 Augmenting path, set of edges (list) for which we
862 create the network modification.
863 Result:
865 Algorithm returns graph structure containing the modified
866 augmenting network.
867 struct::graph::op::createLevelGraph Gf s
869 For given residual graph Gf procedure finds the level graph.
870 Arguments:
873 Graph Object Gf (input)
875 Residual network, where each edge has it's
876 attribute throughput set with certain value.
877 Node s (input)
879 The source node for the residual network Gf.
880 Result:
882 Procedure returns a level graph created from input resid‐
883 ual network.
884 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 Arguments:
894 Graph Object G (input)
896 Undirected and complete graph with attributes
897 "weight" set on each single edge.
898 List C (input)
900 A list of edges being Hamiltonian cycle, which is
901 solution of TSP Problem for graph G.
902 Result:
904 Algorithm returns the best solution for TSP problem, it
905 was able to find.
906 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 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 Arguments:
921 Graph Object G (input)
923 Undirected and complete graph with attributes
924 "weight" set on each single edge.
925 List C (input)
927 A list of edges being Hamiltonian cycle, which is
928 solution of TSP Problem for graph G.
929 Result:
931 Algorithm returns the best solution for TSP problem, it
932 was able to find.
933 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 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 Procedure for input graph G, returns its two-squared graph.
948 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 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
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 Generalizations:
966 · 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 · 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 · 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 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 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 Generalizations:
997 · 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 · 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 · 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 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 Generalizations:
1035 · 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 · 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 · 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 · 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 Related terms:
1068 · 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 · 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 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 Formally:
1085 · a cut C = (S,T) is a partition of V of a graph G = (V,
1087 E).
1088 · 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 · 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 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 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 The cut of a graph can sometimes refer to its cut-set instead of the
1108 partition.
1109 Generalizations:
1111 · Minimum cut - A cut is minimum if the size of the cut is
1113 not larger than the size of any other cut.
1114 · Maximum cut - A cut is maximum if the size of the cut is
1116 not smaller than the size of any other cut.
1117 · 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 K-CENTER PROBLEM
1124 Definitions:
1125 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 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 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 FLOW PROBLEMS
1149 Definitions:
1150 · 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 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 [1] for each edge (u, v) in G such condition should be
1166 satisfied: 0 <= f(u,v) <= c(u,v)
1167 [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 [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 [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 · 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 · blocking flow - a blocking flow for a residual network Gf
1186 we name such flow b in Gf that:
1187 [1] Each path from sink to source is the shortest path
1189 in Gf.
1190 [2] Each shortest path in Gf contains an edge with
1192 fully used throughput in Gf+b.
1193 · 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 · 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 · 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 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 · for minimalization problems: ALG/OPT <= k
1216 · for maximalization problems: OPT/ALG <= k
1218
1220 [1] Adjacency matrix [http://en.wikipedia.org/wiki/Adjacency_matrix]
1221 [2] Adjacency list [http://en.wikipedia.org/wiki/Adjacency_list]
1223 [3] Kruskal's algorithm
1225 [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm]
1226 [4] Prim's algorithm [http://en.wikipedia.org/wiki/Prim%27s_algo‐
1228 rithm]
1229 [5] Bipartite graph [http://en.wikipedia.org/wiki/Bipartite_graph]
1231 [6] Strongly connected components
1233 [http://en.wikipedia.org/wiki/Strongly_connected_components]
1234 [7] Tarjan's strongly connected components algorithm
1236 [http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_com‐
1237 ponents_algorithm]
1238 [8] Cut vertex [http://en.wikipedia.org/wiki/Cut_vertex]
1240 [9] Bridge [http://en.wikipedia.org/wiki/Bridge_(graph_theory)]
1242 [10] Bellman-Ford's algorithm [http://en.wikipedia.org/wiki/Bellman-
1244 Ford_algorithm]
1245 [11] Johnson's algorithm [http://en.wikipedia.org/wiki/Johnson_algo‐
1247 rithm]
1248 [12] Floyd-Warshall's algorithm [http://en.wikipedia.org/wiki/Floyd-
1250 Warshall_algorithm]
1251 [13] Travelling Salesman Problem [http://en.wikipedia.org/wiki/Trav‐
1253 elling_salesman_problem]
1254 [14] Christofides Algorithm
1256 [http://en.wikipedia.org/wiki/Christofides_algorithm]
1257 [15] Max Cut [http://en.wikipedia.org/wiki/Maxcut]
1259 [16] Matching [http://en.wikipedia.org/wiki/Matching]
1261 [17] Max Independent Set [http://en.wikipedia.org/wiki/Maximal_inde‐
1263 pendent_set]
1264 [18] Vertex Cover [http://en.wikipedia.org/wiki/Vertex_cover_problem]
1266 [19] Ford-Fulkerson's algorithm [http://en.wikipedia.org/wiki/Ford-
1268 Fulkerson_algorithm]
1269 [20] Maximum Flow problem [http://en.wikipedia.org/wiki/Maxi‐
1271 mum_flow_problem]
1272 [21] Busacker-Gowen's algorithm [http://en.wikipedia.org/wiki/Mini‐
1274 mum_cost_flow_problem]
1275 [22] Dinic's algorithm [http://en.wikipedia.org/wiki/Dinic's_algo‐
1277 rithm]
1278 [23] K-Center problem [http://www.csc.kth.se/~viggo/wwwcom‐
1280 pendium/node128.html]
1281 [24] BFS [http://en.wikipedia.org/wiki/Breadth-first_search]
1283 [25] Minimum Degree Spanning Tree
1285 [http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree]
1286 [26] Approximation algorithm [http://en.wikipedia.org/wiki/Approxima‐
1288 tion_algorithm]
1289
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 When proposing code changes, please provide unified diffs, i.e the out‐
1298 put of diff -u.
1299 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
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
1319 Data structures
1320
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>
1325tcllib 0.11.3 struct::graph::op(n)