Changeset 657:dacc2cee2b4c in lemon for lemon
- Timestamp:
- 04/17/09 18:14:35 (16 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/circulation.h
r525 r657 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 _FlowMap> 233 248 struct SetFlowMap 234 : public Circulation<Digraph, L CapMap, UCapMap, DeltaMap,249 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 235 250 SetFlowMapTraits<_FlowMap> > { 236 typedef Circulation<Digraph, L CapMap, UCapMap, DeltaMap,251 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 237 252 SetFlowMapTraits<_FlowMap> > Create; 238 253 }; … … 258 273 template <typename _Elevator> 259 274 struct SetElevator 260 : public Circulation<Digraph, L CapMap, UCapMap, DeltaMap,275 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 261 276 SetElevatorTraits<_Elevator> > { 262 typedef Circulation<Digraph, L CapMap, UCapMap, DeltaMap,277 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 263 278 SetElevatorTraits<_Elevator> > Create; 264 279 }; … … 286 301 template <typename _Elevator> 287 302 struct SetStandardElevator 288 : public Circulation<Digraph, L CapMap, UCapMap, DeltaMap,303 : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 289 304 SetStandardElevatorTraits<_Elevator> > { 290 typedef Circulation<Digraph, L CapMap, UCapMap, DeltaMap,305 typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap, 291 306 SetStandardElevatorTraits<_Elevator> > 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->set(n, (*_ delta)[n]);473 _excess->set(n, (*_supply)[n]); 457 474 } 458 475 … … 483 500 484 501 for(NodeIt n(_g);n!=INVALID;++n) { 485 _excess->set(n, (*_ delta)[n]);502 _excess->set(n, (*_supply)[n]); 486 503 } 487 504 … … 496 513 _excess->set(_g.source(e), (*_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->set(_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
r525 r657 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 }; … … 125 125 typedef typename Traits::CapacityMap CapacityMap; 126 126 ///The type of the flow values. 127 typedef typename Traits:: Value Value;127 typedef typename Traits::Flow Flow; 128 128 129 129 ///The type of the flow map. … … 151 151 bool _local_level; 152 152 153 typedef typename Digraph::template NodeMap< Value> ExcessMap;153 typedef typename Digraph::template NodeMap<Flow> ExcessMap; 154 154 ExcessMap* _excess; 155 155 … … 470 470 471 471 for (NodeIt n(_graph); n != INVALID; ++n) { 472 Valueexcess = 0;472 Flow excess = 0; 473 473 for (InArcIt e(_graph, n); e != INVALID; ++e) { 474 474 excess += (*_flow)[e]; … … 519 519 520 520 for (OutArcIt e(_graph, _source); e != INVALID; ++e) { 521 Valuerem = (*_capacity)[e] - (*_flow)[e];521 Flow rem = (*_capacity)[e] - (*_flow)[e]; 522 522 if (_tolerance.positive(rem)) { 523 523 Node u = _graph.target(e); … … 531 531 } 532 532 for (InArcIt e(_graph, _source); e != INVALID; ++e) { 533 Valuerem = (*_flow)[e];533 Flow rem = (*_flow)[e]; 534 534 if (_tolerance.positive(rem)) { 535 535 Node v = _graph.source(e); … … 564 564 565 565 while (num > 0 && n != INVALID) { 566 Valueexcess = (*_excess)[n];566 Flow excess = (*_excess)[n]; 567 567 int new_level = _level->maxLevel(); 568 568 569 569 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 570 Valuerem = (*_capacity)[e] - (*_flow)[e];570 Flow rem = (*_capacity)[e] - (*_flow)[e]; 571 571 if (!_tolerance.positive(rem)) continue; 572 572 Node v = _graph.target(e); … … 591 591 592 592 for (InArcIt e(_graph, n); e != INVALID; ++e) { 593 Valuerem = (*_flow)[e];593 Flow rem = (*_flow)[e]; 594 594 if (!_tolerance.positive(rem)) continue; 595 595 Node v = _graph.source(e); … … 637 637 num = _node_num * 20; 638 638 while (num > 0 && n != INVALID) { 639 Valueexcess = (*_excess)[n];639 Flow excess = (*_excess)[n]; 640 640 int new_level = _level->maxLevel(); 641 641 642 642 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 643 Valuerem = (*_capacity)[e] - (*_flow)[e];643 Flow rem = (*_capacity)[e] - (*_flow)[e]; 644 644 if (!_tolerance.positive(rem)) continue; 645 645 Node v = _graph.target(e); … … 664 664 665 665 for (InArcIt e(_graph, n); e != INVALID; ++e) { 666 Valuerem = (*_flow)[e];666 Flow rem = (*_flow)[e]; 667 667 if (!_tolerance.positive(rem)) continue; 668 668 Node v = _graph.source(e); … … 778 778 Node n; 779 779 while ((n = _level->highestActive()) != INVALID) { 780 Valueexcess = (*_excess)[n];780 Flow excess = (*_excess)[n]; 781 781 int level = _level->highestActiveLevel(); 782 782 int new_level = _level->maxLevel(); 783 783 784 784 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 785 Valuerem = (*_capacity)[e] - (*_flow)[e];785 Flow rem = (*_capacity)[e] - (*_flow)[e]; 786 786 if (!_tolerance.positive(rem)) continue; 787 787 Node v = _graph.target(e); … … 806 806 807 807 for (InArcIt e(_graph, n); e != INVALID; ++e) { 808 Valuerem = (*_flow)[e];808 Flow rem = (*_flow)[e]; 809 809 if (!_tolerance.positive(rem)) continue; 810 810 Node v = _graph.source(e); … … 897 897 /// \pre Either \ref run() or \ref init() must be called before 898 898 /// using this function. 899 ValueflowValue() const {899 Flow flowValue() const { 900 900 return (*_excess)[_target]; 901 901 } … … 908 908 /// \pre Either \ref run() or \ref init() must be called before 909 909 /// using this function. 910 Valueflow(const Arc& arc) const {910 Flow flow(const Arc& arc) const { 911 911 return (*_flow)[arc]; 912 912 }
Note: See TracChangeset
for help on using the changeset viewer.