graph/path: make sure absent nodes are returned with the correct ID
MODIFY
graph/path/dijkstra_test.go
graph/path/dijkstra_test.go
@@ -13,6 +13,7 @@ import (
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/ordered"
"gonum.org/v1/gonum/graph/path/internal/testgraphs"
+ "gonum.org/v1/gonum/graph/simple"
"gonum.org/v1/gonum/graph/traverse"
)
@@ -194,3 +195,34 @@ func TestDijkstraAllPaths(t *testing.T) {
}
}
}
+
+func TestAllShortestAbsentNode(t *testing.T) {
+ g := simple.NewUndirectedGraph()
+ g.SetEdge(simple.Edge{F: simple.Node(1), T: simple.Node(2)})
+ paths := DijkstraAllPaths(g)
+ // Confirm we have a good paths tree.
+ if _, cost := paths.AllBetween(1, 2); cost != 1 {
+ t.Errorf("unexpected cost between existing nodes: got:%v want:1", cost)
+ }
+
+ gotPath, cost, unique := paths.Between(0, 0)
+ if cost != 0 {
+ t.Errorf("unexpected cost from absent node to itself: got:%v want:0", cost)
+ }
+ if !unique {
+ t.Error("unexpected non-unique path from absent node to itself")
+ }
+ wantPath := []graph.Node{node(0)}
+ if !reflect.DeepEqual(gotPath, wantPath) {
+ t.Errorf("unexpected path from absent node to itself: got:%#v want:%#v", gotPath, wantPath)
+ }
+
+ gotPaths, cost := paths.AllBetween(0, 0)
+ if cost != 0 {
+ t.Errorf("unexpected cost from absent node to itself: got:%v want:0", cost)
+ }
+ wantPaths := [][]graph.Node{{node(0)}}
+ if !reflect.DeepEqual(gotPaths, wantPaths) {
+ t.Errorf("unexpected paths from absent node to itself: got:%#v want:%#v", gotPaths, wantPaths)
+ }
+}

MODIFY
graph/path/shortest.go
graph/path/shortest.go
@@ -287,6 +287,9 @@ func (p AllShortest) Between(uid, vid int64) (path []graph.Node, weight float64,
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, true
+ }
return []graph.Node{p.nodes[from]}, 0, true
}
return nil, math.Inf(1), false
@@ -348,6 +351,9 @@ func (p AllShortest) AllBetween(uid, vid int64) (paths [][]graph.Node, weight fl
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)
@@ -403,3 +409,7 @@ func (p AllShortest) allBetween(from, to int, seen []bool, path []graph.Node, pa
}
return paths
}
+
+type node int64
+
+func (n node) ID() int64 { return int64(n) }

graph/path: make sure absent nodes are returned with the correct ID