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 } |