1// Copyright ©2014 The Gonum Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5package testgraphs 6 7import ( 8 "fmt" 9 "math" 10 11 "gonum.org/v1/gonum/graph" 12 "gonum.org/v1/gonum/graph/simple" 13) 14 15func init() { 16 for _, test := range ShortestPathTests { 17 if len(test.WantPaths) != 1 && test.HasUniquePath { 18 panic(fmt.Sprintf("%q: bad shortest path test: non-unique paths marked unique", test.Name)) 19 } 20 } 21} 22 23// ShortestPathTests are graphs used to test the static shortest path routines in path: BellmanFord, 24// DijkstraAllPaths, DijkstraFrom, FloydWarshall and Johnson, and the static degenerate case for the 25// dynamic shortest path routine in path/dynamic: DStarLite. 26var ShortestPathTests = []struct { 27 Name string 28 Graph func() graph.WeightedEdgeAdder 29 Edges []simple.WeightedEdge 30 HasNegativeWeight bool 31 HasNegativeCycle bool 32 33 Query simple.Edge 34 Weight float64 35 WantPaths [][]int64 36 HasUniquePath bool 37 38 NoPathFor simple.Edge 39}{ 40 // Positive weighted graphs. 41 { 42 Name: "empty directed", 43 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 44 45 Query: simple.Edge{F: simple.Node(0), T: simple.Node(1)}, 46 Weight: math.Inf(1), 47 48 NoPathFor: simple.Edge{F: simple.Node(0), T: simple.Node(1)}, 49 }, 50 { 51 Name: "empty undirected", 52 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) }, 53 54 Query: simple.Edge{F: simple.Node(0), T: simple.Node(1)}, 55 Weight: math.Inf(1), 56 57 NoPathFor: simple.Edge{F: simple.Node(0), T: simple.Node(1)}, 58 }, 59 { 60 Name: "one edge directed", 61 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 62 Edges: []simple.WeightedEdge{ 63 {F: simple.Node(0), T: simple.Node(1), W: 1}, 64 }, 65 66 Query: simple.Edge{F: simple.Node(0), T: simple.Node(1)}, 67 Weight: 1, 68 WantPaths: [][]int64{ 69 {0, 1}, 70 }, 71 HasUniquePath: true, 72 73 NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)}, 74 }, 75 { 76 Name: "one edge self directed", 77 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 78 Edges: []simple.WeightedEdge{ 79 {F: simple.Node(0), T: simple.Node(1), W: 1}, 80 }, 81 82 Query: simple.Edge{F: simple.Node(0), T: simple.Node(0)}, 83 Weight: 0, 84 WantPaths: [][]int64{ 85 {0}, 86 }, 87 HasUniquePath: true, 88 89 NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)}, 90 }, 91 { 92 Name: "one edge undirected", 93 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) }, 94 Edges: []simple.WeightedEdge{ 95 {F: simple.Node(0), T: simple.Node(1), W: 1}, 96 }, 97 98 Query: simple.Edge{F: simple.Node(0), T: simple.Node(1)}, 99 Weight: 1, 100 WantPaths: [][]int64{ 101 {0, 1}, 102 }, 103 HasUniquePath: true, 104 105 NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)}, 106 }, 107 { 108 Name: "two paths directed", 109 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 110 Edges: []simple.WeightedEdge{ 111 {F: simple.Node(0), T: simple.Node(2), W: 2}, 112 {F: simple.Node(0), T: simple.Node(1), W: 1}, 113 {F: simple.Node(1), T: simple.Node(2), W: 1}, 114 }, 115 116 Query: simple.Edge{F: simple.Node(0), T: simple.Node(2)}, 117 Weight: 2, 118 WantPaths: [][]int64{ 119 {0, 1, 2}, 120 {0, 2}, 121 }, 122 HasUniquePath: false, 123 124 NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(1)}, 125 }, 126 { 127 Name: "two paths undirected", 128 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) }, 129 Edges: []simple.WeightedEdge{ 130 {F: simple.Node(0), T: simple.Node(2), W: 2}, 131 {F: simple.Node(0), T: simple.Node(1), W: 1}, 132 {F: simple.Node(1), T: simple.Node(2), W: 1}, 133 }, 134 135 Query: simple.Edge{F: simple.Node(0), T: simple.Node(2)}, 136 Weight: 2, 137 WantPaths: [][]int64{ 138 {0, 1, 2}, 139 {0, 2}, 140 }, 141 HasUniquePath: false, 142 143 NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(4)}, 144 }, 145 { 146 Name: "confounding paths directed", 147 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 148 Edges: []simple.WeightedEdge{ 149 // Add a path from 0->5 of weight 4 150 {F: simple.Node(0), T: simple.Node(1), W: 1}, 151 {F: simple.Node(1), T: simple.Node(2), W: 1}, 152 {F: simple.Node(2), T: simple.Node(3), W: 1}, 153 {F: simple.Node(3), T: simple.Node(5), W: 1}, 154 155 // Add direct edge to goal of weight 4 156 {F: simple.Node(0), T: simple.Node(5), W: 4}, 157 158 // Add edge to a node that's still optimal 159 {F: simple.Node(0), T: simple.Node(2), W: 2}, 160 161 // Add edge to 3 that's overpriced 162 {F: simple.Node(0), T: simple.Node(3), W: 4}, 163 164 // Add very cheap edge to 4 which is a dead end 165 {F: simple.Node(0), T: simple.Node(4), W: 0.25}, 166 }, 167 168 Query: simple.Edge{F: simple.Node(0), T: simple.Node(5)}, 169 Weight: 4, 170 WantPaths: [][]int64{ 171 {0, 1, 2, 3, 5}, 172 {0, 2, 3, 5}, 173 {0, 5}, 174 }, 175 HasUniquePath: false, 176 177 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 178 }, 179 { 180 Name: "confounding paths undirected", 181 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) }, 182 Edges: []simple.WeightedEdge{ 183 // Add a path from 0->5 of weight 4 184 {F: simple.Node(0), T: simple.Node(1), W: 1}, 185 {F: simple.Node(1), T: simple.Node(2), W: 1}, 186 {F: simple.Node(2), T: simple.Node(3), W: 1}, 187 {F: simple.Node(3), T: simple.Node(5), W: 1}, 188 189 // Add direct edge to goal of weight 4 190 {F: simple.Node(0), T: simple.Node(5), W: 4}, 191 192 // Add edge to a node that's still optimal 193 {F: simple.Node(0), T: simple.Node(2), W: 2}, 194 195 // Add edge to 3 that's overpriced 196 {F: simple.Node(0), T: simple.Node(3), W: 4}, 197 198 // Add very cheap edge to 4 which is a dead end 199 {F: simple.Node(0), T: simple.Node(4), W: 0.25}, 200 }, 201 202 Query: simple.Edge{F: simple.Node(0), T: simple.Node(5)}, 203 Weight: 4, 204 WantPaths: [][]int64{ 205 {0, 1, 2, 3, 5}, 206 {0, 2, 3, 5}, 207 {0, 5}, 208 }, 209 HasUniquePath: false, 210 211 NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(6)}, 212 }, 213 { 214 Name: "confounding paths directed 2-step", 215 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 216 Edges: []simple.WeightedEdge{ 217 // Add a path from 0->5 of weight 4 218 {F: simple.Node(0), T: simple.Node(1), W: 1}, 219 {F: simple.Node(1), T: simple.Node(2), W: 1}, 220 {F: simple.Node(2), T: simple.Node(3), W: 1}, 221 {F: simple.Node(3), T: simple.Node(5), W: 1}, 222 223 // Add two step path to goal of weight 4 224 {F: simple.Node(0), T: simple.Node(6), W: 2}, 225 {F: simple.Node(6), T: simple.Node(5), W: 2}, 226 227 // Add edge to a node that's still optimal 228 {F: simple.Node(0), T: simple.Node(2), W: 2}, 229 230 // Add edge to 3 that's overpriced 231 {F: simple.Node(0), T: simple.Node(3), W: 4}, 232 233 // Add very cheap edge to 4 which is a dead end 234 {F: simple.Node(0), T: simple.Node(4), W: 0.25}, 235 }, 236 237 Query: simple.Edge{F: simple.Node(0), T: simple.Node(5)}, 238 Weight: 4, 239 WantPaths: [][]int64{ 240 {0, 1, 2, 3, 5}, 241 {0, 2, 3, 5}, 242 {0, 6, 5}, 243 }, 244 HasUniquePath: false, 245 246 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 247 }, 248 { 249 Name: "confounding paths undirected 2-step", 250 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) }, 251 Edges: []simple.WeightedEdge{ 252 // Add a path from 0->5 of weight 4 253 {F: simple.Node(0), T: simple.Node(1), W: 1}, 254 {F: simple.Node(1), T: simple.Node(2), W: 1}, 255 {F: simple.Node(2), T: simple.Node(3), W: 1}, 256 {F: simple.Node(3), T: simple.Node(5), W: 1}, 257 258 // Add two step path to goal of weight 4 259 {F: simple.Node(0), T: simple.Node(6), W: 2}, 260 {F: simple.Node(6), T: simple.Node(5), W: 2}, 261 262 // Add edge to a node that's still optimal 263 {F: simple.Node(0), T: simple.Node(2), W: 2}, 264 265 // Add edge to 3 that's overpriced 266 {F: simple.Node(0), T: simple.Node(3), W: 4}, 267 268 // Add very cheap edge to 4 which is a dead end 269 {F: simple.Node(0), T: simple.Node(4), W: 0.25}, 270 }, 271 272 Query: simple.Edge{F: simple.Node(0), T: simple.Node(5)}, 273 Weight: 4, 274 WantPaths: [][]int64{ 275 {0, 1, 2, 3, 5}, 276 {0, 2, 3, 5}, 277 {0, 6, 5}, 278 }, 279 HasUniquePath: false, 280 281 NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(7)}, 282 }, 283 { 284 Name: "zero-weight cycle directed", 285 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 286 Edges: []simple.WeightedEdge{ 287 // Add a path from 0->4 of weight 4 288 {F: simple.Node(0), T: simple.Node(1), W: 1}, 289 {F: simple.Node(1), T: simple.Node(2), W: 1}, 290 {F: simple.Node(2), T: simple.Node(3), W: 1}, 291 {F: simple.Node(3), T: simple.Node(4), W: 1}, 292 293 // Add a zero-weight cycle. 294 {F: simple.Node(1), T: simple.Node(5), W: 0}, 295 {F: simple.Node(5), T: simple.Node(1), W: 0}, 296 }, 297 298 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 299 Weight: 4, 300 WantPaths: [][]int64{ 301 {0, 1, 2, 3, 4}, 302 }, 303 HasUniquePath: false, 304 305 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 306 }, 307 { 308 Name: "zero-weight cycle^2 directed", 309 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 310 Edges: []simple.WeightedEdge{ 311 // Add a path from 0->4 of weight 4 312 {F: simple.Node(0), T: simple.Node(1), W: 1}, 313 {F: simple.Node(1), T: simple.Node(2), W: 1}, 314 {F: simple.Node(2), T: simple.Node(3), W: 1}, 315 {F: simple.Node(3), T: simple.Node(4), W: 1}, 316 317 // Add a zero-weight cycle. 318 {F: simple.Node(1), T: simple.Node(5), W: 0}, 319 {F: simple.Node(5), T: simple.Node(1), W: 0}, 320 // With its own zero-weight cycle. 321 {F: simple.Node(5), T: simple.Node(6), W: 0}, 322 {F: simple.Node(6), T: simple.Node(5), W: 0}, 323 }, 324 325 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 326 Weight: 4, 327 WantPaths: [][]int64{ 328 {0, 1, 2, 3, 4}, 329 }, 330 HasUniquePath: false, 331 332 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 333 }, 334 { 335 Name: "zero-weight cycle^2 confounding directed", 336 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 337 Edges: []simple.WeightedEdge{ 338 // Add a path from 0->4 of weight 4 339 {F: simple.Node(0), T: simple.Node(1), W: 1}, 340 {F: simple.Node(1), T: simple.Node(2), W: 1}, 341 {F: simple.Node(2), T: simple.Node(3), W: 1}, 342 {F: simple.Node(3), T: simple.Node(4), W: 1}, 343 344 // Add a zero-weight cycle. 345 {F: simple.Node(1), T: simple.Node(5), W: 0}, 346 {F: simple.Node(5), T: simple.Node(1), W: 0}, 347 // With its own zero-weight cycle. 348 {F: simple.Node(5), T: simple.Node(6), W: 0}, 349 {F: simple.Node(6), T: simple.Node(5), W: 0}, 350 // But leading to the target. 351 {F: simple.Node(5), T: simple.Node(4), W: 3}, 352 }, 353 354 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 355 Weight: 4, 356 WantPaths: [][]int64{ 357 {0, 1, 2, 3, 4}, 358 {0, 1, 5, 4}, 359 }, 360 HasUniquePath: false, 361 362 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 363 }, 364 { 365 Name: "zero-weight cycle^3 directed", 366 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 367 Edges: []simple.WeightedEdge{ 368 // Add a path from 0->4 of weight 4 369 {F: simple.Node(0), T: simple.Node(1), W: 1}, 370 {F: simple.Node(1), T: simple.Node(2), W: 1}, 371 {F: simple.Node(2), T: simple.Node(3), W: 1}, 372 {F: simple.Node(3), T: simple.Node(4), W: 1}, 373 374 // Add a zero-weight cycle. 375 {F: simple.Node(1), T: simple.Node(5), W: 0}, 376 {F: simple.Node(5), T: simple.Node(1), W: 0}, 377 // With its own zero-weight cycle. 378 {F: simple.Node(5), T: simple.Node(6), W: 0}, 379 {F: simple.Node(6), T: simple.Node(5), W: 0}, 380 // With its own zero-weight cycle. 381 {F: simple.Node(6), T: simple.Node(7), W: 0}, 382 {F: simple.Node(7), T: simple.Node(6), W: 0}, 383 }, 384 385 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 386 Weight: 4, 387 WantPaths: [][]int64{ 388 {0, 1, 2, 3, 4}, 389 }, 390 HasUniquePath: false, 391 392 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 393 }, 394 { 395 Name: "zero-weight 3·cycle^2 confounding directed", 396 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 397 Edges: []simple.WeightedEdge{ 398 // Add a path from 0->4 of weight 4 399 {F: simple.Node(0), T: simple.Node(1), W: 1}, 400 {F: simple.Node(1), T: simple.Node(2), W: 1}, 401 {F: simple.Node(2), T: simple.Node(3), W: 1}, 402 {F: simple.Node(3), T: simple.Node(4), W: 1}, 403 404 // Add a zero-weight cycle. 405 {F: simple.Node(1), T: simple.Node(5), W: 0}, 406 {F: simple.Node(5), T: simple.Node(1), W: 0}, 407 // With 3 of its own zero-weight cycles. 408 {F: simple.Node(5), T: simple.Node(6), W: 0}, 409 {F: simple.Node(6), T: simple.Node(5), W: 0}, 410 {F: simple.Node(5), T: simple.Node(7), W: 0}, 411 {F: simple.Node(7), T: simple.Node(5), W: 0}, 412 // Each leading to the target. 413 {F: simple.Node(5), T: simple.Node(4), W: 3}, 414 {F: simple.Node(6), T: simple.Node(4), W: 3}, 415 {F: simple.Node(7), T: simple.Node(4), W: 3}, 416 }, 417 418 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 419 Weight: 4, 420 WantPaths: [][]int64{ 421 {0, 1, 2, 3, 4}, 422 {0, 1, 5, 4}, 423 {0, 1, 5, 6, 4}, 424 {0, 1, 5, 7, 4}, 425 }, 426 HasUniquePath: false, 427 428 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 429 }, 430 { 431 Name: "zero-weight reversed 3·cycle^2 confounding directed", 432 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 433 Edges: []simple.WeightedEdge{ 434 // Add a path from 0->4 of weight 4 435 {F: simple.Node(0), T: simple.Node(1), W: 1}, 436 {F: simple.Node(1), T: simple.Node(2), W: 1}, 437 {F: simple.Node(2), T: simple.Node(3), W: 1}, 438 {F: simple.Node(3), T: simple.Node(4), W: 1}, 439 440 // Add a zero-weight cycle. 441 {F: simple.Node(3), T: simple.Node(5), W: 0}, 442 {F: simple.Node(5), T: simple.Node(3), W: 0}, 443 // With 3 of its own zero-weight cycles. 444 {F: simple.Node(5), T: simple.Node(6), W: 0}, 445 {F: simple.Node(6), T: simple.Node(5), W: 0}, 446 {F: simple.Node(5), T: simple.Node(7), W: 0}, 447 {F: simple.Node(7), T: simple.Node(5), W: 0}, 448 // Each leading from the source. 449 {F: simple.Node(0), T: simple.Node(5), W: 3}, 450 {F: simple.Node(0), T: simple.Node(6), W: 3}, 451 {F: simple.Node(0), T: simple.Node(7), W: 3}, 452 }, 453 454 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 455 Weight: 4, 456 WantPaths: [][]int64{ 457 {0, 1, 2, 3, 4}, 458 {0, 5, 3, 4}, 459 {0, 6, 5, 3, 4}, 460 {0, 7, 5, 3, 4}, 461 }, 462 HasUniquePath: false, 463 464 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 465 }, 466 { 467 Name: "zero-weight |V|·cycle^(n/|V|) directed", 468 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 469 Edges: func() []simple.WeightedEdge { 470 e := []simple.WeightedEdge{ 471 // Add a path from 0->4 of weight 4 472 {F: simple.Node(0), T: simple.Node(1), W: 1}, 473 {F: simple.Node(1), T: simple.Node(2), W: 1}, 474 {F: simple.Node(2), T: simple.Node(3), W: 1}, 475 {F: simple.Node(3), T: simple.Node(4), W: 1}, 476 } 477 next := len(e) + 1 478 479 // Add n zero-weight cycles. 480 const n = 100 481 for i := 0; i < n; i++ { 482 e = append(e, 483 simple.WeightedEdge{F: simple.Node(next + i), T: simple.Node(i), W: 0}, 484 simple.WeightedEdge{F: simple.Node(i), T: simple.Node(next + i), W: 0}, 485 ) 486 } 487 return e 488 }(), 489 490 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 491 Weight: 4, 492 WantPaths: [][]int64{ 493 {0, 1, 2, 3, 4}, 494 }, 495 HasUniquePath: false, 496 497 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 498 }, 499 { 500 Name: "zero-weight n·cycle directed", 501 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 502 Edges: func() []simple.WeightedEdge { 503 e := []simple.WeightedEdge{ 504 // Add a path from 0->4 of weight 4 505 {F: simple.Node(0), T: simple.Node(1), W: 1}, 506 {F: simple.Node(1), T: simple.Node(2), W: 1}, 507 {F: simple.Node(2), T: simple.Node(3), W: 1}, 508 {F: simple.Node(3), T: simple.Node(4), W: 1}, 509 } 510 next := len(e) + 1 511 512 // Add n zero-weight cycles. 513 const n = 100 514 for i := 0; i < n; i++ { 515 e = append(e, 516 simple.WeightedEdge{F: simple.Node(next + i), T: simple.Node(1), W: 0}, 517 simple.WeightedEdge{F: simple.Node(1), T: simple.Node(next + i), W: 0}, 518 ) 519 } 520 return e 521 }(), 522 523 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 524 Weight: 4, 525 WantPaths: [][]int64{ 526 {0, 1, 2, 3, 4}, 527 }, 528 HasUniquePath: false, 529 530 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 531 }, 532 { 533 Name: "zero-weight bi-directional tree with single exit directed", 534 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 535 Edges: func() []simple.WeightedEdge { 536 e := []simple.WeightedEdge{ 537 // Add a path from 0->4 of weight 4 538 {F: simple.Node(0), T: simple.Node(1), W: 1}, 539 {F: simple.Node(1), T: simple.Node(2), W: 1}, 540 {F: simple.Node(2), T: simple.Node(3), W: 1}, 541 {F: simple.Node(3), T: simple.Node(4), W: 1}, 542 } 543 544 // Make a bi-directional tree rooted at node 2 with 545 // a single exit to node 4 and co-equal cost from 546 // 2 to 4. 547 const ( 548 depth = 4 549 branching = 4 550 ) 551 552 next := len(e) + 1 553 src := 2 554 var i, last int 555 for l := 0; l < depth; l++ { 556 for i = 0; i < branching; i++ { 557 last = next + i 558 e = append(e, simple.WeightedEdge{F: simple.Node(src), T: simple.Node(last), W: 0}) 559 e = append(e, simple.WeightedEdge{F: simple.Node(last), T: simple.Node(src), W: 0}) 560 } 561 src = next + 1 562 next += branching 563 } 564 e = append(e, simple.WeightedEdge{F: simple.Node(last), T: simple.Node(4), W: 2}) 565 return e 566 }(), 567 568 Query: simple.Edge{F: simple.Node(0), T: simple.Node(4)}, 569 Weight: 4, 570 WantPaths: [][]int64{ 571 {0, 1, 2, 3, 4}, 572 {0, 1, 2, 6, 10, 14, 20, 4}, 573 }, 574 HasUniquePath: false, 575 576 NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)}, 577 }, 578 579 // Negative weighted graphs. 580 { 581 Name: "one edge directed negative", 582 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 583 Edges: []simple.WeightedEdge{ 584 {F: simple.Node(0), T: simple.Node(1), W: -1}, 585 }, 586 HasNegativeWeight: true, 587 588 Query: simple.Edge{F: simple.Node(0), T: simple.Node(1)}, 589 Weight: -1, 590 WantPaths: [][]int64{ 591 {0, 1}, 592 }, 593 HasUniquePath: true, 594 595 NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)}, 596 }, 597 { 598 Name: "one edge undirected negative", 599 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) }, 600 Edges: []simple.WeightedEdge{ 601 {F: simple.Node(0), T: simple.Node(1), W: -1}, 602 }, 603 HasNegativeWeight: true, 604 HasNegativeCycle: true, 605 606 Query: simple.Edge{F: simple.Node(0), T: simple.Node(1)}, 607 }, 608 { 609 Name: "wp graph negative", // http://en.wikipedia.org/w/index.php?title=Johnson%27s_algorithm&oldid=564595231 610 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 611 Edges: []simple.WeightedEdge{ 612 {F: simple.Node('w'), T: simple.Node('z'), W: 2}, 613 {F: simple.Node('x'), T: simple.Node('w'), W: 6}, 614 {F: simple.Node('x'), T: simple.Node('y'), W: 3}, 615 {F: simple.Node('y'), T: simple.Node('w'), W: 4}, 616 {F: simple.Node('y'), T: simple.Node('z'), W: 5}, 617 {F: simple.Node('z'), T: simple.Node('x'), W: -7}, 618 {F: simple.Node('z'), T: simple.Node('y'), W: -3}, 619 }, 620 HasNegativeWeight: true, 621 622 Query: simple.Edge{F: simple.Node('z'), T: simple.Node('y')}, 623 Weight: -4, 624 WantPaths: [][]int64{ 625 {'z', 'x', 'y'}, 626 }, 627 HasUniquePath: true, 628 629 NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)}, 630 }, 631 { 632 Name: "roughgarden negative", 633 Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) }, 634 Edges: []simple.WeightedEdge{ 635 {F: simple.Node('a'), T: simple.Node('b'), W: -2}, 636 {F: simple.Node('b'), T: simple.Node('c'), W: -1}, 637 {F: simple.Node('c'), T: simple.Node('a'), W: 4}, 638 {F: simple.Node('c'), T: simple.Node('x'), W: 2}, 639 {F: simple.Node('c'), T: simple.Node('y'), W: -3}, 640 {F: simple.Node('z'), T: simple.Node('x'), W: 1}, 641 {F: simple.Node('z'), T: simple.Node('y'), W: -4}, 642 }, 643 HasNegativeWeight: true, 644 645 Query: simple.Edge{F: simple.Node('a'), T: simple.Node('y')}, 646 Weight: -6, 647 WantPaths: [][]int64{ 648 {'a', 'b', 'c', 'y'}, 649 }, 650 HasUniquePath: true, 651 652 NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)}, 653 }, 654} 655