Changes in / [658:85cb3aa71cce:647:0ba8dfce7259] in lemon
- Files:
-
- 2 deleted
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r658 r637 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: 320 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: 322 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_{ 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 \q uad \forall u\in V\setminus\{s,t\} \f]328 \f[ 0 \leq f( uv) \leq cap(uv) \quad \forall uv\in A \f]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 \qquad \forall v\in V\setminus\{s,t\} \f] 328 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\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 (lower and upper bounds) 354 and arc costs. 353 in a network with capacity constraints and arc costs. 355 354 Formally, let \f$G=(V,A)\f$ be a digraph, 356 355 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and 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$. 356 upper bounds for the flow values on the arcs, 359 357 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow 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 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 372 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 429 376 pivot strategies. 430 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on431 cost scaling.432 - \ref CapacityScaling Successive Shortest %Path algorithm with optional433 capacity scaling.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 the438 minimum cost flow problem, but CancelAndTighten and CycleCanceling439 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).445 377 */ 446 378 -
lemon/Makefile.am
r658 r641 94 94 lemon/min_cost_arborescence.h \ 95 95 lemon/nauty_reader.h \ 96 lemon/network_simplex.h \97 96 lemon/path.h \ 98 97 lemon/preflow.h \ -
lemon/circulation.h
r658 r628 32 32 /// 33 33 /// Default traits class of Circulation class. 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. 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. 39 38 template <typename GR, typename LM, 40 typename UM, typename SM>39 typename UM, typename DM> 41 40 struct CirculationDefaultTraits { 42 41 … … 44 43 typedef GR Digraph; 45 44 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; 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" 64 /// concept. 65 typedef DM DeltaMap; 65 66 66 67 /// \brief The type of the flow values. 67 typedef typename SupplyMap::Value Flow;68 typedef typename DeltaMap::Value Value; 68 69 69 70 /// \brief The type of the map that stores the flow values. 70 71 /// 71 72 /// The type of the map that stores the flow values. 72 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" 73 /// concept. 74 typedef typename Digraph::template ArcMap<Flow> FlowMap; 73 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 74 typedef typename Digraph::template ArcMap<Value> FlowMap; 75 75 76 76 /// \brief Instantiates a FlowMap. 77 77 /// 78 78 /// This function instantiates a \ref FlowMap. 79 /// \param digraph The digraph forwhich we would like to define79 /// \param digraph The digraph, to 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 forwhich we would like to define96 /// \param digraph The digraph, to 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< Flow> Tolerance;106 typedef lemon::Tolerance<Value> Tolerance; 107 107 108 108 }; … … 112 112 113 113 \ingroup max_flow 114 This class implements a push-relabel algorithm for the \enetwork115 \ecirculation problem.114 This class implements a push-relabel algorithm for the network 115 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 are 118 given for the difference between the outgoing and incoming flow 119 at the nodes. 117 are given for the flow values on the arcs and lower bounds 118 are given for the supply values of the nodes. 120 119 121 120 The exact formulation of this problem is the following. 122 121 Let \f$G=(V,A)\f$ be a digraph, 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". 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. 156 139 157 140 \tparam GR The type of the digraph the algorithm runs on. 158 \tparam LM The type of the lower bound map. The default141 \tparam LM The type of the lower bound capacity map. The default 159 142 map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 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 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 163 147 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>". 164 148 */ … … 167 151 typename LM, 168 152 typename UM, 169 typename SM,153 typename DM, 170 154 typename TR > 171 155 #else … … 173 157 typename LM = typename GR::template ArcMap<int>, 174 158 typename UM = LM, 175 typename SM = typename GR::template NodeMap<typename UM::Value>,176 typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >159 typename DM = typename GR::template NodeMap<typename UM::Value>, 160 typename TR = CirculationDefaultTraits<GR, LM, UM, DM> > 177 161 #endif 178 162 class Circulation { … … 184 168 typedef typename Traits::Digraph Digraph; 185 169 ///The type of the flow values. 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; 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; 194 179 ///The type of the flow map. 195 180 typedef typename Traits::FlowMap FlowMap; … … 207 192 int _node_num; 208 193 209 const L owerMap *_lo;210 const U pperMap *_up;211 const SupplyMap *_supply;194 const LCapMap *_lo; 195 const UCapMap *_up; 196 const DeltaMap *_delta; 212 197 213 198 FlowMap *_flow; … … 217 202 bool _local_level; 218 203 219 typedef typename Digraph::template NodeMap< Flow> ExcessMap;204 typedef typename Digraph::template NodeMap<Value> ExcessMap; 220 205 ExcessMap* _excess; 221 206 … … 247 232 template <typename T> 248 233 struct SetFlowMap 249 : public Circulation<Digraph, L owerMap, UpperMap, SupplyMap,234 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 250 235 SetFlowMapTraits<T> > { 251 typedef Circulation<Digraph, L owerMap, UpperMap, SupplyMap,236 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 252 237 SetFlowMapTraits<T> > Create; 253 238 }; … … 273 258 template <typename T> 274 259 struct SetElevator 275 : public Circulation<Digraph, L owerMap, UpperMap, SupplyMap,260 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 276 261 SetElevatorTraits<T> > { 277 typedef Circulation<Digraph, L owerMap, UpperMap, SupplyMap,262 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 278 263 SetElevatorTraits<T> > Create; 279 264 }; … … 301 286 template <typename T> 302 287 struct SetStandardElevator 303 : public Circulation<Digraph, L owerMap, UpperMap, SupplyMap,288 : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 304 289 SetStandardElevatorTraits<T> > { 305 typedef Circulation<Digraph, L owerMap, UpperMap, SupplyMap,290 typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap, 306 291 SetStandardElevatorTraits<T> > Create; 307 292 }; … … 315 300 public: 316 301 317 /// Constructor.318 319 302 /// The constructor of the class. 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 values324 /// onthe arcs.325 /// \param supply The signed supply valuesof the nodes.326 Circulation(const Digraph &g raph, const LowerMap &lower,327 const U pperMap &upper, const SupplyMap &supply)328 : _g(g raph), _lo(&lower), _up(&upper), _supply(&supply),329 _ flow(NULL), _local_flow(false), _level(NULL), _local_level(false),330 _ excess(NULL) {}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 of the arcs. 308 /// \param delta The lower bound for the supply of the nodes. 309 Circulation(const Digraph &g,const LCapMap &lo, 310 const UCapMap &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() {} 331 314 332 315 /// Destructor. … … 368 351 public: 369 352 370 /// Sets the lower bound map.371 372 /// Sets the lower bound map.353 /// Sets the lower bound capacity map. 354 355 /// Sets the lower bound capacity map. 373 356 /// \return <tt>(*this)</tt> 374 Circulation& lower Map(const LowerMap& map) {357 Circulation& lowerCapMap(const LCapMap& map) { 375 358 _lo = ↦ 376 359 return *this; 377 360 } 378 361 379 /// Sets the upper bound (capacity)map.380 381 /// Sets the upper bound (capacity)map.362 /// Sets the upper bound capacity map. 363 364 /// Sets the upper bound capacity map. 382 365 /// \return <tt>(*this)</tt> 383 Circulation& upper Map(const LowerMap& map) {366 Circulation& upperCapMap(const LCapMap& map) { 384 367 _up = ↦ 385 368 return *this; 386 369 } 387 370 388 /// Sets the supply map.389 390 /// Sets the supply map.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. 391 374 /// \return <tt>(*this)</tt> 392 Circulation& supplyMap(const SupplyMap& map) {393 _ supply= ↦375 Circulation& deltaMap(const DeltaMap& map) { 376 _delta = ↦ 394 377 return *this; 395 378 } … … 471 454 472 455 for(NodeIt n(_g);n!=INVALID;++n) { 473 (*_excess)[n] = (*_ supply)[n];456 (*_excess)[n] = (*_delta)[n]; 474 457 } 475 458 … … 500 483 501 484 for(NodeIt n(_g);n!=INVALID;++n) { 502 (*_excess)[n] = (*_ supply)[n];485 (*_excess)[n] = (*_delta)[n]; 503 486 } 504 487 … … 513 496 (*_excess)[_g.source(e)] -= (*_lo)[e]; 514 497 } else { 515 Flowfc = -(*_excess)[_g.target(e)];498 Value fc = -(*_excess)[_g.target(e)]; 516 499 _flow->set(e, fc); 517 500 (*_excess)[_g.target(e)] = 0; … … 546 529 int actlevel=(*_level)[act]; 547 530 int mlevel=_node_num; 548 Flowexc=(*_excess)[act];531 Value exc=(*_excess)[act]; 549 532 550 533 for(OutArcIt e(_g,act);e!=INVALID; ++e) { 551 534 Node v = _g.target(e); 552 Flowfc=(*_up)[e]-(*_flow)[e];535 Value fc=(*_up)[e]-(*_flow)[e]; 553 536 if(!_tol.positive(fc)) continue; 554 537 if((*_level)[v]<actlevel) { … … 574 557 for(InArcIt e(_g,act);e!=INVALID; ++e) { 575 558 Node v = _g.source(e); 576 Flowfc=(*_flow)[e]-(*_lo)[e];559 Value fc=(*_flow)[e]-(*_lo)[e]; 577 560 if(!_tol.positive(fc)) continue; 578 561 if((*_level)[v]<actlevel) { … … 650 633 /// \pre Either \ref run() or \ref init() must be called before 651 634 /// using this function. 652 Flowflow(const Arc& arc) const {635 Value flow(const Arc& arc) const { 653 636 return (*_flow)[arc]; 654 637 } … … 669 652 Barrier is a set \e B of nodes for which 670 653 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]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] 673 656 674 657 holds. The existence of a set with this property prooves that a … … 733 716 for(NodeIt n(_g);n!=INVALID;++n) 734 717 { 735 Flow dif=-(*_supply)[n];718 Value dif=-(*_delta)[n]; 736 719 for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e]; 737 720 for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e]; … … 748 731 bool checkBarrier() const 749 732 { 750 Flowdelta=0;733 Value delta=0; 751 734 for(NodeIt n(_g);n!=INVALID;++n) 752 735 if(barrier(n)) 753 delta-=(*_ supply)[n];736 delta-=(*_delta)[n]; 754 737 for(ArcIt e(_g);e!=INVALID;++e) 755 738 { -
lemon/preflow.h
r658 r628 47 47 48 48 /// \brief The type of the flow values. 49 typedef typename CapacityMap::Value Flow;49 typedef typename CapacityMap::Value Value; 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< Flow> FlowMap;55 typedef typename Digraph::template ArcMap<Value> FlowMap; 56 56 57 57 /// \brief Instantiates a FlowMap. 58 58 /// 59 59 /// This function instantiates a \ref FlowMap. 60 /// \param digraph The digraph forwhich we would like to define60 /// \param digraph The digraph, to 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 forwhich we would like to define77 /// \param digraph The digraph, to 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< Flow> Tolerance;87 typedef lemon::Tolerance<Value> Tolerance; 88 88 89 89 }; … … 126 126 typedef typename Traits::CapacityMap CapacityMap; 127 127 ///The type of the flow values. 128 typedef typename Traits:: Flow Flow;128 typedef typename Traits::Value Value; 129 129 130 130 ///The type of the flow map. … … 152 152 bool _local_level; 153 153 154 typedef typename Digraph::template NodeMap< Flow> ExcessMap;154 typedef typename Digraph::template NodeMap<Value> ExcessMap; 155 155 ExcessMap* _excess; 156 156 … … 471 471 472 472 for (NodeIt n(_graph); n != INVALID; ++n) { 473 Flowexcess = 0;473 Value 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 Flowrem = (*_capacity)[e] - (*_flow)[e];522 Value 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 Flowrem = (*_flow)[e];534 Value 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 Flowexcess = (*_excess)[n];567 Value excess = (*_excess)[n]; 568 568 int new_level = _level->maxLevel(); 569 569 570 570 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 571 Flowrem = (*_capacity)[e] - (*_flow)[e];571 Value 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 Flowrem = (*_flow)[e];594 Value 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 Flowexcess = (*_excess)[n];640 Value excess = (*_excess)[n]; 641 641 int new_level = _level->maxLevel(); 642 642 643 643 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 644 Flowrem = (*_capacity)[e] - (*_flow)[e];644 Value 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 Flowrem = (*_flow)[e];667 Value 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 Flowexcess = (*_excess)[n];781 Value 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 Flowrem = (*_capacity)[e] - (*_flow)[e];786 Value 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 Flowrem = (*_flow)[e];809 Value 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 FlowflowValue() const {900 Value 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 Flowflow(const Arc& arc) const {911 Value flow(const Arc& arc) const { 912 912 return (*_flow)[arc]; 913 913 } -
test/CMakeLists.txt
r658 r641 32 32 matching_test 33 33 min_cost_arborescence_test 34 min_cost_flow_test35 34 path_test 36 35 preflow_test -
test/Makefile.am
r658 r641 28 28 test/matching_test \ 29 29 test/min_cost_arborescence_test \ 30 test/min_cost_flow_test \31 30 test/path_test \ 32 31 test/preflow_test \ … … 74 73 test_matching_test_SOURCES = test/matching_test.cc 75 74 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc 76 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc77 75 test_path_test_SOURCES = test/path_test.cc 78 76 test_preflow_test_SOURCES = test/preflow_test.cc -
test/circulation_test.cc
r658 r632 58 58 typedef Digraph::Arc Arc; 59 59 typedef concepts::ReadMap<Arc,VType> CapMap; 60 typedef concepts::ReadMap<Node,VType> SupplyMap;60 typedef concepts::ReadMap<Node,VType> DeltaMap; 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 SupplyMap supply;71 DeltaMap delta; 72 72 FlowMap flow; 73 73 BarrierMap bar; … … 75 75 bool b; 76 76 77 typedef Circulation<Digraph, CapMap, CapMap, SupplyMap>77 typedef Circulation<Digraph, CapMap, CapMap, DeltaMap> 78 78 ::SetFlowMap<FlowMap> 79 79 ::SetElevator<Elev> 80 80 ::SetStandardElevator<LinkedElev> 81 81 ::Create CirculationType; 82 CirculationType circ_test(g, lcap, ucap, supply);82 CirculationType circ_test(g, lcap, ucap, delta); 83 83 const CirculationType& const_circ_test = circ_test; 84 84 85 85 circ_test 86 .lower Map(lcap)87 .upper Map(ucap)88 . supplyMap(supply)86 .lowerCapMap(lcap) 87 .upperCapMap(ucap) 88 .deltaMap(delta) 89 89 .flowMap(flow); 90 90 -
tools/dimacs-solver.cc
r658 r641 44 44 #include <lemon/preflow.h> 45 45 #include <lemon/matching.h> 46 #include <lemon/network_simplex.h>47 46 48 47 using namespace lemon; … … 92 91 } 93 92 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 116 93 void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, 117 94 DimacsDescriptor &desc) … … 152 129 { 153 130 case DimacsDescriptor::MIN: 154 solve_min<Value>(ap,is,os,desc); 131 std::cerr << 132 "\n\n Sorry, the min. cost flow solver is not yet available.\n"; 155 133 break; 156 134 case DimacsDescriptor::MAX:
Note: See TracChangeset
for help on using the changeset viewer.