test/preflow_test.cc
changeset 933 66156a3498ea
parent 585 65fbcf2f978a
child 924 a80381c43760
child 1007 7e368d9b67f7
equal deleted inserted replaced
6:7a1a916d12b2 9:550748c3ccb1
   149     if (sum != 0) return false;
   149     if (sum != 0) return false;
   150   }
   150   }
   151   return true;
   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 int main() {
   178 int main() {
   155 
   179 
   156   typedef SmartDigraph Digraph;
   180   typedef SmartDigraph Digraph;
   157 
   181 
   158   typedef Digraph::Node Node;
   182   typedef Digraph::Node Node;
   239 
   263 
   240 
   264 
   241   check(preflow_test.flowValue() == min_cut_value,
   265   check(preflow_test.flowValue() == min_cut_value,
   242         "The max flow value or the three min cut values are incorrect.");
   266         "The max flow value or the three min cut values are incorrect.");
   243 
   267 
       
   268   initFlowTest();
       
   269   
   244   return 0;
   270   return 0;
   245 }
   271 }