blob: 3627995710f09f74d650fa29cfbfcfa7cb8fc87d [file] [log] [blame]
// Copyright ©2015 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 (
"math"
"testing"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/graphs/gen"
"gonum.org/v1/gonum/graph/simple"
)
var (
gnpUndirected_10_tenth = gnpUndirected(10, 0.1)
gnpUndirected_100_tenth = gnpUndirected(100, 0.1)
gnpUndirected_1000_tenth = gnpUndirected(1000, 0.1)
gnpUndirected_10_half = gnpUndirected(10, 0.5)
gnpUndirected_100_half = gnpUndirected(100, 0.5)
gnpUndirected_1000_half = gnpUndirected(1000, 0.5)
)
func gnpUndirected(n int, p float64) graph.Undirected {
g := simple.NewUndirectedGraph(0, math.Inf(1))
gen.Gnp(g, n, p, nil)
return g
}
func benchmarkAStarNilHeuristic(b *testing.B, g graph.Undirected) {
var expanded int
for i := 0; i < b.N; i++ {
_, expanded = AStar(simple.Node(0), simple.Node(1), g, nil)
}
if expanded == 0 {
b.Fatal("unexpected number of expanded nodes")
}
}
func BenchmarkAStarGnp_10_tenth(b *testing.B) {
benchmarkAStarNilHeuristic(b, gnpUndirected_10_tenth)
}
func BenchmarkAStarGnp_100_tenth(b *testing.B) {
benchmarkAStarNilHeuristic(b, gnpUndirected_100_tenth)
}
func BenchmarkAStarGnp_1000_tenth(b *testing.B) {
benchmarkAStarNilHeuristic(b, gnpUndirected_1000_tenth)
}
func BenchmarkAStarGnp_10_half(b *testing.B) {
benchmarkAStarNilHeuristic(b, gnpUndirected_10_half)
}
func BenchmarkAStarGnp_100_half(b *testing.B) {
benchmarkAStarNilHeuristic(b, gnpUndirected_100_half)
}
func BenchmarkAStarGnp_1000_half(b *testing.B) {
benchmarkAStarNilHeuristic(b, gnpUndirected_1000_half)
}
var (
nswUndirected_10_2_2_2 = navigableSmallWorldUndirected(10, 2, 2, 2)
nswUndirected_10_2_5_2 = navigableSmallWorldUndirected(10, 2, 5, 2)
nswUndirected_100_5_10_2 = navigableSmallWorldUndirected(100, 5, 10, 2)
nswUndirected_100_5_20_2 = navigableSmallWorldUndirected(100, 5, 20, 2)
)
func navigableSmallWorldUndirected(n, p, q int, r float64) graph.Undirected {
g := simple.NewUndirectedGraph(0, math.Inf(1))
gen.NavigableSmallWorld(g, []int{n, n}, p, q, r, nil)
return g
}
func coordinatesForID(n graph.Node, c, r int) [2]int {
id := n.ID()
if id >= int64(c*r) {
panic("out of range")
}
return [2]int{int(id) / r, int(id) % r}
}
// manhattanBetween returns the Manhattan distance between a and b.
func manhattanBetween(a, b [2]int) float64 {
var d int
for i, v := range a {
d += abs(v - b[i])
}
return float64(d)
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func benchmarkAStarHeuristic(b *testing.B, g graph.Undirected, h Heuristic) {
var expanded int
for i := 0; i < b.N; i++ {
_, expanded = AStar(simple.Node(0), simple.Node(1), g, h)
}
if expanded == 0 {
b.Fatal("unexpected number of expanded nodes")
}
}
func BenchmarkAStarUndirectedmallWorld_10_2_2_2(b *testing.B) {
benchmarkAStarHeuristic(b, nswUndirected_10_2_2_2, nil)
}
func BenchmarkAStarUndirectedmallWorld_10_2_2_2_Heur(b *testing.B) {
h := func(x, y graph.Node) float64 {
return manhattanBetween(coordinatesForID(x, 10, 10), coordinatesForID(y, 10, 10))
}
benchmarkAStarHeuristic(b, nswUndirected_10_2_2_2, h)
}
func BenchmarkAStarUndirectedmallWorld_10_2_5_2(b *testing.B) {
benchmarkAStarHeuristic(b, nswUndirected_10_2_5_2, nil)
}
func BenchmarkAStarUndirectedmallWorld_10_2_5_2_Heur(b *testing.B) {
h := func(x, y graph.Node) float64 {
return manhattanBetween(coordinatesForID(x, 10, 10), coordinatesForID(y, 10, 10))
}
benchmarkAStarHeuristic(b, nswUndirected_10_2_5_2, h)
}
func BenchmarkAStarUndirectedmallWorld_100_5_10_2(b *testing.B) {
benchmarkAStarHeuristic(b, nswUndirected_100_5_10_2, nil)
}
func BenchmarkAStarUndirectedmallWorld_100_5_10_2_Heur(b *testing.B) {
h := func(x, y graph.Node) float64 {
return manhattanBetween(coordinatesForID(x, 100, 100), coordinatesForID(y, 100, 100))
}
benchmarkAStarHeuristic(b, nswUndirected_100_5_10_2, h)
}
func BenchmarkAStarUndirectedmallWorld_100_5_20_2(b *testing.B) {
benchmarkAStarHeuristic(b, nswUndirected_100_5_20_2, nil)
}
func BenchmarkAStarUndirectedmallWorld_100_5_20_2_Heur(b *testing.B) {
h := func(x, y graph.Node) float64 {
return manhattanBetween(coordinatesForID(x, 100, 100), coordinatesForID(y, 100, 100))
}
benchmarkAStarHeuristic(b, nswUndirected_100_5_20_2, h)
}