graph/path: re-use test setup for DijkstraFromTo tests

Also rename `v` parameter to `t`.
gonum · Dec 2, 2024 · f112007 · f112007
1 parent 7649851
commit f112007
Show file tree

Hide file tree

Showing 2 changed files with 39 additions and 63 deletions.
diff --git a/graph/path/dijkstra.go b/graph/path/dijkstra.go
@@ -23,27 +23,27 @@ func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest {
 	return dijkstraFrom(u, nil, g)
 }
 
-// DijkstraFromTo returns a shortest path from u to v in the graph g. The
-// result is equivalent to DijkstraFrom(u, g).To(v), but DijkstraFromTo can be
-// more efficient, as it can terminate early if v is reached. If the graph does
-// not implement Weighted, UniformCost is used. DijkstraFromTo will panic if g
-// has a u-reachable negative edge weight that is discovered before reaching v.
+// DijkstraFromTo returns a shortest path from u to t in the graph g. The
+// result is equivalent to DijkstraFrom(u, g).To(t.ID()), but DijkstraFromTo
+// can be more efficient, as it can terminate early if t is reached. If the
+// graph does not implement Weighted, UniformCost is used. DijkstraFromTo will
+// panic if g has a u-reachable negative edge weight that is discovered before
+// reaching t.
 //
 // The time complexity of DijkstraFromTo is O(|E|.log|V|).
-func DijkstraFromTo(u graph.Node, v graph.Node, g traverse.Graph) (path []graph.Node, weight float64) {
+func DijkstraFromTo(u, t graph.Node, g traverse.Graph) (path []graph.Node, weight float64) {
 	// An implementation of Bidirectional Dijkstra's algorithm could be even
 	// more efficient, but it requires a transposed (or undirected) graph.
-	if v == nil {
+	if t == nil {
 		panic("dijkstra: nil target node")
 	}
-	return dijkstraFrom(u, v, g).To(v.ID())
+	return dijkstraFrom(u, t, g).To(t.ID())
 }
 
-// Shared implementation of DijkstraFrom and DijkstraFromTo.
-func dijkstraFrom(u, target graph.Node, g traverse.Graph) Shortest {
+func dijkstraFrom(u, t graph.Node, g traverse.Graph) Shortest {
 	var path Shortest
 	// Use the incremental version when a target is provided
-	if h, ok := g.(graph.Graph); target == nil && ok {
+	if h, ok := g.(graph.Graph); t == nil && ok {
 		if h.Node(u.ID()) == nil {
 			return Shortest{from: u}
 		}
@@ -80,7 +80,7 @@ func dijkstraFrom(u, target graph.Node, g traverse.Graph) Shortest {
 			continue
 		}
 		mnid := mid.node.ID()
-		if target != nil && mnid == target.ID() {
+		if t != nil && mnid == t.ID() {
 			break
 		}
 		to := g.From(mnid)

diff --git a/graph/path/dijkstra_test.go b/graph/path/dijkstra_test.go
@@ -24,35 +24,14 @@ func TestDijkstraFrom(t *testing.T) {
 			g.SetWeightedEdge(e)
 		}
 
-		checkPath := func(typ string, p []graph.Node, weight float64) {
-			if weight != test.Weight {
-				t.Errorf("%q %s: unexpected weight from To: got:%f want:%f",
-					test.Name, typ, weight, test.Weight)
-			}
-
-			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 %s: unexpected shortest path:\ngot: %v\nwant from:%v",
-					test.Name, typ, p, test.WantPaths)
-			}
-		}
-
 		for _, tg := range []struct {
 			typ string
 			g   traverse.Graph
+			t   graph.Node
 		}{
-			{"complete", g.(graph.Graph)},
-			{"incremental", incremental{g.(graph.Weighted)}},
+			{"complete", g.(graph.Graph), nil},
+			{"incremental", incremental{g.(graph.Weighted)}, nil},
+			{"single-destination", g.(graph.Graph), test.Query.To()},
 		} {
 			var (
 				pt Shortest
@@ -63,13 +42,13 @@ func TestDijkstraFrom(t *testing.T) {
 				defer func() {
 					panicked = recover() != nil
 				}()
-				pt = DijkstraFrom(test.Query.From(), tg.g)
+				pt = dijkstraFrom(test.Query.From(), tg.t, tg.g)
 			}()
 			if panicked || test.HasNegativeWeight {
 				if !test.HasNegativeWeight {
 					t.Errorf("%q %s: unexpected panic", test.Name, tg.typ)
 				}
-				if !panicked {
+				if !panicked && tg.t == nil {
 					t.Errorf("%q %s: expected panic for negative edge weight", test.Name, tg.typ)
 				}
 				continue
@@ -79,41 +58,38 @@ func TestDijkstraFrom(t *testing.T) {
 				t.Fatalf("%q %s: unexpected from node ID: got:%d want:%d", test.Name, tg.typ, pt.From().ID(), test.Query.From().ID())
 			}
 
+			p, weight := pt.To(test.Query.To().ID())
+			if weight != test.Weight {
+				t.Errorf("%q %s: unexpected weight from To: got:%f want:%f",
+					test.Name, tg.typ, weight, test.Weight)
+			}
 			if weight := pt.WeightTo(test.Query.To().ID()); weight != test.Weight {
-				t.Errorf("%q %s: unexpected weight from Weight: got:%f want:%f",
+				t.Errorf("%q %s: unexpected weight from WeightTo: got:%f want:%f",
 					test.Name, tg.typ, weight, test.Weight)
 			}
 
-			p, weight := pt.To(test.Query.To().ID())
-			checkPath(tg.typ, p, weight)
+			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 %s: unexpected shortest path:\ngot: %v\nwant from:%v",
+					test.Name, tg.typ, p, test.WantPaths)
+			}
 
 			np, weight := pt.To(test.NoPathFor.To().ID())
 			if pt.From().ID() == test.NoPathFor.From().ID() && (np != nil || !math.IsInf(weight, 1)) {
 				t.Errorf("%q %s: unexpected path:\ngot: path=%v weight=%f\nwant:path=<nil> weight=+Inf",
 					test.Name, tg.typ, np, weight)
 			}
 		}
-
-		// Test the single-destination variant.
-		var (
-			p        []graph.Node
-			weight   float64
-			panicked bool
-		)
-		func() {
-			defer func() {
-				panicked = recover() != nil
-			}()
-			p, weight = DijkstraFromTo(test.Query.From(), test.Query.To(), g.(graph.Graph))
-		}()
-		if panicked || test.HasNegativeWeight {
-			if !test.HasNegativeWeight {
-				t.Errorf("%q: unexpected panic", test.Name)
-			}
-			continue
-		}
-
-		checkPath("from-to", p, weight)
 	}
 }