path_finding/
path.rs

1#[cfg(test)]
2use std::collections::HashMap;
3use std::collections::HashSet;
4
5use crate::{graph::{Edge, Graph}};
6use crate::grid::{Direction, Grid};
7use crate::node::Node;
8#[cfg(test)]
9use crate::node::Vec3;
10#[cfg(test)]
11use crate::search::AStar;
12#[cfg(test)]
13use crate::search::breadth_first::BreadthFirstSearch;
14#[cfg(test)]
15use crate::search::breadth_first_bi::BiBreadthFirstSearch;
16#[cfg(test)]
17use crate::search::cost::INFINITY;
18#[cfg(test)]
19use crate::search::depth_first::DepthFirstSearch;
20#[cfg(test)]
21use crate::search::dijkstra::Dijkstra;
22
23#[derive(Clone)]
24pub(crate) struct Waypoint {
25    pub leg: Option<Edge>,
26    pub previous: Option<Box<Waypoint>>,
27    pub node_id: usize,
28}
29
30impl Waypoint {
31    pub fn from(edge: Option<Edge>, node_id: usize, previous: Option<Box<Waypoint>>) -> Waypoint {
32        return Waypoint {
33            leg: edge,
34            previous,
35            node_id,
36        };
37    }
38}
39
40pub trait PathFinding {
41    fn graph(&self, source: Node, target: Node, graph: &Graph) -> Graph;
42    fn grid(&self, source: (usize, usize), target: (usize, usize), grid: &Grid, directions: &[Direction]) -> Graph;
43}
44
45pub fn in_graph(source: usize, target: usize, graph: &Graph, path_finding: Box<dyn PathFinding>) -> Graph {
46    let source_node = graph.nodes_lookup.get(&source);
47    let target_node = graph.nodes_lookup.get(&target);
48
49    if source_node.is_none() || target_node.is_none() {
50        return Graph::from(Vec::new());
51    };
52
53    return path_finding.graph(source_node.unwrap().clone(), target_node.unwrap().clone(), graph);
54}
55
56pub fn in_grid(source: (usize, usize), target: (usize, usize),
57               grid: &Grid, path_finding: Box<dyn PathFinding>, directions: &[Direction]) -> Graph {
58    if grid.outside(source) || grid.outside(target) {
59        return Graph::from(Vec::new());
60    };
61
62    return path_finding.grid(source, target, grid, directions);
63}
64
65pub(crate) fn walk_back(waypoint: Waypoint) -> Vec<Edge> {
66    let mut edges = HashSet::new();
67    let mut path = Some(waypoint);
68
69    while let Some(current) = path {
70        if let Some(leg) = current.leg {
71            edges.insert(leg);
72        }
73        path = current.previous.map(|previous| *previous);
74    }
75
76    Vec::from_iter(edges)
77}
78
79
80// Testing
81#[cfg(test)]
82fn test_grid() -> Grid {
83    return Grid::from(&[
84        &[0.0, 0.0, 0.0, INFINITY, 0.0],
85        &[INFINITY, 0.0, 0.0, INFINITY, INFINITY],
86        &[0.0, 0.0, 0.0, INFINITY, 0.0],
87        &[INFINITY, 0.0, 0.0, 0.0, 0.0],
88        &[0.0, 0.0, INFINITY, 0.0, 0.0],
89    ]);
90}
91
92#[test]
93fn depth_first_search_in_grid_should_be_successful() {
94    let grid = test_grid();
95
96    let dfs = in_grid((0, 0), (4, 4), &grid, Box::from(DepthFirstSearch {}), &[
97        Direction::Up,
98        Direction::Down,
99        Direction::Left,
100        Direction::Right,
101        Direction::UpLeft,
102        Direction::UpRight,
103        Direction::DownLeft,
104        Direction::DownRight,
105    ]);
106
107    assert_eq!(4, dfs.edges.len())
108}
109
110#[test]
111fn depth_first_search_in_grid_should_be_successful_with_only_four_directions() {
112    let grid = test_grid();
113    let dfs = in_grid((0, 0), (4, 4), &grid, Box::from(DepthFirstSearch {}), &[
114        Direction::Down,
115        Direction::Right,
116        Direction::Up,
117        Direction::Left
118    ]);
119
120    assert_eq!(10, dfs.edges.len())
121}
122
123#[test]
124fn breadth_first_search_should_be_successful() {
125    let grid = test_grid();
126    let dfs = in_grid((0, 0), (4, 4), &grid, Box::from(BreadthFirstSearch {}), &[
127        Direction::Down,
128        Direction::Right,
129        Direction::Up,
130        Direction::Left
131    ]);
132
133    assert_eq!(8, dfs.edges.len())
134}
135
136#[test]
137fn bi_breadth_first_search_in_grid_should_be_successful() {
138    let grid = test_grid();
139
140    let bi_bfs = in_grid((0, 0), (4, 4), &grid, Box::from(BiBreadthFirstSearch {}), &[
141        Direction::Up,
142        Direction::Down,
143        Direction::Left,
144        Direction::Right,
145        Direction::UpLeft,
146        Direction::UpRight,
147        Direction::DownLeft,
148        Direction::DownRight,
149    ]);
150
151    assert_eq!(4, bi_bfs.edges.len())
152}
153
154#[test]
155fn bi_breadth_first_search_should_be_successful() {
156    let grid = test_grid();
157    let bi_bfs = in_grid((0, 0), (4, 4), &grid, Box::from(BiBreadthFirstSearch {}), &[
158        Direction::Down,
159        Direction::Right,
160        Direction::Up,
161        Direction::Left
162    ]);
163
164    assert_eq!(8, bi_bfs.edges.len())
165}
166
167#[cfg(test)]
168fn dijkstra_grid() -> Grid {
169    return Grid::from(&[
170        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
171        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
172        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
173        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
174        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
175        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, INFINITY],
176        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
177        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
178        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, 1.0, 1.0, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
179        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, 1.0, 2.0, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
180        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, 1.0, 1.0, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
181        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
182        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, 1.0, 1.0, 1.0, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
183        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
184        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
185        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
186        &[INFINITY, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, INFINITY],
187        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
188    ]);
189}
190
191#[cfg(test)]
192fn dijkstra_grid_with_short_cut() -> Grid {
193    return Grid::from(&[
194        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
195        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
196        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
197        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
198        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
199        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, INFINITY],
200        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
201        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
202        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, 1.0, 1.0, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
203        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, 1.0, 2.0, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
204        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, 1.0, 1.0, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
205        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
206        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, 1.0, 1.0, 1.0, 1.0, INFINITY, INFINITY, 1.0, INFINITY],
207        &[INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
208        &[INFINITY, INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
209        &[INFINITY, INFINITY, 1.0, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1.0, INFINITY],
210        &[INFINITY, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, INFINITY],
211        &[INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY],
212    ]);
213}
214
215#[test]
216fn dijkstra_in_grid_should_be_successful() {
217    let grid = dijkstra_grid();
218
219    let dijkstra = in_grid((16, 1), (9, 7), &grid, Box::from(Dijkstra {}), &[
220        Direction::Up,
221        Direction::Down,
222        Direction::Left,
223        Direction::Right,
224        Direction::UpLeft,
225        Direction::UpRight,
226        Direction::DownLeft,
227        Direction::DownRight,
228    ]);
229
230
231    assert_eq!(47, dijkstra.edges.len())
232}
233
234#[test]
235fn dijkstra_in_grid_with_short_cut_should_be_successful() {
236    let grid = dijkstra_grid_with_short_cut();
237
238    let dijkstra = in_grid((16, 1), (9, 7), &grid, Box::from(Dijkstra {}), &[
239        Direction::Up,
240        Direction::Down,
241        Direction::Left,
242        Direction::Right,
243        Direction::UpLeft,
244        Direction::UpRight,
245        Direction::DownLeft,
246        Direction::DownRight,
247    ]);
248
249    assert_eq!(16, dijkstra.edges.len())
250}
251
252#[test]
253fn walk_back_with_only_one_waypoint_should_succeed() {
254    let waypoint = Waypoint::from(Some(Edge::from(0, 0, 1, 1.0)), 1, None);
255
256    let mut sum_weight = 0.0;
257    for edge in walk_back(waypoint) {
258        sum_weight += edge.weight;
259    }
260
261    assert_eq!(1.0, sum_weight)
262}
263
264#[test]
265fn walk_back_without_leg_should_succeed() {
266    let waypoint = Waypoint::from(None, 1, None);
267
268    let edges = walk_back(waypoint);
269    assert_eq!(0, edges.len());
270}
271
272
273#[test]
274fn walk_back_with_path_should_succeed() {
275    let edges = walk_back(stubbed_path());
276    let mut sum_weight = 0.0;
277    for edge in &edges {
278        sum_weight += edge.weight;
279    }
280
281    assert_eq!(10.0, sum_weight);
282    assert_eq!(10, edges.len());
283}
284
285#[test]
286fn should_find_path_with_depth_first_search_in_undirected_graph() {
287    let graph = undirected_graph();
288    let dfs = in_graph(0, 2, &graph, Box::from(DepthFirstSearch {}));
289
290    let mut total_cost: f32 = 0.0;
291    for edge in dfs.edges {
292        total_cost += edge.weight;
293    }
294
295    assert_eq!(1.4285715, total_cost);
296}
297
298#[test]
299fn should_find_path_with_depth_first_search_in_directed_graph() {
300    let dfs = in_graph(4, 1, &directed_graph(), Box::from(DepthFirstSearch {}));
301
302    let mut total_cost: f32 = 0.0;
303    for edge in dfs.edges {
304        total_cost += edge.weight;
305    }
306
307    assert_eq!(39.0, total_cost);
308}
309
310#[test]
311fn should_find_path_with_breadth_first_search_in_undirected_graph() {
312    let graph = undirected_graph();
313    let bfs = in_graph(0, 2, &graph,
314                       Box::from(crate::search::breadth_first::BreadthFirstSearch {}));
315
316    let mut total_cost: f32 = 0.0;
317    for edge in bfs.edges {
318        total_cost += edge.weight;
319    }
320
321    assert_eq!(0.2857143, total_cost);
322}
323
324#[test]
325fn should_find_path_with_breadth_first_search_in_directed_graph() {
326    let bfs = in_graph(4, 1, &directed_graph(), Box::from(BreadthFirstSearch {}));
327
328    let mut total_cost: f32 = 0.0;
329    for edge in bfs.edges {
330        total_cost += edge.weight;
331    }
332
333    assert_eq!(39.0, total_cost);
334}
335
336#[test]
337fn should_find_path_with_bi_breadth_first_search_in_undirected_graph() {
338    let graph = undirected_graph();
339    let bfs = in_graph(0, 2, &graph, Box::from(BreadthFirstSearch {}));
340
341    let mut total_cost: f32 = 0.0;
342    for edge in bfs.edges {
343        total_cost += edge.weight;
344    }
345
346    assert_eq!(0.2857143, total_cost);
347}
348
349#[test]
350fn should_find_path_with_bi_breadth_first_search_in_directed_graph() {
351    let bfs = in_graph(4, 1, &directed_graph(), Box::from(BiBreadthFirstSearch {}));
352
353    let mut total_cost: f32 = 0.0;
354    for edge in bfs.edges {
355        total_cost += edge.weight;
356    }
357
358    assert_eq!(39.0, total_cost);
359}
360
361#[test]
362fn should_find_path_with_one_edge() {
363    let mut edges = Vec::new();
364    edges.push(Edge::from(0, 0, 1, 1.0));
365    let bfs = in_graph(0, 1, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
366
367    let mut total_cost: f32 = 0.0;
368    for edge in &bfs.edges {
369        total_cost += edge.weight;
370    }
371
372    assert_eq!(1.0, total_cost);
373    assert_eq!(1, bfs.edges.len());
374}
375
376#[test]
377fn should_not_find_path_with_same_target_and_source() {
378    let mut edges = Vec::new();
379    edges.push(Edge::from(0, 0, 1, 1.0));
380    let bfs = in_graph(1, 1, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
381
382    let mut total_cost: f32 = 0.0;
383    for edge in &bfs.edges {
384        total_cost += edge.weight;
385    }
386
387    assert_eq!(0.0, total_cost);
388    assert_eq!(0, bfs.edges.len());
389}
390
391#[test]
392fn should_not_find_path_with_unknown_target() {
393    let mut edges = Vec::new();
394    edges.push(Edge::from(0, 0, 1, 1.0));
395    let bfs = in_graph(0, 2, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
396
397    let mut total_cost: f32 = 0.0;
398    for edge in &bfs.edges {
399        total_cost += edge.weight;
400    }
401
402    assert_eq!(0.0, total_cost);
403    assert_eq!(0, bfs.edges.len());
404}
405
406#[test]
407fn should_not_find_path_with_unknown_source() {
408    let mut edges = Vec::new();
409    edges.push(Edge::from(0, 0, 1, 1.0));
410    let bfs = in_graph(2, 0, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
411
412    let mut total_cost: f32 = 0.0;
413    for edge in &bfs.edges {
414        total_cost += edge.weight;
415    }
416
417    assert_eq!(0.0, total_cost);
418    assert_eq!(0, bfs.edges.len());
419}
420
421#[test]
422fn should_find_path_with_source_and_target_reversed() {
423    let mut edges = Vec::new();
424    edges.push(Edge::from(0, 0, 1, 1.0));
425    let bfs = in_graph(1, 0, &Graph::from(edges), Box::from(BiBreadthFirstSearch {}));
426
427    let mut total_cost: f32 = 0.0;
428    for edge in &bfs.edges {
429        total_cost += edge.weight;
430    }
431
432    assert_eq!(1.0, total_cost);
433    assert_eq!(1, bfs.edges.len());
434}
435
436#[cfg(test)]
437fn inconsistent(source: &Vec3, destination: &Vec3) -> f32 {
438    return HashMap::from([
439        ((&Vec3::from(0.0, 0.0, 0.0), &Vec3::from(0.0, 0.0, 0.4)), 2.0),
440        ((&Vec3::from(0.0, 0.0, 0.1), &Vec3::from(0.0, 0.0, 0.4)), 4.0),
441        ((&Vec3::from(0.0, 0.0, 0.2), &Vec3::from(0.0, 0.0, 0.4)), 1.0),
442        ((&Vec3::from(0.0, 0.0, 0.3), &Vec3::from(0.0, 0.0, 0.4)), 1.0),
443        ((&Vec3::from(0.0, 0.0, 0.4), &Vec3::from(0.0, 0.0, 0.4)), 0.0)
444    ]).get(&(source, destination)).unwrap().clone();
445}
446
447#[cfg(test)]
448fn a_star_graph() -> Graph {
449    let mut graph = Graph::from(Vec::from([
450        Edge::from(0, 0, 1, 1.0),
451        Edge::from(1, 0, 2, 1.0),
452        Edge::from(2, 1, 3, 1.0),
453        Edge::from(3, 2, 3, 2.0),
454        Edge::from(4, 3, 4, 3.0),
455    ]));
456
457    graph.offer_positions(HashMap::from([
458        (0, Vec3::from(0.0, 0.0, 0.0)),
459        (1, Vec3::from(0.0, 0.0, 0.1)),
460        (2, Vec3::from(0.0, 0.0, 0.2)),
461        (3, Vec3::from(0.0, 0.0, 0.3)),
462        (4, Vec3::from(0.0, 0.0, 0.4)),
463    ]));
464
465    return graph;
466}
467
468#[test]
469fn should_find_path_with_a_star_and_inconsistent_heuristic() {
470    let a_star = in_graph(0, 4, &a_star_graph(),
471                          Box::from(AStar { heuristic: Box::from(inconsistent) }));
472
473    let mut total_cost: f32 = 0.0;
474    for edge in &a_star.edges {
475        total_cost += edge.weight;
476    }
477
478    assert_eq!(6.0, total_cost);
479    assert_eq!(3, a_star.edges.len());
480}
481
482#[cfg(test)]
483fn consistent(source: &Vec3, destination: &Vec3) -> f32 {
484    return HashMap::from([
485        ((&Vec3::from(0.0, 0.0, 0.0), &Vec3::from(0.0, 0.0, 0.4)), 2.0),
486        ((&Vec3::from(0.0, 0.0, 0.1), &Vec3::from(0.0, 0.0, 0.4)), 1.0),
487        ((&Vec3::from(0.0, 0.0, 0.2), &Vec3::from(0.0, 0.0, 0.4)), 1.0),
488        ((&Vec3::from(0.0, 0.0, 0.3), &Vec3::from(0.0, 0.0, 0.4)), 1.0),
489        ((&Vec3::from(0.0, 0.0, 0.4), &Vec3::from(0.0, 0.0, 0.4)), 0.0)
490    ]).get(&(source, destination)).unwrap().clone();
491}
492
493#[test]
494fn should_find_path_with_a_star_and_consistent_heuristic() {
495    let algo = AStar { heuristic: Box::from(consistent) };
496    let a_star = in_graph(0, 4, &a_star_graph(), Box::from(algo));
497
498    let mut total_cost: f32 = 0.0;
499    for edge in &a_star.edges {
500        total_cost += edge.weight;
501    }
502
503    assert_eq!(5.0, total_cost);
504    assert_eq!(3, a_star.edges.len());
505}
506
507#[test]
508fn should_find_path_with_bi_breadth_first_search_in_graphs_with_one_connection() {
509    let bfs = in_graph(0, 13, &graphs_with_one_connection(),
510                       Box::from(BiBreadthFirstSearch {}));
511
512    let mut total_cost: f32 = 0.0;
513    for edge in bfs.edges {
514        total_cost += edge.weight;
515    }
516
517    assert_eq!(50.0, total_cost);
518}
519
520#[test]
521fn should_find_path_with_dijkstra_in_graphs_with_one_connection() {
522    let dijkstra = in_graph(0, 13, &graphs_with_one_connection(),
523                            Box::from(Dijkstra {}));
524
525    let mut total_cost: f32 = 0.0;
526    for edge in dijkstra.edges {
527        total_cost += edge.weight;
528    }
529
530    assert_eq!(50.0, total_cost);
531}
532
533#[cfg(test)]
534fn undirected_graph() -> Graph {
535    let edge1 = Edge::from(0, 1, 2, 0.0);
536    let edge2 = Edge::from(1, 2, 1, 0.0);
537    let edge3 = Edge::from(2, 2, 3, 0.1428571429);
538    let edge4 = Edge::from(3, 3, 2, 0.1428571429);
539    let edge5 = Edge::from(4, 1, 0, 0.2857142857);
540    let edge6 = Edge::from(5, 0, 1, 0.2857142857);
541    let edge7 = Edge::from(6, 3, 4, 0.2857142857);
542    let edge8 = Edge::from(7, 4, 3, 0.2857142857);
543    let edge9 = Edge::from(8, 1, 3, 0.4285714286);
544    let edge10 = Edge::from(9, 3, 1, 0.4285714286);
545    let edge11 = Edge::from(10, 0, 3, 0.8571428571);
546    let edge12 = Edge::from(11, 3, 0, 0.8571428571);
547    let edge13 = Edge::from(12, 0, 4, 1.0);
548    let edge14 = Edge::from(13, 4, 0, 1.0);
549
550
551    return Graph::from(Vec::from([edge1, edge2, edge3, edge4, edge5, edge6, edge7,
552        edge8, edge9, edge10, edge11, edge12, edge13, edge14]));
553}
554
555#[cfg(test)]
556fn directed_graph() -> Graph {
557    let edge1 = Edge::from(0, 4, 0, 7.0);
558    let edge2 = Edge::from(1, 0, 2, 12.0);
559    let edge3 = Edge::from(2, 0, 3, 60.0);
560    let edge4 = Edge::from(3, 2, 1, 20.0);
561    let edge5 = Edge::from(4, 2, 3, 32.0);
562    let edge6 = Edge::from(5, 1, 0, 10.0);
563
564    return Graph::from(Vec::from([edge1, edge2, edge3, edge4, edge5, edge6]));
565}
566
567#[cfg(test)]
568fn graphs_with_one_connection() -> Graph {
569    let edge1 = Edge::from(0, 0, 4, 1.0);
570    let edge2 = Edge::from(1, 1, 4, 2.0);
571    let edge3 = Edge::from(2, 4, 6, 3.0);
572    let edge4 = Edge::from(3, 3, 5, 4.0);
573    let edge5 = Edge::from(4, 2, 5, 5.0);
574    let edge6 = Edge::from(5, 5, 6, 6.0);
575    let edge7 = Edge::from(6, 6, 7, 7.0);
576
577    let edge8 = Edge::from(7, 11, 9, 8.0);
578    let edge9 = Edge::from(8, 12, 9, 9.0);
579    let edge10 = Edge::from(9, 9, 8, 10.0);
580    let edge11 = Edge::from(10, 14, 10, 11.0);
581    let edge12 = Edge::from(11, 13, 10, 12.0);
582    let edge13 = Edge::from(12, 10, 8, 13.0);
583    let edge14 = Edge::from(13, 8, 7, 14.0);
584
585    let edge15 = Edge::from(14, 4, 0, 1.0);
586    let edge16 = Edge::from(15, 4, 1, 2.0);
587    let edge17 = Edge::from(16, 6, 4, 3.0);
588    let edge18 = Edge::from(17, 5, 3, 4.0);
589    let edge19 = Edge::from(18, 5, 2, 5.0);
590    let edge20 = Edge::from(19, 6, 5, 6.0);
591    let edge21 = Edge::from(20, 7, 6, 7.0);
592
593    let edge22 = Edge::from(21, 9, 11, 8.0);
594    let edge23 = Edge::from(22, 9, 12, 9.0);
595    let edge24 = Edge::from(23, 8, 9, 10.0);
596    let edge25 = Edge::from(24, 10, 14, 11.0);
597    let edge26 = Edge::from(25, 10, 13, 12.0);
598    let edge27 = Edge::from(26, 8, 10, 13.0);
599    let edge28 = Edge::from(27, 7, 8, 14.0);
600
601    return Graph::from(Vec::from([edge1, edge2, edge3, edge4, edge5, edge6, edge7, edge8,
602        edge9, edge10, edge11, edge12, edge13, edge14, edge15, edge16, edge17, edge18, edge19, edge20,
603        edge21, edge22, edge23, edge24, edge25, edge26, edge27, edge28]));
604}
605
606#[cfg(test)]
607fn stubbed_path() -> Waypoint {
608    let start_point = Waypoint::from(Some(Edge::from(0, 0, 1, 1.0)), 0, None);
609
610    let mut current = start_point;
611    for i in 0..10 {
612        let edge_stub = Some(Edge::from(i, 0, 1, 1.0));
613        current = Waypoint::from(edge_stub.clone(), 0, Some(Box::from(current.clone())))
614    }
615
616    return current.clone();
617}
path_finding/path.rs

path_finding/
path.rs
