Changeset 669:28f58740b6f8 in lemon
- Timestamp:
- 04/25/09 18:25:59 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/circulation.h
r658 r669 22 22 #include <lemon/tolerance.h> 23 23 #include <lemon/elevator.h> 24 #include <limits> 24 25 25 26 ///\ingroup max_flow … … 120 121 121 122 The exact formulation of this problem is the following. 122 Let \f$G=(V,A)\f$ be a digraph, 123 \f$ lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and124 upper bounds on the arcs, for which \f$ 0 \leqlower(uv) \leq upper(uv)\f$123 Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$ 124 \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and 125 upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$ 125 126 holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$ 126 127 denotes the signed supply values of the nodes. … … 128 129 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with 129 130 \f$-sup(u)\f$ demand. 130 A feasible circulation is an \f$f: A\rightarrow\mathbf{R} ^+_0\f$131 A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$ 131 132 solution of the following problem. 132 133 … … 151 152 the direction of the arcs and taking the negative of the supply values 152 153 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). 154 155 This algorithm either calculates a feasible circulation, or provides 156 a \ref barrier() "barrier", which prooves that a feasible soultion 157 cannot exist. 153 158 154 159 Note that this algorithm also provides a feasible solution for the … … 338 343 private: 339 344 345 bool checkBoundMaps() { 346 for (ArcIt e(_g);e!=INVALID;++e) { 347 if (_tol.less((*_up)[e], (*_lo)[e])) return false; 348 } 349 return true; 350 } 351 340 352 void createStructures() { 341 353 _node_num = _el = countNodes(_g); … … 381 393 /// Sets the upper bound (capacity) map. 382 394 /// \return <tt>(*this)</tt> 383 Circulation& upperMap(const LowerMap& map) {395 Circulation& upperMap(const UpperMap& map) { 384 396 _up = ↦ 385 397 return *this; … … 468 480 void init() 469 481 { 482 LEMON_DEBUG(checkBoundMaps(), 483 "Upper bounds must be greater or equal to the lower bounds"); 484 470 485 createStructures(); 471 486 … … 497 512 void greedyInit() 498 513 { 514 LEMON_DEBUG(checkBoundMaps(), 515 "Upper bounds must be greater or equal to the lower bounds"); 516 499 517 createStructures(); 500 518 … … 504 522 505 523 for (ArcIt e(_g);e!=INVALID;++e) { 506 if (!_tol. positive((*_excess)[_g.target(e)] +(*_up)[e])) {524 if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) { 507 525 _flow->set(e, (*_up)[e]); 508 526 (*_excess)[_g.target(e)] += (*_up)[e]; 509 527 (*_excess)[_g.source(e)] -= (*_up)[e]; 510 } else if (_tol. positive((*_excess)[_g.target(e)] +(*_lo)[e])) {528 } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) { 511 529 _flow->set(e, (*_lo)[e]); 512 530 (*_excess)[_g.target(e)] += (*_lo)[e]; … … 749 767 { 750 768 Flow delta=0; 769 Flow inf_cap = std::numeric_limits<Flow>::has_infinity ? 770 std::numeric_limits<Flow>::infinity() : 771 std::numeric_limits<Flow>::max(); 751 772 for(NodeIt n(_g);n!=INVALID;++n) 752 773 if(barrier(n)) … … 756 777 Node s=_g.source(e); 757 778 Node t=_g.target(e); 758 if(barrier(s)&&!barrier(t)) delta+=(*_up)[e]; 779 if(barrier(s)&&!barrier(t)) { 780 if (_tol.less(inf_cap - (*_up)[e], delta)) return false; 781 delta+=(*_up)[e]; 782 } 759 783 else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e]; 760 784 }
Note: See TracChangeset
for help on using the changeset viewer.