r622:28f58740b6f8
Sat, 25 Apr 2009 18:25:59
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -22,4 +22,5 @@ |
| 22 | 22 |
#include <lemon/tolerance.h> |
| 23 | 23 |
#include <lemon/elevator.h> |
| 24 |
#include <limits> |
|
| 24 | 25 |
|
| 25 | 26 |
///\ingroup max_flow |
| ... | ... |
@@ -120,7 +121,7 @@ |
| 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 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$
|
| 126 | 127 |
denotes the signed supply values of the nodes. |
| ... | ... |
@@ -128,5 +129,5 @@ |
| 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}
|
|
| 131 |
A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
|
|
| 131 | 132 |
solution of the following problem. |
| 132 | 133 |
|
| ... | ... |
@@ -152,4 +153,8 @@ |
| 152 | 153 |
(e.g. using \ref ReverseDigraph and \ref NegMap adaptors). |
| 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 |
| 155 | 160 |
\ref min_cost_flow "minimum cost flow problem". |
| ... | ... |
@@ -338,4 +343,11 @@ |
| 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,5 +393,5 @@ |
| 381 | 393 |
/// Sets the upper bound (capacity) map. |
| 382 | 394 |
/// \return <tt>(*this)</tt> |
| 383 |
Circulation& upperMap(const |
|
| 395 |
Circulation& upperMap(const UpperMap& map) {
|
|
| 384 | 396 |
_up = ↦ |
| 385 | 397 |
return *this; |
| ... | ... |
@@ -468,4 +480,7 @@ |
| 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,4 +512,7 @@ |
| 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,9 +522,9 @@ |
| 504 | 522 |
|
| 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]); |
| 508 | 526 |
(*_excess)[_g.target(e)] += (*_up)[e]; |
| 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]); |
| 512 | 530 |
(*_excess)[_g.target(e)] += (*_lo)[e]; |
| ... | ... |
@@ -749,4 +767,7 @@ |
| 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,5 +777,8 @@ |
| 756 | 777 |
Node s=_g.source(e); |
| 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]; |
| 760 | 784 |
} |
0 comments (0 inline)