Changeset 611:85cb3aa71cce in lemon-1.2 for doc/groups.dox
- Timestamp:
- 04/21/09 16:18:54 (16 years ago)
- Branch:
- default
- Children:
- 612:0c8e5c688440, 613:b1811c363299, 619:ec817dfc2cb7
- Parents:
- 600:0ba8dfce7259 (diff), 610:dacc2cee2b4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 2 edited
-
doc/groups.dox (modified) (2 diffs)
-
doc/groups.dox (modified) (34 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r590 r611 318 318 The \e maximum \e flow \e problem is to find a flow of maximum value between 319 319 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ 320 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and320 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and 321 321 \f$s, t \in V\f$ source and target nodes. 322 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the322 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the 323 323 following optimization problem. 324 324 325 \f[ \max\sum_{ a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]326 \f[ \sum_{ a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)327 \q quad \forall v\in V\setminus\{s,t\} \f]328 \f[ 0 \leq f( a) \leq cap(a) \qquad \forall a\in A \f]325 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] 326 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) 327 \quad \forall u\in V\setminus\{s,t\} \f] 328 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 329 329 330 330 LEMON contains several algorithms for solving maximum flow problems: … … 351 351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of 352 352 minimum total cost from a set of supply nodes to a set of demand nodes 353 in a network with capacity constraints and arc costs. 353 in a network with capacity constraints (lower and upper bounds) 354 and arc costs. 354 355 Formally, let \f$G=(V,A)\f$ be a digraph, 355 356 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and 356 upper bounds for the flow values on the arcs, 357 upper bounds for the flow values on the arcs, for which 358 \f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$. 357 359 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow 358 on the arcs, and 359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values 360 of the nodes. 361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of 362 the following optimization problem. 363 364 \f[ \min\sum_{a\in A} f(a) cost(a) \f] 365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) = 366 supply(v) \qquad \forall v\in V \f] 367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f] 368 369 LEMON contains several algorithms for solving minimum cost flow problems: 370 - \ref CycleCanceling Cycle-canceling algorithms. 371 - \ref CapacityScaling Successive shortest path algorithm with optional 360 on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the 361 signed supply values of the nodes. 362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ 363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with 364 \f$-sup(u)\f$ demand. 365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution 366 of the following optimization problem. 367 368 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] 369 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq 370 sup(u) \quad \forall u\in V \f] 371 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] 372 373 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be 374 zero or negative in order to have a feasible solution (since the sum 375 of the expressions on the left-hand side of the inequalities is zero). 376 It means that the total demand must be greater or equal to the total 377 supply and all the supplies have to be carried out from the supply nodes, 378 but there could be demands that are not satisfied. 379 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand 380 constraints have to be satisfied with equality, i.e. all demands 381 have to be satisfied and all supplies have to be used. 382 383 If you need the opposite inequalities in the supply/demand constraints 384 (i.e. the total demand is less than the total supply and all the demands 385 have to be satisfied while there could be supplies that are not used), 386 then you could easily transform the problem to the above form by reversing 387 the direction of the arcs and taking the negative of the supply values 388 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). 389 However \ref NetworkSimplex algorithm also supports this form directly 390 for the sake of convenience. 391 392 A feasible solution for this problem can be found using \ref Circulation. 393 394 Note that the above formulation is actually more general than the usual 395 definition of the minimum cost flow problem, in which strict equalities 396 are required in the supply/demand contraints, i.e. 397 398 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) = 399 sup(u) \quad \forall u\in V. \f] 400 401 However if the sum of the supply values is zero, then these two problems 402 are equivalent. So if you need the equality form, you have to ensure this 403 additional contraint for the algorithms. 404 405 The dual solution of the minimum cost flow problem is represented by node 406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. 407 An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem 408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ 409 node potentials the following \e complementary \e slackness optimality 410 conditions hold. 411 412 - For all \f$uv\in A\f$ arcs: 413 - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; 414 - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$; 415 - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. 416 - For all \f$u\in V\f$: 417 - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, 418 then \f$\pi(u)=0\f$. 419 420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc 421 \f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e. 422 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] 423 424 All algorithms provide dual solution (node potentials) as well 425 if an optimal flow is found. 426 427 LEMON contains several algorithms for solving minimum cost flow problems. 428 - \ref NetworkSimplex Primal Network Simplex algorithm with various 429 pivot strategies. 430 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on 431 cost scaling. 432 - \ref CapacityScaling Successive Shortest %Path algorithm with optional 372 433 capacity scaling. 373 - \ref CostScaling Push-relabel and augment-relabel algorithms based on 374 cost scaling. 375 - \ref NetworkSimplex Primal network simplex algorithm with various 376 pivot strategies. 434 - \ref CancelAndTighten The Cancel and Tighten algorithm. 435 - \ref CycleCanceling Cycle-Canceling algorithms. 436 437 Most of these implementations support the general inequality form of the 438 minimum cost flow problem, but CancelAndTighten and CycleCanceling 439 only support the equality form due to the primal method they use. 440 441 In general NetworkSimplex is the most efficient implementation, 442 but in special cases other algorithms could be faster. 443 For example, if the total supply and/or capacities are rather small, 444 CapacityScaling is usually the fastest algorithm (without effective scaling). 377 445 */ 378 446 -
doc/groups.dox
r609 r611 21 21 /** 22 22 @defgroup datas Data Structures 23 This group describes the several data structures implemented in LEMON.23 This group contains the several data structures implemented in LEMON. 24 24 */ 25 25 … … 143 143 \brief Graph types between real graphs and graph adaptors. 144 144 145 This group describes some graph types between real graphs and graph adaptors.145 This group contains some graph types between real graphs and graph adaptors. 146 146 These classes wrap graphs to give new functionality as the adaptors do it. 147 147 On the other hand they are not light-weight structures as the adaptors. … … 153 153 \brief Map structures implemented in LEMON. 154 154 155 This group describes the map structures implemented in LEMON.155 This group contains the map structures implemented in LEMON. 156 156 157 157 LEMON provides several special purpose maps and map adaptors that e.g. combine … … 166 166 \brief Special graph-related maps. 167 167 168 This group describes maps that are specifically designed to assign168 This group contains maps that are specifically designed to assign 169 169 values to the nodes and arcs/edges of graphs. 170 170 … … 178 178 \brief Tools to create new maps from existing ones 179 179 180 This group describes map adaptors that are used to create "implicit"180 This group contains map adaptors that are used to create "implicit" 181 181 maps from other maps. 182 182 … … 241 241 \brief Two dimensional data storages implemented in LEMON. 242 242 243 This group describes two dimensional data storages implemented in LEMON.243 This group contains two dimensional data storages implemented in LEMON. 244 244 */ 245 245 … … 249 249 \brief %Path structures implemented in LEMON. 250 250 251 This group describes the path structures implemented in LEMON.251 This group contains the path structures implemented in LEMON. 252 252 253 253 LEMON provides flexible data structures to work with paths. … … 265 265 \brief Auxiliary data structures implemented in LEMON. 266 266 267 This group describes some data structures implemented in LEMON in267 This group contains some data structures implemented in LEMON in 268 268 order to make it easier to implement combinatorial algorithms. 269 269 */ … … 271 271 /** 272 272 @defgroup algs Algorithms 273 \brief This group describes the several algorithms273 \brief This group contains the several algorithms 274 274 implemented in LEMON. 275 275 276 This group describes the several algorithms276 This group contains the several algorithms 277 277 implemented in LEMON. 278 278 */ … … 283 283 \brief Common graph search algorithms. 284 284 285 This group describes the common graph search algorithms, namely285 This group contains the common graph search algorithms, namely 286 286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 287 287 */ … … 292 292 \brief Algorithms for finding shortest paths. 293 293 294 This group describes the algorithms for finding shortest paths in digraphs.294 This group contains the algorithms for finding shortest paths in digraphs. 295 295 296 296 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 313 313 \brief Algorithms for finding maximum flows. 314 314 315 This group describes the algorithms for finding maximum flows and315 This group contains the algorithms for finding maximum flows and 316 316 feasible circulations. 317 317 … … 451 451 \brief Algorithms for finding minimum cut in graphs. 452 452 453 This group describes the algorithms for finding minimum cut in graphs.453 This group contains the algorithms for finding minimum cut in graphs. 454 454 455 455 The \e minimum \e cut \e problem is to find a non-empty and non-complete … … 468 468 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 469 469 calculating minimum cut in undirected graphs. 470 - \ref GomoryHu Tree"Gomory-Hu tree computation" for calculating470 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 471 471 all-pairs minimum cut in undirected graphs. 472 472 … … 476 476 477 477 /** 478 @defgroup graph_prop Connectivity and Other Graph Properties478 @defgroup graph_properties Connectivity and Other Graph Properties 479 479 @ingroup algs 480 480 \brief Algorithms for discovering the graph properties 481 481 482 This group describes the algorithms for discovering the graph properties482 This group contains the algorithms for discovering the graph properties 483 483 like connectivity, bipartiteness, euler property, simplicity etc. 484 484 … … 492 492 \brief Algorithms for planarity checking, embedding and drawing 493 493 494 This group describes the algorithms for planarity checking,494 This group contains the algorithms for planarity checking, 495 495 embedding and drawing. 496 496 … … 504 504 \brief Algorithms for finding matchings in graphs and bipartite graphs. 505 505 506 This group contains algorithm objects and functions to calculate506 This group contains the algorithms for calculating 507 507 matchings in graphs and bipartite graphs. The general matching problem is 508 finding a subset of the arcs which does not shares common endpoints. 508 finding a subset of the edges for which each node has at most one incident 509 edge. 509 510 510 511 There are several different algorithms for calculate matchings in … … 543 544 \brief Algorithms for finding a minimum cost spanning tree in a graph. 544 545 545 This group describes the algorithms for finding a minimum cost spanning546 This group contains the algorithms for finding a minimum cost spanning 546 547 tree in a graph. 547 548 */ … … 552 553 \brief Auxiliary algorithms implemented in LEMON. 553 554 554 This group describes some algorithms implemented in LEMON555 This group contains some algorithms implemented in LEMON 555 556 in order to make it easier to implement complex algorithms. 556 557 */ … … 561 562 \brief Approximation algorithms. 562 563 563 This group describes the approximation and heuristic algorithms564 This group contains the approximation and heuristic algorithms 564 565 implemented in LEMON. 565 566 */ … … 567 568 /** 568 569 @defgroup gen_opt_group General Optimization Tools 569 \brief This group describes some general optimization frameworks570 \brief This group contains some general optimization frameworks 570 571 implemented in LEMON. 571 572 572 This group describes some general optimization frameworks573 This group contains some general optimization frameworks 573 574 implemented in LEMON. 574 575 */ … … 579 580 \brief Lp and Mip solver interfaces for LEMON. 580 581 581 This group describes Lp and Mip solver interfaces for LEMON. The582 This group contains Lp and Mip solver interfaces for LEMON. The 582 583 various LP solvers could be used in the same manner with this 583 584 interface. … … 598 599 \brief Metaheuristics for LEMON library. 599 600 600 This group describes some metaheuristic optimization tools.601 This group contains some metaheuristic optimization tools. 601 602 */ 602 603 … … 613 614 \brief Simple basic graph utilities. 614 615 615 This group describes some simple basic graph utilities.616 This group contains some simple basic graph utilities. 616 617 */ 617 618 … … 621 622 \brief Tools for development, debugging and testing. 622 623 623 This group describes several useful tools for development,624 This group contains several useful tools for development, 624 625 debugging and testing. 625 626 */ … … 630 631 \brief Simple tools for measuring the performance of algorithms. 631 632 632 This group describes simple tools for measuring the performance633 This group contains simple tools for measuring the performance 633 634 of algorithms. 634 635 */ … … 639 640 \brief Exceptions defined in LEMON. 640 641 641 This group describes the exceptions defined in LEMON.642 This group contains the exceptions defined in LEMON. 642 643 */ 643 644 … … 646 647 \brief Graph Input-Output methods 647 648 648 This group describes the tools for importing and exporting graphs649 This group contains the tools for importing and exporting graphs 649 650 and graph related data. Now it supports the \ref lgf-format 650 651 "LEMON Graph Format", the \c DIMACS format and the encapsulated … … 657 658 \brief Reading and writing LEMON Graph Format. 658 659 659 This group describes methods for reading and writing660 This group contains methods for reading and writing 660 661 \ref lgf-format "LEMON Graph Format". 661 662 */ … … 666 667 \brief General \c EPS drawer and graph exporter 667 668 668 This group describes general \c EPS drawing methods and special669 This group contains general \c EPS drawing methods and special 669 670 graph exporting tools. 670 671 */ … … 690 691 \brief Skeleton classes and concept checking classes 691 692 692 This group describes the data/algorithm skeletons and concept checking693 This group contains the data/algorithm skeletons and concept checking 693 694 classes implemented in LEMON. 694 695 … … 720 721 \brief Skeleton and concept checking classes for graph structures 721 722 722 This group describes the skeletons and concept checking classes of LEMON's723 This group contains the skeletons and concept checking classes of LEMON's 723 724 graph structures and helper classes used to implement these. 724 725 */ … … 729 730 \brief Skeleton and concept checking classes for maps 730 731 731 This group describes the skeletons and concept checking classes of maps.732 This group contains the skeletons and concept checking classes of maps. 732 733 */ 733 734 … … 740 741 the \c demo subdirectory of the source tree. 741 742 742 I t order to compile them, use <tt>--enable-demo</tt> configure option when743 build the library.743 In order to compile them, use the <tt>make demo</tt> or the 744 <tt>make check</tt> commands. 744 745 */ 745 746
Note: See TracChangeset
for help on using the changeset viewer.
