diff --git a/lemon/preflow.h b/lemon/preflow.h --- a/lemon/preflow.h +++ b/lemon/preflow.h @@ -525,9 +525,6 @@ if ((*_level)[u] == _level->maxLevel()) continue; _flow->set(e, (*_capacity)[e]); (*_excess)[u] += rem; - if (u != _target && !_level->active(u)) { - _level->activate(u); - } } } for (InArcIt e(_graph, _source); e != INVALID; ++e) { @@ -537,11 +534,12 @@ if ((*_level)[v] == _level->maxLevel()) continue; _flow->set(e, 0); (*_excess)[v] += rem; - if (v != _target && !_level->active(v)) { - _level->activate(v); - } } } + for (NodeIt n(_graph); n != INVALID; ++n) + if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n])) + _level->activate(n); + return true; } diff --git a/test/preflow_test.cc b/test/preflow_test.cc --- a/test/preflow_test.cc +++ b/test/preflow_test.cc @@ -151,6 +151,30 @@ return true; } +void initFlowTest() +{ + DIGRAPH_TYPEDEFS(SmartDigraph); + + SmartDigraph g; + SmartDigraph::ArcMap cap(g),iflow(g); + Node s=g.addNode(); Node t=g.addNode(); + Node n1=g.addNode(); Node n2=g.addNode(); + Arc a; + a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; + a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; + a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; + + Preflow pre(g,cap,s,t); + pre.init(iflow); + pre.startFirstPhase(); + check(pre.flowValue() == 10, "The incorrect max flow value."); + check(pre.minCut(s), "Wrong min cut (Node s)."); + check(pre.minCut(n1), "Wrong min cut (Node n1)."); + check(!pre.minCut(n2), "Wrong min cut (Node n2)."); + check(!pre.minCut(t), "Wrong min cut (Node t)."); +} + + int main() { typedef SmartDigraph Digraph; @@ -241,5 +265,7 @@ check(preflow_test.flowValue() == min_cut_value, "The max flow value or the three min cut values are incorrect."); + initFlowTest(); + return 0; }