r622:28f58740b6f8
Sat, 25 Apr 2009 18:25:59
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -23,2 +23,3 @@ |
| 23 | 23 |
#include <lemon/elevator.h> |
| 24 |
#include <limits> |
|
| 24 | 25 |
|
| ... | ... |
@@ -121,5 +122,5 @@ |
| 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 and
|
|
| 124 |
|
|
| 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$
|
| ... | ... |
@@ -129,3 +130,3 @@ |
| 129 | 130 |
\f$-sup(u)\f$ demand. |
| 130 |
A feasible circulation is an \f$f: A\rightarrow\mathbf{R}
|
|
| 131 |
A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
|
|
| 131 | 132 |
solution of the following problem. |
| ... | ... |
@@ -153,2 +154,6 @@ |
| 153 | 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. |
|
| 158 |
|
|
| 154 | 159 |
Note that this algorithm also provides a feasible solution for the |
| ... | ... |
@@ -339,2 +344,9 @@ |
| 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() {
|
| ... | ... |
@@ -382,3 +394,3 @@ |
| 382 | 394 |
/// \return <tt>(*this)</tt> |
| 383 |
Circulation& upperMap(const |
|
| 395 |
Circulation& upperMap(const UpperMap& map) {
|
|
| 384 | 396 |
_up = ↦ |
| ... | ... |
@@ -469,2 +481,5 @@ |
| 469 | 481 |
{
|
| 482 |
LEMON_DEBUG(checkBoundMaps(), |
|
| 483 |
"Upper bounds must be greater or equal to the lower bounds"); |
|
| 484 |
|
|
| 470 | 485 |
createStructures(); |
| ... | ... |
@@ -498,2 +513,5 @@ |
| 498 | 513 |
{
|
| 514 |
LEMON_DEBUG(checkBoundMaps(), |
|
| 515 |
"Upper bounds must be greater or equal to the lower bounds"); |
|
| 516 |
|
|
| 499 | 517 |
createStructures(); |
| ... | ... |
@@ -505,3 +523,3 @@ |
| 505 | 523 |
for (ArcIt e(_g);e!=INVALID;++e) {
|
| 506 |
if (!_tol. |
|
| 524 |
if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
|
|
| 507 | 525 |
_flow->set(e, (*_up)[e]); |
| ... | ... |
@@ -509,3 +527,3 @@ |
| 509 | 527 |
(*_excess)[_g.source(e)] -= (*_up)[e]; |
| 510 |
} else if (_tol. |
|
| 528 |
} else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
|
|
| 511 | 529 |
_flow->set(e, (*_lo)[e]); |
| ... | ... |
@@ -750,2 +768,5 @@ |
| 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) |
| ... | ... |
@@ -757,3 +778,6 @@ |
| 757 | 778 |
Node t=_g.target(e); |
| 758 |
if(barrier(s)&&!barrier(t)) |
|
| 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]; |
0 comments (0 inline)