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
use hashbrown::HashMap;
use crate::algo::k_shortest_path::k_shortest_path;
use crate::prelude::*;
#[test]
fn second_shortest_path() {
hypergraph! {
let mut graph: DirectedHypergraph<_, _> {
nodes: {
let a = ();
let b = ();
let c = ();
let d = ();
let e = ();
let f = ();
let g = ();
let h = ();
let i = ();
let j = ();
let k = ();
let l = ();
let m = ();
};
edges: {
([a] -> [b]) = ();
([b] -> [c]) = ();
([c] -> [d]) = ();
([b] -> [f]) = ();
([f] -> [g]) = ();
([c] -> [g]) = ();
([g] -> [h]) = ();
([d] -> [e]) = ();
([e] -> [h]) = ();
([h] -> [i]) = ();
([h] -> [j]) = ();
([h] -> [k]) = ();
([h] -> [l]) = ();
([i] -> [m]) = ();
([l] -> [k]) = ();
([j] -> [k]) = ();
([j] -> [m]) = ();
([k] -> [m]) = ();
([l] -> [m]) = ();
([m] -> [e]) = ();
// [a, b] = ();
// [b, c] = ();
// [c, d] = ();
// [b, f] = ();
// [f, g] = ();
// [c, g] = ();
// [g, h] = ();
// [d, e] = ();
// [e, h] = ();
// [h, i] = ();
// [h, j] = ();
// [h, k] = ();
// [h, l] = ();
// [i, m] = ();
// [l, k] = ();
// [j, k] = ();
// [j, m] = ();
// [k, m] = ();
// [l, m] = ();
// [m, e] = ();
};
}
}
let res = k_shortest_path(&graph, a, None, 2, |_| 1);
let expected_res: HashMap<usize, usize> = [
(e, 7),
(g, 3),
(h, 4),
(i, 5),
(j, 5),
(k, 5),
(l, 5),
(m, 6),
]
.iter()
.cloned()
.collect();
assert_eq!(res, expected_res);
}