203 arcMap("length", length). |
203 arcMap("length", length). |
204 node("source", s). |
204 node("source", s). |
205 node("target", t). |
205 node("target", t). |
206 run(); |
206 run(); |
207 |
207 |
208 // Find 2 paths |
208 // Check run() |
209 { |
209 { |
210 Suurballe<ListDigraph> suurballe(digraph, length); |
210 Suurballe<ListDigraph> suurballe(digraph, length); |
|
211 |
|
212 // Find 2 paths |
211 check(suurballe.run(s, t) == 2, "Wrong number of paths"); |
213 check(suurballe.run(s, t) == 2, "Wrong number of paths"); |
212 check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), |
214 check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), |
213 "The flow is not feasible"); |
215 "The flow is not feasible"); |
214 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
216 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
215 check(checkOptimality(digraph, length, suurballe.flowMap(), |
217 check(checkOptimality(digraph, length, suurballe.flowMap(), |
216 suurballe.potentialMap()), |
218 suurballe.potentialMap()), |
217 "Wrong potentials"); |
219 "Wrong potentials"); |
218 for (int i = 0; i < suurballe.pathNum(); ++i) |
220 for (int i = 0; i < suurballe.pathNum(); ++i) |
219 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
221 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
220 } |
222 |
221 |
223 // Find 3 paths |
222 // Find 3 paths |
|
223 { |
|
224 Suurballe<ListDigraph> suurballe(digraph, length); |
|
225 check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); |
224 check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); |
226 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), |
225 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), |
227 "The flow is not feasible"); |
226 "The flow is not feasible"); |
228 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
227 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
229 check(checkOptimality(digraph, length, suurballe.flowMap(), |
228 check(checkOptimality(digraph, length, suurballe.flowMap(), |
230 suurballe.potentialMap()), |
229 suurballe.potentialMap()), |
231 "Wrong potentials"); |
230 "Wrong potentials"); |
232 for (int i = 0; i < suurballe.pathNum(); ++i) |
231 for (int i = 0; i < suurballe.pathNum(); ++i) |
233 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
232 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
234 } |
233 |
235 |
234 // Find 5 paths (only 3 can be found) |
236 // Find 5 paths (only 3 can be found) |
|
237 { |
|
238 Suurballe<ListDigraph> suurballe(digraph, length); |
|
239 check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); |
235 check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); |
240 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), |
236 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), |
241 "The flow is not feasible"); |
237 "The flow is not feasible"); |
242 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
238 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
243 check(checkOptimality(digraph, length, suurballe.flowMap(), |
239 check(checkOptimality(digraph, length, suurballe.flowMap(), |
244 suurballe.potentialMap()), |
240 suurballe.potentialMap()), |
245 "Wrong potentials"); |
241 "Wrong potentials"); |
246 for (int i = 0; i < suurballe.pathNum(); ++i) |
242 for (int i = 0; i < suurballe.pathNum(); ++i) |
247 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
243 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
248 } |
244 } |
|
245 |
|
246 // Check fullInit() + start() |
|
247 { |
|
248 Suurballe<ListDigraph> suurballe(digraph, length); |
|
249 suurballe.fullInit(s); |
|
250 |
|
251 // Find 2 paths |
|
252 check(suurballe.start(t) == 2, "Wrong number of paths"); |
|
253 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
|
254 |
|
255 // Find 3 paths |
|
256 check(suurballe.start(t, 3) == 3, "Wrong number of paths"); |
|
257 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
|
258 |
|
259 // Find 5 paths (only 3 can be found) |
|
260 check(suurballe.start(t, 5) == 3, "Wrong number of paths"); |
|
261 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
|
262 } |
249 |
263 |
250 return 0; |
264 return 0; |
251 } |
265 } |