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
|
#![cfg(test)]
use pathfinding::prelude::*;
use std::collections::HashMap;
// Latitude, longitude
struct Coords(f32, f32);
impl Coords {
fn lat_rad(&self) -> f32 {
self.0.to_radians()
}
fn lon_rad(&self) -> f32 {
self.1.to_radians()
}
#[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
fn distance_in_meters(&self, other: &Self) -> u64 {
let x =
(other.lon_rad() - self.lon_rad()) * ((other.lat_rad() + self.lat_rad()) / 2.0).cos();
let y = other.lat_rad() - self.lat_rad();
(x.hypot(y) * 6_371_000.0).round() as u64
}
}
fn coords() -> HashMap<&'static str, Coords> {
vec![
("Paris", Coords(48.8567, 2.3508)),
("Lyon", Coords(45.76, 4.84)),
("Marseille", Coords(43.2964, 5.37)),
("Bordeaux", Coords(44.84, -0.58)),
("Cannes", Coords(43.5513, 7.0128)),
("Toulouse", Coords(43.6045, 1.444)),
("Reims", Coords(49.2628, 4.0347)),
]
.into_iter()
.collect()
}
fn successor_distances(
coords: &HashMap<&str, Coords>,
) -> HashMap<&'static str, Vec<(&'static str, u64)>> {
let mut successors = HashMap::new();
{
let mut insert_successor = |from: &'static str, to: &'static str| {
let from_coords = &coords[from];
let ns = to
.split(',')
.map(|successor| {
(
successor,
from_coords.distance_in_meters(&coords[successor]),
)
})
.collect();
successors.insert(from, ns);
};
insert_successor("Paris", "Lyon,Bordeaux,Reims");
insert_successor("Lyon", "Paris,Marseille");
insert_successor("Marseille", "Lyon,Cannes,Toulouse");
insert_successor("Bordeaux", "Toulouse,Paris");
insert_successor("Cannes", "Marseille");
insert_successor("Toulouse", "Marseille,Bordeaux");
insert_successor("Reims", "Paris");
}
successors
}
#[test]
fn gps() {
let coords = coords();
let successor_distances = successor_distances(&coords);
let (start, goal) = ("Paris", "Cannes");
let goal_coords = &coords[goal];
let expected_path = vec!["Paris", "Lyon", "Marseille", "Cannes"];
let r = astar(
&start,
|city| successor_distances[city].clone(),
|city| goal_coords.distance_in_meters(&coords[city]),
|city| city == &goal,
);
let (path, cost_astar) = r.expect("no path found with astar");
assert_eq!(path, expected_path, "bad path found with astar");
let r = fringe(
&start,
|city| successor_distances[city].clone(),
|city| goal_coords.distance_in_meters(&coords[city]),
|city| city == &goal,
);
let (path, cost_fringe) = r.expect("no path found with fringe");
assert_eq!(path, expected_path, "bad path found with fringe");
assert_eq!(
cost_astar, cost_fringe,
"costs for astar and fringe are different"
);
let r = dijkstra(
&start,
|city| successor_distances[city].clone(),
|city| city == &goal,
);
let (path, cost_dijkstra) = r.expect("no path found with dijkstra");
assert_eq!(path, expected_path, "bad path found with dijkstra");
assert_eq!(
cost_astar, cost_dijkstra,
"costs for astar and dijkstra are different"
);
let r = idastar(
&start,
|city| successor_distances[city].clone(),
|city| goal_coords.distance_in_meters(&coords[city]),
|city| city == &goal,
);
let (path, cost_idastar) = r.expect("no path found with idastar");
assert_eq!(path, expected_path, "bad path found with idastar");
assert_eq!(
cost_astar, cost_idastar,
"costs for astar and idastar are different"
);
}
|
