petgraph/algo/
k_shortest_path.rs

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

petgraph/algo/
k_shortest_path.rs
