Changeset 658:85cb3aa71cce in lemon
- Timestamp:
- 04/21/09 16:18:54 (16 years ago)
- Branch:
- default
- Children:
- 659:0c8e5c688440, 660:b1811c363299, 666:ec817dfc2cb7
- Parents:
- 647:0ba8dfce7259 (diff), 657: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:
-
- 16 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r637 r658 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
r656 r658 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 -
lemon/Makefile.am
r641 r658 94 94 lemon/min_cost_arborescence.h \ 95 95 lemon/nauty_reader.h \ 96 lemon/network_simplex.h \ 96 97 lemon/path.h \ 97 98 lemon/preflow.h \ -
lemon/Makefile.am
r648 r658 13 13 lemon/lp_base.cc \ 14 14 lemon/lp_skeleton.cc \ 15 15 lemon/random.cc \ 16 16 lemon/bits/windows.cc 17 17 18 18 19 19 lemon_libemon_la_CXXFLAGS = \ 20 $(AM_CXXFLAGS) \ 20 21 $(GLPK_CFLAGS) \ 21 22 $(CPLEX_CFLAGS) \ 22 23 $(SOPLEX_CXXFLAGS) \ 23 $(CLP_CXXFLAGS) 24 $(CLP_CXXFLAGS) \ 25 $(CBC_CXXFLAGS) 24 26 25 27 lemon_libemon_la_LDFLAGS = \ … … 27 29 $(CPLEX_LIBS) \ 28 30 $(SOPLEX_LIBS) \ 29 $(CLP_LIBS) 31 $(CLP_LIBS) \ 32 $(CBC_LIBS) 30 33 31 34 if HAVE_GLPK … … 43 46 if HAVE_CLP 44 47 lemon_libemon_la_SOURCES += lemon/clp.cc 48 endif 49 50 if HAVE_CBC 51 lemon_libemon_la_SOURCES += lemon/cbc.cc 45 52 endif 46 53 … … 69 76 lemon/full_graph.h \ 70 77 lemon/glpk.h \ 78 lemon/gomory_hu.h \ 71 79 lemon/graph_to_eps.h \ 72 80 lemon/grid_graph.h \ … … 82 90 lemon/list_graph.h \ 83 91 lemon/maps.h \ 92 lemon/matching.h \ 84 93 lemon/math.h \ 85 lemon/max_matching.h \86 94 lemon/min_cost_arborescence.h \ 87 95 lemon/nauty_reader.h \ -
lemon/circulation.h
r628 r658 32 32 /// 33 33 /// Default traits class of Circulation class. 34 /// \tparam GR Digraph type. 35 /// \tparam LM Lower bound capacity map type. 36 /// \tparam UM Upper bound capacity map type. 37 /// \tparam DM Delta map type. 34 /// 35 /// \tparam GR Type of the digraph the algorithm runs on. 36 /// \tparam LM The type of the lower bound map. 37 /// \tparam UM The type of the upper bound (capacity) map. 38 /// \tparam SM The type of the supply map. 38 39 template <typename GR, typename LM, 39 typename UM, typename DM>40 typename UM, typename SM> 40 41 struct CirculationDefaultTraits { 41 42 … … 43 44 typedef GR Digraph; 44 45 45 /// \brief The type of the map that stores the circulation lower 46 /// bound. 47 /// 48 /// The type of the map that stores the circulation lower bound. 49 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 50 typedef LM LCapMap; 51 52 /// \brief The type of the map that stores the circulation upper 53 /// bound. 54 /// 55 /// The type of the map that stores the circulation upper bound. 56 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 57 typedef UM UCapMap; 58 59 /// \brief The type of the map that stores the lower bound for 60 /// the supply of the nodes. 61 /// 62 /// The type of the map that stores the lower bound for the supply 63 /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap" 46 /// \brief The type of the lower bound map. 47 /// 48 /// The type of the map that stores the lower bounds on the arcs. 49 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. 50 typedef LM LowerMap; 51 52 /// \brief The type of the upper bound (capacity) map. 53 /// 54 /// The type of the map that stores the upper bounds (capacities) 55 /// on the arcs. 56 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. 57 typedef UM UpperMap; 58 59 /// \brief The type of supply map. 60 /// 61 /// The type of the map that stores the signed supply values of the 62 /// nodes. 63 /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. 64 typedef SM SupplyMap; 65 66 /// \brief The type of the flow values. 67 typedef typename SupplyMap::Value Flow; 68 69 /// \brief The type of the map that stores the flow values. 70 /// 71 /// The type of the map that stores the flow values. 72 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" 64 73 /// concept. 65 typedef DM DeltaMap; 66 67 /// \brief The type of the flow values. 68 typedef typename DeltaMap::Value Value; 69 70 /// \brief The type of the map that stores the flow values. 71 /// 72 /// The type of the map that stores the flow values. 73 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 74 typedef typename Digraph::template ArcMap<Value> FlowMap; 74 typedef typename Digraph::template ArcMap<Flow> FlowMap; 75 75 76 76 /// \brief Instantiates a FlowMap. 77 77 /// 78 78 /// This function instantiates a \ref FlowMap. 79 /// \param digraph The digraph , towhich we would like to define79 /// \param digraph The digraph for which we would like to define 80 80 /// the flow map. 81 81 static FlowMap* createFlowMap(const Digraph& digraph) { … … 94 94 /// 95 95 /// This function instantiates an \ref Elevator. 96 /// \param digraph The digraph , towhich we would like to define96 /// \param digraph The digraph for which we would like to define 97 97 /// the elevator. 98 98 /// \param max_level The maximum level of the elevator. … … 104 104 /// 105 105 /// The tolerance used by the algorithm to handle inexact computation. 106 typedef lemon::Tolerance< Value> Tolerance;106 typedef lemon::Tolerance<Flow> Tolerance; 107 107 108 108 }; … … 112 112 113 113 \ingroup max_flow 114 This class implements a push-relabel algorithm for the network115 circulation problem.114 This class implements a push-relabel algorithm for the \e network 115 \e circulation problem. 116 116 It is to find a feasible circulation when lower and upper bounds 117 are given for the flow values on the arcs and lower bounds 118 are given for the supply values of the nodes. 117 are given for the flow values on the arcs and lower bounds are 118 given for the difference between the outgoing and incoming flow 119 at the nodes. 119 120 120 121 The exact formulation of this problem is the following. 121 122 Let \f$G=(V,A)\f$ be a digraph, 122 \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$, 123 \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation 124 \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that 125 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) 126 \geq delta(v) \quad \forall v\in V, \f] 127 \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f] 128 \note \f$delta(v)\f$ specifies a lower bound for the supply of node 129 \f$v\f$. It can be either positive or negative, however note that 130 \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to 131 have a feasible solution. 132 133 \note A special case of this problem is when 134 \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$ 135 will be \e equal \e to \f$delta(v)\f$, if a circulation can be found. 136 Thus a feasible solution for the 137 \ref min_cost_flow "minimum cost flow" problem can be calculated 138 in this way. 123 \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and 124 upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$ 125 holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$ 126 denotes the signed supply values of the nodes. 127 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ 128 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with 129 \f$-sup(u)\f$ demand. 130 A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ 131 solution of the following problem. 132 133 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) 134 \geq sup(u) \quad \forall u\in V, \f] 135 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f] 136 137 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be 138 zero or negative in order to have a feasible solution (since the sum 139 of the expressions on the left-hand side of the inequalities is zero). 140 It means that the total demand must be greater or equal to the total 141 supply and all the supplies have to be carried out from the supply nodes, 142 but there could be demands that are not satisfied. 143 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand 144 constraints have to be satisfied with equality, i.e. all demands 145 have to be satisfied and all supplies have to be used. 146 147 If you need the opposite inequalities in the supply/demand constraints 148 (i.e. the total demand is less than the total supply and all the demands 149 have to be satisfied while there could be supplies that are not used), 150 then you could easily transform the problem to the above form by reversing 151 the direction of the arcs and taking the negative of the supply values 152 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). 153 154 Note that this algorithm also provides a feasible solution for the 155 \ref min_cost_flow "minimum cost flow problem". 139 156 140 157 \tparam GR The type of the digraph the algorithm runs on. 141 \tparam LM The type of the lower bound capacitymap. The default158 \tparam LM The type of the lower bound map. The default 142 159 map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 143 \tparam UM The type of the upper bound capacity map. The default 144 map type is \c LM. 145 \tparam DM The type of the map that stores the lower bound 146 for the supply of the nodes. The default map type is 160 \tparam UM The type of the upper bound (capacity) map. 161 The default map type is \c LM. 162 \tparam SM The type of the supply map. The default map type is 147 163 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>". 148 164 */ … … 151 167 typename LM, 152 168 typename UM, 153 typename DM,169 typename SM, 154 170 typename TR > 155 171 #else … … 157 173 typename LM = typename GR::template ArcMap<int>, 158 174 typename UM = LM, 159 typename DM = typename GR::template NodeMap<typename UM::Value>,160 typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >175 typename SM = typename GR::template NodeMap<typename UM::Value>, 176 typename TR = CirculationDefaultTraits<GR, LM, UM, SM> > 161 177 #endif 162 178 class Circulation { … … 168 184 typedef typename Traits::Digraph Digraph; 169 185 ///The type of the flow values. 170 typedef typename Traits::Value Value; 171 172 /// The type of the lower bound capacity map. 173 typedef typename Traits::LCapMap LCapMap; 174 /// The type of the upper bound capacity map. 175 typedef typename Traits::UCapMap UCapMap; 176 /// \brief The type of the map that stores the lower bound for 177 /// the supply of the nodes. 178 typedef typename Traits::DeltaMap DeltaMap; 186 typedef typename Traits::Flow Flow; 187 188 ///The type of the lower bound map. 189 typedef typename Traits::LowerMap LowerMap; 190 ///The type of the upper bound (capacity) map. 191 typedef typename Traits::UpperMap UpperMap; 192 ///The type of the supply map. 193 typedef typename Traits::SupplyMap SupplyMap; 179 194 ///The type of the flow map. 180 195 typedef typename Traits::FlowMap FlowMap; … … 192 207 int _node_num; 193 208 194 const L CapMap *_lo;195 const U CapMap *_up;196 const DeltaMap *_delta;209 const LowerMap *_lo; 210 const UpperMap *_up; 211 const SupplyMap *_supply; 197 212 198 213 FlowMap *_flow; … … 202 217 bool _local_level; 203 218 204 typedef typename Digraph::template NodeMap< Value> ExcessMap;219 typedef typename Digraph::template NodeMap<Flow> ExcessMap; 205 220 ExcessMap* _excess; 206 221 … … 232 247 template <typename T> 233 248 struct SetFlowMap 234 : public Circulation<Digraph, L CapMap, UCapMap, DeltaMap,249 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 235 250 SetFlowMapTraits<T> > { 236 typedef Circulation<Digraph, L CapMap, UCapMap, DeltaMap,251 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 237 252 SetFlowMapTraits<T> > Create; 238 253 }; … … 258 273 template <typename T> 259 274 struct SetElevator 260 : public Circulation<Digraph, L CapMap, UCapMap, DeltaMap,275 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 261 276 SetElevatorTraits<T> > { 262 typedef Circulation<Digraph, L CapMap, UCapMap, DeltaMap,277 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 263 278 SetElevatorTraits<T> > Create; 264 279 }; … … 286 301 template <typename T> 287 302 struct SetStandardElevator 288 : public Circulation<Digraph, L CapMap, UCapMap, DeltaMap,303 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 289 304 SetStandardElevatorTraits<T> > { 290 typedef Circulation<Digraph, L CapMap, UCapMap, DeltaMap,305 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 291 306 SetStandardElevatorTraits<T> > Create; 292 307 }; … … 300 315 public: 301 316 317 /// Constructor. 318 302 319 /// The constructor of the class. 303 304 /// The constructor of the class.305 /// \param g The digraph the algorithm runs on.306 /// \param lo The lower bound capacity of the arcs.307 /// \param up The upper bound capacity ofthe arcs.308 /// \param delta The lower bound for the supplyof the nodes.309 Circulation(const Digraph &g ,const LCapMap &lo,310 const U CapMap &up,const DeltaMap &delta)311 : _g(g ), _node_num(),312 _ lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),313 _ level(0), _local_level(false), _excess(0), _el() {}320 /// 321 /// \param graph The digraph the algorithm runs on. 322 /// \param lower The lower bounds for the flow values on the arcs. 323 /// \param upper The upper bounds (capacities) for the flow values 324 /// on the arcs. 325 /// \param supply The signed supply values of the nodes. 326 Circulation(const Digraph &graph, const LowerMap &lower, 327 const UpperMap &upper, const SupplyMap &supply) 328 : _g(graph), _lo(&lower), _up(&upper), _supply(&supply), 329 _flow(NULL), _local_flow(false), _level(NULL), _local_level(false), 330 _excess(NULL) {} 314 331 315 332 /// Destructor. … … 351 368 public: 352 369 353 /// Sets the lower bound capacitymap.354 355 /// Sets the lower bound capacitymap.370 /// Sets the lower bound map. 371 372 /// Sets the lower bound map. 356 373 /// \return <tt>(*this)</tt> 357 Circulation& lower CapMap(const LCapMap& map) {374 Circulation& lowerMap(const LowerMap& map) { 358 375 _lo = ↦ 359 376 return *this; 360 377 } 361 378 362 /// Sets the upper bound capacitymap.363 364 /// Sets the upper bound capacitymap.379 /// Sets the upper bound (capacity) map. 380 381 /// Sets the upper bound (capacity) map. 365 382 /// \return <tt>(*this)</tt> 366 Circulation& upper CapMap(const LCapMap& map) {383 Circulation& upperMap(const LowerMap& map) { 367 384 _up = ↦ 368 385 return *this; 369 386 } 370 387 371 /// Sets the lower bound map for the supply of the nodes.372 373 /// Sets the lower bound map for the supply of the nodes.388 /// Sets the supply map. 389 390 /// Sets the supply map. 374 391 /// \return <tt>(*this)</tt> 375 Circulation& deltaMap(const DeltaMap& map) {376 _ delta= ↦392 Circulation& supplyMap(const SupplyMap& map) { 393 _supply = ↦ 377 394 return *this; 378 395 } … … 454 471 455 472 for(NodeIt n(_g);n!=INVALID;++n) { 456 (*_excess)[n] = (*_ delta)[n];473 (*_excess)[n] = (*_supply)[n]; 457 474 } 458 475 … … 483 500 484 501 for(NodeIt n(_g);n!=INVALID;++n) { 485 (*_excess)[n] = (*_ delta)[n];502 (*_excess)[n] = (*_supply)[n]; 486 503 } 487 504 … … 496 513 (*_excess)[_g.source(e)] -= (*_lo)[e]; 497 514 } else { 498 Valuefc = -(*_excess)[_g.target(e)];515 Flow fc = -(*_excess)[_g.target(e)]; 499 516 _flow->set(e, fc); 500 517 (*_excess)[_g.target(e)] = 0; … … 529 546 int actlevel=(*_level)[act]; 530 547 int mlevel=_node_num; 531 Valueexc=(*_excess)[act];548 Flow exc=(*_excess)[act]; 532 549 533 550 for(OutArcIt e(_g,act);e!=INVALID; ++e) { 534 551 Node v = _g.target(e); 535 Valuefc=(*_up)[e]-(*_flow)[e];552 Flow fc=(*_up)[e]-(*_flow)[e]; 536 553 if(!_tol.positive(fc)) continue; 537 554 if((*_level)[v]<actlevel) { … … 557 574 for(InArcIt e(_g,act);e!=INVALID; ++e) { 558 575 Node v = _g.source(e); 559 Valuefc=(*_flow)[e]-(*_lo)[e];576 Flow fc=(*_flow)[e]-(*_lo)[e]; 560 577 if(!_tol.positive(fc)) continue; 561 578 if((*_level)[v]<actlevel) { … … 633 650 /// \pre Either \ref run() or \ref init() must be called before 634 651 /// using this function. 635 Valueflow(const Arc& arc) const {652 Flow flow(const Arc& arc) const { 636 653 return (*_flow)[arc]; 637 654 } … … 652 669 Barrier is a set \e B of nodes for which 653 670 654 \f[ \sum_{ a\in\delta_{out}(B)} upper(a) -655 \sum_{ a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]671 \f[ \sum_{uv\in A: u\in B} upper(uv) - 672 \sum_{uv\in A: v\in B} lower(uv) < \sum_{v\in B} sup(v) \f] 656 673 657 674 holds. The existence of a set with this property prooves that a … … 716 733 for(NodeIt n(_g);n!=INVALID;++n) 717 734 { 718 Value dif=-(*_delta)[n];735 Flow dif=-(*_supply)[n]; 719 736 for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e]; 720 737 for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e]; … … 731 748 bool checkBarrier() const 732 749 { 733 Valuedelta=0;750 Flow delta=0; 734 751 for(NodeIt n(_g);n!=INVALID;++n) 735 752 if(barrier(n)) 736 delta-=(*_ delta)[n];753 delta-=(*_supply)[n]; 737 754 for(ArcIt e(_g);e!=INVALID;++e) 738 755 { -
lemon/circulation.h
r657 r658 231 231 ///@{ 232 232 233 template <typename _FlowMap>233 template <typename T> 234 234 struct SetFlowMapTraits : public Traits { 235 typedef _FlowMapFlowMap;235 typedef T FlowMap; 236 236 static FlowMap *createFlowMap(const Digraph&) { 237 237 LEMON_ASSERT(false, "FlowMap is not initialized"); … … 245 245 /// \ref named-templ-param "Named parameter" for setting FlowMap 246 246 /// type. 247 template <typename _FlowMap>247 template <typename T> 248 248 struct SetFlowMap 249 249 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 250 SetFlowMapTraits< _FlowMap> > {250 SetFlowMapTraits<T> > { 251 251 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 252 SetFlowMapTraits< _FlowMap> > Create;252 SetFlowMapTraits<T> > Create; 253 253 }; 254 254 255 template <typename _Elevator>255 template <typename T> 256 256 struct SetElevatorTraits : public Traits { 257 typedef _ElevatorElevator;257 typedef T Elevator; 258 258 static Elevator *createElevator(const Digraph&, int) { 259 259 LEMON_ASSERT(false, "Elevator is not initialized"); … … 271 271 /// \ref run() or \ref init(). 272 272 /// \sa SetStandardElevator 273 template <typename _Elevator>273 template <typename T> 274 274 struct SetElevator 275 275 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 276 SetElevatorTraits< _Elevator> > {276 SetElevatorTraits<T> > { 277 277 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 278 SetElevatorTraits< _Elevator> > Create;278 SetElevatorTraits<T> > Create; 279 279 }; 280 280 281 template <typename _Elevator>281 template <typename T> 282 282 struct SetStandardElevatorTraits : public Traits { 283 typedef _ElevatorElevator;283 typedef T Elevator; 284 284 static Elevator *createElevator(const Digraph& digraph, int max_level) { 285 285 return new Elevator(digraph, max_level); … … 299 299 /// before calling \ref run() or \ref init(). 300 300 /// \sa SetElevator 301 template <typename _Elevator>301 template <typename T> 302 302 struct SetStandardElevator 303 303 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 304 SetStandardElevatorTraits< _Elevator> > {304 SetStandardElevatorTraits<T> > { 305 305 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 306 SetStandardElevatorTraits< _Elevator> > Create;306 SetStandardElevatorTraits<T> > Create; 307 307 }; 308 308 … … 471 471 472 472 for(NodeIt n(_g);n!=INVALID;++n) { 473 _excess->set(n, (*_supply)[n]);473 (*_excess)[n] = (*_supply)[n]; 474 474 } 475 475 476 476 for (ArcIt e(_g);e!=INVALID;++e) { 477 477 _flow->set(e, (*_lo)[e]); 478 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);479 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);478 (*_excess)[_g.target(e)] += (*_flow)[e]; 479 (*_excess)[_g.source(e)] -= (*_flow)[e]; 480 480 } 481 481 … … 500 500 501 501 for(NodeIt n(_g);n!=INVALID;++n) { 502 _excess->set(n, (*_supply)[n]);502 (*_excess)[n] = (*_supply)[n]; 503 503 } 504 504 … … 506 506 if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) { 507 507 _flow->set(e, (*_up)[e]); 508 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);509 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);508 (*_excess)[_g.target(e)] += (*_up)[e]; 509 (*_excess)[_g.source(e)] -= (*_up)[e]; 510 510 } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { 511 511 _flow->set(e, (*_lo)[e]); 512 _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);513 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);512 (*_excess)[_g.target(e)] += (*_lo)[e]; 513 (*_excess)[_g.source(e)] -= (*_lo)[e]; 514 514 } else { 515 515 Flow fc = -(*_excess)[_g.target(e)]; 516 516 _flow->set(e, fc); 517 _excess->set(_g.target(e), 0);518 _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);517 (*_excess)[_g.target(e)] = 0; 518 (*_excess)[_g.source(e)] -= fc; 519 519 } 520 520 } … … 555 555 if(!_tol.less(fc, exc)) { 556 556 _flow->set(e, (*_flow)[e] + exc); 557 _excess->set(v, (*_excess)[v] + exc);557 (*_excess)[v] += exc; 558 558 if(!_level->active(v) && _tol.positive((*_excess)[v])) 559 559 _level->activate(v); 560 _excess->set(act,0);560 (*_excess)[act] = 0; 561 561 _level->deactivate(act); 562 562 goto next_l; … … 564 564 else { 565 565 _flow->set(e, (*_up)[e]); 566 _excess->set(v, (*_excess)[v] + fc);566 (*_excess)[v] += fc; 567 567 if(!_level->active(v) && _tol.positive((*_excess)[v])) 568 568 _level->activate(v); … … 579 579 if(!_tol.less(fc, exc)) { 580 580 _flow->set(e, (*_flow)[e] - exc); 581 _excess->set(v, (*_excess)[v] + exc);581 (*_excess)[v] += exc; 582 582 if(!_level->active(v) && _tol.positive((*_excess)[v])) 583 583 _level->activate(v); 584 _excess->set(act,0);584 (*_excess)[act] = 0; 585 585 _level->deactivate(act); 586 586 goto next_l; … … 588 588 else { 589 589 _flow->set(e, (*_lo)[e]); 590 _excess->set(v, (*_excess)[v] + fc);590 (*_excess)[v] += fc; 591 591 if(!_level->active(v) && _tol.positive((*_excess)[v])) 592 592 _level->activate(v); … … 597 597 } 598 598 599 _excess->set(act, exc);599 (*_excess)[act] = exc; 600 600 if(!_tol.positive(exc)) _level->deactivate(act); 601 601 else if(mlevel==_node_num) { … … 700 700 /// 701 701 /// \note This function calls \ref barrier() for each node, 702 /// so it runs in \f$O(n)\f$time.702 /// so it runs in O(n) time. 703 703 /// 704 704 /// \pre Either \ref run() or \ref init() must be called before -
lemon/preflow.h
r628 r658 47 47 48 48 /// \brief The type of the flow values. 49 typedef typename CapacityMap::Value Value;49 typedef typename CapacityMap::Value Flow; 50 50 51 51 /// \brief The type of the map that stores the flow values. … … 53 53 /// The type of the map that stores the flow values. 54 54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 55 typedef typename Digraph::template ArcMap< Value> FlowMap;55 typedef typename Digraph::template ArcMap<Flow> FlowMap; 56 56 57 57 /// \brief Instantiates a FlowMap. 58 58 /// 59 59 /// This function instantiates a \ref FlowMap. 60 /// \param digraph The digraph , towhich we would like to define60 /// \param digraph The digraph for which we would like to define 61 61 /// the flow map. 62 62 static FlowMap* createFlowMap(const Digraph& digraph) { … … 75 75 /// 76 76 /// This function instantiates an \ref Elevator. 77 /// \param digraph The digraph , towhich we would like to define77 /// \param digraph The digraph for which we would like to define 78 78 /// the elevator. 79 79 /// \param max_level The maximum level of the elevator. … … 85 85 /// 86 86 /// The tolerance used by the algorithm to handle inexact computation. 87 typedef lemon::Tolerance< Value> Tolerance;87 typedef lemon::Tolerance<Flow> Tolerance; 88 88 89 89 }; … … 126 126 typedef typename Traits::CapacityMap CapacityMap; 127 127 ///The type of the flow values. 128 typedef typename Traits:: Value Value;128 typedef typename Traits::Flow Flow; 129 129 130 130 ///The type of the flow map. … … 152 152 bool _local_level; 153 153 154 typedef typename Digraph::template NodeMap< Value> ExcessMap;154 typedef typename Digraph::template NodeMap<Flow> ExcessMap; 155 155 ExcessMap* _excess; 156 156 … … 471 471 472 472 for (NodeIt n(_graph); n != INVALID; ++n) { 473 Valueexcess = 0;473 Flow excess = 0; 474 474 for (InArcIt e(_graph, n); e != INVALID; ++e) { 475 475 excess += (*_flow)[e]; … … 520 520 521 521 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { 522 Valuerem = (*_capacity)[e] - (*_flow)[e];522 Flow rem = (*_capacity)[e] - (*_flow)[e]; 523 523 if (_tolerance.positive(rem)) { 524 524 Node u = _graph.target(e); … … 532 532 } 533 533 for (InArcIt e(_graph, _source); e != INVALID; ++e) { 534 Valuerem = (*_flow)[e];534 Flow rem = (*_flow)[e]; 535 535 if (_tolerance.positive(rem)) { 536 536 Node v = _graph.source(e); … … 565 565 566 566 while (num > 0 && n != INVALID) { 567 Valueexcess = (*_excess)[n];567 Flow excess = (*_excess)[n]; 568 568 int new_level = _level->maxLevel(); 569 569 570 570 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 571 Valuerem = (*_capacity)[e] - (*_flow)[e];571 Flow rem = (*_capacity)[e] - (*_flow)[e]; 572 572 if (!_tolerance.positive(rem)) continue; 573 573 Node v = _graph.target(e); … … 592 592 593 593 for (InArcIt e(_graph, n); e != INVALID; ++e) { 594 Valuerem = (*_flow)[e];594 Flow rem = (*_flow)[e]; 595 595 if (!_tolerance.positive(rem)) continue; 596 596 Node v = _graph.source(e); … … 638 638 num = _node_num * 20; 639 639 while (num > 0 && n != INVALID) { 640 Valueexcess = (*_excess)[n];640 Flow excess = (*_excess)[n]; 641 641 int new_level = _level->maxLevel(); 642 642 643 643 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 644 Valuerem = (*_capacity)[e] - (*_flow)[e];644 Flow rem = (*_capacity)[e] - (*_flow)[e]; 645 645 if (!_tolerance.positive(rem)) continue; 646 646 Node v = _graph.target(e); … … 665 665 666 666 for (InArcIt e(_graph, n); e != INVALID; ++e) { 667 Valuerem = (*_flow)[e];667 Flow rem = (*_flow)[e]; 668 668 if (!_tolerance.positive(rem)) continue; 669 669 Node v = _graph.source(e); … … 779 779 Node n; 780 780 while ((n = _level->highestActive()) != INVALID) { 781 Valueexcess = (*_excess)[n];781 Flow excess = (*_excess)[n]; 782 782 int level = _level->highestActiveLevel(); 783 783 int new_level = _level->maxLevel(); 784 784 785 785 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 786 Valuerem = (*_capacity)[e] - (*_flow)[e];786 Flow rem = (*_capacity)[e] - (*_flow)[e]; 787 787 if (!_tolerance.positive(rem)) continue; 788 788 Node v = _graph.target(e); … … 807 807 808 808 for (InArcIt e(_graph, n); e != INVALID; ++e) { 809 Valuerem = (*_flow)[e];809 Flow rem = (*_flow)[e]; 810 810 if (!_tolerance.positive(rem)) continue; 811 811 Node v = _graph.source(e); … … 898 898 /// \pre Either \ref run() or \ref init() must be called before 899 899 /// using this function. 900 ValueflowValue() const {900 Flow flowValue() const { 901 901 return (*_excess)[_target]; 902 902 } … … 909 909 /// \pre Either \ref run() or \ref init() must be called before 910 910 /// using this function. 911 Valueflow(const Arc& arc) const {911 Flow flow(const Arc& arc) const { 912 912 return (*_flow)[arc]; 913 913 } -
lemon/preflow.h
r657 r658 33 33 /// Default traits class of Preflow class. 34 34 /// \tparam GR Digraph type. 35 /// \tparam C MCapacity map type.36 template <typename GR, typename C M>35 /// \tparam CAP Capacity map type. 36 template <typename GR, typename CAP> 37 37 struct PreflowDefaultTraits { 38 38 … … 44 44 /// The type of the map that stores the arc capacities. 45 45 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. 46 typedef C MCapacityMap;46 typedef CAP CapacityMap; 47 47 48 48 /// \brief The type of the flow values. … … 95 95 /// 96 96 /// This class provides an implementation of Goldberg-Tarjan's \e preflow 97 /// \e push-relabel algorithm producing a flow of maximum value in a 98 /// digraph. The preflow algorithms are the fastest known maximum 97 /// \e push-relabel algorithm producing a \ref max_flow 98 /// "flow of maximum value" in a digraph. 99 /// The preflow algorithms are the fastest known maximum 99 100 /// flow algorithms. The current implementation use a mixture of the 100 101 /// \e "highest label" and the \e "bound decrease" heuristics. … … 106 107 /// 107 108 /// \tparam GR The type of the digraph the algorithm runs on. 108 /// \tparam C MThe type of the capacity map. The default map109 /// \tparam CAP The type of the capacity map. The default map 109 110 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 110 111 #ifdef DOXYGEN 111 template <typename GR, typename C M, typename TR>112 template <typename GR, typename CAP, typename TR> 112 113 #else 113 114 template <typename GR, 114 typename C M= typename GR::template ArcMap<int>,115 typename TR = PreflowDefaultTraits<GR, C M> >115 typename CAP = typename GR::template ArcMap<int>, 116 typename TR = PreflowDefaultTraits<GR, CAP> > 116 117 #endif 117 118 class Preflow { … … 195 196 ///@{ 196 197 197 template <typename _FlowMap>198 template <typename T> 198 199 struct SetFlowMapTraits : public Traits { 199 typedef _FlowMapFlowMap;200 typedef T FlowMap; 200 201 static FlowMap *createFlowMap(const Digraph&) { 201 202 LEMON_ASSERT(false, "FlowMap is not initialized"); … … 209 210 /// \ref named-templ-param "Named parameter" for setting FlowMap 210 211 /// type. 211 template <typename _FlowMap>212 template <typename T> 212 213 struct SetFlowMap 213 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits< _FlowMap> > {214 : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > { 214 215 typedef Preflow<Digraph, CapacityMap, 215 SetFlowMapTraits< _FlowMap> > Create;216 SetFlowMapTraits<T> > Create; 216 217 }; 217 218 218 template <typename _Elevator>219 template <typename T> 219 220 struct SetElevatorTraits : public Traits { 220 typedef _ElevatorElevator;221 typedef T Elevator; 221 222 static Elevator *createElevator(const Digraph&, int) { 222 223 LEMON_ASSERT(false, "Elevator is not initialized"); … … 234 235 /// \ref run() or \ref init(). 235 236 /// \sa SetStandardElevator 236 template <typename _Elevator>237 template <typename T> 237 238 struct SetElevator 238 : public Preflow<Digraph, CapacityMap, SetElevatorTraits< _Elevator> > {239 : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > { 239 240 typedef Preflow<Digraph, CapacityMap, 240 SetElevatorTraits< _Elevator> > Create;241 SetElevatorTraits<T> > Create; 241 242 }; 242 243 243 template <typename _Elevator>244 template <typename T> 244 245 struct SetStandardElevatorTraits : public Traits { 245 typedef _ElevatorElevator;246 typedef T Elevator; 246 247 static Elevator *createElevator(const Digraph& digraph, int max_level) { 247 248 return new Elevator(digraph, max_level); … … 261 262 /// before calling \ref run() or \ref init(). 262 263 /// \sa SetElevator 263 template <typename _Elevator>264 template <typename T> 264 265 struct SetStandardElevator 265 266 : public Preflow<Digraph, CapacityMap, 266 SetStandardElevatorTraits< _Elevator> > {267 SetStandardElevatorTraits<T> > { 267 268 typedef Preflow<Digraph, CapacityMap, 268 SetStandardElevatorTraits< _Elevator> > Create;269 SetStandardElevatorTraits<T> > Create; 269 270 }; 270 271 … … 404 405 _phase = true; 405 406 for (NodeIt n(_graph); n != INVALID; ++n) { 406 _excess->set(n, 0);407 (*_excess)[n] = 0; 407 408 } 408 409 … … 417 418 418 419 std::vector<Node> queue; 419 reached .set(_source, true);420 reached[_source] = true; 420 421 421 422 queue.push_back(_target); 422 reached .set(_target, true);423 reached[_target] = true; 423 424 while (!queue.empty()) { 424 425 _level->initNewLevel(); … … 429 430 Node u = _graph.source(e); 430 431 if (!reached[u] && _tolerance.positive((*_capacity)[e])) { 431 reached .set(u, true);432 reached[u] = true; 432 433 _level->initAddItem(u); 433 434 nqueue.push_back(u); … … 444 445 if ((*_level)[u] == _level->maxLevel()) continue; 445 446 _flow->set(e, (*_capacity)[e]); 446 _excess->set(u, (*_excess)[u] + (*_capacity)[e]);447 (*_excess)[u] += (*_capacity)[e]; 447 448 if (u != _target && !_level->active(u)) { 448 449 _level->activate(u); … … 478 479 } 479 480 if (excess < 0 && n != _source) return false; 480 _excess->set(n, excess);481 (*_excess)[n] = excess; 481 482 } 482 483 … … 487 488 488 489 std::vector<Node> queue; 489 reached .set(_source, true);490 reached[_source] = true; 490 491 491 492 queue.push_back(_target); 492 reached .set(_target, true);493 reached[_target] = true; 493 494 while (!queue.empty()) { 494 495 _level->initNewLevel(); … … 500 501 if (!reached[u] && 501 502 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { 502 reached .set(u, true);503 reached[u] = true; 503 504 _level->initAddItem(u); 504 505 nqueue.push_back(u); … … 508 509 Node v = _graph.target(e); 509 510 if (!reached[v] && _tolerance.positive((*_flow)[e])) { 510 reached .set(v, true);511 reached[v] = true; 511 512 _level->initAddItem(v); 512 513 nqueue.push_back(v); … … 524 525 if ((*_level)[u] == _level->maxLevel()) continue; 525 526 _flow->set(e, (*_capacity)[e]); 526 _excess->set(u, (*_excess)[u] + rem);527 (*_excess)[u] += rem; 527 528 if (u != _target && !_level->active(u)) { 528 529 _level->activate(u); … … 536 537 if ((*_level)[v] == _level->maxLevel()) continue; 537 538 _flow->set(e, 0); 538 _excess->set(v, (*_excess)[v] + rem);539 (*_excess)[v] += rem; 539 540 if (v != _target && !_level->active(v)) { 540 541 _level->activate(v); … … 577 578 if (!_tolerance.less(rem, excess)) { 578 579 _flow->set(e, (*_flow)[e] + excess); 579 _excess->set(v, (*_excess)[v] + excess);580 (*_excess)[v] += excess; 580 581 excess = 0; 581 582 goto no_more_push_1; 582 583 } else { 583 584 excess -= rem; 584 _excess->set(v, (*_excess)[v] + rem);585 (*_excess)[v] += rem; 585 586 _flow->set(e, (*_capacity)[e]); 586 587 } … … 600 601 if (!_tolerance.less(rem, excess)) { 601 602 _flow->set(e, (*_flow)[e] - excess); 602 _excess->set(v, (*_excess)[v] + excess);603 (*_excess)[v] += excess; 603 604 excess = 0; 604 605 goto no_more_push_1; 605 606 } else { 606 607 excess -= rem; 607 _excess->set(v, (*_excess)[v] + rem);608 (*_excess)[v] += rem; 608 609 _flow->set(e, 0); 609 610 } … … 615 616 no_more_push_1: 616 617 617 _excess->set(n, excess);618 (*_excess)[n] = excess; 618 619 619 620 if (excess != 0) { … … 650 651 if (!_tolerance.less(rem, excess)) { 651 652 _flow->set(e, (*_flow)[e] + excess); 652 _excess->set(v, (*_excess)[v] + excess);653 (*_excess)[v] += excess; 653 654 excess = 0; 654 655 goto no_more_push_2; 655 656 } else { 656 657 excess -= rem; 657 _excess->set(v, (*_excess)[v] + rem);658 (*_excess)[v] += rem; 658 659 _flow->set(e, (*_capacity)[e]); 659 660 } … … 673 674 if (!_tolerance.less(rem, excess)) { 674 675 _flow->set(e, (*_flow)[e] - excess); 675 _excess->set(v, (*_excess)[v] + excess);676 (*_excess)[v] += excess; 676 677 excess = 0; 677 678 goto no_more_push_2; 678 679 } else { 679 680 excess -= rem; 680 _excess->set(v, (*_excess)[v] + rem);681 (*_excess)[v] += rem; 681 682 _flow->set(e, 0); 682 683 } … … 688 689 no_more_push_2: 689 690 690 _excess->set(n, excess);691 (*_excess)[n] = excess; 691 692 692 693 if (excess != 0) { … … 731 732 typename Digraph::template NodeMap<bool> reached(_graph); 732 733 for (NodeIt n(_graph); n != INVALID; ++n) { 733 reached .set(n, (*_level)[n] < _level->maxLevel());734 reached[n] = (*_level)[n] < _level->maxLevel(); 734 735 } 735 736 … … 739 740 std::vector<Node> queue; 740 741 queue.push_back(_source); 741 reached .set(_source, true);742 reached[_source] = true; 742 743 743 744 while (!queue.empty()) { … … 749 750 Node v = _graph.target(e); 750 751 if (!reached[v] && _tolerance.positive((*_flow)[e])) { 751 reached .set(v, true);752 reached[v] = true; 752 753 _level->initAddItem(v); 753 754 nqueue.push_back(v); … … 758 759 if (!reached[u] && 759 760 _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { 760 reached .set(u, true);761 reached[u] = true; 761 762 _level->initAddItem(u); 762 763 nqueue.push_back(u); … … 792 793 if (!_tolerance.less(rem, excess)) { 793 794 _flow->set(e, (*_flow)[e] + excess); 794 _excess->set(v, (*_excess)[v] + excess);795 (*_excess)[v] += excess; 795 796 excess = 0; 796 797 goto no_more_push; 797 798 } else { 798 799 excess -= rem; 799 _excess->set(v, (*_excess)[v] + rem);800 (*_excess)[v] += rem; 800 801 _flow->set(e, (*_capacity)[e]); 801 802 } … … 815 816 if (!_tolerance.less(rem, excess)) { 816 817 _flow->set(e, (*_flow)[e] - excess); 817 _excess->set(v, (*_excess)[v] + excess);818 (*_excess)[v] += excess; 818 819 excess = 0; 819 820 goto no_more_push; 820 821 } else { 821 822 excess -= rem; 822 _excess->set(v, (*_excess)[v] + rem);823 (*_excess)[v] += rem; 823 824 _flow->set(e, 0); 824 825 } … … 830 831 no_more_push: 831 832 832 _excess->set(n, excess);833 (*_excess)[n] = excess; 833 834 834 835 if (excess != 0) { … … 947 948 /// 948 949 /// \note This function calls \ref minCut() for each node, so it runs in 949 /// \f$O(n)\f$time.950 /// O(n) time. 950 951 /// 951 952 /// \pre Either \ref run() or \ref init() must be called before -
test/CMakeLists.txt
r641 r658 32 32 matching_test 33 33 min_cost_arborescence_test 34 min_cost_flow_test 34 35 path_test 35 36 preflow_test -
test/CMakeLists.txt
r648 r658 1 1 INCLUDE_DIRECTORIES( 2 ${ CMAKE_SOURCE_DIR}3 ${ CMAKE_BINARY_DIR}2 ${PROJECT_SOURCE_DIR} 3 ${PROJECT_BINARY_DIR} 4 4 ) 5 5 … … 8 8 ENDIF(HAVE_GLPK) 9 9 10 LINK_DIRECTORIES(${ CMAKE_BINARY_DIR}/lemon)10 LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon) 11 11 12 12 SET(TESTS … … 22 22 error_test 23 23 euler_test 24 gomory_hu_test 24 25 graph_copy_test 25 26 graph_test … … 29 30 kruskal_test 30 31 maps_test 31 ma x_matching_test32 matching_test 32 33 min_cost_arborescence_test 33 34 min_cost_flow_test -
test/Makefile.am
r641 r658 28 28 test/matching_test \ 29 29 test/min_cost_arborescence_test \ 30 test/min_cost_flow_test \ 30 31 test/path_test \ 31 32 test/preflow_test \ … … 73 74 test_matching_test_SOURCES = test/matching_test.cc 74 75 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc 76 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc 75 77 test_path_test_SOURCES = test/path_test.cc 76 78 test_preflow_test_SOURCES = test/preflow_test.cc -
test/Makefile.am
r648 r658 18 18 test/error_test \ 19 19 test/euler_test \ 20 test/gomory_hu_test \ 20 21 test/graph_copy_test \ 21 22 test/graph_test \ … … 25 26 test/kruskal_test \ 26 27 test/maps_test \ 27 test/ma x_matching_test \28 test/matching_test \ 28 29 test/min_cost_arborescence_test \ 29 30 test/min_cost_flow_test \ … … 37 38 test/time_measure_test \ 38 39 test/unionfind_test 40 41 test_test_tools_pass_DEPENDENCIES = demo 39 42 40 43 if HAVE_LP … … 59 62 test_error_test_SOURCES = test/error_test.cc 60 63 test_euler_test_SOURCES = test/euler_test.cc 64 test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc 61 65 test_graph_copy_test_SOURCES = test/graph_copy_test.cc 62 66 test_graph_test_SOURCES = test/graph_test.cc … … 68 72 test_maps_test_SOURCES = test/maps_test.cc 69 73 test_mip_test_SOURCES = test/mip_test.cc 70 test_ma x_matching_test_SOURCES = test/max_matching_test.cc74 test_matching_test_SOURCES = test/matching_test.cc 71 75 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc 72 76 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc -
test/circulation_test.cc
r632 r658 58 58 typedef Digraph::Arc Arc; 59 59 typedef concepts::ReadMap<Arc,VType> CapMap; 60 typedef concepts::ReadMap<Node,VType> DeltaMap;60 typedef concepts::ReadMap<Node,VType> SupplyMap; 61 61 typedef concepts::ReadWriteMap<Arc,VType> FlowMap; 62 62 typedef concepts::WriteMap<Node,bool> BarrierMap; … … 69 69 Arc a; 70 70 CapMap lcap, ucap; 71 DeltaMap delta;71 SupplyMap supply; 72 72 FlowMap flow; 73 73 BarrierMap bar; … … 75 75 bool b; 76 76 77 typedef Circulation<Digraph, CapMap, CapMap, DeltaMap>77 typedef Circulation<Digraph, CapMap, CapMap, SupplyMap> 78 78 ::SetFlowMap<FlowMap> 79 79 ::SetElevator<Elev> 80 80 ::SetStandardElevator<LinkedElev> 81 81 ::Create CirculationType; 82 CirculationType circ_test(g, lcap, ucap, delta);82 CirculationType circ_test(g, lcap, ucap, supply); 83 83 const CirculationType& const_circ_test = circ_test; 84 84 85 85 circ_test 86 .lower CapMap(lcap)87 .upper CapMap(ucap)88 . deltaMap(delta)86 .lowerMap(lcap) 87 .upperMap(ucap) 88 .supplyMap(supply) 89 89 .flowMap(flow); 90 90 -
test/circulation_test.cc
r657 r658 72 72 FlowMap flow; 73 73 BarrierMap bar; 74 VType v; 75 bool b; 74 76 75 Circulation<Digraph, CapMap, CapMap, SupplyMap> 76 ::SetFlowMap<FlowMap> 77 ::SetElevator<Elev> 78 ::SetStandardElevator<LinkedElev> 79 ::Create circ_test(g,lcap,ucap,supply); 80 81 circ_test.lowerMap(lcap); 82 circ_test.upperMap(ucap); 83 circ_test.supplyMap(supply); 84 flow = circ_test.flowMap(); 85 circ_test.flowMap(flow); 77 typedef Circulation<Digraph, CapMap, CapMap, SupplyMap> 78 ::SetFlowMap<FlowMap> 79 ::SetElevator<Elev> 80 ::SetStandardElevator<LinkedElev> 81 ::Create CirculationType; 82 CirculationType circ_test(g, lcap, ucap, supply); 83 const CirculationType& const_circ_test = circ_test; 84 85 circ_test 86 .lowerMap(lcap) 87 .upperMap(ucap) 88 .supplyMap(supply) 89 .flowMap(flow); 86 90 87 91 circ_test.init(); … … 90 94 circ_test.run(); 91 95 92 circ_test.barrier(n); 93 circ_test.barrierMap(bar); 94 circ_test.flow(a); 96 v = const_circ_test.flow(a); 97 const FlowMap& fm = const_circ_test.flowMap(); 98 b = const_circ_test.barrier(n); 99 const_circ_test.barrierMap(bar); 100 101 ignore_unused_variable_warning(fm); 95 102 } 96 103 -
tools/dimacs-solver.cc
r641 r658 44 44 #include <lemon/preflow.h> 45 45 #include <lemon/matching.h> 46 #include <lemon/network_simplex.h> 46 47 47 48 using namespace lemon; … … 91 92 } 92 93 94 template<class Value> 95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &, 96 DimacsDescriptor &desc) 97 { 98 bool report = !ap.given("q"); 99 Digraph g; 100 Digraph::ArcMap<Value> lower(g), cap(g), cost(g); 101 Digraph::NodeMap<Value> sup(g); 102 Timer ti; 103 ti.restart(); 104 readDimacsMin(is, g, lower, cap, cost, sup, 0, desc); 105 if (report) std::cerr << "Read the file: " << ti << '\n'; 106 ti.restart(); 107 NetworkSimplex<Digraph, Value> ns(g); 108 ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); 109 if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; 110 ti.restart(); 111 ns.run(); 112 if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; 113 if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n'; 114 } 115 93 116 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, 94 117 DimacsDescriptor &desc) … … 129 152 { 130 153 case DimacsDescriptor::MIN: 131 std::cerr << 132 "\n\n Sorry, the min. cost flow solver is not yet available.\n"; 154 solve_min<Value>(ap,is,os,desc); 133 155 break; 134 156 case DimacsDescriptor::MAX: -
tools/dimacs-solver.cc
r652 r658 24 24 /// 25 25 /// See 26 /// \ verbatim27 /// dimacs-solver --help28 /// \end verbatim26 /// \code 27 /// dimacs-solver --help 28 /// \endcode 29 29 /// for more info on usage. 30 ///31 30 32 31 #include <iostream> … … 44 43 #include <lemon/dijkstra.h> 45 44 #include <lemon/preflow.h> 46 #include <lemon/ma x_matching.h>45 #include <lemon/matching.h> 47 46 #include <lemon/network_simplex.h> 48 47 … … 74 73 template<class Value> 75 74 void solve_max(ArgParser &ap, std::istream &is, std::ostream &, 76 DimacsDescriptor &desc)75 Value infty, DimacsDescriptor &desc) 77 76 { 78 77 bool report = !ap.given("q"); … … 82 81 Timer ti; 83 82 ti.restart(); 84 readDimacsMax(is, g, cap, s, t, desc);83 readDimacsMax(is, g, cap, s, t, infty, desc); 85 84 if(report) std::cerr << "Read the file: " << ti << '\n'; 86 85 ti.restart(); … … 103 102 Timer ti; 104 103 ti.restart(); 105 readDimacsMin(is, g, lower, cap, cost, sup, desc);104 readDimacsMin(is, g, lower, cap, cost, sup, 0, desc); 106 105 if (report) std::cerr << "Read the file: " << ti << '\n'; 107 106 ti.restart(); … … 139 138 DimacsDescriptor &desc) 140 139 { 140 std::stringstream iss(static_cast<std::string>(ap["infcap"])); 141 Value infty; 142 iss >> infty; 143 if(iss.fail()) 144 { 145 std::cerr << "Cannot interpret '" 146 << static_cast<std::string>(ap["infcap"]) << "' as infinite" 147 << std::endl; 148 exit(1); 149 } 150 141 151 switch(desc.type) 142 152 { … … 145 155 break; 146 156 case DimacsDescriptor::MAX: 147 solve_max<Value>(ap,is,os, desc);157 solve_max<Value>(ap,is,os,infty,desc); 148 158 break; 149 159 case DimacsDescriptor::SP: … … 182 192 .optionGroup("datatype","ldouble") 183 193 .onlyOneGroup("datatype") 194 .stringOption("infcap","Value used for 'very high' capacities","0") 184 195 .run(); 185 196
Note: See TracChangeset
for help on using the changeset viewer.