1 use std::collections::{BinaryHeap, HashMap};
2
3 use std::hash::Hash;
4
5 use crate::algo::Measure;
6 use crate::scored::MinScored;
7 use crate::visit::{EdgeRef, IntoEdges, NodeCount, NodeIndexable, Visitable};
8
9 /// \[Generic\] k'th shortest path algorithm.
10 ///
11 /// Compute the length of the k'th shortest path from `start` to every reachable
12 /// node.
13 ///
14 /// The graph should be `Visitable` and implement `IntoEdges`. The function
15 /// `edge_cost` should return the cost for a particular edge, which is used
16 /// to compute path costs. Edge costs must be non-negative.
17 ///
18 /// If `goal` is not `None`, then the algorithm terminates once the `goal` node's
19 /// cost is calculated.
20 ///
21 /// Computes in **O(k * (|E| + |V|*log(|V|)))** time (average).
22 ///
23 /// Returns a `HashMap` that maps `NodeId` to path cost.
24 /// # Example
25 /// ```rust
26 /// use petgraph::Graph;
27 /// use petgraph::algo::k_shortest_path;
28 /// use petgraph::prelude::*;
29 /// use std::collections::HashMap;
30 ///
31 /// let mut graph : Graph<(),(),Directed>= Graph::new();
32 /// let a = graph.add_node(()); // node with no weight
33 /// let b = graph.add_node(());
34 /// let c = graph.add_node(());
35 /// let d = graph.add_node(());
36 /// let e = graph.add_node(());
37 /// let f = graph.add_node(());
38 /// let g = graph.add_node(());
39 /// let h = graph.add_node(());
40 /// // z will be in another connected component
41 /// let z = graph.add_node(());
42 ///
43 /// graph.extend_with_edges(&[
44 /// (a, b),
45 /// (b, c),
46 /// (c, d),
47 /// (d, a),
48 /// (e, f),
49 /// (b, e),
50 /// (f, g),
51 /// (g, h),
52 /// (h, e)
53 /// ]);
54 /// // a ----> b ----> e ----> f
55 /// // ^ | ^ |
56 /// // | v | v
57 /// // d <---- c h <---- g
58 ///
59 /// let expected_res: HashMap<NodeIndex, usize> = [
60 /// (a, 7),
61 /// (b, 4),
62 /// (c, 5),
63 /// (d, 6),
64 /// (e, 5),
65 /// (f, 6),
66 /// (g, 7),
67 /// (h, 8)
68 /// ].iter().cloned().collect();
69 /// let res = k_shortest_path(&graph,b,None,2, |_| 1);
70 /// assert_eq!(res, expected_res);
71 /// // z is not inside res because there is not path from b to z.
72 /// ```
k_shortest_path<G, F, K>( graph: G, start: G::NodeId, goal: Option<G::NodeId>, k: usize, mut edge_cost: F, ) -> HashMap<G::NodeId, K> where G: IntoEdges + Visitable + NodeCount + NodeIndexable, G::NodeId: Eq + Hash, F: FnMut(G::EdgeRef) -> K, K: Measure + Copy,73 pub fn k_shortest_path<G, F, K>(
74 graph: G,
75 start: G::NodeId,
76 goal: Option<G::NodeId>,
77 k: usize,
78 mut edge_cost: F,
79 ) -> HashMap<G::NodeId, K>
80 where
81 G: IntoEdges + Visitable + NodeCount + NodeIndexable,
82 G::NodeId: Eq + Hash,
83 F: FnMut(G::EdgeRef) -> K,
84 K: Measure + Copy,
85 {
86 let mut counter: Vec<usize> = vec![0; graph.node_count()];
87 let mut scores = HashMap::new();
88 let mut visit_next = BinaryHeap::new();
89 let zero_score = K::default();
90
91 visit_next.push(MinScored(zero_score, start));
92
93 while let Some(MinScored(node_score, node)) = visit_next.pop() {
94 counter[graph.to_index(node)] += 1;
95 let current_counter = counter[graph.to_index(node)];
96
97 if current_counter > k {
98 continue;
99 }
100
101 if current_counter == k {
102 scores.insert(node, node_score);
103 }
104
105 //Already reached goal k times
106 if goal.as_ref() == Some(&node) && current_counter == k {
107 break;
108 }
109
110 for edge in graph.edges(node) {
111 visit_next.push(MinScored(node_score + edge_cost(edge), edge.target()));
112 }
113 }
114 scores
115 }
116