pathfinding 0.6.11

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

#![cfg(test)]

extern crate pathfinding;

use pathfinding::*;
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()
    }

    fn distance_in_meters(&self, other: &Coords) -> 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 neighbour_distances(
    coords: &HashMap<&str, Coords>,
) -> HashMap<&'static str, Vec<(&'static str, u64)>> {
    let mut neighbours = HashMap::new();
    {
        let mut insert_neighbour = |from: &'static str, to: &'static str| {
            let from_coords = &coords[from];
            let ns = to.split(',')
                .map(|neighbour| {
                    (
                        neighbour,
                        from_coords.distance_in_meters(&coords[neighbour]),
                    )
                })
                .collect();
            neighbours.insert(from, ns);
        };
        insert_neighbour("Paris", "Lyon,Bordeaux,Reims");
        insert_neighbour("Lyon", "Paris,Marseille");
        insert_neighbour("Marseille", "Lyon,Cannes,Toulouse");
        insert_neighbour("Bordeaux", "Toulouse,Paris");
        insert_neighbour("Cannes", "Marseille");
        insert_neighbour("Toulouse", "Marseille,Bordeaux");
        insert_neighbour("Reims", "Paris");
    }
    neighbours
}

#[test]
fn test_gps() {
    let coords = coords();
    let neighbour_distances = neighbour_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| neighbour_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| neighbour_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| neighbour_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| neighbour_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"
    );
}