1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
// 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"
"reflect"
"testing"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/path/internal/testgraphs"
"gonum.org/v1/gonum/internal/order"
)
func TestFloydWarshall(t *testing.T) {
t.Parallel()
for _, test := range testgraphs.ShortestPathTests {
g := test.Graph()
for _, e := range test.Edges {
g.SetWeightedEdge(e)
}
pt, ok := FloydWarshall(g.(graph.Graph))
if test.HasNegativeCycle {
if ok {
t.Errorf("%q: expected negative cycle", test.Name)
}
continue
}
if !ok {
t.Fatalf("%q: unexpected negative cycle", test.Name)
}
// Check all random paths returned are OK.
for i := 0; i < 10; i++ {
p, weight, unique := pt.Between(test.Query.From().ID(), test.Query.To().ID())
if weight != test.Weight {
t.Errorf("%q: unexpected weight from Between: got:%f want:%f",
test.Name, weight, test.Weight)
}
if weight := pt.Weight(test.Query.From().ID(), test.Query.To().ID()); weight != test.Weight {
t.Errorf("%q: unexpected weight from Weight: got:%f want:%f",
test.Name, weight, test.Weight)
}
if unique != test.HasUniquePath {
t.Errorf("%q: unexpected number of paths: got: unique=%t want: unique=%t",
test.Name, unique, test.HasUniquePath)
}
var got []int64
for _, n := range p {
got = append(got, n.ID())
}
ok := len(got) == 0 && len(test.WantPaths) == 0
for _, sp := range test.WantPaths {
if reflect.DeepEqual(got, sp) {
ok = true
break
}
}
if !ok {
t.Errorf("%q: unexpected shortest path:\ngot: %v\nwant from:%v",
test.Name, p, test.WantPaths)
}
}
np, weight, unique := pt.Between(test.NoPathFor.From().ID(), test.NoPathFor.To().ID())
if np != nil || !math.IsInf(weight, 1) || unique {
t.Errorf("%q: unexpected path:\ngot: path=%v weight=%f unique=%t\nwant:path=<nil> weight=+Inf unique=false",
test.Name, np, weight, unique)
}
paths, weight := pt.AllBetween(test.Query.From().ID(), test.Query.To().ID())
if weight != test.Weight {
t.Errorf("%q: unexpected weight from Between: got:%f want:%f",
test.Name, weight, test.Weight)
}
var got [][]int64
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())
}
}
order.BySliceValues(got)
if !reflect.DeepEqual(got, test.WantPaths) {
t.Errorf("testing %q: unexpected shortest paths:\ngot: %v\nwant:%v",
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())
}
}
order.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",
test.Name, nps, weight)
}
}
}
|
