test/bellman_ford_test.cc
changeset 751 f5f260a63a9b
parent 698 f9746e45246e
child 781 6f10c6ec5a21
equal deleted inserted replaced
0:9d9dce622d85 1:8f9cc97590a4
   218       }
   218       }
   219     }
   219     }
   220   }
   220   }
   221 }
   221 }
   222 
   222 
       
   223 void checkBellmanFordNegativeCycle() {
       
   224   DIGRAPH_TYPEDEFS(SmartDigraph);
       
   225 
       
   226   SmartDigraph gr;
       
   227   IntArcMap length(gr);
       
   228   
       
   229   Node n1 = gr.addNode();
       
   230   Node n2 = gr.addNode();
       
   231   Node n3 = gr.addNode();
       
   232   Node n4 = gr.addNode();
       
   233   
       
   234   Arc a1 = gr.addArc(n1, n2);
       
   235   Arc a2 = gr.addArc(n2, n2);
       
   236   
       
   237   length[a1] = 2;
       
   238   length[a2] = -1;
       
   239   
       
   240   {
       
   241     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
       
   242     bf.run(n1);
       
   243     StaticPath<SmartDigraph> p = bf.negativeCycle();
       
   244     check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
       
   245           "Wrong negative cycle.");
       
   246   }
       
   247  
       
   248   length[a2] = 0;
       
   249   
       
   250   {
       
   251     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
       
   252     bf.run(n1);
       
   253     check(bf.negativeCycle().empty(),
       
   254           "Negative cycle should not be found.");
       
   255   }
       
   256   
       
   257   length[gr.addArc(n1, n3)] = 5;
       
   258   length[gr.addArc(n4, n3)] = 1;
       
   259   length[gr.addArc(n2, n4)] = 2;
       
   260   length[gr.addArc(n3, n2)] = -4;
       
   261   
       
   262   {
       
   263     BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
       
   264     bf.init();
       
   265     bf.addSource(n1);
       
   266     for (int i = 0; i < 4; ++i) {
       
   267       check(bf.negativeCycle().empty(),
       
   268             "Negative cycle should not be found.");
       
   269       bf.processNextRound();
       
   270     }
       
   271     StaticPath<SmartDigraph> p = bf.negativeCycle();
       
   272     check(p.length() == 3, "Wrong negative cycle.");
       
   273     check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
       
   274           "Wrong negative cycle.");
       
   275   }
       
   276 }
       
   277 
   223 int main() {
   278 int main() {
   224   checkBellmanFord<ListDigraph, int>();
   279   checkBellmanFord<ListDigraph, int>();
   225   checkBellmanFord<SmartDigraph, double>();
   280   checkBellmanFord<SmartDigraph, double>();
       
   281   checkBellmanFordNegativeCycle();
   226   return 0;
   282   return 0;
   227 }
   283 }