Fix wrong initialization in Preflow (#414)
authorAlpar Juttner <alpar@cs.elte.hu>
Fri, 25 Feb 2011 21:37:47 +0100
changeset 73930d5f950aa5f
parent 732 bb70ad62c95f
child 740 075de3c84e1f
child 741 8ae2627aba1a
Fix wrong initialization in Preflow (#414)
lemon/preflow.h
test/preflow_test.cc
     1.1 --- a/lemon/preflow.h	Thu Jun 24 09:27:53 2010 +0200
     1.2 +++ b/lemon/preflow.h	Fri Feb 25 21:37:47 2011 +0100
     1.3 @@ -525,9 +525,6 @@
     1.4            if ((*_level)[u] == _level->maxLevel()) continue;
     1.5            _flow->set(e, (*_capacity)[e]);
     1.6            (*_excess)[u] += rem;
     1.7 -          if (u != _target && !_level->active(u)) {
     1.8 -            _level->activate(u);
     1.9 -          }
    1.10          }
    1.11        }
    1.12        for (InArcIt e(_graph, _source); e != INVALID; ++e) {
    1.13 @@ -537,11 +534,12 @@
    1.14            if ((*_level)[v] == _level->maxLevel()) continue;
    1.15            _flow->set(e, 0);
    1.16            (*_excess)[v] += rem;
    1.17 -          if (v != _target && !_level->active(v)) {
    1.18 -            _level->activate(v);
    1.19 -          }
    1.20          }
    1.21        }
    1.22 +      for (NodeIt n(_graph); n != INVALID; ++n) 
    1.23 +        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
    1.24 +          _level->activate(n);
    1.25 +          
    1.26        return true;
    1.27      }
    1.28  
     2.1 --- a/test/preflow_test.cc	Thu Jun 24 09:27:53 2010 +0200
     2.2 +++ b/test/preflow_test.cc	Fri Feb 25 21:37:47 2011 +0100
     2.3 @@ -151,6 +151,30 @@
     2.4    return true;
     2.5  }
     2.6  
     2.7 +void initFlowTest()
     2.8 +{
     2.9 +  DIGRAPH_TYPEDEFS(SmartDigraph);
    2.10 +  
    2.11 +  SmartDigraph g;
    2.12 +  SmartDigraph::ArcMap<int> cap(g),iflow(g);
    2.13 +  Node s=g.addNode(); Node t=g.addNode();
    2.14 +  Node n1=g.addNode(); Node n2=g.addNode();
    2.15 +  Arc a;
    2.16 +  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
    2.17 +  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
    2.18 +  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
    2.19 +
    2.20 +  Preflow<SmartDigraph> pre(g,cap,s,t);
    2.21 +  pre.init(iflow);
    2.22 +  pre.startFirstPhase();
    2.23 +  check(pre.flowValue() == 10, "The incorrect max flow value.");
    2.24 +  check(pre.minCut(s), "Wrong min cut (Node s).");
    2.25 +  check(pre.minCut(n1), "Wrong min cut (Node n1).");
    2.26 +  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
    2.27 +  check(!pre.minCut(t), "Wrong min cut (Node t).");
    2.28 +}
    2.29 +
    2.30 +
    2.31  int main() {
    2.32  
    2.33    typedef SmartDigraph Digraph;
    2.34 @@ -241,5 +265,7 @@
    2.35    check(preflow_test.flowValue() == min_cut_value,
    2.36          "The max flow value or the three min cut values are incorrect.");
    2.37  
    2.38 +  initFlowTest();
    2.39 +  
    2.40    return 0;
    2.41  }