r923:30d5f950aa5f
Fri, 25 Feb 2011 21:37:47
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -524,11 +524,8 @@ |
| 524 | 524 |
Node u = _graph.target(e); |
| 525 | 525 |
if ((*_level)[u] == _level->maxLevel()) continue; |
| 526 | 526 |
_flow->set(e, (*_capacity)[e]); |
| 527 | 527 |
(*_excess)[u] += rem; |
| 528 |
if (u != _target && !_level->active(u)) {
|
|
| 529 |
_level->activate(u); |
|
| 530 |
} |
|
| 531 | 528 |
} |
| 532 | 529 |
} |
| 533 | 530 |
for (InArcIt e(_graph, _source); e != INVALID; ++e) {
|
| 534 | 531 |
Value rem = (*_flow)[e]; |
| ... | ... |
@@ -536,13 +533,14 @@ |
| 536 | 533 |
Node v = _graph.source(e); |
| 537 | 534 |
if ((*_level)[v] == _level->maxLevel()) continue; |
| 538 | 535 |
_flow->set(e, 0); |
| 539 | 536 |
(*_excess)[v] += rem; |
| 540 |
if (v != _target && !_level->active(v)) {
|
|
| 541 |
_level->activate(v); |
|
| 542 |
} |
|
| 543 | 537 |
} |
| 544 | 538 |
} |
| 539 |
for (NodeIt n(_graph); n != INVALID; ++n) |
|
| 540 |
if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n])) |
|
| 541 |
_level->activate(n); |
|
| 542 |
|
|
| 545 | 543 |
return true; |
| 546 | 544 |
} |
| 547 | 545 |
|
| 548 | 546 |
/// \brief Starts the first phase of the preflow algorithm. |
| ... | ... |
@@ -150,8 +150,32 @@ |
| 150 | 150 |
} |
| 151 | 151 |
return true; |
| 152 | 152 |
} |
| 153 | 153 |
|
| 154 |
void initFlowTest() |
|
| 155 |
{
|
|
| 156 |
DIGRAPH_TYPEDEFS(SmartDigraph); |
|
| 157 |
|
|
| 158 |
SmartDigraph g; |
|
| 159 |
SmartDigraph::ArcMap<int> cap(g),iflow(g); |
|
| 160 |
Node s=g.addNode(); Node t=g.addNode(); |
|
| 161 |
Node n1=g.addNode(); Node n2=g.addNode(); |
|
| 162 |
Arc a; |
|
| 163 |
a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; |
|
| 164 |
a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; |
|
| 165 |
a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; |
|
| 166 |
|
|
| 167 |
Preflow<SmartDigraph> pre(g,cap,s,t); |
|
| 168 |
pre.init(iflow); |
|
| 169 |
pre.startFirstPhase(); |
|
| 170 |
check(pre.flowValue() == 10, "The incorrect max flow value."); |
|
| 171 |
check(pre.minCut(s), "Wrong min cut (Node s)."); |
|
| 172 |
check(pre.minCut(n1), "Wrong min cut (Node n1)."); |
|
| 173 |
check(!pre.minCut(n2), "Wrong min cut (Node n2)."); |
|
| 174 |
check(!pre.minCut(t), "Wrong min cut (Node t)."); |
|
| 175 |
} |
|
| 176 |
|
|
| 177 |
|
|
| 154 | 178 |
int main() {
|
| 155 | 179 |
|
| 156 | 180 |
typedef SmartDigraph Digraph; |
| 157 | 181 |
|
| ... | ... |
@@ -240,6 +264,8 @@ |
| 240 | 264 |
|
| 241 | 265 |
check(preflow_test.flowValue() == min_cut_value, |
| 242 | 266 |
"The max flow value or the three min cut values are incorrect."); |
| 243 | 267 |
|
| 268 |
initFlowTest(); |
|
| 269 |
|
|
| 244 | 270 |
return 0; |
| 245 | 271 |
} |
0 comments (0 inline)