Changes in lemon/circulation.h [611:85cb3aa71cce:581:aa1804409f29] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/circulation.h
r611 r581 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 {
Note: See TracChangeset
for help on using the changeset viewer.