1#[cfg(test)]
2use std::collections::HashMap;
3use std::collections::HashSet;
4
5use crate::{graph::{Edge, Graph}};
6use crate::node::Node;
7#[cfg(test)]
8use crate::search::AStar;
9#[cfg(test)]
10use crate::search::breadth_first::{BiBreadthFirstSearch, BreadthFirstSearch};
11#[cfg(test)]
12use crate::search::depth_first::DepthFirstSearch;
13#[cfg(test)]
14use crate::search::dijkstra::Dijkstra;
15
16#[derive(Clone)]
17pub(crate) struct Waypoint {
18 pub leg: Option<Edge>,
19 pub previous: Option<Box<Waypoint>>,
20 pub node: Node,
21}
22
23impl Waypoint {
24 pub fn from(edge: Option<Edge>, node: Node, previous: Option<Box<Waypoint>>) -> Waypoint {
25 return Waypoint {
26 leg: edge,
27 previous,
28 node,
29 };
30 }
31}
32
33pub trait PathFinding {
34 fn execute(&self, source: Node, target: Node, graph: &Graph) -> Graph;
35}
36
37pub fn find(source: usize, target: usize, graph: &Graph, path_finding: Box<dyn PathFinding>) -> Graph {
38 let source_node = graph.nodes_lookup.get(&source);
39 let target_node = graph.nodes_lookup.get(&target);
40
41 if source_node.is_none() || target_node.is_none() {
42 return Graph::from(Vec::new());
43 };
44
45 return path_finding.execute(source_node.unwrap().clone(), target_node.unwrap().clone(), graph);
46}
47
48pub(crate) fn walk_back(waypoint: Waypoint) -> HashSet<Edge> {
49 let mut edges = HashSet::new();
50 let mut path = Some(Box::new(waypoint));
51
52 while path.is_some() {
53 let current = path.unwrap();
54 let leg = current.leg;
55 let previous = current.previous;
56 path = previous.clone();
57 if leg.is_some() {
58 edges.insert(leg.unwrap());
59 }
60 }
61
62 return edges;
63}
64
65
66#[test]
69fn walk_back_with_only_one_waypoint_should_succeed() {
70 let waypoint = Waypoint::from(Some(Edge::from(0, 0, 1, 1.0)), Node {
71 id: 1,
72 edges: Vec::new(),
73 }, None);
74
75 let mut sum_weight = 0.0;
76 for edge in walk_back(waypoint) {
77 sum_weight += edge.weight;
78 }
79
80 assert_eq!(1.0, sum_weight)
81}
82
83#[test]
84fn walk_back_without_leg_should_succeed() {
85 let waypoint = Waypoint::from(None, Node {
86 id: 1,
87 edges: Vec::new(),
88 }, None);
89
90 let edges = walk_back(waypoint);
91 assert_eq!(0, edges.len());
92}
93
94
95#[test]
96fn walk_back_with_path_should_succeed() {
97 let edges = walk_back(stubbed_path());
98 let mut sum_weight = 0.0;
99 for edge in &edges {
100 sum_weight += edge.weight;
101 }
102
103 assert_eq!(10.0, sum_weight);
104 assert_eq!(10, edges.len());
105}
106
107#[test]
108fn should_find_path_with_depth_first_search_in_undirected_graph() {
109 let graph = undirected_graph();
110 let dfs = find(0, 2, &graph, Box::from(DepthFirstSearch {}));
111
112 let mut total_cost: f32 = 0.0;
113 for edge in dfs.edges {
114 total_cost += edge.weight;
115 }
116
117 assert_eq!(1.4285715, total_cost);
118}
119
120#[test]
121fn should_find_path_with_depth_first_search_in_directed_graph() {
122 let dfs = find(4, 1, &directed_graph(), Box::from(DepthFirstSearch {}));
123
124 let mut total_cost: f32 = 0.0;
125 for edge in dfs.edges {
126 total_cost += edge.weight;
127 }
128
129 assert_eq!(39.0, total_cost);
130}
131
132#[test]
133fn should_find_path_with_breadth_first_search_in_undirected_graph() {
134 let graph = undirected_graph();
135 let bfs = find(0, 2, &graph,
136 Box::from(crate::search::breadth_first::BreadthFirstSearch {}));
137
138 let mut total_cost: f32 = 0.0;
139 for edge in bfs.edges {
140 total_cost += edge.weight;
141 }
142
143 assert_eq!(0.2857143, total_cost);
144}
145
146#[test]
147fn should_find_path_with_breadth_first_search_in_directed_graph() {
148 let bfs = find(4, 1, &directed_graph(), Box::from(BreadthFirstSearch {}));
149
150 let mut total_cost: f32 = 0.0;
151 for edge in bfs.edges {
152 total_cost += edge.weight;
153 }
154
155 assert_eq!(39.0, total_cost);
156}
157
158#[test]
159fn should_find_path_with_bi_breadth_first_search_in_undirected_graph() {
160 let graph = undirected_graph();
161 let bfs = find(0, 2, &graph, Box::from(BreadthFirstSearch {}));
162
163 let mut total_cost: f32 = 0.0;
164 for edge in bfs.edges {
165 total_cost += edge.weight;
166 }
167
168 assert_eq!(0.2857143, total_cost);
169}
170
171#[test]
172fn should_find_path_with_bi_breadth_first_search_in_directed_graph() {
173 let bfs = find(4, 1, &directed_graph(), Box::from(BiBreadthFirstSearch {}));
174
175 let mut total_cost: f32 = 0.0;
176 for edge in bfs.edges {
177 total_cost += edge.weight;
178 }
179
180 assert_eq!(39.0, total_cost);
181}
182
183#[test]
184fn should_find_path_with_one_edge() {
185 let mut edges = Vec::new();
186 edges.push(Edge::from(0, 0, 1, 1.0));
187 let bfs = find(0, 1, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
188
189 let mut total_cost: f32 = 0.0;
190 for edge in &bfs.edges {
191 total_cost += edge.weight;
192 }
193
194 assert_eq!(1.0, total_cost);
195 assert_eq!(1, bfs.edges.len());
196}
197
198#[test]
199fn should_not_find_path_with_same_target_and_source() {
200 let mut edges = Vec::new();
201 edges.push(Edge::from(0, 0, 1, 1.0));
202 let bfs = find(1, 1, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
203
204 let mut total_cost: f32 = 0.0;
205 for edge in &bfs.edges {
206 total_cost += edge.weight;
207 }
208
209 assert_eq!(0.0, total_cost);
210 assert_eq!(0, bfs.edges.len());
211}
212
213#[test]
214fn should_not_find_path_with_unknown_target() {
215 let mut edges = Vec::new();
216 edges.push(Edge::from(0, 0, 1, 1.0));
217 let bfs = find(0, 2, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
218
219 let mut total_cost: f32 = 0.0;
220 for edge in &bfs.edges {
221 total_cost += edge.weight;
222 }
223
224 assert_eq!(0.0, total_cost);
225 assert_eq!(0, bfs.edges.len());
226}
227
228#[test]
229fn should_not_find_path_with_unknown_source() {
230 let mut edges = Vec::new();
231 edges.push(Edge::from(0, 0, 1, 1.0));
232 let bfs = find(2, 0, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
233
234 let mut total_cost: f32 = 0.0;
235 for edge in &bfs.edges {
236 total_cost += edge.weight;
237 }
238
239 assert_eq!(0.0, total_cost);
240 assert_eq!(0, bfs.edges.len());
241}
242
243#[test]
244fn should_find_path_with_source_and_target_reversed() {
245 let mut edges = Vec::new();
246 edges.push(Edge::from(0, 0, 1, 1.0));
247 let bfs = find(1, 0, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
248
249 let mut total_cost: f32 = 0.0;
250 for edge in &bfs.edges {
251 total_cost += edge.weight;
252 }
253
254 assert_eq!(1.0, total_cost);
255 assert_eq!(1, bfs.edges.len());
256}
257
258#[cfg(test)]
259fn a_star_edges() -> Vec<Edge> {
260 return Vec::from([
261 Edge::from(0, 0, 1, 1.0),
262 Edge::from(1, 0, 2, 1.0),
263 Edge::from(2, 1, 3, 1.0),
264 Edge::from(3, 2, 3, 2.0),
265 Edge::from(4, 3, 4, 3.0),
266 ]);
267}
268
269#[cfg(test)]
270fn inconsistent(source: usize, destination: usize, _graph: &Graph) -> f32 {
271 return HashMap::from([
272 ((0, 4), 2.0),
273 ((1, 4), 4.0),
274 ((2, 4), 1.0),
275 ((3, 4), 1.0),
276 ((4, 4), 0.0)
277 ]).get(&(source, destination)).unwrap().clone();
278}
279
280#[test]
281fn should_find_path_with_a_star_and_inconsistent_heuristic() {
282 let a_star = find(0, 4, &Graph::from(a_star_edges()),
283 Box::from( AStar { heuristic: Box::from(inconsistent) }));
284
285 let mut total_cost: f32 = 0.0;
286 for edge in &a_star.edges {
287 total_cost += edge.weight;
288 }
289
290 assert_eq!(6.0, total_cost);
291 assert_eq!(3, a_star.edges.len());
292}
293
294#[cfg(test)]
295fn consistent(source: usize, destination: usize, _graph: &Graph) -> f32 {
296 return HashMap::from([
297 ((0, 4), 2.0),
298 ((1, 4), 1.0),
299 ((2, 4), 1.0),
300 ((3, 4), 1.0),
301 ((4, 4), 0.0)
302 ]).get(&(source, destination)).unwrap().clone();
303}
304
305#[test]
306fn should_find_path_with_a_star_and_consistent_heuristic() {
307 let algo = AStar { heuristic: Box::from(consistent) };
308 let a_star = find(0, 4, &Graph::from(a_star_edges()),
309 Box::from(algo));
310
311 let mut total_cost: f32 = 0.0;
312 for edge in &a_star.edges {
313 total_cost += edge.weight;
314 }
315
316 assert_eq!(5.0, total_cost);
317 assert_eq!(3, a_star.edges.len());
318}
319
320#[test]
321fn should_find_path_with_bi_breadth_first_search_in_graphs_with_one_connection() {
322 let bfs = find(0, 13, &graphs_with_one_connection(),
323 Box::from(BiBreadthFirstSearch {}));
324
325 let mut total_cost: f32 = 0.0;
326 for edge in bfs.edges {
327 total_cost += edge.weight;
328 }
329
330 assert_eq!(50.0, total_cost);
331}
332
333#[test]
334fn should_find_path_with_dijkstra_in_graphs_with_one_connection() {
335 let dijkstra = find(0, 13, &graphs_with_one_connection(),
336 Box::from(Dijkstra {}));
337
338 let mut total_cost: f32 = 0.0;
339 for edge in dijkstra.edges {
340 total_cost += edge.weight;
341 }
342
343 assert_eq!(50.0, total_cost);
344}
345
346#[cfg(test)]
347fn undirected_graph() -> Graph {
348 let edge1 = Edge::from(0, 1, 2, 0.0);
349 let edge2 = Edge::from(1, 2, 1, 0.0);
350 let edge3 = Edge::from(2, 2, 3, 0.1428571429);
351 let edge4 = Edge::from(3, 3, 2, 0.1428571429);
352 let edge5 = Edge::from(4, 1, 0, 0.2857142857);
353 let edge6 = Edge::from(5, 0, 1, 0.2857142857);
354 let edge7 = Edge::from(6, 3, 4, 0.2857142857);
355 let edge8 = Edge::from(7, 4, 3, 0.2857142857);
356 let edge9 = Edge::from(8, 1, 3, 0.4285714286);
357 let edge10 = Edge::from(9, 3, 1, 0.4285714286);
358 let edge11 = Edge::from(10, 0, 3, 0.8571428571);
359 let edge12 = Edge::from(11, 3, 0, 0.8571428571);
360 let edge13 = Edge::from(12, 0, 4, 1.0);
361 let edge14 = Edge::from(13, 4, 0, 1.0);
362
363
364 return Graph::from(Vec::from([edge1, edge2, edge3, edge4, edge5, edge6, edge7,
365 edge8, edge9, edge10, edge11, edge12, edge13, edge14]));
366}
367
368#[cfg(test)]
369fn directed_graph() -> Graph {
370 let edge1 = Edge::from(0, 4, 0, 7.0);
371 let edge2 = Edge::from(1, 0, 2, 12.0);
372 let edge3 = Edge::from(2, 0, 3, 60.0);
373 let edge4 = Edge::from(3, 2, 1, 20.0);
374 let edge5 = Edge::from(4, 2, 3, 32.0);
375 let edge6 = Edge::from(5, 1, 0, 10.0);
376
377 return Graph::from(Vec::from([edge1, edge2, edge3, edge4, edge5, edge6]));
378}
379
380#[cfg(test)]
381fn graphs_with_one_connection() -> Graph {
382 let edge1 = Edge::from(0, 0, 4, 1.0);
383 let edge2 = Edge::from(1, 1, 4, 2.0);
384 let edge3 = Edge::from(2, 4, 6, 3.0);
385 let edge4 = Edge::from(3, 3, 5, 4.0);
386 let edge5 = Edge::from(4, 2, 5, 5.0);
387 let edge6 = Edge::from(5, 5, 6, 6.0);
388 let edge7 = Edge::from(6, 6, 7, 7.0);
389
390 let edge8 = Edge::from(7, 11, 9, 8.0);
391 let edge9 = Edge::from(8, 12, 9, 9.0);
392 let edge10 = Edge::from(9, 9, 8, 10.0);
393 let edge11 = Edge::from(10, 14, 10, 11.0);
394 let edge12 = Edge::from(11, 13, 10, 12.0);
395 let edge13 = Edge::from(12, 10, 8, 13.0);
396 let edge14 = Edge::from(13, 8, 7, 14.0);
397
398 let edge15 = Edge::from(14, 4, 0, 1.0);
399 let edge16 = Edge::from(15, 4, 1, 2.0);
400 let edge17 = Edge::from(16, 6, 4, 3.0);
401 let edge18 = Edge::from(17, 5, 3, 4.0);
402 let edge19 = Edge::from(18, 5, 2, 5.0);
403 let edge20 = Edge::from(19, 6, 5, 6.0);
404 let edge21 = Edge::from(20, 7, 6, 7.0);
405
406 let edge22 = Edge::from(21, 9, 11, 8.0);
407 let edge23 = Edge::from(22, 9, 12, 9.0);
408 let edge24 = Edge::from(23, 8, 9, 10.0);
409 let edge25 = Edge::from(24, 10, 14, 11.0);
410 let edge26 = Edge::from(25, 10, 13, 12.0);
411 let edge27 = Edge::from(26, 8, 10, 13.0);
412 let edge28 = Edge::from(27, 7, 8, 14.0);
413
414 return Graph::from(Vec::from([edge1, edge2, edge3, edge4, edge5, edge6, edge7, edge8,
415 edge9, edge10, edge11, edge12, edge13, edge14, edge15, edge16, edge17, edge18, edge19, edge20,
416 edge21, edge22, edge23, edge24, edge25, edge26, edge27, edge28]));
417}
418
419#[cfg(test)]
420fn stubbed_path() -> Waypoint {
421 let start_point = Waypoint::from(Some(Edge::from(0, 0, 1, 1.0)), Node {
422 id: 0,
423 edges: Vec::new(),
424 }, None);
425
426 let mut current = start_point;
427 for i in 0..10 {
428 let edge_stub = Some(Edge::from(i, 0, 1, 1.0));
429 current = Waypoint::from(edge_stub.clone(), Node {
430 id: 0,
431 edges: Vec::new(),
432 }, Some(Box::from(current.clone())))
433 }
434
435 return current.clone();
436}