r669:28f58740b6f8
Sat, 25 Apr 2009 18:25:59
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -21,6 +21,7 @@ |
| 21 | 21 |
|
| 22 | 22 |
#include <lemon/tolerance.h> |
| 23 | 23 |
#include <lemon/elevator.h> |
| 24 |
#include <limits> |
|
| 24 | 25 |
|
| 25 | 26 |
///\ingroup max_flow |
| 26 | 27 |
///\file |
| ... | ... |
@@ -119,15 +120,15 @@ |
| 119 | 120 |
at the nodes. |
| 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. |
| 127 | 128 |
If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ |
| 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 |
|
| 133 | 134 |
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
|
| ... | ... |
@@ -151,6 +152,10 @@ |
| 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). |
| 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". |
| 156 | 161 |
|
| ... | ... |
@@ -337,6 +342,13 @@ |
| 337 | 342 |
|
| 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); |
| 342 | 354 |
|
| ... | ... |
@@ -380,7 +392,7 @@ |
| 380 | 392 |
|
| 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; |
| 386 | 398 |
} |
| ... | ... |
@@ -467,6 +479,9 @@ |
| 467 | 479 |
/// to the lower bound. |
| 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 |
|
| 472 | 487 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
| ... | ... |
@@ -496,6 +511,9 @@ |
| 496 | 511 |
/// to construct the initial solution. |
| 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 |
|
| 501 | 519 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
| ... | ... |
@@ -503,11 +521,11 @@ |
| 503 | 521 |
} |
| 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]; |
| 513 | 531 |
(*_excess)[_g.source(e)] -= (*_lo)[e]; |
| ... | ... |
@@ -748,6 +766,9 @@ |
| 748 | 766 |
bool checkBarrier() const |
| 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)) |
| 753 | 774 |
delta-=(*_supply)[n]; |
| ... | ... |
@@ -755,7 +776,10 @@ |
| 755 | 776 |
{
|
| 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 |
} |
| 761 | 785 |
return _tol.negative(delta); |
0 comments (0 inline)