dijkstra_test.gno
8.20 Kb · 274 lines
1package dijkstra
2
3import (
4 "strings"
5 "testing"
6
7 "gno.land/p/nt/uassert/v0"
8)
9
10// roads is the worked example used by most of the tests below, small enough to
11// solve by hand. It is directed, and it is built so that the obvious answers
12// are both wrong: the direct a -> c arc of 4 loses to a -> b -> c at 3, and c
13// is the first node to offer a route to e (at 9) but d supplies a cheaper one
14// (8) two steps later.
15//
16// a -2-> b a -4-> c b -1-> c b -3-> d c -6-> e d -3-> e
17//
18// f is an island: nothing reaches it, and it reaches nothing.
19func roads() *Graph {
20 g := New()
21 g.AddEdge("a", "b", 2)
22 g.AddEdge("a", "c", 4)
23 g.AddEdge("b", "c", 1)
24 g.AddEdge("b", "d", 3)
25 g.AddEdge("c", "e", 6)
26 g.AddEdge("d", "e", 3)
27 g.AddNode("f")
28 return g
29}
30
31func TestDistances(t *testing.T) {
32 r := roads().From("a")
33
34 tests := []struct {
35 node string
36 want int
37 ok bool
38 }{
39 {"a", 0, true},
40 {"b", 2, true},
41 {"c", 3, true}, // via b, not the direct arc of 4
42 {"d", 5, true},
43 {"e", 8, true}, // a,b,d,e at 8 beats a,b,c,e at 9
44 {"f", Unreachable, false},
45 {"nowhere", Unreachable, false},
46 }
47 for _, tt := range tests {
48 got, ok := r.Dist(tt.node)
49 uassert.Equal(t, tt.ok, ok, "ok for "+tt.node)
50 uassert.Equal(t, tt.want, got, "dist for "+tt.node)
51 }
52}
53
54func TestPaths(t *testing.T) {
55 r := roads().From("a")
56
57 tests := []struct {
58 node string
59 want string
60 }{
61 {"a", "a"},
62 {"b", "a>b"},
63 {"c", "a>b>c"},
64 {"d", "a>b>d"},
65 {"e", "a>b>d>e"},
66 {"f", ""},
67 {"nowhere", ""},
68 }
69 for _, tt := range tests {
70 uassert.Equal(t, tt.want, r.PathString(tt.node, ">"), "path to "+tt.node)
71 }
72
73 uassert.Equal(t, 0, len(r.Path("f")), "unreachable path is nil")
74 uassert.Equal(t, 1, len(r.Path("a")), "the source is a path of one")
75}
76
77// A node is settled in distance order, closest first, and that sequence is the
78// algorithm. The island never settles at all.
79func TestSettleOrder(t *testing.T) {
80 r := roads().From("a")
81 uassert.Equal(t, "a,b,c,d,e", strings.Join(r.Order(), ","))
82 uassert.Equal(t, 5, r.Reachable())
83 uassert.Equal(t, "a", r.Source())
84}
85
86// The tie-break is the property an on-chain Render depends on: two nodes at
87// the same distance settle in the order they were added, never in map order,
88// so the same graph gives the same answer on every validator.
89func TestTiesSettleInInsertionOrder(t *testing.T) {
90 g := New()
91 for _, n := range []string{"hub", "west", "east", "north"} {
92 g.AddNode(n)
93 }
94 g.AddEdge("hub", "west", 5)
95 g.AddEdge("hub", "east", 5)
96 g.AddEdge("hub", "north", 5)
97 uassert.Equal(t, "hub,west,east,north", strings.Join(g.From("hub").Order(), ","))
98
99 // Same graph, nodes declared in a different order: the settle order
100 // follows the declaration, which is the whole claim.
101 h := New()
102 for _, n := range []string{"hub", "north", "east", "west"} {
103 h.AddNode(n)
104 }
105 h.AddEdge("hub", "west", 5)
106 h.AddEdge("hub", "east", 5)
107 h.AddEdge("hub", "north", 5)
108 uassert.Equal(t, "hub,north,east,west", strings.Join(h.From("hub").Order(), ","))
109}
110
111// An equal-cost route never displaces the incumbent, so the predecessor chain
112// is the first one found rather than the last one tried.
113func TestEqualCostKeepsTheFirstPredecessor(t *testing.T) {
114 g := New()
115 g.AddEdge("s", "left", 1)
116 g.AddEdge("s", "right", 1)
117 g.AddEdge("left", "t", 1)
118 g.AddEdge("right", "t", 1)
119 r := g.From("s")
120 uassert.Equal(t, 2, mustDist(t, r, "t"))
121 uassert.Equal(t, "s>left>t", r.PathString("t", ">"))
122
123 via, ok := r.Via("t")
124 uassert.True(t, ok)
125 uassert.Equal(t, "left", via)
126
127 _, ok = r.Via("s")
128 uassert.False(t, ok, "the source has no predecessor")
129}
130
131// Parallel arcs are kept, and the search takes the cheapest of them.
132func TestParallelArcsTakeTheCheapest(t *testing.T) {
133 g := New()
134 g.AddEdge("a", "b", 9)
135 g.AddEdge("a", "b", 2)
136 g.AddEdge("a", "b", 7)
137 uassert.Equal(t, 3, g.Edges())
138 uassert.Equal(t, 2, g.Len())
139 uassert.Equal(t, 2, mustDist(t, g.From("a"), "b"))
140}
141
142func TestUndirectedGoesBothWays(t *testing.T) {
143 g := New()
144 g.AddUndirected("x", "y", 3)
145 g.AddUndirected("y", "z", 4)
146 uassert.Equal(t, 4, g.Edges(), "each undirected pair is two arcs")
147 uassert.Equal(t, 7, mustDist(t, g.From("x"), "z"))
148 uassert.Equal(t, 7, mustDist(t, g.From("z"), "x"))
149}
150
151// A zero-weight arc is legal and must not be mistaken for "no arc".
152func TestZeroWeightArcs(t *testing.T) {
153 g := New()
154 g.AddEdge("a", "b", 0)
155 g.AddEdge("b", "c", 0)
156 r := g.From("a")
157 uassert.Equal(t, 0, mustDist(t, r, "c"))
158 uassert.Equal(t, "a>b>c", r.PathString("c", ">"))
159}
160
161// Relaxations counts improvements, not arcs looked at. On roads() the six
162// arcs yield six improvements, but two of them are second thoughts: c drops
163// from 4 to 3 once b settles, and e drops from 9 to 8 once d does.
164func TestRelaxationsCountImprovements(t *testing.T) {
165 uassert.Equal(t, 6, roads().From("a").Relaxations())
166}
167
168func TestGraphBookkeeping(t *testing.T) {
169 g := roads()
170 uassert.Equal(t, 6, g.Len())
171 uassert.Equal(t, 6, g.Edges())
172 uassert.Equal(t, "a,b,c,d,e,f", strings.Join(g.Names(), ","))
173 uassert.True(t, g.Has("f"))
174 uassert.False(t, g.Has("nowhere"))
175
176 // AddNode is idempotent and returns the existing index.
177 uassert.Equal(t, 0, g.AddNode("a"))
178 uassert.Equal(t, 6, g.Len())
179
180 // Names is a copy: reordering it must not reorder the graph.
181 names := g.Names()
182 names[0] = "mutated"
183 uassert.Equal(t, "a", g.Names()[0])
184}
185
186// A search from an island reaches only itself, and that is not an error.
187func TestSearchFromAnIsland(t *testing.T) {
188 r := roads().From("f")
189 uassert.Equal(t, 1, r.Reachable())
190 uassert.Equal(t, "f", strings.Join(r.Order(), ","))
191 uassert.Equal(t, 0, mustDist(t, r, "f"))
192 _, ok := r.Dist("a")
193 uassert.False(t, ok, "arcs are one-way, f reaches nothing")
194}
195
196// A Result is a snapshot. Adding arcs afterwards does not change what it says,
197// which is what makes it safe to hold across a Render.
198func TestResultIsASnapshot(t *testing.T) {
199 g := New()
200 g.AddEdge("a", "b", 10)
201 r := g.From("a")
202 g.AddEdge("a", "b", 1)
203 uassert.Equal(t, 10, mustDist(t, r, "b"))
204 uassert.Equal(t, 1, mustDist(t, g.From("a"), "b"))
205}
206
207// The preconditions are enforced at build time, where the caller can still do
208// something about it, rather than silently returning a wrong shortest path.
209func TestBuildPanics(cur realm, t *testing.T) {
210 g := New()
211 uassert.PanicsWithMessage(t, cur, "dijkstra: negative weight", func() { g.AddEdge("a", "b", -1) })
212 uassert.PanicsWithMessage(t, cur, "dijkstra: self-loop", func() { g.AddEdge("a", "a", 1) })
213 uassert.PanicsWithMessage(t, cur, "dijkstra: empty node name", func() { g.AddNode("") })
214 uassert.PanicsWithMessage(t, cur, "dijkstra: unknown source: zz", func() { g.From("zz") })
215 uassert.NotPanics(t, cur, func() { g.AddEdge("a", "b", 0) })
216}
217
218func TestCapacityPanics(cur realm, t *testing.T) {
219 g := New()
220 for i := 0; i < MaxNodes; i++ {
221 g.AddNode(name(i))
222 }
223 uassert.Equal(t, MaxNodes, g.Len())
224 uassert.PanicsWithMessage(t, cur, "dijkstra: too many nodes", func() { g.AddNode("one-too-many") })
225
226 // Parallel arcs, so the edge cap is reached without tripping the node cap
227 // first: MaxEdges is deliberately larger than MaxNodes.
228 h := New()
229 for i := 0; i < MaxEdges; i++ {
230 h.AddEdge("hub", "spoke", 1)
231 }
232 uassert.Equal(t, MaxEdges, h.Edges())
233 uassert.Equal(t, 2, h.Len())
234 uassert.PanicsWithMessage(t, cur, "dijkstra: too many edges", func() { h.AddEdge("hub", "late", 1) })
235}
236
237// A long chain exercises the heap past the point where a linear scan would
238// still look correct, and pins the cost at the same time.
239func TestLongChain(t *testing.T) {
240 g := New()
241 for i := 0; i < 200; i++ {
242 g.AddEdge(name(i), name(i+1), 2)
243 }
244 r := g.From(name(0))
245 uassert.Equal(t, 400, mustDist(t, r, name(200)))
246 uassert.Equal(t, 201, r.Reachable())
247 uassert.Equal(t, 200, r.Relaxations(), "a chain improves each node exactly once")
248 uassert.Equal(t, 201, len(r.Path(name(200))))
249}
250
251// mustDist fails the test rather than returning a zero that reads like a real
252// distance.
253func mustDist(t *testing.T, r *Result, node string) int {
254 t.Helper()
255 d, ok := r.Dist(node)
256 if !ok {
257 t.Fatalf("no route to %s", node)
258 }
259 return d
260}
261
262// name turns an index into a stable node name, so the generated graphs above
263// do not depend on formatting helpers.
264func name(i int) string {
265 if i == 0 {
266 return "n0"
267 }
268 var digits []byte
269 for i > 0 {
270 digits = append([]byte{byte('0' + i%10)}, digits...)
271 i /= 10
272 }
273 return "n" + string(digits)
274}
