graph/path: fix YenKShortestPaths
MODIFY
graph/path/yen_ksp.go
graph/path/yen_ksp.go
@@ -14,6 +14,9 @@ import (
// YenKShortestPaths returns the k-shortest loopless paths from s to t in g.
// YenKShortestPaths will panic if g contains a negative edge weight.
func YenKShortestPaths(g graph.Graph, k int, s, t graph.Node) [][]graph.Node {
+ // See https://en.wikipedia.org/wiki/Yen's_algorithm and
+ // the paper at https://doi.org/10.1090%2Fqam%2F253822.
+
_, isDirected := g.(graph.Directed)
yk := yenKSPAdjuster{
Graph: g,
@@ -38,7 +41,7 @@ func YenKShortestPaths(g graph.Graph, k int, s, t graph.Node) [][]graph.Node {
var pot []yenShortest
var root []graph.Node
for i := int64(1); i < int64(k); i++ {
- for n := 0; n < len(paths[i-1])-1; n++ {
+ for n := 0; n < len(paths[i-1])-2; n++ {
yk.reset()
spur := paths[i-1][n]

MODIFY
graph/path/yen_ksp_test.go
graph/path/yen_ksp_test.go
@@ -147,6 +147,30 @@ var yenShortestPathTests = []struct {
{-1, 2, 1},
},
},
+ {
+ name: "waterfall", // This is the failing case in gonum/gonum#1700.
+ graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
+ edges: []simple.WeightedEdge{
+ {F: simple.Node(0), T: simple.Node(1), W: 1},
+ {F: simple.Node(1), T: simple.Node(2), W: 1},
+ {F: simple.Node(1), T: simple.Node(3), W: 1},
+ {F: simple.Node(1), T: simple.Node(5), W: 1},
+ {F: simple.Node(2), T: simple.Node(4), W: 1},
+ {F: simple.Node(2), T: simple.Node(5), W: 1},
+ {F: simple.Node(3), T: simple.Node(6), W: 1},
+ {F: simple.Node(4), T: simple.Node(6), W: 1},
+ {F: simple.Node(5), T: simple.Node(6), W: 1},
+ {F: simple.Node(5), T: simple.Node(6), W: 1},
+ },
+ query: simple.Edge{F: simple.Node(0), T: simple.Node(6)},
+ k: 4,
+ wantPaths: [][]int64{
+ {0, 1, 3, 6},
+ {0, 1, 5, 6},
+ {0, 1, 2, 4, 6},
+ {0, 1, 2, 5, 6},
+ },
+ },
}
func bipartite(n int, weight, inc float64) []simple.WeightedEdge {

graph/path: fix YenKShortestPaths