test/preflow_test.cc
changeset 925 06491fd08efd
parent 877 141f9c0db4a3
parent 923 30d5f950aa5f
child 1008 d216e1c8b3fa
equal deleted inserted replaced
8:cda9f62537a7 10:b5ed68b02d39
   154     if (sum != 0) return false;
   154     if (sum != 0) return false;
   155   }
   155   }
   156   return true;
   156   return true;
   157 }
   157 }
   158 
   158 
       
   159 void initFlowTest()
       
   160 {
       
   161   DIGRAPH_TYPEDEFS(SmartDigraph);
       
   162   
       
   163   SmartDigraph g;
       
   164   SmartDigraph::ArcMap<int> cap(g),iflow(g);
       
   165   Node s=g.addNode(); Node t=g.addNode();
       
   166   Node n1=g.addNode(); Node n2=g.addNode();
       
   167   Arc a;
       
   168   a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
       
   169   a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
       
   170   a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
       
   171 
       
   172   Preflow<SmartDigraph> pre(g,cap,s,t);
       
   173   pre.init(iflow);
       
   174   pre.startFirstPhase();
       
   175   check(pre.flowValue() == 10, "The incorrect max flow value.");
       
   176   check(pre.minCut(s), "Wrong min cut (Node s).");
       
   177   check(pre.minCut(n1), "Wrong min cut (Node n1).");
       
   178   check(!pre.minCut(n2), "Wrong min cut (Node n2).");
       
   179   check(!pre.minCut(t), "Wrong min cut (Node t).");
       
   180 }
       
   181 
       
   182 
   159 int main() {
   183 int main() {
   160 
   184 
   161   typedef SmartDigraph Digraph;
   185   typedef SmartDigraph Digraph;
   162 
   186 
   163   typedef Digraph::Node Node;
   187   typedef Digraph::Node Node;
   244 
   268 
   245 
   269 
   246   check(preflow_test.flowValue() == min_cut_value,
   270   check(preflow_test.flowValue() == min_cut_value,
   247         "The max flow value or the three min cut values are incorrect.");
   271         "The max flow value or the three min cut values are incorrect.");
   248 
   272 
       
   273   initFlowTest();
       
   274   
   249   return 0;
   275   return 0;
   250 }
   276 }