Changes in / [592:0ba8dfce7259:603:85cb3aa71cce] in lemon-1.1
- Files:
-
- 2 added
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r582 r603 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 -
lemon/Makefile.am
r586 r603 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/circulation.h
r573 r603 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/preflow.h
r573 r603 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 } -
test/CMakeLists.txt
r586 r603 32 32 matching_test 33 33 min_cost_arborescence_test 34 min_cost_flow_test 34 35 path_test 35 36 preflow_test -
test/Makefile.am
r586 r603 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/circulation_test.cc
r577 r603 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 -
tools/dimacs-solver.cc
r586 r603 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:
Note: See TracChangeset
for help on using the changeset viewer.