blob: 6eb3907a6e805df5ab88683e5465fe2c7c595546 [file] [log] [blame]
 // 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) } } }) } }