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
|
use petgraph::algo::k_shortest_path;
use petgraph::prelude::*;
use petgraph::Graph;
use std::collections::HashMap;
#[test]
fn second_shortest_path() {
let mut graph: Graph<(), (), Directed> = Graph::new();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
let i = graph.add_node(());
let j = graph.add_node(());
let k = graph.add_node(());
let l = graph.add_node(());
let m = graph.add_node(());
graph.extend_with_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),
]);
let res = k_shortest_path(&graph, a, None, 2, |_| 1);
let expected_res: HashMap<NodeIndex, 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);
}
|
