pathfinding 4.15.0

Pathfinding, flow, and graph algorithms
Documentation 
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()
    }

    #[expect(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
    fn distance_in_meters(&self, other: &Self) -> u64 {
        let x = (other.lon_rad() - self.lon_rad())
            * f32::midpoint(other.lat_rad(), self.lat_rad()).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"
    );
}