r948:9f6ed854d409
Tue, 02 Mar 2010 10:27:47
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -202,50 +202,64 @@ |
| 202 | 202 |
DigraphReader<ListDigraph>(digraph, input). |
| 203 | 203 |
arcMap("length", length).
|
| 204 | 204 |
node("source", s).
|
| 205 | 205 |
node("target", t).
|
| 206 | 206 |
run(); |
| 207 | 207 |
|
| 208 |
// |
|
| 208 |
// Check run() |
|
| 209 | 209 |
{
|
| 210 | 210 |
Suurballe<ListDigraph> suurballe(digraph, length); |
| 211 |
|
|
| 212 |
// Find 2 paths |
|
| 211 | 213 |
check(suurballe.run(s, t) == 2, "Wrong number of paths"); |
| 212 | 214 |
check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), |
| 213 | 215 |
"The flow is not feasible"); |
| 214 | 216 |
check(suurballe.totalLength() == 510, "The flow is not optimal"); |
| 215 | 217 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
| 216 | 218 |
suurballe.potentialMap()), |
| 217 | 219 |
"Wrong potentials"); |
| 218 | 220 |
for (int i = 0; i < suurballe.pathNum(); ++i) |
| 219 | 221 |
check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
| 220 |
} |
|
| 221 |
|
|
| 222 |
// Find 3 paths |
|
| 223 |
{
|
|
| 224 |
|
|
| 222 |
|
|
| 223 |
// Find 3 paths |
|
| 225 | 224 |
check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); |
| 226 | 225 |
check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), |
| 227 | 226 |
"The flow is not feasible"); |
| 228 | 227 |
check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
| 229 | 228 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
| 230 | 229 |
suurballe.potentialMap()), |
| 231 | 230 |
"Wrong potentials"); |
| 232 | 231 |
for (int i = 0; i < suurballe.pathNum(); ++i) |
| 233 | 232 |
check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); |
| 234 |
} |
|
| 235 |
|
|
| 236 |
// Find 5 paths (only 3 can be found) |
|
| 237 |
{
|
|
| 238 |
|
|
| 233 |
|
|
| 234 |
// Find 5 paths (only 3 can be found) |
|
| 239 | 235 |
check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); |
| 240 | 236 |
check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), |
| 241 | 237 |
"The flow is not feasible"); |
| 242 | 238 |
check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
| 243 | 239 |
check(checkOptimality(digraph, length, suurballe.flowMap(), |
| 244 | 240 |
suurballe.potentialMap()), |
| 245 | 241 |
"Wrong potentials"); |
| 246 | 242 |
for (int i = 0; i < suurballe.pathNum(); ++i) |
| 247 | 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 | 264 |
return 0; |
| 251 | 265 |
} |
0 comments (0 inline)