1[comment {-*- tcl -*-}] 2[manpage_begin struct::graph::op n 0.11.3] 3[copyright {2008 Alejandro Paz <vidriloco@gmail.com>}] 4[copyright {2008 (docs) Andreas Kupries <andreas_kupries@users.sourceforge.net>}] 5[copyright {2009 Michal Antoniewski <antoniewski.m@gmail.com>}] 6[moddesc {Tcl Data Structures}] 7[titledesc {Operation for (un)directed graph objects}] 8[category {Data structures}] 9[require Tcl 8.4] 10[require struct::graph::op [opt 0.11.3]] 11[comment {[require struct::graph [opt 2.3]] }] 12[comment {[require struct::list [opt 1.5]] }] 13[comment {[require struct::set [opt 2.2.3]] }] 14[description] 15[para] 16 17The package described by this document, [package struct::graph::op], 18is a companion to the package [package struct::graph]. It provides a 19series of common operations and algorithms applicable to (un)directed 20graphs. 21 22[para] 23 24Despite being a companion the package is not directly dependent on 25[package struct::graph], only on the API defined by that 26package. I.e. the operations of this package can be applied to any and 27all graph objects which provide the same API as the objects created 28through [package struct::graph]. 29 30[section {Operations}] 31 32[list_begin definitions] 33 34[call [cmd struct::graph:op::toAdjacencyMatrix] [arg g]] 35 36This command takes the graph [arg g] and returns a nested list 37containing the adjacency matrix of [arg g]. 38 39[para] 40 41The elements of the outer list are the rows of the matrix, the inner 42elements are the column values in each row. The matrix has "[var n]+1" 43rows and columns, with the first row and column (index 0) containing 44the name of the node the row/column is for. All other elements are 45boolean values, [const True] if there is an arc between the 2 nodes 46of the respective row and column, and [const False] otherwise. 47 48[para] 49 50Note that the matrix is symmetric. It does not represent the 51directionality of arcs, only their presence between nodes. It is also 52unable to represent parallel arcs in [arg g]. 53 54 55 56[call [cmd struct::graph:op::toAdjacencyList] [arg G] [opt [arg options]...]] 57 58Procedure creates for input graph [arg G], it's representation as [term "Adjacency List"]. 59It handles both directed and undirected graphs (default is undirected). 60It returns dictionary that for each node (key) returns list of nodes adjacent 61to it. When considering weighted version, for each adjacent node there is also 62weight of the edge included. 63 64[para] 65[list_begin definitions] 66[def Arguments:] 67 68[list_begin arguments] 69[arg_def {Graph object} G input] 70A graph to convert into an [term "Adjacency List"]. 71 72[list_end][comment {-- arguments --}] 73 74[def Options:] 75[list_begin options] 76[opt_def -directed] 77 78By default [arg G] is operated as if it were an [term {Undirected graph}]. 79Using this option tells the command to handle [arg G] as the directed graph it is. 80 81[opt_def -weights] 82 83By default any weight information the graph [arg G] may have is ignored. 84Using this option tells the command to put weight information into the result. 85In that case it is expected that all arcs have a proper weight, and an error 86is thrown if that is not the case. 87 88[list_end][comment {-- options --}] 89[list_end][comment {-- definitions --}] 90 91 92 93[call [cmd struct::graph:op::kruskal] [arg g]] 94 95This command takes the graph [arg g] and returns a list containing the 96names of the arcs in [arg g] which span up a minimum weight spanning tree 97(MST), or, in the case of an un-connected graph, a minimum weight spanning 98forest (except for the 1-vertex components). Kruskal's algorithm is used 99to compute the tree or forest. 100 101This algorithm has a time complexity of [term {O(E*log E)}] or [term {O(E* log V)}], 102where [term V] is the number of vertices and [term E] is the number of edges 103in graph [arg g]. 104 105[para] 106 107The command will throw an error if one or more arcs in [arg g] have no 108weight associated with them. 109 110[para] 111 112A note regarding the result, the command refrains from explicitly 113listing the nodes of the MST as this information is implicitly 114provided in the arcs already. 115 116 117 118[call [cmd struct::graph:op::prim] [arg g]] 119 120This command takes the graph [arg g] and returns a list containing the 121names of the arcs in [arg g] which span up a minimum weight spanning tree 122(MST), or, in the case of an un-connected graph, a minimum weight spanning 123forest (except for the 1-vertex components). Prim's algorithm is used to 124compute the tree or forest. 125 126This algorithm has a time complexity between [term {O(E+V*log V)}] and [term {O(V*V)}], 127depending on the implementation (Fibonacci heap + Adjacency list versus 128Adjacency Matrix). As usual [term V] is the number of vertices and 129[term E] the number of edges in graph [arg g]. 130 131[para] 132 133The command will throw an error if one or more arcs in [arg g] have no 134weight associated with them. 135 136[para] 137 138A note regarding the result, the command refrains from explicitly 139listing the nodes of the MST as this information is implicitly 140provided in the arcs already. 141 142 143 144[call [cmd struct::graph:op::isBipartite?] [arg g] [opt [arg bipartvar]]] 145 146This command takes the graph [arg g] and returns a boolean value 147indicating whether it is bipartite ([const true]) or not 148([const false]). If the variable [arg bipartvar] is specified the two 149partitions of the graph are there as a list, if, and only if the graph 150is bipartit. If it is not the variable, if specified, is not touched. 151 152 153 154[call [cmd struct::graph:op::tarjan] [arg g]] 155 156This command computes the set of [emph {strongly connected}] 157components (SCCs) of the graph [arg g]. The result of the command is a 158list of sets, each of which contains the nodes for one of the SCCs of 159[arg g]. The union of all SCCs covers the whole graph, and no two SCCs 160intersect with each other. 161 162[para] 163 164The graph [arg g] is [term acyclic] if all SCCs in the result contain 165only a single node. The graph [arg g] is [term {strongly connected}] 166if the result contains only a single SCC containing all nodes of 167[arg g]. 168 169 170 171[call [cmd struct::graph:op::connectedComponents] [arg g]] 172 173This command computes the set of [emph connected] components (CCs) of 174the graph [arg g]. The result of the command is a list of sets, each 175of which contains the nodes for one of the CCs of [arg g]. The union 176of all CCs covers the whole graph, and no two CCs intersect with each 177other. 178 179[para] 180 181The graph [arg g] is [term connected] if the result contains only a 182single SCC containing all nodes of [arg g]. 183 184 185[call [cmd struct::graph:op::connectedComponentOf] [arg g] [arg n]] 186 187This command computes the [emph connected] component (CC) of the graph 188[arg g] containing the node [arg n]. The result of the command is a 189sets which contains the nodes for the CC of [arg n] in [arg g]. 190 191[para] 192 193The command will throw an error if [arg n] is not a node of the graph 194[arg g]. 195 196 197 198[call [cmd struct::graph:op::isConnected?] [arg g]] 199 200This is a convenience command determining whether the graph [arg g] is 201[term connected] or not. The result is a boolean value, [const true] 202if the graph is connected, and [const false] otherwise. 203 204 205 206[call [cmd struct::graph:op::isCutVertex?] [arg g] [arg n]] 207 208This command determines whether the node [arg n] in the graph [arg g] 209is a [term {cut vertex}] (aka [term {articulation point}]). The result 210is a boolean value, [const true] if the node is a cut vertex, and 211[const false] otherwise. 212 213[para] 214 215The command will throw an error if [arg n] is not a node of the graph 216[arg g]. 217 218 219[call [cmd struct::graph:op::isBridge?] [arg g] [arg a]] 220 221This command determines whether the arc [arg a] in the graph [arg g] 222is a [term bridge] (aka [term {cut edge}], or [term isthmus]). The 223result is a boolean value, [const true] if the arc is a bridge, and 224[const false] otherwise. 225 226[para] 227 228The command will throw an error if [arg a] is not an arc of the graph 229[arg g]. 230 231 232[call [cmd struct::graph:op::isEulerian?] [arg g] [opt [arg tourvar]]] 233 234This command determines whether the graph [arg g] is [term eulerian] 235or not. The result is a boolean value, [const true] if the graph is 236eulerian, and [const false] otherwise. 237 238[para] 239 240If the graph is eulerian and [arg tourvar] is specified then an euler 241tour is computed as well and stored in the named variable. The tour is 242represented by the list of arcs traversed, in the order of traversal. 243 244 245[call [cmd struct::graph:op::isSemiEulerian?] [arg g] [opt [arg pathvar]]] 246 247This command determines whether the graph [arg g] is 248[term semi-eulerian] or not. The result is a boolean value, [const true] 249if the graph is semi-eulerian, and [const false] otherwise. 250 251[para] 252 253If the graph is semi-eulerian and [arg pathvar] is specified then an 254euler path is computed as well and stored in the named variable. The 255path is represented by the list of arcs traversed, in the order of 256traversal. 257 258 259[call [cmd struct::graph:op::dijkstra] [arg g] [arg start] [opt [arg options]...]] 260 261This command determines distances in the weighted [arg g] from the 262node [arg start] to all other nodes in the graph. The options specify 263how to traverse graphs, and the format of the result. 264 265[para] 266 267Two options are recognized 268 269[list_begin options] 270[opt_def -arcmode mode] 271 272The accepted mode values are [const directed] and [const undirected]. 273For directed traversal all arcs are traversed from source to 274target. For undirected traversal all arcs are traversed in the 275opposite direction as well. Undirected traversal is the default. 276 277[opt_def -outputformat format] 278 279The accepted format values are [const distances] and [const tree]. In 280both cases the result is a dictionary keyed by the names of all nodes 281in the graph. For [const distances] the value is the distance of the 282node to [arg start], whereas for [const tree] the value is the path 283from the node to [arg start], excluding the node itself, but including 284[arg start]. Tree format is the default. 285 286[list_end] 287 288 289[call [cmd struct::graph:op::distance] [arg g] [arg origin] [arg destination] [opt [arg options]...]] 290 291This command determines the (un)directed distance between the two 292nodes [arg origin] and [arg destination] in the graph [arg g]. It 293accepts the option [option -arcmode] of [cmd struct::graph:op::dijkstra]. 294 295 296[call [cmd struct::graph:op::eccentricity] [arg g] [arg n] [opt [arg options]...]] 297 298This command determines the (un)directed [term eccentricity] of the 299node [arg n] in the graph [arg g]. It accepts the option 300[option -arcmode] of [cmd struct::graph:op::dijkstra]. 301 302[para] 303 304The (un)directed [term eccentricity] of a node is the maximal 305(un)directed distance between the node and any other node in the 306graph. 307 308 309[call [cmd struct::graph:op::radius] [arg g] [opt [arg options]...]] 310 311This command determines the (un)directed [term radius] of the graph 312[arg g]. It accepts the option [option -arcmode] of [cmd struct::graph:op::dijkstra]. 313 314[para] 315 316The (un)directed [term radius] of a graph is the minimal (un)directed 317[term eccentricity] of all nodes in the graph. 318 319 320[call [cmd struct::graph:op::diameter] [arg g] [opt [arg options]...]] 321 322This command determines the (un)directed [term diameter] of the graph 323[arg g]. It accepts the option [option -arcmode] of [cmd struct::graph:op::dijkstra]. 324 325[para] 326 327The (un)directed [term diameter] of a graph is the maximal (un)directed 328[term eccentricity] of all nodes in the graph. 329 330 331 332[call [cmd struct::graph::op::BellmanFord] [arg G] [arg startnode]] 333 334Searching for [sectref {Shortest Path Problem} "shortests paths"] between chosen node and all other nodes in graph [arg G]. Based 335on relaxation method. In comparison to [cmd struct::graph::op::dijkstra] it doesn't need assumption that all weights 336on edges in input graph [arg G] have to be positive. 337 338[para] 339 340That generality sets the complexity of algorithm to - [term O(V*E)], where [term V] is the number of vertices 341and [term E] is number of edges in graph [arg G]. 342 343[para] 344[list_begin definitions] 345 346[def Arguments:] 347[list_begin arguments] 348[arg_def {Graph object} G input] 349Directed, connected and edge weighted graph [arg G], without any negative cycles ( presence of cycles with the negative sum 350of weight means that there is no shortest path, since the total weight becomes lower each time the cycle is 351traversed ). Negative weights on edges are allowed. 352 353[arg_def {Node} startnode input] 354The node for which we find all shortest paths to each other node in graph [arg G]. 355[list_end][comment {-- arguments --}] 356 357[def Result:] 358Dictionary containing for each node (key) distances to each other node in graph [arg G]. 359[list_end][comment {-- definitions --}] 360 361[para] 362 363[emph Note:] If algorithm finds a negative cycle, it will return error message. 364 365 366 367[call [cmd struct::graph::op::Johnsons] [arg G] [opt [arg options]...]] 368 369Searching for [sectref {Shortest Path Problem} "shortest paths"] between all pairs of vertices in graph. For sparse graphs 370asymptotically quicker than [cmd struct::graph::op::FloydWarshall] algorithm. Johnson's algorithm 371uses [cmd struct::graph::op::BellmanFord] and [cmd struct::graph::op::dijkstra] as subprocedures. 372 373[para] 374 375Time complexity: [term "O(n**2*log(n) +n*m)"], where [term n] is the number of nodes and [term m] is 376the number of edges in graph [arg G]. 377 378[para] 379 380[list_begin definitions] 381 382[def Arguments:] 383[list_begin arguments] 384[arg_def {Graph object} G input] 385 386Directed graph [arg G], weighted on edges and not containing 387any cycles with negative sum of weights ( the presence of such cycles means 388there is no shortest path, since the total weight becomes lower each time the 389cycle is traversed ). Negative weights on edges are allowed. 390 391[list_end][comment {-- arguments --}] 392 393[def Options:] 394[list_begin options] 395[opt_def -filter] 396 397Returns only existing distances, cuts all [term Inf] values for 398non-existing connections between pairs of nodes. 399 400[list_end][comment {-- options --}] 401 402[def Result:] 403 404Dictionary containing distances between all pairs of vertices. 405 406[list_end][comment {-- definitions --}] 407 408 409 410[call [cmd struct::graph::op::FloydWarshall] [arg G]] 411 412Searching for [sectref {Shortest Path Problem} "shortest paths"] between all pairs of edges in weighted graphs.[para] 413Time complexity: [term O(V^3)] - where [term V] is number of vertices.[para] 414Memory complexity: [term O(V^2)]. 415 416[para] 417 418[list_begin definitions] 419 420[def Arguments:] 421[list_begin arguments] 422[arg_def {Graph object} G input] 423 424Directed and weighted graph [arg G]. 425 426[list_end][comment {-- arguments --}] 427 428[def Result:] 429Dictionary containing shortest distances to each node from each node. 430[list_end][comment {-- definitions --}] 431 432[emph Note:] Algorithm finds solutions dynamically. It compares all possible paths through the graph 433between each pair of vertices. Graph shouldn't possess any cycle with negative 434sum of weights (the presence of such cycles means there is no shortest path, 435since the total weight becomes lower each time the cycle is traversed). 436[para] 437On the other hand algorithm can be used to find those cycles - if any shortest distance 438found by algorithm for any nodes [term v] and [term u] (when [term v] is the same node as [term u]) is negative, 439that node surely belong to at least one negative cycle. 440 441 442 443[call [cmd struct::graph::op::MetricTravellingSalesman] [arg G]] 444 445Algorithm for solving a metric variation of [sectref {Travelling Salesman Problem} "Travelling salesman problem"]. 446[term "TSP problem"] is [term NP-Complete], so there is no efficient algorithm to solve it. Greedy methods 447are getting extremely slow, with the increase in the set of nodes. 448 449[para] 450 451[list_begin definitions] 452 453[def Arguments:] 454[list_begin arguments] 455[arg_def {Graph object} G input] 456Undirected, weighted graph [arg G]. 457[list_end][comment {-- arguments --}] 458 459[def Result:] 460Approximated solution of minimum [term "Hamilton Cycle"] - closed path visiting all nodes, 461each exactly one time. 462 463[list_end][comment {-- definitions --}] 464 465[emph Note:] [sectref {Approximation algorithm} "It's 2-approximation algorithm."] 466 467 468 469[call [cmd struct::graph::op::Christofides] [arg G]] 470 471Another algorithm for solving [sectref {Travelling Salesman Problem} "metric [term "TSP problem"]"]. 472Christofides implementation uses [term "Max Matching"] for reaching better approximation factor. 473 474[para] 475 476[list_begin definitions] 477 478[def Arguments:] 479[list_begin arguments] 480[arg_def {Graph Object} G input] 481 482Undirected, weighted graph [arg G]. 483 484[list_end][comment {-- arguments --}] 485 486[def Result:] 487Approximated solution of minimum [term "Hamilton Cycle"] - closed path visiting all nodes, 488each exactly one time. 489 490[list_end][comment {-- definitions --}] 491 492[para] 493 494[emph Note:] [sectref {Approximation algorithm} "It's is a 3/2 approximation algorithm. "] 495 496 497 498[call [cmd struct::graph::op::GreedyMaxMatching] [arg G]] 499 500[term "Greedy Max Matching"] procedure, which finds [sectref {Matching Problem} "maximal matching"] (not maximum) 501for given graph [arg G]. It adds edges to solution, beginning from edges with the 502lowest cost. 503 504[para] 505[list_begin definitions] 506 507[def Arguments:] 508[list_begin arguments] 509[arg_def {Graph Object} G input] 510 511Undirected graph [arg G]. 512 513[list_end][comment {-- arguments --}] 514 515[def Result:] 516Set of edges - the max matching for graph [arg G]. 517 518[list_end][comment {-- definitions --}] 519 520 521 522[call [cmd struct::graph::op::MaxCut] [arg G] [arg U] [arg V]] 523 524Algorithm solving a [sectref {Cut Problems} "Maximum Cut Problem"]. 525 526[para] 527[list_begin definitions] 528 529[def Arguments:] 530[list_begin arguments] 531[arg_def {Graph Object} G input] 532 533The graph to cut. 534 535[arg_def {List} U output] 536 537Variable storing first set of nodes (cut) given by solution. 538 539[arg_def {List} V output] 540 541Variable storing second set of nodes (cut) given by solution. 542 543[list_end][comment {-- arguments --}] 544 545[def Result:] 546Algorithm returns number of edges between found two sets of nodes. 547 548[list_end][comment {-- definitions --}] 549 550[emph Note:] [term MaxCut] is a [sectref {Approximation algorithm} "2-approximation algorithm."] 551 552 553 554[call [cmd struct::graph::op::UnweightedKCenter] [arg G] [arg k]] 555 556Approximation algorithm that solves a [sectref {K-Center Problem} "k-center problem"]. 557 558 559[para] 560[list_begin definitions] 561 562[def Arguments:] 563[list_begin arguments] 564[arg_def {Graph Object} G input] 565Undirected complete graph [arg G], which satisfies triangle inequality.[para] 566[arg_def {Integer} k input] 567Positive integer that sets the number of nodes that will be included in [term "k-center"]. 568 569[list_end][comment {-- arguments --}] 570 571[def Result:] 572Set of nodes - [arg k] center for graph [arg G]. 573 574[list_end][comment {-- definitions --}] 575 576[emph Note:] [term UnweightedKCenter] is a [sectref {Approximation algorithm} "2-approximation algorithm."] 577 578 579 580[call [cmd struct::graph::op::WeightedKCenter] [arg G] [arg nodeWeights] [arg W]] 581 582Approximation algorithm that solves a weighted version of [sectref {K-Center Problem} "k-center problem"]. 583 584[para] 585[list_begin definitions] 586 587[def Arguments:] 588[list_begin arguments] 589[arg_def {Graph Object} G input] 590Undirected complete graph [arg G], which satisfies triangle inequality. 591[arg_def {Integer} W input] 592Positive integer that sets the maximum possible weight of [term "k-center"] found by algorithm. 593[arg_def {List} nodeWeights input] 594List of nodes and its weights in graph [arg G]. 595 596[list_end][comment {-- arguments --}] 597 598[def Result:] 599Set of nodes, which is solution found by algorithm. 600[list_end][comment {-- definitions --}] 601 602[emph Note:][term WeightedKCenter] is a [sectref {Approximation algorithm} "3-approximation algorithm."] 603 604 605 606[call [cmd struct::graph::op::GreedyMaxIndependentSet] [arg G]] 607 608A [term "maximal independent set"] is an [term "independent set"] such that adding any other node 609to the set forces the set to contain an edge. 610 611[para] 612 613Algorithm for input graph [arg G] returns set of nodes (list), which are contained in Max Independent 614Set found by algorithm. 615 616 617 618[call [cmd struct::graph::op::GreedyWeightedMaxIndependentSet] [arg G] [arg nodeWeights]] 619 620Weighted variation of [term "Maximal Independent Set"]. It takes as an input argument 621not only graph [arg G] but also set of weights for all vertices in graph [arg G]. 622 623[para] 624[emph Note:] 625Read also [term "Maximal Independent Set"] description for more info. 626 627 628 629[call [cmd struct::graph::op::VerticesCover] [arg G]] 630 631[term "Vertices cover"] is a set of vertices such that each edge of the graph is incident to 632at least one vertex of the set. This 2-approximation algorithm searches for minimum 633[term "vertices cover"], which is a classical optimization problem in computer science and 634is a typical example of an [term "NP-hard"] optimization problem that has an approximation 635algorithm. 636 637For input graph [arg G] algorithm returns the set of edges (list), which is Vertex Cover found by algorithm. 638 639 640 641[call [cmd struct::graph::op::EdmondsKarp] [arg G] [arg s] [arg t]] 642 643Improved Ford-Fulkerson's algorithm, computing the [sectref {Flow Problems} "maximum flow"] in given flow network [arg G]. 644 645[para] 646[list_begin definitions] 647 648[def Arguments:] 649[list_begin arguments] 650[arg_def {Graph Object} G input] 651Weighted and directed graph. Each edge should have set integer attribute considered as 652maximum throughputs that can be carried by that link (edge). 653[arg_def {Node} s input] 654The node that is a source for graph [arg G]. 655[arg_def {Node} t input] 656The node that is a sink for graph [arg G]. 657[list_end][comment {-- arguments --}] 658 659[def Result:] 660Procedure returns the dictionary containing throughputs for all edges. For 661each key ( the edge between nodes [term u] and [term v] in the form of [term "list u v"] ) there is 662a value that is a throughput for that key. Edges where throughput values 663are equal to 0 are not returned ( it is like there was no link in the flow network 664between nodes connected by such edge). 665 666[list_end][comment {-- definitions --}] 667 668[para] 669 670The general idea of algorithm is finding the shortest augumenting paths in graph [arg G], as long 671as they exist, and for each path updating the edge's weights along that path, 672with maximum possible throughput. The final (maximum) flow is found 673when there is no other augumenting path from source to sink. 674 675[para] 676 677[emph Note:] Algorithm complexity : [term O(V*E)], where [term V] is the number of nodes and [term E] is the number 678of edges in graph [term G]. 679 680 681 682[call [cmd struct::graph::op::BusackerGowen] [arg G] [arg desiredFlow] [arg s] [arg t]] 683 684Algorithm finds solution for a [sectref {Flow Problems} "minimum cost flow problem"]. So, the goal is to find a flow, 685whose max value can be [arg desiredFlow], from source node [arg s] to sink node [arg t] in given flow network [arg G]. 686That network except throughputs at edges has also defined a non-negative cost on each edge - cost of using that edge when 687directing flow with that edge ( it can illustrate e.g. fuel usage, time or any other measure dependent on usages ). 688 689[para] 690[list_begin definitions] 691 692[def Arguments:] 693[list_begin arguments] 694[arg_def {Graph Object} G input] 695Flow network (directed graph), each edge in graph should have two integer attributes: [term cost] and [term throughput]. 696[arg_def {Integer} desiredFlow input] 697Max value of the flow for that network. 698[arg_def {Node} s input] 699The source node for graph [arg G]. 700[arg_def {Node} t input] 701The sink node for graph [arg G]. 702 703[list_end][comment {-- arguments --}] 704 705[def Result:] 706Dictionary containing values of used throughputs for each edge ( key ). 707found by algorithm. 708 709[list_end][comment {-- definitions --}] 710 711[emph Note:] Algorithm complexity : [term O(V**2*desiredFlow)], where [term V] is the number of nodes in graph [arg G]. 712 713 714 715[call [cmd struct::graph::op::ShortestsPathsByBFS] [arg G] [arg s] [arg outputFormat]] 716 717Shortest pathfinding algorithm using BFS method. In comparison to [cmd struct::graph::op::dijkstra] it can 718work with negative weights on edges. Of course negative cycles are not allowed. Algorithm is better than dijkstra 719for sparse graphs, but also there exist some pathological cases (those cases generally don't appear in practise) that 720make time complexity increase exponentially with the growth of the number of nodes. 721 722[para] 723[list_begin definitions] 724 725[def Arguments:] 726[list_begin arguments] 727[arg_def {Graph Object} G input] 728Input graph. 729[arg_def {Node} s input] 730Source node for which all distances to each other node in graph [arg G] are computed. 731[list_end][comment {-- arguments --}] 732 733[def "Options and result:"] 734[list_begin options] 735[opt_def distances] 736 737When selected [arg outputFormat] is [const distances] - procedure returns dictionary containing 738distances between source node [arg s] and each other node in graph [arg G]. 739 740[opt_def paths] 741 742When selected [arg outputFormat] is [const paths] - procedure returns dictionary containing 743for each node [term v], a list of nodes, which is a path between source node [arg s] and node [term v]. 744 745[list_end][comment {-- options --}] 746 747 748 749[list_end][comment {-- definitions --}] 750 751 752 753[call [cmd struct::graph::op::BFS] [arg G] [arg s] [opt [arg outputFormat]...]] 754 755Breadth-First Search - algorithm creates the BFS Tree. 756Memory and time complexity: [term "O(V + E)"], where [term V] is the number of nodes and [term E] 757is number of edges. 758 759[para] 760[list_begin definitions] 761 762[def Arguments:] 763[list_begin arguments] 764[arg_def {Graph Object} G input] 765Input graph. 766[arg_def {Node} s input] 767Source node for BFS procedure. 768 769[list_end][comment {-- arguments --}] 770 771[def "Options and result:"] 772[list_begin options] 773[opt_def graph] 774 775When selected [option outputFormat] is [option graph] - procedure returns a graph structure ([cmd struct::graph]), 776which is equivalent to BFS tree found by algorithm. 777 778[opt_def tree] 779 780When selected [option outputFormat] is [option tree] - procedure returns a tree structure ([cmd struct::tree]), 781which is equivalent to BFS tree found by algorithm. 782 783[list_end][comment {-- options --}] 784 785[list_end][comment {-- definitions --}] 786 787 788 789[call [cmd struct::graph::op::MinimumDiameterSpanningTree] [arg G]] 790 791The goal is to find for input graph [arg G], the [term "spanning tree"] that 792has the minimum [term "diameter"] value. 793 794[para] 795 796General idea of algorithm is to run [term BFS] over all vertices in graph 797[arg G]. If the diameter [term d] of the tree is odd, then we are sure that tree 798given by [term BFS] is minimum (considering diameter value). When, diameter [term d] 799is even, then optimal tree can have minimum [term diameter] equal to [term d] or 800[term d-1]. 801 802[para] 803 804In that case, what algorithm does is rebuilding the tree given by [term BFS], by 805adding a vertice between root node and root's child node (nodes), such that 806subtree created with child node as root node is the greatest one (has the 807greatests height). In the next step for such rebuilded tree, we run again [term BFS] 808with new node as root node. If the height of the tree didn't changed, we have found 809a better solution. 810 811[para] 812 813For input graph [arg G] algorithm returns the graph structure ([cmd struct::graph]) that is 814a spanning tree with minimum diameter found by algorithm. 815 816 817 818[call [cmd struct::graph::op::MinimumDegreeSpanningTree] [arg G]] 819 820Algorithm finds for input graph [arg G], a spanning tree [term T] with the minimum possible 821degree. That problem is [term NP-hard], so algorithm is an approximation algorithm. 822 823[para] 824 825Let [term V] be the set of nodes for graph [arg G] and let [term W] be any subset of [term V]. Lets 826assume also that [term OPT] is optimal solution and [term ALG] is solution found by algorithm for input 827graph [arg G]. [para] 828It can be proven that solution found with the algorithm must fulfil inequality: [para] [term "((|W| + k - 1) / |W|) <= ALG <= 2*OPT + log2(n) + 1"]. 829 830[para] 831[list_begin definitions] 832 833[def Arguments:] 834[list_begin arguments] 835[arg_def {Graph Object} G input] 836Undirected simple graph. 837 838[list_end][comment {-- arguments --}] 839 840[def Result:] 841Algorithm returns graph structure, which is equivalent to spanning tree [term T] found by algorithm. 842 843[list_end][comment {-- definitions --}] 844 845 846 847[call [cmd struct::graph::op::MaximumFlowByDinic] [arg G] [arg s] [arg t] [arg blockingFlowAlg]] 848 849Algorithm finds [sectref {Flow Problems} "maximum flow"] for the flow network represented by graph [arg G]. It is based on 850the blocking-flow finding methods, which give us different complexities what makes a better fit for 851different graphs. 852 853[para] 854[list_begin definitions] 855 856[def Arguments:] 857[list_begin arguments] 858[arg_def {Graph Object} G input] 859Directed graph [arg G] representing the flow network. Each edge should have attribute 860[term throughput] set with integer value. 861 862[arg_def {Node} s input] 863The source node for the flow network [arg G]. 864 865[arg_def {Node} t input] 866The sink node for the flow network [arg G]. 867 868[list_end][comment {-- arguments --}] 869 870[def Options:] 871[list_begin options] 872[opt_def dinic] 873Procedure will find maximum flow for flow network [arg G] using Dinic's algorithm ([cmd struct::graph::op::BlockingFlowByDinic]) 874for blocking flow computation. 875[opt_def mkm] 876Procedure will find maximum flow for flow network [arg G] using Malhotra, Kumar and Maheshwari's algorithm ([cmd struct::graph::op::BlockingFlowByMKM]) 877for blocking flow computation. 878[list_end][comment {-- options --}] 879 880[def Result:] 881Algorithm returns dictionary containing it's flow value for each edge (key) in network [arg G]. 882 883[list_end][comment {-- definitions --}] 884 885[para] 886 887[emph Note:] [cmd struct::graph::op::BlockingFlowByDinic] gives [term O(m*n^2)] complexity and 888[cmd struct::graph::op::BlockingFlowByMKM] gives [term O(n^3)] complexity, where [term n] is the number of nodes 889and [term m] is the number of edges in flow network [arg G]. 890 891 892 893[call [cmd struct::graph::op::BlockingFlowByDinic] [arg G] [arg s] [arg t]] 894 895Algorithm for given network [arg G] with source [arg s] and sink [arg t], finds a [sectref {Flow Problems} "blocking 896flow"], which can be used to obtain a [term "maximum flow"] for that network [arg G]. 897 898[para] 899[list_begin definitions] 900 901[def Arguments:] 902[list_begin arguments] 903[arg_def {Graph Object} G input] 904Directed graph [arg G] representing the flow network. Each edge should have attribute 905[term throughput] set with integer value. 906[arg_def {Node} s input] 907The source node for the flow network [arg G]. 908[arg_def {Node} t input] 909The sink node for the flow network [arg G]. 910[list_end][comment {-- arguments --}] 911 912[def Result:] 913Algorithm returns dictionary containing it's blocking flow value for each edge (key) in network [arg G]. 914 915[list_end][comment {-- definitions --}] 916 917[emph Note:] Algorithm's complexity is [term O(n*m)], where [term n] is the number of nodes 918and [term m] is the number of edges in flow network [arg G]. 919 920 921 922[call [cmd struct::graph::op::BlockingFlowByMKM] [arg G] [arg s] [arg t]] 923 924Algorithm for given network [arg G] with source [arg s] and sink [arg t], finds a [sectref {Flow Problems} "blocking 925flow"], which can be used to obtain a [term "maximum flow"] for that [term network] [arg G]. 926 927[para] 928[list_begin definitions] 929 930[def Arguments:] 931[list_begin arguments] 932[arg_def {Graph Object} G input] 933Directed graph [arg G] representing the flow network. Each edge should have attribute 934[term throughput] set with integer value. 935[arg_def {Node} s input] 936The source node for the flow network [arg G]. 937[arg_def {Node} t input] 938The sink node for the flow network [arg G]. 939 940[list_end][comment {-- arguments --}] 941 942[def Result:] 943Algorithm returns dictionary containing it's blocking flow value for each edge (key) in network [arg G]. 944 945[list_end][comment {-- definitions --}] 946 947[emph Note:] Algorithm's complexity is [term O(n^2)], where [term n] is the number of nodes in flow network [arg G]. 948 949 950 951[call [cmd struct::graph::op::createResidualGraph] [arg G] [arg f]] 952 953 954Procedure creates a [term "residual graph"] (or [sectref {Flow Problems} "residual network"] ) for network [arg G] and given 955flow [arg f]. 956 957[para] 958[list_begin definitions] 959 960[def Arguments:] 961[list_begin arguments] 962[arg_def {Graph Object} G input] 963Flow network (directed graph where each edge has set attribute: [term throughput] ). 964 965[arg_def {dictionary} f input] 966Current flows in flow network [arg G]. 967 968[list_end][comment {-- arguments --}] 969 970[def Result:] 971Procedure returns graph structure that is a [term "residual graph"] created from input flow 972network [arg G]. 973[list_end][comment {-- definitions --}] 974 975 976 977[call [cmd struct::graph::op::createAugmentingNetwork] [arg G] [arg f] [arg path]] 978 979Procedure creates an [sectref {Flow Problems} "augmenting network"] for a given residual network [arg G] 980, flow [arg f] and augmenting path [arg path]. 981 982[para] 983[list_begin definitions] 984 985[def Arguments:] 986[list_begin arguments] 987[arg_def {Graph Object} G input] 988Residual network (directed graph), where for every edge there are set two attributes: throughput and cost. 989[arg_def {Dictionary} f input] 990Dictionary which contains for every edge (key), current value of the flow on that edge. 991[arg_def {List} path input] 992Augmenting path, set of edges (list) for which we create the network modification. 993 994[list_end][comment {-- arguments --}] 995 996[def Result:] 997Algorithm returns graph structure containing the modified augmenting network. 998 999[list_end][comment {-- definitions --}] 1000 1001 1002 1003[call [cmd struct::graph::op::createLevelGraph] [arg Gf] [arg s]] 1004 1005For given residual graph [arg Gf] procedure finds the [sectref {Flow Problems} "level graph"]. 1006 1007[para] 1008[list_begin definitions] 1009 1010[def Arguments:] 1011[list_begin arguments] 1012[arg_def {Graph Object} Gf input] 1013Residual network, where each edge has it's attribute [term throughput] set with certain value. 1014[arg_def {Node} s input] 1015The source node for the residual network [arg Gf]. 1016[list_end][comment {-- arguments --}] 1017 1018[def Result:] 1019Procedure returns a [term "level graph"] created from input [term "residual network"]. 1020[list_end][comment {-- definitions --}] 1021 1022 1023 1024[call [cmd struct::graph::op::TSPLocalSearching] [arg G] [arg C]] 1025 1026Algorithm is a [term "heuristic of local searching"] for [term "Travelling Salesman Problem"]. For some 1027solution of [term "TSP problem"], it checks if it's possible to find a better solution. As [term "TSP"] 1028is well known NP-Complete problem, so algorithm is a approximation algorithm (with 2 approximation factor). 1029 1030[para] 1031[list_begin definitions] 1032 1033[def Arguments:] 1034[list_begin arguments] 1035[arg_def {Graph Object} G input] 1036Undirected and complete graph with attributes "weight" set on each single edge. 1037[arg_def {List} C input] 1038A list of edges being [term "Hamiltonian cycle"], which is solution of [term "TSP Problem"] for graph [arg G]. 1039[list_end][comment {-- arguments --}] 1040 1041[def Result:] 1042Algorithm returns the best solution for [term "TSP problem"], it was able to find. 1043[list_end][comment {-- definitions --}] 1044 1045[emph Note:] The solution depends on the choosing of the beginning cycle [arg C]. It's not true that better cycle 1046assures that better solution will be found, but practise shows that we should give starting cycle with as small 1047sum of weights as possible. 1048 1049 1050 1051[call [cmd struct::graph::op::TSPLocalSearching3Approx] [arg G] [arg C]] 1052 1053Algorithm is a [term "heuristic of local searching"] for [term "Travelling Salesman Problem"]. For some 1054solution of [term "TSP problem"], it checks if it's possible to find a better solution. As [term "TSP"] 1055is well known NP-Complete problem, so algorithm is a approximation algorithm (with 3 approximation factor). 1056 1057[para] 1058 1059[list_begin definitions] 1060 1061[def Arguments:] 1062[list_begin arguments] 1063[arg_def {Graph Object} G input] 1064Undirected and complete graph with attributes "weight" set on each single edge. 1065[arg_def {List} C input] 1066A list of edges being [term "Hamiltonian cycle"], which is solution of [term "TSP Problem"] for graph [arg G]. 1067[list_end][comment {-- arguments --}] 1068 1069[def Result:] 1070Algorithm returns the best solution for [term "TSP problem"], it was able to find. 1071 1072[list_end][comment {-- definitions --}] 1073 1074[emph Note:] In practise 3-approximation algorithm turns out to be far more effective than 2-approximation, but it gives 1075worser approximation factor. Further heuristics of local searching (e.g. 4-approximation) doesn't give enough boost to 1076square the increase of approximation factor, so 2 and 3 approximations are mainly used. 1077 1078 1079 1080[call [cmd struct::graph::op::createSquaredGraph] [arg G]] 1081 1082X-Squared graph is a graph with the same set of nodes as input graph [arg G], but a different set of edges. X-Squared graph 1083has edge [term (u,v)], if and only if, the distance between [term u] and [term v] nodes is not greater than X and [term "u != v"]. 1084[para] 1085Procedure for input graph [arg G], returns its two-squared graph. 1086 1087[para] 1088 1089[emph Note:] Distances used in choosing new set of edges are considering the number of edges, not the sum of weights at edges. 1090 1091 1092 1093[call [cmd struct::graph::op::createCompleteGraph] [arg G] [arg originalEdges]] 1094 1095For input graph [arg G] procedure adds missing arcs to make it a [term "complete graph"]. It also holds in 1096variable [arg originalEdges] the set of arcs that graph [arg G] possessed before that operation. 1097 1098[list_end] 1099 1100 1101 1102[section "Background theory and terms"] 1103 1104 1105 1106[subsection "Shortest Path Problem"] 1107 1108[list_begin definitions] 1109 1110[def "Definition ([term "single-pair shortest path problem"]):"] 1111Formally, given a weighted graph (let [term V] be the set of vertices, and [term E] a set of edges), 1112and one vertice [term v] of [term V], find a path [term P] from [term v] to a [term "v'"] of V so that 1113the sum of weights on edges along the path is minimal among all paths connecting v to v'. 1114 1115[def "Generalizations:"] 1116 1117[list_begin itemized] 1118[item][term "The single-source shortest path problem"], in which we have to find shortest paths from a source vertex v to all other vertices in the graph. 1119[item][term "The single-destination shortest path problem"], in which we have to find shortest paths from all vertices in the graph to a single destination vertex v. This can be reduced to the single-source shortest path problem by reversing the edges in the graph. 1120[item][term "The all-pairs shortest path problem"], in which we have to find shortest paths between every pair of vertices v, v' in the graph. 1121[list_end][comment {-- itemized --}] 1122 1123[emph "Note:"] 1124The result of [term "Shortest Path problem"] can be [term "Shortest Path tree"], which is a subgraph of a given (possibly weighted) graph constructed so that the 1125distance between a selected root node and all other nodes is minimal. It is a tree because if there are two paths between the root node and some 1126vertex v (i.e. a cycle), we can delete the last edge of the longer path without increasing the distance from the root node to any node in the subgraph. 1127 1128[list_end][comment {-- definitions --}] 1129 1130 1131[subsection "Travelling Salesman Problem"] 1132 1133[list_begin definitions] 1134 1135[def "Definition:"] 1136For given edge-weighted (weights on edges should be positive) graph the goal is to find the cycle that visits each node in graph 1137exactly once ([term "Hamiltonian cycle"]). 1138 1139[def "Generalizations:"] 1140 1141[list_begin itemized] 1142[item][term "Metric TSP"] - A very natural restriction of the [term TSP] is to require that the distances between cities form a [term metric], i.e., 1143they satisfy [term "the triangle inequality"]. That is, for any 3 cities [term A], [term B] and [term C], the distance between [term A] and [term C] 1144must be at most the distance from [term A] to [term B] plus the distance from [term B] to [term C]. Most natural instances of [term TSP] 1145satisfy this constraint. 1146 1147[item][term "Euclidean TSP"] - Euclidean TSP, or [term "planar TSP"], is the [term TSP] with the distance being the ordinary [term "Euclidean distance"]. 1148[term "Euclidean TSP"] is a particular case of [term TSP] with [term "triangle inequality"], since distances in plane obey triangle inequality. However, 1149it seems to be easier than general [term TSP] with [term "triangle inequality"]. For example, [term "the minimum spanning tree"] of the graph associated 1150with an instance of [term "Euclidean TSP"] is a [term "Euclidean minimum spanning tree"], and so can be computed in expected [term "O(n log n)"] time for 1151[term n] points (considerably less than the number of edges). This enables the simple [term "2-approximation algorithm"] for TSP with triangle 1152inequality above to operate more quickly. 1153 1154[item][term "Asymmetric TSP"] - In most cases, the distance between two nodes in the [term TSP] network is the same in both directions. 1155The case where the distance from [term A] to [term B] is not equal to the distance from [term B] to [term A] is called [term "asymmetric TSP"]. 1156A practical application of an [term "asymmetric TSP"] is route optimisation using street-level routing (asymmetric due to one-way streets, 1157slip-roads and motorways). 1158 1159[list_end][comment {-- itemized --}] 1160[list_end][comment {-- definitions --}] 1161 1162[subsection "Matching Problem"] 1163 1164[list_begin definitions] 1165 1166[def "Definition:"] 1167Given a graph [term "G = (V,E)"], a matching or [term "edge-independent set"] [term M] in [term G] is a set of pairwise non-adjacent edges, 1168that is, no two edges share a common vertex. A vertex is [term matched] if it is incident to an edge in the [term "matching M"]. 1169Otherwise the vertex is [term unmatched]. 1170 1171 1172[def "Generalizations:"] 1173 1174[list_begin itemized] 1175[item][term "Maximal matching"] - a matching [term M] of a graph G with the property that if any edge not in [term M] is added to [term M], 1176it is no longer a [term matching], that is, [term M] is maximal if it is not a proper subset of any other [term matching] in graph G. 1177In other words, a [term "matching M"] of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in [term M]. 1178 1179[item][term "Maximum matching"] - a matching that contains the largest possible number of edges. There may be many [term "maximum matchings"]. 1180The [term "matching number"] of a graph G is the size of a [term "maximum matching"]. Note that every [term "maximum matching"] is [term maximal], 1181but not every [term "maximal matching"] is a [term "maximum matching"]. 1182 1183[item][term "Perfect matching"] - a matching which matches all vertices of the graph. That is, every vertex of the graph is incident to exactly one 1184edge of the matching. Every [term "perfect matching"] is [term maximum] and hence [term maximal]. In some literature, the term [term "complete matching"] 1185is used. A [term "perfect matching"] is also a [term "minimum-size edge cover"]. Moreover, the size of a [term "maximum matching"] is no larger than the 1186size of a [term "minimum edge cover"]. 1187 1188[item][term "Near-perfect matching"] - a matching in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, 1189and such a [term matching] must be [term maximum]. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph 1190is also called [term factor-critical]. 1191 1192[list_end][comment {-- itemized --}] 1193 1194[def "Related terms:"] 1195 1196[list_begin itemized] 1197[item][term "Alternating path"] - given a matching [term M], an [term "alternating path"] is a path in which the edges belong alternatively 1198to the matching and not to the matching. 1199 1200[item][term "Augmenting path"] - given a matching [term M], an [term "augmenting path"] is an [term "alternating path"] that starts from 1201and ends on free (unmatched) vertices. 1202 1203[list_end][comment {-- itemized --}] 1204 1205[list_end][comment {-- definitons --}] 1206 1207 1208 1209[subsection "Cut Problems"] 1210 1211[list_begin definitions] 1212 1213[def "Definition:"] 1214A [term cut] is a partition of the vertices of a graph into two [term "disjoint subsets"]. The [term cut-set] of the [term cut] is the 1215set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its [term cut-set]. 1216[para] 1217Formally: 1218[list_begin itemized] 1219[item] a [term cut] [term "C = (S,T)"] is a partition of [term V] of a graph [term "G = (V, E)"]. 1220 1221[item] an [term "s-t cut"] [term "C = (S,T)"] of a [term "flow network"] [term "N = (V, E)"] is a cut of [term N] such that [term s] is included in [term S] 1222and [term t] is included in [term T], where [term s] and [term t] are the [term source] and the [term sink] of [term N] respectively. 1223 1224[item] The [term cut-set] of a [term "cut C = (S,T)"] is such set of edges from graph [term "G = (V, E)"] that each edge [term "(u, v)"] satisfies 1225condition that [term u] is included in [term S] and [term v] is included in [term T]. 1226 1227[list_end][comment {-- itemized --}] 1228[para] 1229In an [term "unweighted undirected"] graph, the size or weight of a cut is the number of edges crossing the cut. In a [term "weighted graph"], 1230the same term is defined by the sum of the weights of the edges crossing the cut. 1231[para] 1232In a [term "flow network"], an [term "s-t cut"] is a cut that requires the [term source] and the [term sink] to be in different subsets, 1233and its [term cut-set] only consists of edges going from the [term source's] side to the [term sink's] side. The capacity of an [term "s-t cut"] 1234is defined by the sum of capacity of each edge in the [term cut-set]. 1235[para] 1236The [term cut] of a graph can sometimes refer to its [term cut-set] instead of the partition. 1237 1238 1239[def "Generalizations:"] 1240[list_begin itemized] 1241[item][term "Minimum cut"] - A cut is minimum if the size of the cut is not larger than the size of any other cut. 1242[item][term "Maximum cut"] - A cut is maximum if the size of the cut is not smaller than the size of any other cut. 1243[item][term "Sparsest cut"] - The [term "Sparsest cut problem"] is to bipartition the vertices so as to minimize the ratio of the number 1244of edges across the cut divided by the number of vertices in the smaller half of the partition. 1245[list_end][comment {-- itemized --}] 1246 1247[list_end][comment {-- definitons --}] 1248 1249 1250[subsection "K-Center Problem"] 1251 1252[list_begin definitions] 1253 1254[def "Definitions:"] 1255[list_begin definitions] 1256[def "[term "Unweighted K-Center"]"] 1257For any set [term S] ( which is subset of [term V] ) and node [term v], let the [term connect(v,S)] be the 1258cost of cheapest edge connecting [term v] with any node in [term S]. The goal is to find 1259such [term S], that [term "|S| = k"] and [term "max_v{connect(v,S)}"] is possibly small. 1260[para] 1261In other words, we can use it i.e. for finding best locations in the city ( nodes 1262of input graph ) for placing k buildings, such that those buildings will be as close 1263as possible to all other locations in town. 1264[para] 1265[def "[term "Weighted K-Center"]"] 1266The variation of [term "unweighted k-center problem"]. Besides the fact graph is edge-weighted, 1267there are also weights on vertices of input graph [arg G]. We've got also restriction 1268[arg W]. The goal is to choose such set of nodes [term S] ( which is a subset of [term V] ), that it's 1269total weight is not greater than [arg W] and also function: [term "max_v { min_u { cost(u,v) }}"] 1270has the smallest possible worth ( [term v] is a node in [term V] and [term u] is a node in [term S] ). 1271 1272[list_end][comment {-- definitions --}] 1273[list_end][comment {-- definitions --}] 1274 1275 1276 1277[subsection "Flow Problems"] 1278 1279[list_begin definitions] 1280 1281[def "Definitions:"] 1282[list_begin itemized] 1283[item][term "the maximum flow problem"] - the goal is to find a feasible flow through a single-source, single-sink flow network that is maximum. 1284The [term "maximum flow problem"] can be seen as a special case of more complex network flow problems, such as the [term "circulation problem"]. 1285The maximum value of an [term "s-t flow"] is equal to the minimum capacity of an [term "s-t cut"] in the network, as stated in the 1286[term "max-flow min-cut theorem"]. 1287[para] 1288More formally for flow network [term "G = (V,E)"], where for each edge [term "(u, v)"] we have its throuhgput [term "c(u,v)"] defined. As [term flow] 1289[term F] we define set of non-negative integer attributes [term f(u,v)] assigned to edges, satisfying such conditions: 1290[list_begin enumerated] 1291[enum]for each edge [term "(u, v)"] in [term G] such condition should be satisfied: 0 <= f(u,v) <= c(u,v) 1292[enum]Network [term G] has source node [term s] such that the flow [term F] is equal to the sum of outcoming flow decreased by the sum of incoming flow from that source node [term s]. 1293[enum]Network [term G] has sink node [term t] such that the the [term -F] value is equal to the sum of the incoming flow decreased by the sum of outcoming flow from that sink node [term t]. 1294[enum]For each node that is not a [term source] or [term sink] the sum of incoming flow and sum of outcoming flow should be equal. 1295[list_end][comment {-- enumerated --}] 1296 1297[item][term "the minimum cost flow problem"] - the goal is finding the cheapest possible way of sending a certain amount of flow through a [term "flow network"]. 1298 1299[item][term "blocking flow"] - a [term "blocking flow"] for a [term "residual network"] [term Gf] we name such flow [term b] in [term Gf] that: 1300[list_begin enumerated] 1301[enum]Each path from [term sink] to [term source] is the shortest path in [term Gf]. 1302[enum]Each shortest path in [term Gf] contains an edge with fully used throughput in [term Gf+b]. 1303[list_end][comment {-- enumerated --}] 1304 1305[item][term "residual network"] - for a flow network [term G] and flow [term f] [term "residual network"] is built with those edges, which can 1306send larger flow. It contains only those edges, which can send flow larger than 0. 1307 1308[item][term "level network"] - it has the same set of nodes as [term "residual graph"], but has only those edges [term "(u,v)"] from [arg Gf] 1309for which such equality is satisfied: [term "distance(s,u)+1 = distance(s,v)"]. 1310 1311[item][term "augmenting network"] - it is a modification of [term "residual network"] considering the new 1312flow values. Structure stays unchanged but values of throughputs and costs at edges 1313are different. 1314 1315[list_end][comment {-- itemized --}] 1316[list_end][comment {-- definitions --}] 1317 1318 1319 1320 1321[subsection "Approximation algorithm"] 1322 1323[list_begin definitions] 1324 1325[def "k-approximation algorithm:"] 1326Algorithm is a k-approximation, when for [term ALG] (solution returned by algorithm) and 1327[term OPT] (optimal solution), such inequality is true: 1328 1329[list_begin itemized] 1330[item] for minimalization problems: [term "ALG/OPT <= k" ] 1331[item] for maximalization problems: [term "OPT/ALG <= k" ] 1332[list_end][comment {-- itemized --}] 1333 1334 1335[list_end][comment {-- definitions --}] 1336 1337 1338[section References] 1339 1340[list_begin enum] 1341[enum] [uri http://en.wikipedia.org/wiki/Adjacency_matrix {Adjacency matrix}] 1342[enum] [uri http://en.wikipedia.org/wiki/Adjacency_list {Adjacency list}] 1343[enum] [uri http://en.wikipedia.org/wiki/Kruskal%27s_algorithm {Kruskal's algorithm}] 1344[enum] [uri http://en.wikipedia.org/wiki/Prim%27s_algorithm {Prim's algorithm}] 1345[enum] [uri http://en.wikipedia.org/wiki/Bipartite_graph {Bipartite graph}] 1346[enum] [uri http://en.wikipedia.org/wiki/Strongly_connected_components {Strongly connected components}] 1347[enum] [uri http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm {Tarjan's strongly connected components algorithm}] 1348[enum] [uri http://en.wikipedia.org/wiki/Cut_vertex {Cut vertex}] 1349[enum] [uri http://en.wikipedia.org/wiki/Bridge_(graph_theory) Bridge] 1350[enum] [uri http://en.wikipedia.org/wiki/Bellman-Ford_algorithm {Bellman-Ford's algorithm}] 1351[enum] [uri http://en.wikipedia.org/wiki/Johnson_algorithm {Johnson's algorithm}] 1352[enum] [uri http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm {Floyd-Warshall's algorithm}] 1353[enum] [uri http://en.wikipedia.org/wiki/Travelling_salesman_problem {Travelling Salesman Problem}] 1354[enum] [uri http://en.wikipedia.org/wiki/Christofides_algorithm {Christofides Algorithm}] 1355[enum] [uri http://en.wikipedia.org/wiki/Maxcut {Max Cut}] 1356[enum] [uri http://en.wikipedia.org/wiki/Matching {Matching}] 1357[enum] [uri http://en.wikipedia.org/wiki/Maximal_independent_set {Max Independent Set}] 1358[enum] [uri http://en.wikipedia.org/wiki/Vertex_cover_problem {Vertex Cover}] 1359[enum] [uri http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm {Ford-Fulkerson's algorithm}] 1360[enum] [uri http://en.wikipedia.org/wiki/Maximum_flow_problem {Maximum Flow problem}] 1361[enum] [uri http://en.wikipedia.org/wiki/Minimum_cost_flow_problem {Busacker-Gowen's algorithm}] 1362[enum] [uri http://en.wikipedia.org/wiki/Dinic's_algorithm {Dinic's algorithm}] 1363[enum] [uri http://www.csc.kth.se/~viggo/wwwcompendium/node128.html {K-Center problem}] 1364[enum] [uri http://en.wikipedia.org/wiki/Breadth-first_search {BFS}] 1365[enum] [uri http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree {Minimum Degree Spanning Tree}] 1366[enum] [uri http://en.wikipedia.org/wiki/Approximation_algorithm {Approximation algorithm}] 1367[list_end] 1368 1369 1370[section {BUGS, IDEAS, FEEDBACK}] 1371 1372This document, and the package it describes, will undoubtedly contain 1373bugs and other problems. 1374 1375Please report such in the category [emph {struct :: graph}] of the 1376[uri {http://sourceforge.net/tracker/?group_id=12883} {Tcllib SF Trackers}]. 1377 1378Please also report any ideas for enhancements you may have for either 1379package and/or documentation. 1380 1381 1382[keywords graph dijkstra distance radius diameter eccentricity] 1383[keywords edge arc node vertex subgraph neighbour] 1384[keywords adjacent loop degree] 1385[keywords {cut vertex} {articulation point} {connected component}] 1386[keywords {strongly connected component} {adjacency matrix} {adjacency list}] 1387[keywords {minimal spanning tree} bipartite bridge {cut edge} isthmus] 1388[keywords {shortest path} {travelling salesman} {max cut} matching {independent set}] 1389[keywords {vertex cover} {maximum flow} {minimum cost flow} {blocking flow}] 1390[keywords {augmenting path} {residual graph} {level graph} {flow network} {augmenting network}] 1391[keywords {complete graph} {squared graph} {local searching} {heuristic} {bfs} {approximation algorithm}] 1392[keywords {minimum diameter spanning tree} {minimum degree spanning tree} {degree constrained spanning tree}] 1393[manpage_end] 1394