1// Copyright ©2015 The Gonum Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package testgraphs
6
7import (
8	"math"
9	"reflect"
10	"testing"
11
12	"gonum.org/v1/gonum/graph"
13	"gonum.org/v1/gonum/graph/simple"
14)
15
16type changes struct {
17	n graph.Node
18
19	new, old []simple.WeightedEdge
20}
21
22var limitedVisionTests = []struct {
23	g        *Grid
24	radius   float64
25	diag     bool
26	remember bool
27
28	path []graph.Node
29
30	want []changes
31}{
32	{
33		g: NewGridFrom(
34			"*..*",
35			"**.*",
36			"**.*",
37			"**.*",
38		),
39		radius:   1,
40		diag:     false,
41		remember: false,
42		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},
43
44		want: []changes{
45			{
46				n: node(1),
47				new: []simple.WeightedEdge{
48					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
49					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
50					{F: simple.Node(1), T: simple.Node(2), W: 1},
51					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
52					{F: simple.Node(2), T: simple.Node(1), W: 1},
53					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
54				},
55				old: nil,
56			},
57			{
58				n: node(2),
59				new: []simple.WeightedEdge{
60					{F: simple.Node(1), T: simple.Node(2), W: 1},
61					{F: simple.Node(2), T: simple.Node(1), W: 1},
62					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
63					{F: simple.Node(2), T: simple.Node(6), W: 1},
64					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
65					{F: simple.Node(6), T: simple.Node(2), W: 1},
66				},
67				old: nil,
68			},
69			{
70				n: node(6),
71				new: []simple.WeightedEdge{
72					{F: simple.Node(2), T: simple.Node(6), W: 1},
73					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
74					{F: simple.Node(6), T: simple.Node(2), W: 1},
75					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
76					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
77					{F: simple.Node(6), T: simple.Node(10), W: 1},
78					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
79					{F: simple.Node(10), T: simple.Node(6), W: 1},
80				},
81				old: nil,
82			},
83			{
84				n: node(10),
85				new: []simple.WeightedEdge{
86					{F: simple.Node(6), T: simple.Node(10), W: 1},
87					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
88					{F: simple.Node(10), T: simple.Node(6), W: 1},
89					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
90					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
91					{F: simple.Node(10), T: simple.Node(14), W: 1},
92					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
93					{F: simple.Node(14), T: simple.Node(10), W: 1},
94				},
95				old: nil,
96			},
97			{
98				n: node(14),
99				new: []simple.WeightedEdge{
100					{F: simple.Node(10), T: simple.Node(14), W: 1},
101					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
102					{F: simple.Node(14), T: simple.Node(10), W: 1},
103					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
104					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
105					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
106				},
107				old: nil,
108			},
109		},
110	},
111	{
112		g: NewGridFrom(
113			"*..*",
114			"**.*",
115			"**.*",
116			"**.*",
117		),
118		radius:   1.5,
119		diag:     false,
120		remember: false,
121		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},
122
123		want: []changes{
124			{
125				n: node(1),
126				new: []simple.WeightedEdge{
127					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
128					{F: simple.Node(0), T: simple.Node(4), W: math.Inf(1)},
129					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
130					{F: simple.Node(1), T: simple.Node(2), W: 1},
131					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
132					{F: simple.Node(2), T: simple.Node(1), W: 1},
133					{F: simple.Node(2), T: simple.Node(6), W: 1},
134					{F: simple.Node(4), T: simple.Node(0), W: math.Inf(1)},
135					{F: simple.Node(4), T: simple.Node(5), W: math.Inf(1)},
136					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
137					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
138					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
139					{F: simple.Node(6), T: simple.Node(2), W: 1},
140					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
141				},
142				old: nil,
143			},
144			{
145				n: node(2),
146				new: []simple.WeightedEdge{
147					{F: simple.Node(1), T: simple.Node(2), W: 1},
148					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
149					{F: simple.Node(2), T: simple.Node(1), W: 1},
150					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
151					{F: simple.Node(2), T: simple.Node(6), W: 1},
152					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
153					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
154					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
155					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
156					{F: simple.Node(6), T: simple.Node(2), W: 1},
157					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
158					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
159					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
160					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
161				},
162				old: nil,
163			},
164			{
165				n: node(6),
166				new: []simple.WeightedEdge{
167					{F: simple.Node(1), T: simple.Node(2), W: 1},
168					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
169					{F: simple.Node(2), T: simple.Node(1), W: 1},
170					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
171					{F: simple.Node(2), T: simple.Node(6), W: 1},
172					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
173					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
174					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
175					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
176					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
177					{F: simple.Node(6), T: simple.Node(2), W: 1},
178					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
179					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
180					{F: simple.Node(6), T: simple.Node(10), W: 1},
181					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
182					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
183					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
184					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
185					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
186					{F: simple.Node(10), T: simple.Node(6), W: 1},
187					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
188					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
189					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
190					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
191				},
192				old: nil,
193			},
194			{
195				n: node(10),
196				new: []simple.WeightedEdge{
197					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
198					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
199					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
200					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
201					{F: simple.Node(6), T: simple.Node(10), W: 1},
202					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
203					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
204					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
205					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
206					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
207					{F: simple.Node(10), T: simple.Node(6), W: 1},
208					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
209					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
210					{F: simple.Node(10), T: simple.Node(14), W: 1},
211					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
212					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
213					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
214					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
215					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
216					{F: simple.Node(14), T: simple.Node(10), W: 1},
217					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
218					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
219					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
220					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
221				},
222				old: nil,
223			},
224			{
225				n: node(14),
226				new: []simple.WeightedEdge{
227					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
228					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
229					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
230					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
231					{F: simple.Node(10), T: simple.Node(14), W: 1},
232					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
233					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
234					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
235					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
236					{F: simple.Node(14), T: simple.Node(10), W: 1},
237					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
238					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
239					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
240					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
241				},
242				old: nil,
243			},
244		},
245	},
246	{
247		g: NewGridFrom(
248			"*..*",
249			"**.*",
250			"**.*",
251			"**.*",
252		),
253		radius:   1,
254		diag:     false,
255		remember: true,
256		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},
257
258		want: []changes{
259			{
260				n: node(1),
261				new: []simple.WeightedEdge{
262					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
263					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
264					{F: simple.Node(1), T: simple.Node(2), W: 1},
265					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
266					{F: simple.Node(2), T: simple.Node(1), W: 1},
267					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
268				},
269				old: nil,
270			},
271			{
272				n: node(2),
273				new: []simple.WeightedEdge{
274					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
275					{F: simple.Node(2), T: simple.Node(6), W: 1},
276					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
277					{F: simple.Node(6), T: simple.Node(2), W: 1},
278					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
279				},
280				old: []simple.WeightedEdge{
281					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
282					{F: simple.Node(1), T: simple.Node(2), W: 1},
283					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
284					{F: simple.Node(2), T: simple.Node(1), W: 1},
285				},
286			},
287			{
288				n: node(6),
289				new: []simple.WeightedEdge{
290					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
291					{F: simple.Node(6), T: simple.Node(10), W: 1},
292					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
293					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
294					{F: simple.Node(10), T: simple.Node(6), W: 1},
295				},
296				old: []simple.WeightedEdge{
297					{F: simple.Node(2), T: simple.Node(1), W: 1},
298					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
299					{F: simple.Node(2), T: simple.Node(6), W: 1},
300					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
301					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
302					{F: simple.Node(6), T: simple.Node(2), W: 1},
303					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
304				},
305			},
306			{
307				n: node(10),
308				new: []simple.WeightedEdge{
309					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
310					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
311					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
312					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
313					{F: simple.Node(10), T: simple.Node(14), W: 1},
314					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
315					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
316					{F: simple.Node(14), T: simple.Node(10), W: 1},
317				},
318				old: []simple.WeightedEdge{
319					{F: simple.Node(6), T: simple.Node(2), W: 1},
320					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
321					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
322					{F: simple.Node(6), T: simple.Node(10), W: 1},
323					{F: simple.Node(10), T: simple.Node(6), W: 1},
324				},
325			},
326			{
327				n: node(14),
328				new: []simple.WeightedEdge{
329					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
330					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
331					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
332					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
333					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
334					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
335				},
336				old: []simple.WeightedEdge{
337					{F: simple.Node(10), T: simple.Node(6), W: 1},
338					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
339					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
340					{F: simple.Node(10), T: simple.Node(14), W: 1},
341					{F: simple.Node(14), T: simple.Node(10), W: 1},
342				},
343			},
344		},
345	},
346	{
347		g: NewGridFrom(
348			"*..*",
349			"**.*",
350			"**.*",
351			"**.*",
352		),
353		radius:   1.5,
354		diag:     false,
355		remember: true,
356		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},
357
358		want: []changes{
359			{
360				n: node(1),
361				new: []simple.WeightedEdge{
362					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
363					{F: simple.Node(0), T: simple.Node(4), W: math.Inf(1)},
364					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
365					{F: simple.Node(1), T: simple.Node(2), W: 1},
366					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
367					{F: simple.Node(2), T: simple.Node(1), W: 1},
368					{F: simple.Node(2), T: simple.Node(6), W: 1},
369					{F: simple.Node(4), T: simple.Node(0), W: math.Inf(1)},
370					{F: simple.Node(4), T: simple.Node(5), W: math.Inf(1)},
371					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
372					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
373					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
374					{F: simple.Node(6), T: simple.Node(2), W: 1},
375					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
376				},
377				old: nil,
378			},
379			{
380				n: node(2),
381				new: []simple.WeightedEdge{
382					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
383					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
384					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
385					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
386					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
387					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
388				},
389				old: []simple.WeightedEdge{
390					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
391					{F: simple.Node(1), T: simple.Node(2), W: 1},
392					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
393					{F: simple.Node(2), T: simple.Node(1), W: 1},
394					{F: simple.Node(2), T: simple.Node(6), W: 1},
395					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
396					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
397					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
398					{F: simple.Node(6), T: simple.Node(2), W: 1},
399					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
400				},
401			},
402			{
403				n: node(6),
404				new: []simple.WeightedEdge{
405					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
406					{F: simple.Node(6), T: simple.Node(10), W: 1},
407					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
408					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
409					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
410					{F: simple.Node(10), T: simple.Node(6), W: 1},
411					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
412					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
413					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
414					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
415				},
416				old: []simple.WeightedEdge{
417					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
418					{F: simple.Node(1), T: simple.Node(2), W: 1},
419					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
420					{F: simple.Node(2), T: simple.Node(1), W: 1},
421					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
422					{F: simple.Node(2), T: simple.Node(6), W: 1},
423					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
424					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
425					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
426					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
427					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
428					{F: simple.Node(6), T: simple.Node(2), W: 1},
429					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
430					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
431					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
432					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
433				},
434			},
435			{
436				n: node(10),
437				new: []simple.WeightedEdge{
438					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
439					{F: simple.Node(10), T: simple.Node(14), W: 1},
440					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
441					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
442					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
443					{F: simple.Node(14), T: simple.Node(10), W: 1},
444					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
445					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
446					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
447					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
448				},
449				old: []simple.WeightedEdge{
450					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
451					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
452					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
453					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
454					{F: simple.Node(6), T: simple.Node(2), W: 1},
455					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
456					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
457					{F: simple.Node(6), T: simple.Node(10), W: 1},
458					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
459					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
460					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
461					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
462					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
463					{F: simple.Node(10), T: simple.Node(6), W: 1},
464					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
465					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
466					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
467					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
468				},
469			},
470			{
471				n:   node(14),
472				new: nil,
473				old: []simple.WeightedEdge{
474					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
475					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
476					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
477					{F: simple.Node(10), T: simple.Node(6), W: 1},
478					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
479					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
480					{F: simple.Node(10), T: simple.Node(14), W: 1},
481					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
482					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
483					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
484					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
485					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
486					{F: simple.Node(14), T: simple.Node(10), W: 1},
487					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
488					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
489					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
490					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
491				},
492			},
493		},
494	},
495	{
496		g: NewGridFrom(
497			"*..*",
498			"**.*",
499			"**.*",
500			"**.*",
501		),
502		radius:   1,
503		diag:     true,
504		remember: false,
505		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},
506
507		want: []changes{
508			{
509				n: node(1),
510				new: []simple.WeightedEdge{
511					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
512					{F: simple.Node(0), T: simple.Node(5), W: math.Inf(1)},
513					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
514					{F: simple.Node(1), T: simple.Node(2), W: 1},
515					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
516					{F: simple.Node(2), T: simple.Node(1), W: 1},
517					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
518					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
519					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
520					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
521				},
522				old: nil,
523			},
524			{
525				n: node(2),
526				new: []simple.WeightedEdge{
527					{F: simple.Node(1), T: simple.Node(2), W: 1},
528					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
529					{F: simple.Node(2), T: simple.Node(1), W: 1},
530					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
531					{F: simple.Node(2), T: simple.Node(6), W: 1},
532					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
533					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
534					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
535					{F: simple.Node(6), T: simple.Node(2), W: 1},
536					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
537				},
538				old: nil,
539			},
540			{
541				n: node(6),
542				new: []simple.WeightedEdge{
543					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
544					{F: simple.Node(2), T: simple.Node(6), W: 1},
545					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
546					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
547					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
548					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
549					{F: simple.Node(6), T: simple.Node(2), W: 1},
550					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
551					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
552					{F: simple.Node(6), T: simple.Node(10), W: 1},
553					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
554					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
555					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
556					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
557					{F: simple.Node(10), T: simple.Node(6), W: 1},
558					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
559				},
560				old: nil,
561			},
562			{
563				n: node(10),
564				new: []simple.WeightedEdge{
565					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
566					{F: simple.Node(6), T: simple.Node(10), W: 1},
567					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
568					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
569					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
570					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
571					{F: simple.Node(10), T: simple.Node(6), W: 1},
572					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
573					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
574					{F: simple.Node(10), T: simple.Node(14), W: 1},
575					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
576					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
577					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
578					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
579					{F: simple.Node(14), T: simple.Node(10), W: 1},
580					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
581				},
582				old: nil,
583			},
584			{
585				n: node(14),
586				new: []simple.WeightedEdge{
587					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
588					{F: simple.Node(10), T: simple.Node(14), W: 1},
589					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
590					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
591					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
592					{F: simple.Node(14), T: simple.Node(10), W: 1},
593					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
594					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
595					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
596					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
597				},
598				old: nil,
599			},
600		},
601	},
602	{
603		g: NewGridFrom(
604			"*..*",
605			"**.*",
606			"**.*",
607			"**.*",
608		),
609		radius:   1.5,
610		diag:     true,
611		remember: false,
612		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},
613
614		want: []changes{
615			{
616				n: node(1),
617				new: []simple.WeightedEdge{
618					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
619					{F: simple.Node(0), T: simple.Node(4), W: math.Inf(1)},
620					{F: simple.Node(0), T: simple.Node(5), W: math.Inf(1)},
621					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
622					{F: simple.Node(1), T: simple.Node(2), W: 1},
623					{F: simple.Node(1), T: simple.Node(4), W: math.Inf(1)},
624					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
625					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
626					{F: simple.Node(2), T: simple.Node(1), W: 1},
627					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
628					{F: simple.Node(2), T: simple.Node(6), W: 1},
629					{F: simple.Node(4), T: simple.Node(0), W: math.Inf(1)},
630					{F: simple.Node(4), T: simple.Node(1), W: math.Inf(1)},
631					{F: simple.Node(4), T: simple.Node(5), W: math.Inf(1)},
632					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
633					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
634					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
635					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
636					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
637					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
638					{F: simple.Node(6), T: simple.Node(2), W: 1},
639					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
640				},
641				old: nil,
642			},
643			{
644				n: node(2),
645				new: []simple.WeightedEdge{
646					{F: simple.Node(1), T: simple.Node(2), W: 1},
647					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
648					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
649					{F: simple.Node(2), T: simple.Node(1), W: 1},
650					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
651					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
652					{F: simple.Node(2), T: simple.Node(6), W: 1},
653					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
654					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
655					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
656					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
657					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
658					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
659					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
660					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
661					{F: simple.Node(6), T: simple.Node(2), W: 1},
662					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
663					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
664					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
665					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
666					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
667					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
668				},
669				old: nil,
670			},
671			{
672				n: node(6),
673				new: []simple.WeightedEdge{
674					{F: simple.Node(1), T: simple.Node(2), W: 1},
675					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
676					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
677					{F: simple.Node(2), T: simple.Node(1), W: 1},
678					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
679					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
680					{F: simple.Node(2), T: simple.Node(6), W: 1},
681					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
682					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
683					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
684					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
685					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
686					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
687					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
688					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
689					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
690					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
691					{F: simple.Node(6), T: simple.Node(2), W: 1},
692					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
693					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
694					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
695					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
696					{F: simple.Node(6), T: simple.Node(10), W: 1},
697					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
698					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
699					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
700					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
701					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
702					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
703					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
704					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
705					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
706					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
707					{F: simple.Node(10), T: simple.Node(6), W: 1},
708					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
709					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
710					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
711					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
712					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
713					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
714				},
715				old: nil,
716			},
717			{
718				n: node(10),
719				new: []simple.WeightedEdge{
720					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
721					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
722					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
723					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
724					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
725					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
726					{F: simple.Node(6), T: simple.Node(10), W: 1},
727					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
728					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
729					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
730					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
731					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
732					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
733					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
734					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
735					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
736					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
737					{F: simple.Node(10), T: simple.Node(6), W: 1},
738					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
739					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
740					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
741					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
742					{F: simple.Node(10), T: simple.Node(14), W: 1},
743					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
744					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
745					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
746					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
747					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
748					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
749					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
750					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
751					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
752					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
753					{F: simple.Node(14), T: simple.Node(10), W: 1},
754					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
755					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
756					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
757					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
758					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
759					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
760				},
761				old: nil,
762			},
763			{
764				n: node(14),
765				new: []simple.WeightedEdge{
766					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
767					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
768					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
769					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
770					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
771					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
772					{F: simple.Node(10), T: simple.Node(14), W: 1},
773					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
774					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
775					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
776					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
777					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
778					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
779					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
780					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
781					{F: simple.Node(14), T: simple.Node(10), W: 1},
782					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
783					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
784					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
785					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
786					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
787					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
788				},
789				old: nil,
790			},
791		},
792	},
793	{
794		g: NewGridFrom(
795			"*..*",
796			"**.*",
797			"**.*",
798			"**.*",
799		),
800		radius:   1,
801		diag:     true,
802		remember: true,
803		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},
804
805		want: []changes{
806			{
807				n: node(1),
808				new: []simple.WeightedEdge{
809					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
810					{F: simple.Node(0), T: simple.Node(5), W: math.Inf(1)},
811					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
812					{F: simple.Node(1), T: simple.Node(2), W: 1},
813					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
814					{F: simple.Node(2), T: simple.Node(1), W: 1},
815					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
816					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
817					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
818					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
819				},
820				old: nil,
821			},
822			{
823				n: node(2),
824				new: []simple.WeightedEdge{
825					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
826					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
827					{F: simple.Node(2), T: simple.Node(6), W: 1},
828					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
829					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
830					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
831					{F: simple.Node(6), T: simple.Node(2), W: 1},
832					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
833					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
834				},
835				old: []simple.WeightedEdge{
836					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
837					{F: simple.Node(1), T: simple.Node(2), W: 1},
838					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
839					{F: simple.Node(2), T: simple.Node(1), W: 1},
840					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
841				},
842			},
843			{
844				n: node(6),
845				new: []simple.WeightedEdge{
846					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
847					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
848					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
849					{F: simple.Node(6), T: simple.Node(10), W: 1},
850					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
851					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
852					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
853					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
854					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
855					{F: simple.Node(10), T: simple.Node(6), W: 1},
856					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
857				},
858				old: []simple.WeightedEdge{
859					{F: simple.Node(2), T: simple.Node(1), W: 1},
860					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
861					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
862					{F: simple.Node(2), T: simple.Node(6), W: 1},
863					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
864					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
865					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
866					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
867					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
868					{F: simple.Node(6), T: simple.Node(2), W: 1},
869					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
870					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
871				},
872			},
873			{
874				n: node(10),
875				new: []simple.WeightedEdge{
876					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
877					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
878					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
879					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
880					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
881					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
882					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
883					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
884					{F: simple.Node(10), T: simple.Node(14), W: 1},
885					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
886					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
887					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
888					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
889					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
890					{F: simple.Node(14), T: simple.Node(10), W: 1},
891					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
892				},
893				old: []simple.WeightedEdge{
894					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
895					{F: simple.Node(6), T: simple.Node(2), W: 1},
896					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
897					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
898					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
899					{F: simple.Node(6), T: simple.Node(10), W: 1},
900					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
901					{F: simple.Node(10), T: simple.Node(6), W: 1},
902					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
903				},
904			},
905			{
906				n: node(14),
907				new: []simple.WeightedEdge{
908					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
909					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
910					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
911					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
912					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
913					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
914					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
915					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
916					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
917					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
918				},
919				old: []simple.WeightedEdge{
920					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
921					{F: simple.Node(10), T: simple.Node(6), W: 1},
922					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
923					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
924					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
925					{F: simple.Node(10), T: simple.Node(14), W: 1},
926					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
927					{F: simple.Node(14), T: simple.Node(10), W: 1},
928					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
929				},
930			},
931		},
932	},
933	{
934		g: NewGridFrom(
935			"*..*",
936			"**.*",
937			"**.*",
938			"**.*",
939		),
940		radius:   1.5,
941		diag:     true,
942		remember: true,
943		path:     []graph.Node{node(1), node(2), node(6), node(10), node(14)},
944
945		want: []changes{
946			{
947				n: node(1),
948				new: []simple.WeightedEdge{
949					{F: simple.Node(0), T: simple.Node(1), W: math.Inf(1)},
950					{F: simple.Node(0), T: simple.Node(4), W: math.Inf(1)},
951					{F: simple.Node(0), T: simple.Node(5), W: math.Inf(1)},
952					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
953					{F: simple.Node(1), T: simple.Node(2), W: 1},
954					{F: simple.Node(1), T: simple.Node(4), W: math.Inf(1)},
955					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
956					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
957					{F: simple.Node(2), T: simple.Node(1), W: 1},
958					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
959					{F: simple.Node(2), T: simple.Node(6), W: 1},
960					{F: simple.Node(4), T: simple.Node(0), W: math.Inf(1)},
961					{F: simple.Node(4), T: simple.Node(1), W: math.Inf(1)},
962					{F: simple.Node(4), T: simple.Node(5), W: math.Inf(1)},
963					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
964					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
965					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
966					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
967					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
968					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
969					{F: simple.Node(6), T: simple.Node(2), W: 1},
970					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
971				},
972				old: nil,
973			},
974			{
975				n: node(2),
976				new: []simple.WeightedEdge{
977					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
978					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
979					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
980					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
981					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
982					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
983					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
984					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
985					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
986					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
987				},
988				old: []simple.WeightedEdge{
989					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
990					{F: simple.Node(1), T: simple.Node(2), W: 1},
991					{F: simple.Node(1), T: simple.Node(4), W: math.Inf(1)},
992					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
993					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
994					{F: simple.Node(2), T: simple.Node(1), W: 1},
995					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
996					{F: simple.Node(2), T: simple.Node(6), W: 1},
997					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
998					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
999					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
1000					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
1001					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
1002					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
1003					{F: simple.Node(6), T: simple.Node(2), W: 1},
1004					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
1005				},
1006			},
1007			{
1008				n: node(6),
1009				new: []simple.WeightedEdge{
1010					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
1011					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
1012					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
1013					{F: simple.Node(6), T: simple.Node(10), W: 1},
1014					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
1015					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
1016					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
1017					{F: simple.Node(9), T: simple.Node(4), W: math.Inf(1)},
1018					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
1019					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
1020					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
1021					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
1022					{F: simple.Node(10), T: simple.Node(6), W: 1},
1023					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
1024					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
1025					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
1026					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
1027					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
1028					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
1029				},
1030				old: []simple.WeightedEdge{
1031					{F: simple.Node(1), T: simple.Node(0), W: math.Inf(1)},
1032					{F: simple.Node(1), T: simple.Node(2), W: 1},
1033					{F: simple.Node(1), T: simple.Node(4), W: math.Inf(1)},
1034					{F: simple.Node(1), T: simple.Node(5), W: math.Inf(1)},
1035					{F: simple.Node(1), T: simple.Node(6), W: math.Sqrt2},
1036					{F: simple.Node(2), T: simple.Node(1), W: 1},
1037					{F: simple.Node(2), T: simple.Node(3), W: math.Inf(1)},
1038					{F: simple.Node(2), T: simple.Node(5), W: math.Inf(1)},
1039					{F: simple.Node(2), T: simple.Node(6), W: 1},
1040					{F: simple.Node(2), T: simple.Node(7), W: math.Inf(1)},
1041					{F: simple.Node(3), T: simple.Node(2), W: math.Inf(1)},
1042					{F: simple.Node(3), T: simple.Node(6), W: math.Inf(1)},
1043					{F: simple.Node(3), T: simple.Node(7), W: math.Inf(1)},
1044					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
1045					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
1046					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
1047					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
1048					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
1049					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
1050					{F: simple.Node(6), T: simple.Node(2), W: 1},
1051					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
1052					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
1053					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
1054					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
1055					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
1056					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
1057				},
1058			},
1059			{
1060				n: node(10),
1061				new: []simple.WeightedEdge{
1062					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
1063					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
1064					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
1065					{F: simple.Node(10), T: simple.Node(14), W: 1},
1066					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
1067					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
1068					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
1069					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
1070					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
1071					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
1072					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
1073					{F: simple.Node(14), T: simple.Node(10), W: 1},
1074					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
1075					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
1076					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
1077					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
1078					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
1079					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
1080				},
1081				old: []simple.WeightedEdge{
1082					{F: simple.Node(5), T: simple.Node(0), W: math.Inf(1)},
1083					{F: simple.Node(5), T: simple.Node(1), W: math.Inf(1)},
1084					{F: simple.Node(5), T: simple.Node(2), W: math.Inf(1)},
1085					{F: simple.Node(5), T: simple.Node(4), W: math.Inf(1)},
1086					{F: simple.Node(5), T: simple.Node(6), W: math.Inf(1)},
1087					{F: simple.Node(5), T: simple.Node(9), W: math.Inf(1)},
1088					{F: simple.Node(5), T: simple.Node(10), W: math.Inf(1)},
1089					{F: simple.Node(6), T: simple.Node(1), W: math.Sqrt2},
1090					{F: simple.Node(6), T: simple.Node(2), W: 1},
1091					{F: simple.Node(6), T: simple.Node(3), W: math.Inf(1)},
1092					{F: simple.Node(6), T: simple.Node(5), W: math.Inf(1)},
1093					{F: simple.Node(6), T: simple.Node(7), W: math.Inf(1)},
1094					{F: simple.Node(6), T: simple.Node(9), W: math.Inf(1)},
1095					{F: simple.Node(6), T: simple.Node(10), W: 1},
1096					{F: simple.Node(6), T: simple.Node(11), W: math.Inf(1)},
1097					{F: simple.Node(7), T: simple.Node(2), W: math.Inf(1)},
1098					{F: simple.Node(7), T: simple.Node(3), W: math.Inf(1)},
1099					{F: simple.Node(7), T: simple.Node(6), W: math.Inf(1)},
1100					{F: simple.Node(7), T: simple.Node(10), W: math.Inf(1)},
1101					{F: simple.Node(7), T: simple.Node(11), W: math.Inf(1)},
1102					{F: simple.Node(9), T: simple.Node(4), W: math.Inf(1)},
1103					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
1104					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
1105					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
1106					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
1107					{F: simple.Node(10), T: simple.Node(6), W: 1},
1108					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
1109					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
1110					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
1111					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
1112					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
1113					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
1114				},
1115			},
1116			{
1117				n:   node(14),
1118				new: nil,
1119				old: []simple.WeightedEdge{
1120					{F: simple.Node(9), T: simple.Node(4), W: math.Inf(1)},
1121					{F: simple.Node(9), T: simple.Node(5), W: math.Inf(1)},
1122					{F: simple.Node(9), T: simple.Node(6), W: math.Inf(1)},
1123					{F: simple.Node(9), T: simple.Node(10), W: math.Inf(1)},
1124					{F: simple.Node(9), T: simple.Node(13), W: math.Inf(1)},
1125					{F: simple.Node(9), T: simple.Node(14), W: math.Inf(1)},
1126					{F: simple.Node(10), T: simple.Node(5), W: math.Inf(1)},
1127					{F: simple.Node(10), T: simple.Node(6), W: 1},
1128					{F: simple.Node(10), T: simple.Node(7), W: math.Inf(1)},
1129					{F: simple.Node(10), T: simple.Node(9), W: math.Inf(1)},
1130					{F: simple.Node(10), T: simple.Node(11), W: math.Inf(1)},
1131					{F: simple.Node(10), T: simple.Node(13), W: math.Inf(1)},
1132					{F: simple.Node(10), T: simple.Node(14), W: 1},
1133					{F: simple.Node(10), T: simple.Node(15), W: math.Inf(1)},
1134					{F: simple.Node(11), T: simple.Node(6), W: math.Inf(1)},
1135					{F: simple.Node(11), T: simple.Node(7), W: math.Inf(1)},
1136					{F: simple.Node(11), T: simple.Node(10), W: math.Inf(1)},
1137					{F: simple.Node(11), T: simple.Node(14), W: math.Inf(1)},
1138					{F: simple.Node(11), T: simple.Node(15), W: math.Inf(1)},
1139					{F: simple.Node(13), T: simple.Node(9), W: math.Inf(1)},
1140					{F: simple.Node(13), T: simple.Node(10), W: math.Inf(1)},
1141					{F: simple.Node(13), T: simple.Node(14), W: math.Inf(1)},
1142					{F: simple.Node(14), T: simple.Node(9), W: math.Inf(1)},
1143					{F: simple.Node(14), T: simple.Node(10), W: 1},
1144					{F: simple.Node(14), T: simple.Node(11), W: math.Inf(1)},
1145					{F: simple.Node(14), T: simple.Node(13), W: math.Inf(1)},
1146					{F: simple.Node(14), T: simple.Node(15), W: math.Inf(1)},
1147					{F: simple.Node(15), T: simple.Node(10), W: math.Inf(1)},
1148					{F: simple.Node(15), T: simple.Node(11), W: math.Inf(1)},
1149					{F: simple.Node(15), T: simple.Node(14), W: math.Inf(1)},
1150				},
1151			},
1152		},
1153	},
1154}
1155
1156func TestLimitedVisionGrid(t *testing.T) {
1157	t.Parallel()
1158	for i, test := range limitedVisionTests {
1159		l := &LimitedVisionGrid{
1160			Grid:         test.g,
1161			VisionRadius: test.radius,
1162			Location:     test.path[0],
1163		}
1164		if test.remember {
1165			l.Known = make(map[int64]bool)
1166		}
1167		l.Grid.AllowDiagonal = test.diag
1168
1169		x, y := l.XY(test.path[0].ID())
1170		nodes := graph.NodesOf(l.Nodes())
1171		for _, u := range nodes {
1172			uid := u.ID()
1173			ux, uy := l.XY(uid)
1174			uNear := math.Hypot(x-ux, y-uy) <= test.radius
1175			for _, v := range nodes {
1176				vid := v.ID()
1177				vx, vy := l.XY(vid)
1178				vNear := math.Hypot(x-vx, y-vy) <= test.radius
1179				if u.ID() == v.ID() && l.HasEdgeBetween(uid, vid) {
1180					t.Errorf("unexpected self edge: %v -- %v", u, v)
1181				}
1182				if !uNear && !vNear && !l.HasEdgeBetween(uid, vid) && couldConnectIn(l, uid, vid) {
1183					t.Errorf("unexpected pessimism: no hope in distant edge between %v and %v for test %d",
1184						u, v, i)
1185				}
1186				if (uNear && vNear) && l.HasEdgeBetween(uid, vid) != l.Grid.HasEdgeBetween(uid, vid) {
1187					t.Errorf("unrealistic optimism: disagreement about edge between %v and %v for test %d: got:%t want:%t",
1188						u, v, i, l.HasEdgeBetween(uid, vid), l.Grid.HasEdgeBetween(uid, vid))
1189				}
1190			}
1191		}
1192
1193		var got []changes
1194		for _, n := range test.path {
1195			new, old := l.MoveTo(n)
1196			got = append(got, changes{n: n, new: asConcreteEdges(new, l), old: asConcreteEdges(old, l)})
1197		}
1198		if !reflect.DeepEqual(got, test.want) {
1199			t.Errorf("unexpected walk for test %d:\ngot: %+v\nwant:%+v", i, got, test.want)
1200		}
1201	}
1202}
1203
1204func asConcreteEdges(changes []graph.Edge, in graph.Weighted) []simple.WeightedEdge {
1205	if changes == nil {
1206		return nil
1207	}
1208	we := make([]simple.WeightedEdge, len(changes))
1209	for i, e := range changes {
1210		we[i].F = e.From()
1211		we[i].T = e.To()
1212		w, ok := in.Weight(e.From().ID(), e.To().ID())
1213		if !ok && !math.IsInf(w, 1) {
1214			panic("unexpected invalid finite weight")
1215		}
1216		we[i].W = w
1217	}
1218	return we
1219}
1220
1221func couldConnectIn(l *LimitedVisionGrid, uid, vid int64) bool {
1222	if uid == vid {
1223		return false
1224	}
1225
1226	ur, uc := l.RowCol(uid)
1227	vr, vc := l.RowCol(vid)
1228	if abs(ur-vr) > 1 || abs(uc-vc) > 1 {
1229		return false
1230	}
1231	if (ur != vr || uc != vc) && !l.Grid.AllowDiagonal {
1232		return false
1233	}
1234
1235	if !l.Known[uid] && !l.Known[vid] {
1236		return true
1237	}
1238	if l.Known[uid] && !l.Grid.HasOpen(uid) {
1239		return false
1240	}
1241	if l.Known[vid] && !l.Grid.HasOpen(vid) {
1242		return false
1243	}
1244
1245	return true
1246}
1247