Changeset 838:4e3484a2e90c in lemon
 Timestamp:
 11/18/09 14:22:52 (15 years ago)
 Branch:
 default
 Parents:
 836:8ddb7deabab9 (diff), 837:1870cfd14fb6 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

test/bellman_ford_test.cc
r828 r838 66 66 Arc e; 67 67 Value l; 68 int k ;68 int k=3; 69 69 bool b; 70 70 BF::DistMap d(gr); 
test/bellman_ford_test.cc
r837 r838 97 97 p = const_bf_test.predMap(); 98 98 pp = const_bf_test.path(t); 99 pp = const_bf_test.negativeCycle(); 99 100 100 101 for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {} … … 133 134 b = bf_test.reached(t); 134 135 pp = bf_test.path(t); 136 pp = bf_test.negativeCycle(); 135 137 } 136 138 } … … 221 223 } 222 224 225 void checkBellmanFordNegativeCycle() { 226 DIGRAPH_TYPEDEFS(SmartDigraph); 227 228 SmartDigraph gr; 229 IntArcMap length(gr); 230 231 Node n1 = gr.addNode(); 232 Node n2 = gr.addNode(); 233 Node n3 = gr.addNode(); 234 Node n4 = gr.addNode(); 235 236 Arc a1 = gr.addArc(n1, n2); 237 Arc a2 = gr.addArc(n2, n2); 238 239 length[a1] = 2; 240 length[a2] = 1; 241 242 { 243 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); 244 bf.run(n1); 245 StaticPath<SmartDigraph> p = bf.negativeCycle(); 246 check(p.length() == 1 && p.front() == p.back() && p.front() == a2, 247 "Wrong negative cycle."); 248 } 249 250 length[a2] = 0; 251 252 { 253 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); 254 bf.run(n1); 255 check(bf.negativeCycle().empty(), 256 "Negative cycle should not be found."); 257 } 258 259 length[gr.addArc(n1, n3)] = 5; 260 length[gr.addArc(n4, n3)] = 1; 261 length[gr.addArc(n2, n4)] = 2; 262 length[gr.addArc(n3, n2)] = 4; 263 264 { 265 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); 266 bf.init(); 267 bf.addSource(n1); 268 for (int i = 0; i < 4; ++i) { 269 check(bf.negativeCycle().empty(), 270 "Negative cycle should not be found."); 271 bf.processNextRound(); 272 } 273 StaticPath<SmartDigraph> p = bf.negativeCycle(); 274 check(p.length() == 3, "Wrong negative cycle."); 275 check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == 1, 276 "Wrong negative cycle."); 277 } 278 } 279 223 280 int main() { 224 281 checkBellmanFord<ListDigraph, int>(); 225 282 checkBellmanFord<SmartDigraph, double>(); 283 checkBellmanFordNegativeCycle(); 226 284 return 0; 227 285 }
Note: See TracChangeset
for help on using the changeset viewer.