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
|
use pathfinding::prelude::*;
use rand::{rngs, Rng as _};
fn build_network(size: usize) -> Matrix<usize> {
let mut network = Matrix::new(size, size, 0);
let mut rng = rngs::OsRng;
for a in 0..size {
for b in 0..size {
if rng.gen_ratio(2, 3) {
network[(a, b)] = rng.r#gen::<u16>() as usize;
}
}
}
network
}
fn neighbours(network: Matrix<usize>) -> impl FnMut(&usize) -> Vec<(usize, usize)> {
move |&a| {
(0..network.rows)
.filter_map(|b| match network[(a, b)] {
0 => None,
p => Some((b, p)),
})
.collect()
}
}
#[test]
fn all_paths() {
const SIZE: usize = 30;
let network = build_network(SIZE);
for start in 0..SIZE {
let paths = dijkstra_all(&start, neighbours(network.clone()));
for target in 0..SIZE {
if let Some((path, cost)) =
dijkstra(&start, neighbours(network.clone()), |&n| n == target)
{
if start == target {
assert!(
!paths.contains_key(&target),
"path {start} -> {target} is present in {network:?}"
);
} else {
assert!(
paths.contains_key(&target),
"path {start} -> {target} is not found in {network:?}"
);
assert_eq!(
cost, paths[&target].1,
"cost differ in path {start} -> {target} in {network:?}"
);
let other_path = build_path(&target, &paths);
// There might be several paths, but we know that internally we use the
// same algorithm so the comparison holds.
assert_eq!(path, other_path, "path {start} -> {target} differ in {network:?}: {path:?} vs {other_path:?}");
}
} else {
assert!(
!paths.contains_key(&target),
"path {start} -> {target} is present in {network:?}"
);
}
}
}
}
#[test]
fn partial_paths() {
const SIZE: usize = 100;
let network = build_network(SIZE);
for start in 0..SIZE {
let (paths, reached) = dijkstra_partial(&start, neighbours(network.clone()), |&n| {
start != 0 && n != 0 && n != start && n % start == 0
});
if let Some(target) = reached {
assert!(target % start == 0, "bad stop condition");
// We cannot compare other paths since there is no guarantee that the
// paths variable is up-to-date as the algorithm stopped prematurely.
let cost = paths[&target].1;
let (path, dijkstra_cost) =
dijkstra(&start, neighbours(network.clone()), |&n| n == target).unwrap();
assert_eq!(
cost, dijkstra_cost,
"costs {start} -> {target} differ in {network:?}"
);
let other_path = build_path(&target, &paths);
// There might be several paths, but we know that internally we use the
// same algorithm so the comparison holds.
assert_eq!(
path, other_path,
"path {start} -> {target} differ in {network:?}: {path:?} vs {other_path:?}"
);
} else if start != 0 && start <= (SIZE - 1) / 2 {
for target in 1..(SIZE / start) {
assert!(
dijkstra(&start, neighbours(network.clone()), |&n| n == target).is_none(),
"path {start} -> {target} found in {network:?}"
);
}
}
}
}
|
