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

#![cfg(test)]

// http://bit.ly/2jwqlY6

use pathfinding::prelude::*;
use std::collections::HashMap;

#[derive(Clone, Debug, Eq, PartialEq, Hash)]
struct Point {
    row: usize,
    col: usize,
}

fn add_successor(
    n: &mut HashMap<Point, Vec<(Point, usize)>>,
    from: &Point,
    to: &Point,
    cost: usize,
) {
    let entry = n.entry(from.clone()).or_default();
    entry.push((to.clone(), cost));
}

type SuccessorInfo = Vec<(Point, usize)>;

fn parse(input: &str) -> (Vec<Point>, HashMap<Point, SuccessorInfo>) {
    let mut nodes = Vec::new();
    let mut successors = HashMap::new();
    input
        .lines()
        .map(|l| {
            l.split(' ')
                .map(|s| s.parse::<usize>().unwrap_or(0))
                .collect::<Vec<_>>()
        })
        .for_each(|words| {
            let src = Point {
                row: words[0],
                col: words[1],
            };
            nodes.push(src.clone());
            for n in words[3..].chunks(3) {
                let dst = Point {
                    row: n[0],
                    col: n[1],
                };
                let cost = n[2];
                assert!(cost >= distance(&src, &dst));
                add_successor(&mut successors, &src, &dst, cost);
            }
        });
    (nodes, successors)
}

const fn distance(a: &Point, b: &Point) -> usize {
    a.row.abs_diff(b.row) + a.col.abs_diff(b.col)
}

#[test]
fn main() {
    let expectations = [
        vec![28, 44, 220, 184, 144, 208, 76],
        vec![60, 212, 176, 136, 200, 92],
        vec![252, 216, 176, 240, 36],
        vec![48, 84, 64, 276],
        vec![48, 40, 240],
        vec![72, 200],
        vec![264],
    ];
    let (nodes, graph) = parse(include_str!("r299.data"));
    for (i, start) in nodes[..7].iter().enumerate() {
        for (j, target) in nodes[i + 1..8].iter().enumerate() {
            let expected = expectations[i][j];
            assert_eq!(
                astar(
                    start,
                    |n| graph[n].iter().cloned(),
                    |n| distance(n, target),
                    |n| n == target,
                )
                .unwrap()
                .1,
                expected
            );
            assert_eq!(
                dijkstra(start, |n| graph[n].iter().cloned(), |n| n == target)
                    .unwrap()
                    .1,
                expected
            );
            assert_eq!(
                fringe(
                    start,
                    |n| graph[n].iter().cloned(),
                    |n| distance(n, target),
                    |n| n == target,
                )
                .unwrap()
                .1,
                expected
            );
            if expected < 150 {
                // Longer paths will take too long to run with IDA*.
                assert_eq!(
                    idastar(
                        start,
                        |n| graph[n].iter().cloned(),
                        |n| distance(n, target),
                        |n| n == target,
                    )
                    .unwrap()
                    .1,
                    expected
                );
            }
        }
    }
}