graph/path: reduce allocations in path reconstructions
│ old.bench │ new.bench │
│ sec/op │ sec/op vs base │
ShortestAlts/AllTo_100×2|0.5(17)-8 12.380µ ± 9% 8.577µ ± 6% -30.72% (p=0.000 n=10)
ShortestAlts/AllTo_1000×2|0.5(51)-8 74.87µ ± 17% 47.66µ ± 1% -36.35% (p=0.000 n=10)
ShortestAlts/AllTo_100×4|0.25(53)-8 25.50µ ± 3% 15.35µ ± 3% -39.82% (p=0.000 n=10)
ShortestAlts/AllTo_1000×4|0.25(574)-8 556.5µ ± 5% 279.2µ ± 4% -49.83% (p=0.000 n=10)
ShortestAlts/AllTo_100×16|0.1(76)-8 35.79µ ± 9% 21.71µ ± 3% -39.35% (p=0.000 n=10)
ShortestAlts/AllTo_1000×16|0.1(822)-8 851.8µ ± 6% 400.5µ ± 6% -52.98% (p=0.000 n=10)
AllShortest/AllBetween_100×2|0.5(17)-8 12.482µ ± 6% 8.573µ ± 3% -31.32% (p=0.000 n=10)
AllShortest/AllBetween_1000×2|0.5(51)-8 80.74µ ± 2% 52.90µ ± 4% -34.48% (p=0.000 n=10)
AllShortest/AllBetween_100×4|0.25(53)-8 22.54µ ± 4% 16.17µ ± 4% -28.26% (p=0.000 n=10)
AllShortest/AllBetween_1000×4|0.25(574)-8 543.8µ ± 3% 326.7µ ± 5% -39.93% (p=0.000 n=10)
AllShortest/AllBetween_100×16|0.1(76)-8 31.21µ ± 1% 22.45µ ± 3% -28.07% (p=0.000 n=10)
AllShortest/AllBetween_1000×16|0.1(822)-8 678.4µ ± 1% 402.5µ ± 3% -40.67% (p=0.000 n=10)
ShortestAlts/AllToFunc_100×2|0.5(17)-8 5.892µ ± 2%
ShortestAlts/AllToFunc_1000×2|0.5(51)-8 40.81µ ± 2%
ShortestAlts/AllToFunc_100×4|0.25(53)-8 9.178µ ± 2%
ShortestAlts/AllToFunc_1000×4|0.25(574)-8 214.6µ ± 2%
ShortestAlts/AllToFunc_100×16|0.1(76)-8 12.62µ ± 3%
ShortestAlts/AllToFunc_1000×16|0.1(822)-8 310.7µ ± 3%
AllShortest/AllBetweenFunc_100×2|0.5(17)-8 5.713µ ± 1%
AllShortest/AllBetweenFunc_1000×2|0.5(51)-8 45.68µ ± 3%
AllShortest/AllBetweenFunc_100×4|0.25(53)-8 9.775µ ± 1%
AllShortest/AllBetweenFunc_1000×4|0.25(574)-8 245.2µ ± 5%
AllShortest/AllBetweenFunc_100×16|0.1(76)-8 13.76µ ± 1%
AllShortest/AllBetweenFunc_1000×16|0.1(822)-8 314.7µ ± 1%
geomean 82.87µ 43.03µ -38.14%
│ old.bench │ new.bench │
│ B/op │ B/op vs base │
ShortestAlts/AllTo_100×2|0.5(17)-8 14.148Ki ± 0% 9.727Ki ± 0% -31.25% (p=0.000 n=10)
ShortestAlts/AllTo_1000×2|0.5(51)-8 189.8Ki ± 0% 127.5Ki ± 0% -32.80% (p=0.000 n=10)
ShortestAlts/AllTo_100×4|0.25(53)-8 22.32Ki ± 0% 14.99Ki ± 0% -32.83% (p=0.000 n=10)
ShortestAlts/AllTo_1000×4|0.25(574)-8 1272.9Ki ± 0% 681.9Ki ± 0% -46.42% (p=0.000 n=10)
ShortestAlts/AllTo_100×16|0.1(76)-8 33.23Ki ± 0% 22.66Ki ± 0% -31.79% (p=0.000 n=10)
ShortestAlts/AllTo_1000×16|0.1(822)-8 1799.9Ki ± 0% 953.2Ki ± 0% -47.04% (p=0.000 n=10)
AllShortest/AllBetween_100×2|0.5(17)-8 13.039Ki ± 0% 8.617Ki ± 0% -33.91% (p=0.000 n=10)
AllShortest/AllBetween_1000×2|0.5(51)-8 181.5Ki ± 0% 119.3Ki ± 0% -34.29% (p=0.000 n=10)
AllShortest/AllBetween_100×4|0.25(53)-8 21.34Ki ± 0% 14.01Ki ± 0% -34.35% (p=0.000 n=10)
AllShortest/AllBetween_1000×4|0.25(574)-8 1264.8Ki ± 0% 673.8Ki ± 0% -46.72% (p=0.000 n=10)
AllShortest/AllBetween_100×16|0.1(76)-8 32.24Ki ± 0% 21.68Ki ± 0% -32.76% (p=0.000 n=10)
AllShortest/AllBetween_1000×16|0.1(822)-8 1791.8Ki ± 0% 945.1Ki ± 0% -47.25% (p=0.000 n=10)
ShortestAlts/AllToFunc_100×2|0.5(17)-8 6.922Ki ± 0%
ShortestAlts/AllToFunc_1000×2|0.5(51)-8 119.8Ki ± 0%
ShortestAlts/AllToFunc_100×4|0.25(53)-8 9.531Ki ± 0%
ShortestAlts/AllToFunc_1000×4|0.25(574)-8 611.1Ki ± 0%
ShortestAlts/AllToFunc_100×16|0.1(76)-8 13.12Ki ± 0%
ShortestAlts/AllToFunc_1000×16|0.1(822)-8 870.7Ki ± 0%
AllShortest/AllBetweenFunc_100×2|0.5(17)-8 5.812Ki ± 0%
AllShortest/AllBetweenFunc_1000×2|0.5(51)-8 111.5Ki ± 0%
AllShortest/AllBetweenFunc_100×4|0.25(53)-8 8.547Ki ± 0%
AllShortest/AllBetweenFunc_1000×4|0.25(574)-8 603.0Ki ± 0%
AllShortest/AllBetweenFunc_100×16|0.1(76)-8 12.14Ki ± 0%
AllShortest/AllBetweenFunc_1000×16|0.1(822)-8 862.6Ki ± 0%
geomean 126.5Ki 68.27Ki -37.99%
│ old.bench │ new.bench │
│ allocs/op │ allocs/op vs base │
ShortestAlts/AllTo_100×2|0.5(17)-8 141.00 ± 0% 94.00 ± 0% -33.33% (p=0.000 n=10)
ShortestAlts/AllTo_1000×2|0.5(51)-8 420.0 ± 0% 269.0 ± 0% -35.95% (p=0.000 n=10)
ShortestAlts/AllTo_100×4|0.25(53)-8 279.0 ± 0% 174.0 ± 0% -37.63% (p=0.000 n=10)
ShortestAlts/AllTo_1000×4|0.25(574)-8 2.888k ± 0% 1.741k ± 0% -39.72% (p=0.000 n=10)
ShortestAlts/AllTo_100×16|0.1(76)-8 395.0 ± 0% 244.0 ± 0% -38.23% (p=0.000 n=10)
ShortestAlts/AllTo_1000×16|0.1(822)-8 4.128k ± 0% 2.485k ± 0% -39.80% (p=0.000 n=10)
AllShortest/AllBetween_100×2|0.5(17)-8 136.00 ± 0% 89.00 ± 0% -34.56% (p=0.000 n=10)
AllShortest/AllBetween_1000×2|0.5(51)-8 415.0 ± 0% 264.0 ± 0% -36.39% (p=0.000 n=10)
AllShortest/AllBetween_100×4|0.25(53)-8 275.0 ± 0% 170.0 ± 0% -38.18% (p=0.000 n=10)
AllShortest/AllBetween_1000×4|0.25(574)-8 2.884k ± 0% 1.737k ± 0% -39.77% (p=0.000 n=10)
AllShortest/AllBetween_100×16|0.1(76)-8 391.0 ± 0% 240.0 ± 0% -38.62% (p=0.000 n=10)
AllShortest/AllBetween_1000×16|0.1(822)-8 4.124k ± 0% 2.481k ± 0% -39.84% (p=0.000 n=10)
ShortestAlts/AllToFunc_100×2|0.5(17)-8 71.00 ± 0%
ShortestAlts/AllToFunc_1000×2|0.5(51)-8 211.0 ± 0%
ShortestAlts/AllToFunc_100×4|0.25(53)-8 114.0 ± 0%
ShortestAlts/AllToFunc_1000×4|0.25(574)-8 1.156k ± 0%
ShortestAlts/AllToFunc_100×16|0.1(76)-8 160.0 ± 0%
ShortestAlts/AllToFunc_1000×16|0.1(822)-8 1.652k ± 0%
AllShortest/AllBetweenFunc_100×2|0.5(17)-8 66.00 ± 0%
AllShortest/AllBetweenFunc_1000×2|0.5(51)-8 206.0 ± 0%
AllShortest/AllBetweenFunc_100×4|0.25(53)-8 110.0 ± 0%
AllShortest/AllBetweenFunc_1000×4|0.25(574)-8 1.152k ± 0%
AllShortest/AllBetweenFunc_100×16|0.1(76)-8 156.0 ± 0%
AllShortest/AllBetweenFunc_1000×16|0.1(822)-8 1.648k ± 0%
geomean 649.3 336.5 -37.70%diff --git a/graph/path/bellman_ford_moore_test.go b/graph/path/bellman_ford_moore_test.go
index 237d702..f5835ca 100644
--- a/graph/path/bellman_ford_moore_test.go
+++ b/graph/path/bellman_ford_moore_test.go
@@ -170,6 +170,37 @@
}
}
+ paths = paths[:0]
+ pt.AllToFunc(test.Query.To().ID(), func(path []graph.Node) {
+ paths = append(paths, append([]graph.Node(nil), path...))
+ })
+ if weight := pt.WeightTo(test.Query.To().ID()); !math.IsInf(test.Weight, -1) && weight != test.Weight {
+ t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
+ test.Name, tg.typ, weight, test.Weight)
+ }
+
+ gotPaths = nil
+ if len(paths) != 0 {
+ gotPaths = make([][]int64, len(paths))
+ }
+ for i, p := range paths {
+ for _, v := range p {
+ gotPaths[i] = append(gotPaths[i], v.ID())
+ }
+ }
+ if test.HasNegativeCycleInPath {
+ if gotPaths != nil {
+ t.Errorf("testing %q %s: unexpected shortest paths:\ngot: %v\nwant: []",
+ test.Name, tg.typ, gotPaths)
+ }
+ } else {
+ ordered.BySliceValues(gotPaths)
+ if !reflect.DeepEqual(gotPaths, test.WantPaths) {
+ t.Errorf("testing %q %s: unexpected shortest paths:\ngot: %v\nwant:%v",
+ test.Name, tg.typ, gotPaths, test.WantPaths)
+ }
+ }
+
// Test absent paths.
np, weight, unique := pt.To(test.NoPathFor.To().ID())
if pt.From().ID() == test.NoPathFor.From().ID() && !(np == nil && math.IsInf(weight, 1) && !unique) {
diff --git a/graph/path/dijkstra_test.go b/graph/path/dijkstra_test.go
index ca9d953..45deec2 100644
--- a/graph/path/dijkstra_test.go
+++ b/graph/path/dijkstra_test.go
@@ -188,6 +188,34 @@
test.Name, gotPaths, test.WantPaths)
}
+ paths = paths[:0]
+ pt.AllToFunc(test.Query.To().ID(), func(path []graph.Node) {
+ paths = append(paths, append([]graph.Node(nil), path...))
+ })
+ if weight != test.Weight {
+ t.Errorf("%q %s: unexpected weight from AllTo: got:%f want:%f",
+ test.Name, tg.typ, weight, test.Weight)
+ }
+ if weight := pt.WeightTo(test.Query.To().ID()); !math.IsInf(test.Weight, -1) && weight != test.Weight {
+ t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
+ test.Name, tg.typ, weight, test.Weight)
+ }
+
+ gotPaths = nil
+ if len(paths) != 0 {
+ gotPaths = make([][]int64, len(paths))
+ }
+ for i, p := range paths {
+ for _, v := range p {
+ gotPaths[i] = append(gotPaths[i], v.ID())
+ }
+ }
+ ordered.BySliceValues(gotPaths)
+ if !reflect.DeepEqual(gotPaths, test.WantPaths) {
+ t.Errorf("testing %q %s: unexpected shortest paths:\ngot: %v\nwant:%v",
+ test.Name, tg.typ, gotPaths, test.WantPaths)
+ }
+
// Test absent paths.
np, weight, unique := pt.To(test.NoPathFor.To().ID())
if pt.From().ID() == test.NoPathFor.From().ID() && !(np == nil && math.IsInf(weight, 1) && !unique) {
@@ -296,6 +324,25 @@
test.Name, got, test.WantPaths)
}
+ paths = paths[:0]
+ pt.AllBetweenFunc(test.Query.From().ID(), test.Query.To().ID(), func(path []graph.Node) {
+ paths = append(paths, append([]graph.Node(nil), path...))
+ })
+ got = nil
+ if len(paths) != 0 {
+ got = make([][]int64, len(paths))
+ }
+ for i, p := range paths {
+ for _, v := range p {
+ got[i] = append(got[i], v.ID())
+ }
+ }
+ ordered.BySliceValues(got)
+ if !reflect.DeepEqual(got, test.WantPaths) {
+ t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
+ test.Name, got, test.WantPaths)
+ }
+
nps, weight := pt.AllBetween(test.NoPathFor.From().ID(), test.NoPathFor.To().ID())
if nps != nil || !math.IsInf(weight, 1) {
t.Errorf("%q: unexpected path:\ngot: paths=%v weight=%f\nwant:path=<nil> weight=+Inf",
diff --git a/graph/path/floydwarshall_test.go b/graph/path/floydwarshall_test.go
index 800c067..15afff3 100644
--- a/graph/path/floydwarshall_test.go
+++ b/graph/path/floydwarshall_test.go
@@ -93,6 +93,25 @@
test.Name, got, test.WantPaths)
}
+ paths = paths[:0]
+ pt.AllBetweenFunc(test.Query.From().ID(), test.Query.To().ID(), func(path []graph.Node) {
+ paths = append(paths, append([]graph.Node(nil), path...))
+ })
+ got = nil
+ if len(paths) != 0 {
+ got = make([][]int64, len(paths))
+ }
+ for i, p := range paths {
+ for _, v := range p {
+ got[i] = append(got[i], v.ID())
+ }
+ }
+ ordered.BySliceValues(got)
+ if !reflect.DeepEqual(got, test.WantPaths) {
+ t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
+ test.Name, got, test.WantPaths)
+ }
+
nps, weight := pt.AllBetween(test.NoPathFor.From().ID(), test.NoPathFor.To().ID())
if nps != nil || !math.IsInf(weight, 1) {
t.Errorf("%q: unexpected path:\ngot: paths=%v weight=%f\nwant:path=<nil> weight=+Inf",
diff --git a/graph/path/johnson_apsp_test.go b/graph/path/johnson_apsp_test.go
index d522ff9..c796f20 100644
--- a/graph/path/johnson_apsp_test.go
+++ b/graph/path/johnson_apsp_test.go
@@ -93,6 +93,25 @@
test.Name, got, test.WantPaths)
}
+ paths = paths[:0]
+ pt.AllBetweenFunc(test.Query.From().ID(), test.Query.To().ID(), func(path []graph.Node) {
+ paths = append(paths, append([]graph.Node(nil), path...))
+ })
+ got = nil
+ if len(paths) != 0 {
+ got = make([][]int64, len(paths))
+ }
+ for i, p := range paths {
+ for _, v := range p {
+ got[i] = append(got[i], v.ID())
+ }
+ }
+ ordered.BySliceValues(got)
+ if !reflect.DeepEqual(got, test.WantPaths) {
+ t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
+ test.Name, got, test.WantPaths)
+ }
+
nps, weight := pt.AllBetween(test.NoPathFor.From().ID(), test.NoPathFor.To().ID())
if nps != nil || !math.IsInf(weight, 1) {
t.Errorf("%q: unexpected path:\ngot: paths=%v weight=%f\nwant:path=<nil> weight=+Inf",
diff --git a/graph/path/shortest.go b/graph/path/shortest.go
index db6bb03..4fcd239 100644
--- a/graph/path/shortest.go
+++ b/graph/path/shortest.go
@@ -420,38 +420,67 @@
}
seen := make([]bool, len(p.nodes))
- paths = p.allTo(from, to, seen, []graph.Node{p.nodes[to]}, nil)
+ p.allTo(from, to, seen, []graph.Node{p.nodes[to]}, func(path []graph.Node) {
+ paths = append(paths, append([]graph.Node(nil), path...))
+ })
weight = p.dist[to]
return paths, weight
}
+// AllToFunc calls fn on all shortest paths to v. Paths containing zero-weight
+// cycles are not considered. If a negative cycle exists between u and v, no
+// path is considered. The fn closure must not retain the path parameter.
+func (p ShortestAlts) AllToFunc(vid int64, fn func(path []graph.Node)) {
+ from := p.indexOf[p.from.ID()]
+ to, toOK := p.indexOf[vid]
+ if !toOK || len(p.next[to]) == 0 {
+ if p.from.ID() == vid {
+ fn([]graph.Node{p.nodes[from]})
+ }
+ return
+ }
+
+ _, weight, unique := p.To(vid)
+ if math.IsInf(weight, -1) && !unique {
+ return
+ }
+
+ seen := make([]bool, len(p.nodes))
+ p.allTo(from, to, seen, []graph.Node{p.nodes[to]}, fn)
+}
+
// allTo recursively constructs a slice of paths extending from the node
// indexed into p.nodes by from to the node indexed by to. len(seen) must match
// the number of nodes held by the receiver. The path parameter is the current
-// working path and the results are written into paths.
-func (p ShortestAlts) allTo(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
+// working path and the results passed to fn.
+func (p ShortestAlts) allTo(from, to int, seen []bool, path []graph.Node, fn func(path []graph.Node)) {
seen[to] = true
if from == to {
if path == nil {
- return paths
+ return
}
ordered.Reverse(path)
- return append(paths, path)
+ fn(path)
+ ordered.Reverse(path)
+ return
}
first := true
+ var seenWork []bool
for _, to := range p.next[to] {
if seen[to] {
continue
}
if first {
- path = append([]graph.Node(nil), path...)
+ p := make([]graph.Node, len(path), len(path)+1)
+ copy(p, path)
+ path = p
+ seenWork = make([]bool, len(seen))
first = false
}
- path = path[:len(path):len(path)]
- paths = p.allTo(from, to, append([]bool(nil), seen...), append(path, p.nodes[to]), paths)
+ copy(seenWork, seen)
+ p.allTo(from, to, seenWork, append(path, p.nodes[to]), fn)
}
- return paths
}
// negEdge is a key into the negative costs map used by Shortest and ShortestAlts.
@@ -681,16 +710,51 @@
n = p.nodes[to]
}
seen := make([]bool, len(p.nodes))
- paths = p.allBetween(from, to, seen, []graph.Node{n}, nil)
+ p.allBetween(from, to, seen, []graph.Node{n}, func(path []graph.Node) {
+ paths = append(paths, append([]graph.Node(nil), path...))
+ })
return paths, weight
}
-// allBetween recursively constructs a slice of paths extending from the node
+// AllBetweenFunc calls fn on all shortest paths from u to v. Paths containing
+// zero-weight cycles are not considered. If a negative cycle exists between u
+// and v, no path is considered. The fn closure must not retain the path
+// parameter.
+func (p AllShortest) AllBetweenFunc(uid, vid int64, fn func(path []graph.Node)) {
+ from, fromOK := p.indexOf[uid]
+ to, toOK := p.indexOf[vid]
+ if !fromOK || !toOK || len(p.at(from, to)) == 0 {
+ if uid == vid {
+ if !fromOK {
+ fn([]graph.Node{node(uid)})
+ return
+ }
+ fn([]graph.Node{p.nodes[from]})
+ return
+ }
+ return
+ }
+
+ if math.Float64bits(p.dist.At(from, to)) == defacedBits {
+ return
+ }
+
+ var n graph.Node
+ if p.forward {
+ n = p.nodes[from]
+ } else {
+ n = p.nodes[to]
+ }
+ seen := make([]bool, len(p.nodes))
+ p.allBetween(from, to, seen, []graph.Node{n}, fn)
+}
+
+// allBetween recursively constructs a set of paths extending from the node
// indexed into p.nodes by from to the node indexed by to. len(seen) must match
// the number of nodes held by the receiver. The path parameter is the current
-// working path and the results are written into paths.
-func (p AllShortest) allBetween(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
+// working path and the results passed to fn.
+func (p AllShortest) allBetween(from, to int, seen []bool, path []graph.Node, fn func([]graph.Node)) {
if p.forward {
seen[from] = true
} else {
@@ -698,20 +762,28 @@
}
if from == to {
if path == nil {
- return paths
+ return
}
if !p.forward {
ordered.Reverse(path)
}
- return append(paths, path)
+ fn(path)
+ if !p.forward {
+ ordered.Reverse(path)
+ }
+ return
}
first := true
+ var seenWork []bool
for _, n := range p.at(from, to) {
if seen[n] {
continue
}
if first {
- path = append([]graph.Node(nil), path...)
+ p := make([]graph.Node, len(path), len(path)+1)
+ copy(p, path)
+ path = p
+ seenWork = make([]bool, len(seen))
first = false
}
if p.forward {
@@ -719,10 +791,9 @@
} else {
to = n
}
- path = path[:len(path):len(path)]
- paths = p.allBetween(from, to, append([]bool(nil), seen...), append(path, p.nodes[n]), paths)
+ copy(seenWork, seen)
+ p.allBetween(from, to, seenWork, append(path, p.nodes[n]), fn)
}
- return paths
}
type node int64
diff --git a/graph/path/shortest_test.go b/graph/path/shortest_test.go
new file mode 100644
index 0000000..6eb3907
--- /dev/null
+++ b/graph/path/shortest_test.go
@@ -0,0 +1,304 @@
+// Copyright ©2023 The Gonum Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package path
+
+import (
+ "fmt"
+ "math"
+ "reflect"
+ "testing"
+
+ "golang.org/x/exp/rand"
+
+ "gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/graphs/gen"
+ "gonum.org/v1/gonum/graph/internal/ordered"
+ "gonum.org/v1/gonum/graph/simple"
+)
+
+var shortestTests = []struct {
+ n, d int
+ p float64
+ seed uint64
+}{
+ {n: 100, d: 2, p: 0.5, seed: 1},
+ {n: 200, d: 2, p: 0.5, seed: 1},
+ {n: 100, d: 4, p: 0.25, seed: 1},
+ {n: 200, d: 4, p: 0.25, seed: 1},
+ {n: 100, d: 16, p: 0.1, seed: 1},
+ {n: 200, d: 16, p: 0.1, seed: 1},
+}
+
+func TestShortestAlts(t *testing.T) {
+ for _, test := range shortestTests {
+ t.Run(fmt.Sprintf("AllTo_%d×%d|%v", test.n, test.d, test.p), func(t *testing.T) {
+ g := simple.NewDirectedGraph()
+ gen.SmallWorldsBB(g, test.n, test.d, test.p, rand.New(rand.NewSource(test.seed)))
+ all := allShortest(DijkstraAllPaths(g))
+
+ for uid := int64(0); uid < int64(test.n); uid++ {
+ p := DijkstraAllFrom(g.Node(uid), g)
+ for vid := int64(0); vid < int64(test.n); vid++ {
+ got, gotW := p.AllTo(vid)
+ want, wantW := all.AllBetween(uid, vid)
+ if gotW != wantW {
+ t.Errorf("mismatched weight: got:%f want:%f", gotW, wantW)
+ continue
+ }
+
+ var gotPaths [][]int64
+ if len(got) != 0 {
+ gotPaths = make([][]int64, len(got))
+ }
+ for i, p := range got {
+ for _, v := range p {
+ gotPaths[i] = append(gotPaths[i], v.ID())
+ }
+ }
+ ordered.BySliceValues(gotPaths)
+ var wantPaths [][]int64
+ if len(want) != 0 {
+ wantPaths = make([][]int64, len(want))
+ }
+ for i, p := range want {
+ for _, v := range p {
+ wantPaths[i] = append(wantPaths[i], v.ID())
+ }
+ }
+ ordered.BySliceValues(wantPaths)
+ if !reflect.DeepEqual(gotPaths, wantPaths) {
+ t.Errorf("unexpected shortest paths %d --> %d:\ngot: %v\nwant:%v",
+ uid, vid, gotPaths, wantPaths)
+ }
+ }
+ }
+ })
+ }
+}
+
+func TestAllShortest(t *testing.T) {
+ for _, test := range shortestTests {
+ t.Run(fmt.Sprintf("AllBetween_%d×%d|%v", test.n, test.d, test.p), func(t *testing.T) {
+ g := simple.NewDirectedGraph()
+ gen.SmallWorldsBB(g, test.n, test.d, test.p, rand.New(rand.NewSource(test.seed)))
+
+ p := DijkstraAllPaths(g)
+ for uid := int64(0); uid < int64(test.n); uid++ {
+ for vid := int64(0); vid < int64(test.n); vid++ {
+ got, gotW := p.AllBetween(uid, vid)
+ want, wantW := allShortest(p).AllBetween(uid, vid) // Compare to naive.
+ if gotW != wantW {
+ t.Errorf("mismatched weight: got:%f want:%f", gotW, wantW)
+ continue
+ }
+
+ var gotPaths [][]int64
+ if len(got) != 0 {
+ gotPaths = make([][]int64, len(got))
+ }
+ for i, p := range got {
+ for _, v := range p {
+ gotPaths[i] = append(gotPaths[i], v.ID())
+ }
+ }
+ ordered.BySliceValues(gotPaths)
+ var wantPaths [][]int64
+ if len(want) != 0 {
+ wantPaths = make([][]int64, len(want))
+ }
+ for i, p := range want {
+ for _, v := range p {
+ wantPaths[i] = append(wantPaths[i], v.ID())
+ }
+ }
+ ordered.BySliceValues(wantPaths)
+ if !reflect.DeepEqual(gotPaths, wantPaths) {
+ t.Errorf("unexpected shortest paths %d --> %d:\ngot: %v\nwant:%v",
+ uid, vid, gotPaths, wantPaths)
+ }
+ }
+ }
+ })
+ }
+}
+
+// allShortest implements an allocation-naive AllBetween.
+type allShortest AllShortest
+
+// at returns a slice of node indexes into p.nodes for nodes that are mid points
+// between nodes indexed by from and to.
+func (p allShortest) at(from, to int) (mid []int) {
+ return p.next[from+to*len(p.nodes)]
+}
+
+// AllBetween returns all shortest paths from u to v and the weight of the paths. Paths
+// containing zero-weight cycles are not returned. If a negative cycle exists between
+// u and v, paths is returned nil and weight is returned as -Inf.
+func (p allShortest) AllBetween(uid, vid int64) (paths [][]graph.Node, weight float64) {
+ from, fromOK := p.indexOf[uid]
+ to, toOK := p.indexOf[vid]
+ if !fromOK || !toOK || len(p.at(from, to)) == 0 {
+ if uid == vid {
+ if !fromOK {
+ return [][]graph.Node{{node(uid)}}, 0
+ }
+ return [][]graph.Node{{p.nodes[from]}}, 0
+ }
+ return nil, math.Inf(1)
+ }
+
+ weight = p.dist.At(from, to)
+ if math.Float64bits(weight) == defacedBits {
+ return nil, math.Inf(-1)
+ }
+
+ var n graph.Node
+ if p.forward {
+ n = p.nodes[from]
+ } else {
+ n = p.nodes[to]
+ }
+ seen := make([]bool, len(p.nodes))
+ paths = p.allBetween(from, to, seen, []graph.Node{n}, nil)
+
+ return paths, weight
+}
+
+// allBetween recursively constructs a slice of paths extending from the node
+// indexed into p.nodes by from to the node indexed by to. len(seen) must match
+// the number of nodes held by the receiver. The path parameter is the current
+// working path and the results are written into paths.
+func (p allShortest) allBetween(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
+ if p.forward {
+ seen[from] = true
+ } else {
+ seen[to] = true
+ }
+ if from == to {
+ if path == nil {
+ return paths
+ }
+ if !p.forward {
+ ordered.Reverse(path)
+ }
+ return append(paths, path)
+ }
+ first := true
+ for _, n := range p.at(from, to) {
+ if seen[n] {
+ continue
+ }
+ if first {
+ path = append([]graph.Node(nil), path...)
+ first = false
+ }
+ if p.forward {
+ from = n
+ } else {
+ to = n
+ }
+ path = path[:len(path):len(path)]
+ paths = p.allBetween(from, to, append([]bool(nil), seen...), append(path, p.nodes[n]), paths)
+ }
+ return paths
+}
+
+var shortestBenchmarks = []struct {
+ n, d int
+ p float64
+ seed uint64
+}{
+ {n: 100, d: 2, p: 0.5, seed: 1},
+ {n: 1000, d: 2, p: 0.5, seed: 1},
+ {n: 100, d: 4, p: 0.25, seed: 1},
+ {n: 1000, d: 4, p: 0.25, seed: 1},
+ {n: 100, d: 16, p: 0.1, seed: 1},
+ {n: 1000, d: 16, p: 0.1, seed: 1},
+}
+
+func BenchmarkShortestAlts(b *testing.B) {
+ for _, bench := range shortestBenchmarks {
+ g := simple.NewDirectedGraph()
+ gen.SmallWorldsBB(g, bench.n, bench.d, bench.p, rand.New(rand.NewSource(bench.seed)))
+
+ // Find the widest path set.
+ var (
+ bestP ShortestAlts
+ bestVid int64
+ n int
+ )
+ for uid := int64(0); uid < int64(bench.n); uid++ {
+ p := DijkstraAllFrom(g.Node(uid), g)
+ for vid := int64(0); vid < int64(bench.n); vid++ {
+ paths, _ := p.AllTo(vid)
+ if len(paths) > n {
+ n = len(paths)
+ bestP = p
+ bestVid = vid
+ }
+ }
+ }
+
+ b.Run(fmt.Sprintf("AllTo_%d×%d|%v(%d)", bench.n, bench.d, bench.p, n), func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ paths, _ := bestP.AllTo(bestVid)
+ if len(paths) != n {
+ b.Errorf("unexpected number of paths: got:%d want:%d", len(paths), n)
+ }
+ }
+ })
+ b.Run(fmt.Sprintf("AllToFunc_%d×%d|%v(%d)", bench.n, bench.d, bench.p, n), func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ var paths int
+ bestP.AllToFunc(bestVid, func(_ []graph.Node) { paths++ })
+ if paths != n {
+ b.Errorf("unexpected number of paths: got:%d want:%d", paths, n)
+ }
+ }
+ })
+ }
+}
+
+func BenchmarkAllShortest(b *testing.B) {
+ for _, bench := range shortestBenchmarks {
+ g := simple.NewDirectedGraph()
+ gen.SmallWorldsBB(g, bench.n, bench.d, bench.p, rand.New(rand.NewSource(bench.seed)))
+ p := DijkstraAllPaths(g)
+
+ // Find the widest path set.
+ var (
+ bestUid, bestVid int64
+ n int
+ )
+ for uid := int64(0); uid < int64(bench.n); uid++ {
+ for vid := int64(0); vid < int64(bench.n); vid++ {
+ paths, _ := p.AllBetween(uid, vid)
+ if len(paths) > n {
+ n = len(paths)
+ bestUid = uid
+ bestVid = vid
+ }
+ }
+ }
+
+ b.Run(fmt.Sprintf("AllBetween_%d×%d|%v(%d)", bench.n, bench.d, bench.p, n), func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ paths, _ := p.AllBetween(bestUid, bestVid)
+ if len(paths) != n {
+ b.Errorf("unexpected number of paths: got:%d want:%d", len(paths), n)
+ }
+ }
+ })
+ b.Run(fmt.Sprintf("AllBetweenFunc_%d×%d|%v(%d)", bench.n, bench.d, bench.p, n), func(b *testing.B) {
+ for i := 0; i < b.N; i++ {
+ var paths int
+ p.AllBetweenFunc(bestUid, bestVid, func(_ []graph.Node) { paths++ })
+ if paths != n {
+ b.Errorf("unexpected number of paths: got:%d want:%d", paths, n)
+ }
+ }
+ })
+ }
+}
