-
Notifications
You must be signed in to change notification settings - Fork 299
/
Copy pathAStar_Tests.cs
277 lines (245 loc) · 10.6 KB
/
AStar_Tests.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
using System;
using System.Collections.Generic;
using System.IO;
using Advanced.Algorithms.DataStructures.Graph.AdjacencyList;
using Advanced.Algorithms.Geometry;
using Advanced.Algorithms.Graph;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace Advanced.Algorithms.Tests.Graph
{
[TestClass]
public class AStarTests
{
//test using eucledian (straight line) distance to destination as heuristic.
[TestMethod]
public void AStar_AdjacencyListGraph_Smoke_Test()
{
var testLocations = @"A5 30 573
A4 30 483
A2 30 178
A1 30 48
B1 207 48
B2 207 161
B3 144 339
B4 129 443
B5 127 479
C2 258 162
C3 240 288
C4 225 443
C5 336 573
D1 438 48
D2 438 174
D3 438 335
D4 438 473
D5 438 573
E4 575 475
E5 684 493
F1 611 48
F2 600 173
F5 701 573
G1 797 48
G2 797 150
G2b 770 151
G4 797 382
G4b 770 382
G5 797 573";
var locationMappings = new Dictionary<string, Location>();
var graph = new WeightedDiGraph<Location, double>();
using (var reader = new StringReader(testLocations))
{
string line;
while ((line = reader.ReadLine()?.Trim()) != null)
{
var @params = line.Split(' ');
var location = new Location
{
Point = new Point(double.Parse(@params[1]), double.Parse(@params[2])),
Name = @params[0]
};
locationMappings.Add(@params[0], location);
graph.AddVertex(location);
}
}
var testConnections = @"A1 2 B1 A2
A2 3 A1 B2 A4
A4 3 A2 B5 A5
A5 2 A4 C5
B1 3 A1 D1 B2
B2 4 C2 C3 A2 B1
B3 1 B4
B4 3 B3 B5 C4
B5 3 A4 C5 B4
C2 3 D2 B2 C3
C3 3 C2 B2 C4
C4 3 B4 C3 D4
C5 3 D5 B5 A5
D1 3 B1 F1 D2
D2 3 C2 D1 F2
D3 1 D4
D4 4 D3 C4 E4 D5
D5 3 C5 D4 F5
E4 3 D4 E5 F2
F1 3 F2 D1 G1
F2 4 F1 D2 G2b E4
F5 3 E5 G5 D5
G1 2 G2 F1
G2 3 G1 G2b G4
G2b 3 G2 F2 G4b
G4 3 G4b G2 G5
G4b 3 G4 G2b E5
G5 2 F5 G4
E5 3 F5 E4 G4b";
using (var reader = new StringReader(testConnections))
{
string line;
while ((line = reader.ReadLine()?.Trim()) != null)
{
var @params = line.Split(' ');
for (var i = 2; i < int.Parse(@params[1]) + 2; i++)
graph.AddEdge(locationMappings[@params[0]], locationMappings[@params[i]],
EucledianDistanceCalculator.GetEucledianDistance(locationMappings[@params[0]].Point,
locationMappings[@params[i]].Point));
}
}
var algorithm =
new AStarShortestPath<Location, double>(new AStarShortestPathOperators(), new AStarSearchHeuristic());
var result = algorithm.FindShortestPath(graph, locationMappings["A1"], locationMappings["G5"]);
Assert.AreEqual(10, result.Path.Count);
Assert.AreEqual(1217.3209396395309, result.Length);
var expectedPath = new[] { "A1", "B1", "B2", "C3", "C4", "D4", "E4", "E5", "F5", "G5" };
for (var i = 0; i < expectedPath.Length; i++) Assert.AreEqual(expectedPath[i], result.Path[i].Name);
}
//test using eucledian (straight line) distance to destination as heuristic.
[TestMethod]
public void AStar_AdjacencyMatrixGraph_Smoke_Test()
{
var testLocations = @"A5 30 573
A4 30 483
A2 30 178
A1 30 48
B1 207 48
B2 207 161
B3 144 339
B4 129 443
B5 127 479
C2 258 162
C3 240 288
C4 225 443
C5 336 573
D1 438 48
D2 438 174
D3 438 335
D4 438 473
D5 438 573
E4 575 475
E5 684 493
F1 611 48
F2 600 173
F5 701 573
G1 797 48
G2 797 150
G2b 770 151
G4 797 382
G4b 770 382
G5 797 573";
var locationMappings = new Dictionary<string, Location>();
var graph = new Algorithms.DataStructures.Graph.AdjacencyMatrix.WeightedDiGraph<Location, double>();
using (var reader = new StringReader(testLocations))
{
string line;
while ((line = reader.ReadLine()?.Trim()) != null)
{
var @params = line.Split(' ');
var location = new Location
{
Point = new Point(double.Parse(@params[1]), double.Parse(@params[2])),
Name = @params[0]
};
locationMappings.Add(@params[0], location);
graph.AddVertex(location);
}
}
var testConnections = @"A1 2 B1 A2
A2 3 A1 B2 A4
A4 3 A2 B5 A5
A5 2 A4 C5
B1 3 A1 D1 B2
B2 4 C2 C3 A2 B1
B3 1 B4
B4 3 B3 B5 C4
B5 3 A4 C5 B4
C2 3 D2 B2 C3
C3 3 C2 B2 C4
C4 3 B4 C3 D4
C5 3 D5 B5 A5
D1 3 B1 F1 D2
D2 3 C2 D1 F2
D3 1 D4
D4 4 D3 C4 E4 D5
D5 3 C5 D4 F5
E4 3 D4 E5 F2
F1 3 F2 D1 G1
F2 4 F1 D2 G2b E4
F5 3 E5 G5 D5
G1 2 G2 F1
G2 3 G1 G2b G4
G2b 3 G2 F2 G4b
G4 3 G4b G2 G5
G4b 3 G4 G2b E5
G5 2 F5 G4
E5 3 F5 E4 G4b";
using (var reader = new StringReader(testConnections))
{
string line;
while ((line = reader.ReadLine()?.Trim()) != null)
{
var @params = line.Split(' ');
for (var i = 2; i < int.Parse(@params[1]) + 2; i++)
graph.AddEdge(locationMappings[@params[0]], locationMappings[@params[i]],
EucledianDistanceCalculator.GetEucledianDistance(locationMappings[@params[0]].Point,
locationMappings[@params[i]].Point));
}
}
var algorithm =
new AStarShortestPath<Location, double>(new AStarShortestPathOperators(), new AStarSearchHeuristic());
var result = algorithm.FindShortestPath(graph, locationMappings["A1"], locationMappings["G5"]);
Assert.AreEqual(10, result.Path.Count);
Assert.AreEqual(1217.3209396395309, result.Length);
var expectedPath = new[] { "A1", "B1", "B2", "C3", "C4", "D4", "E4", "E5", "F5", "G5" };
for (var i = 0; i < expectedPath.Length; i++) Assert.AreEqual(expectedPath[i], result.Path[i].Name);
}
public class Location
{
public Point Point { get; set; }
public string Name { get; set; }
}
public class AStarSearchHeuristic : IAStarHeuristic<Location, double>
{
public double HueristicDistanceToTarget(Location sourceVertex, Location targetVertex)
{
return EucledianDistanceCalculator.GetEucledianDistance(sourceVertex.Point,
targetVertex.Point);
}
}
public class AStarShortestPathOperators : IShortestPathOperators<double>
{
public double DefaultValue => default;
public double MaxValue => double.MaxValue;
public double Sum(double a, double b)
{
return a + b;
}
}
}
public class EucledianDistanceCalculator
{
/// <summary>
/// returns the eucledian distance between given two points
/// </summary>
public static double GetEucledianDistance(Point a, Point b)
{
return Math.Sqrt(Math.Pow(Math.Abs(a.X - b.X), 2)
+ Math.Pow(Math.Abs(a.Y - b.Y), 2));
}
}
}