retworkx_core/shortest_path/
k_shortest_path.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13// This module was originally copied and forked from the upstream petgraph
14// repository, specifically:
15// https://github.com/petgraph/petgraph/blob/master/src/k_shortest_path.rs
16// prior to the 0.6.0 release. This was necessary to modify the error handling
17// to allow python callables to be use for the input functions for edge_cost
18// and return any exceptions raised in Python instead of panicking
19
20use std::collections::BinaryHeap;
21use std::hash::Hash;
22
23use petgraph::algo::Measure;
24use petgraph::visit::{
25    EdgeRef, IntoEdges, IntoNodeIdentifiers, NodeCount, NodeIndexable,
26    Visitable,
27};
28
29use crate::distancemap::DistanceMap;
30use crate::min_scored::MinScored;
31
32/// k'th shortest path algorithm.
33///
34/// Compute the length of the k'th shortest path from `start` to every reachable
35/// node.
36///
37/// The graph should be [`Visitable`] and implement [`IntoEdges`]. The function
38/// `edge_cost` should return the cost for a particular edge, which is used
39/// to compute path costs. Edge costs must be non-negative.
40///
41/// If `goal` is not [`None`], then the algorithm terminates once the `goal` node's
42/// cost is calculated.
43///
44/// Computes in **O(k * (|E| + |V|*log(|V|)))** time (average).
45///
46/// Returns a [`DistanceMap`] that maps `NodeId` to path cost as the value.
47///
48/// # Example:
49/// ```rust
50///
51/// use retworkx_core::petgraph;
52/// use retworkx_core::petgraph::graph::NodeIndex;
53/// use retworkx_core::shortest_path::k_shortest_path;
54/// use hashbrown::HashMap;
55/// use retworkx_core::Result;
56///
57/// let g = petgraph::graph::UnGraph::<i32, _>::from_edges(&[
58///     (0, 1), (1, 2), (2, 3), (3, 0), (4, 5), (1, 4), (5, 6), (6, 7), (7, 5)
59/// ]);
60///
61/// let res: Result<HashMap<NodeIndex, f64>> = k_shortest_path(
62///     &g, NodeIndex::new(1), None, 2,
63///     |e: retworkx_core::petgraph::graph::EdgeReference<&'static str>| Ok(1.0),
64/// );
65///
66/// let output = res.unwrap();
67/// let expected: HashMap<NodeIndex, f64> = [
68///     (NodeIndex::new(0), 3.0),
69///     (NodeIndex::new(1), 2.0),
70///     (NodeIndex::new(2), 3.0),
71///     (NodeIndex::new(3), 2.0),
72///     (NodeIndex::new(4), 3.0),
73///     (NodeIndex::new(5), 4.0),
74///     (NodeIndex::new(6), 4.0),
75///     (NodeIndex::new(7), 4.0),
76/// ].iter().cloned().collect();
77/// assert_eq!(expected, output);
78/// ```
79pub fn k_shortest_path<G, F, E, K, S>(
80    graph: G,
81    start: G::NodeId,
82    goal: Option<G::NodeId>,
83    k: usize,
84    mut edge_cost: F,
85) -> Result<S, E>
86where
87    G: IntoEdges + Visitable + NodeCount + NodeIndexable + IntoNodeIdentifiers,
88    G::NodeId: Eq + Hash,
89    F: FnMut(G::EdgeRef) -> Result<K, E>,
90    K: Measure + Copy,
91    S: DistanceMap<G::NodeId, K>,
92{
93    let mut counter: Vec<usize> = vec![0; graph.node_bound()];
94    let mut scores: S = S::build(graph.node_bound());
95    let mut visit_next = BinaryHeap::new();
96    let zero_score = K::default();
97
98    visit_next.push(MinScored(zero_score, start));
99
100    while let Some(MinScored(node_score, node)) = visit_next.pop() {
101        counter[graph.to_index(node)] += 1;
102        let current_counter = counter[graph.to_index(node)];
103
104        if current_counter > k {
105            continue;
106        }
107
108        if current_counter == k {
109            scores.put_item(node, node_score);
110        }
111
112        //Already reached goal k times
113        if goal.as_ref() == Some(&node) && current_counter == k {
114            break;
115        }
116
117        for edge in graph.edges(node) {
118            visit_next
119                .push(MinScored(node_score + edge_cost(edge)?, edge.target()));
120        }
121    }
122
123    Ok(scores)
124}
retworkx_core/shortest_path/k_shortest_path.rs

retworkx_core/shortest_path/
k_shortest_path.rs
