Changeset 746:75325dfccf38 in lemon for test/bellman_ford_test.cc
 Timestamp:
 08/03/09 00:54:04 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/bellman_ford_test.cc
r745 r746 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 278 int main() { 224 279 checkBellmanFord<ListDigraph, int>(); 225 280 checkBellmanFord<SmartDigraph, double>(); 281 checkBellmanFordNegativeCycle(); 226 282 return 0; 227 283 }
Note: See TracChangeset
for help on using the changeset viewer.