1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
95 b = const_bf_test.reached(t); |
95 b = const_bf_test.reached(t); |
96 d = const_bf_test.distMap(); |
96 d = const_bf_test.distMap(); |
97 p = const_bf_test.predMap(); |
97 p = const_bf_test.predMap(); |
98 pp = const_bf_test.path(t); |
98 pp = const_bf_test.path(t); |
99 pp = const_bf_test.negativeCycle(); |
99 pp = const_bf_test.negativeCycle(); |
100 |
100 |
101 for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {} |
101 for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {} |
102 } |
102 } |
103 { |
103 { |
104 BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
104 BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> > |
105 ::SetDistMap<concepts::ReadWriteMap<Node,Value> > |
105 ::SetDistMap<concepts::ReadWriteMap<Node,Value> > |
108 ::Create bf_test(gr,length); |
108 ::Create bf_test(gr,length); |
109 |
109 |
110 LengthMap length_map; |
110 LengthMap length_map; |
111 concepts::ReadWriteMap<Node,Arc> pred_map; |
111 concepts::ReadWriteMap<Node,Arc> pred_map; |
112 concepts::ReadWriteMap<Node,Value> dist_map; |
112 concepts::ReadWriteMap<Node,Value> dist_map; |
113 |
113 |
114 bf_test |
114 bf_test |
115 .lengthMap(length_map) |
115 .lengthMap(length_map) |
116 .predMap(pred_map) |
116 .predMap(pred_map) |
117 .distMap(dist_map); |
117 .distMap(dist_map); |
118 |
118 |
187 check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path."); |
187 check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path."); |
188 check(p.length() == 3, "path() found a wrong path."); |
188 check(p.length() == 3, "path() found a wrong path."); |
189 check(checkPath(gr, p), "path() found a wrong path."); |
189 check(checkPath(gr, p), "path() found a wrong path."); |
190 check(pathSource(gr, p) == s, "path() found a wrong path."); |
190 check(pathSource(gr, p) == s, "path() found a wrong path."); |
191 check(pathTarget(gr, p) == t, "path() found a wrong path."); |
191 check(pathTarget(gr, p) == t, "path() found a wrong path."); |
192 |
192 |
193 ListPath<Digraph> path; |
193 ListPath<Digraph> path; |
194 Value dist; |
194 Value dist; |
195 bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t); |
195 bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t); |
196 |
196 |
197 check(reached && dist == -1, "Bellman-Ford found a wrong path."); |
197 check(reached && dist == -1, "Bellman-Ford found a wrong path."); |
226 void checkBellmanFordNegativeCycle() { |
226 void checkBellmanFordNegativeCycle() { |
227 DIGRAPH_TYPEDEFS(SmartDigraph); |
227 DIGRAPH_TYPEDEFS(SmartDigraph); |
228 |
228 |
229 SmartDigraph gr; |
229 SmartDigraph gr; |
230 IntArcMap length(gr); |
230 IntArcMap length(gr); |
231 |
231 |
232 Node n1 = gr.addNode(); |
232 Node n1 = gr.addNode(); |
233 Node n2 = gr.addNode(); |
233 Node n2 = gr.addNode(); |
234 Node n3 = gr.addNode(); |
234 Node n3 = gr.addNode(); |
235 Node n4 = gr.addNode(); |
235 Node n4 = gr.addNode(); |
236 |
236 |
237 Arc a1 = gr.addArc(n1, n2); |
237 Arc a1 = gr.addArc(n1, n2); |
238 Arc a2 = gr.addArc(n2, n2); |
238 Arc a2 = gr.addArc(n2, n2); |
239 |
239 |
240 length[a1] = 2; |
240 length[a1] = 2; |
241 length[a2] = -1; |
241 length[a2] = -1; |
242 |
242 |
243 { |
243 { |
244 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); |
244 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); |
245 bf.run(n1); |
245 bf.run(n1); |
246 StaticPath<SmartDigraph> p = bf.negativeCycle(); |
246 StaticPath<SmartDigraph> p = bf.negativeCycle(); |
247 check(p.length() == 1 && p.front() == p.back() && p.front() == a2, |
247 check(p.length() == 1 && p.front() == p.back() && p.front() == a2, |
248 "Wrong negative cycle."); |
248 "Wrong negative cycle."); |
249 } |
249 } |
250 |
250 |
251 length[a2] = 0; |
251 length[a2] = 0; |
252 |
252 |
253 { |
253 { |
254 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); |
254 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); |
255 bf.run(n1); |
255 bf.run(n1); |
256 check(bf.negativeCycle().empty(), |
256 check(bf.negativeCycle().empty(), |
257 "Negative cycle should not be found."); |
257 "Negative cycle should not be found."); |
258 } |
258 } |
259 |
259 |
260 length[gr.addArc(n1, n3)] = 5; |
260 length[gr.addArc(n1, n3)] = 5; |
261 length[gr.addArc(n4, n3)] = 1; |
261 length[gr.addArc(n4, n3)] = 1; |
262 length[gr.addArc(n2, n4)] = 2; |
262 length[gr.addArc(n2, n4)] = 2; |
263 length[gr.addArc(n3, n2)] = -4; |
263 length[gr.addArc(n3, n2)] = -4; |
264 |
264 |
265 { |
265 { |
266 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); |
266 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); |
267 bf.init(); |
267 bf.init(); |
268 bf.addSource(n1); |
268 bf.addSource(n1); |
269 for (int i = 0; i < 4; ++i) { |
269 for (int i = 0; i < 4; ++i) { |