weavatrix_graph/algo/
shortest.rs

1use super::measure::Measure;
2use super::traversal::{Direction, for_each_adjacent};
3use super::walk::{DijkstraWorkspace, dijkstra_iter_filtered};
4use crate::Vec;
5use crate::{IndexGraphView, Result};
6use alloc::collections::BinaryHeap;
7use core::cmp::Reverse;
8
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub struct WeightedPath<Node, Cost = u64> {
11    nodes: Vec<Node>,
12    total_cost: Cost,
13}
14
15impl<Node, Cost> WeightedPath<Node, Cost> {
16    pub(super) fn from_parts(nodes: Vec<Node>, total_cost: Cost) -> Self {
17        Self { nodes, total_cost }
18    }
19
20    #[must_use]
21    pub fn nodes(&self) -> &[Node] {
22        &self.nodes
23    }
24
25    #[must_use]
26    pub const fn total_cost(&self) -> Cost
27    where
28        Cost: Copy,
29    {
30        self.total_cost
31    }
32
33    #[must_use]
34    pub fn into_nodes(self) -> Vec<Node> {
35        self.nodes
36    }
37}
38
39/// Computes a shortest path with an arbitrary checked measure.
40///
41/// # Errors
42///
43/// Returns an error for negative, non-finite, or overflowing path costs.
44pub fn dijkstra_measure<G, Cost, F>(
45    graph: &G,
46    source: G::Node,
47    target: G::Node,
48    mut edge_cost: F,
49) -> Result<Option<WeightedPath<G::Node, Cost>>>
50where
51    G: IndexGraphView,
52    Cost: Measure,
53    F: FnMut(G::Edge) -> Cost,
54{
55    dijkstra_measure_filtered(graph, source, target, Direction::Outgoing, |edge| {
56        Some(edge_cost(edge))
57    })
58}
59
60/// Computes a filtered shortest path with an arbitrary checked measure.
61///
62/// # Errors
63///
64/// Returns an error for negative, non-finite, or overflowing path costs.
65pub fn dijkstra_measure_filtered<G, Cost, F>(
66    graph: &G,
67    source: G::Node,
68    target: G::Node,
69    direction: Direction,
70    edge_cost: F,
71) -> Result<Option<WeightedPath<G::Node, Cost>>>
72where
73    G: IndexGraphView,
74    Cost: Measure,
75    F: FnMut(G::Edge) -> Option<Cost>,
76{
77    if !graph.contains_node(source) || !graph.contains_node(target) {
78        return Ok(None);
79    }
80    let mut workspace = DijkstraWorkspace::new();
81    let mut target_cost = None;
82    {
83        let search = dijkstra_iter_filtered(graph, source, direction, &mut workspace, edge_cost);
84        for settled in search {
85            let (node, cost) = settled?;
86            if node == target {
87                target_cost = Some(cost);
88                break;
89            }
90        }
91    }
92    let Some(total_cost) = target_cost else {
93        return Ok(None);
94    };
95    Ok(workspace
96        .path_to::<G>(source, target)
97        .map(|nodes| WeightedPath::from_parts(nodes, total_cost)))
98}
99
100pub fn dijkstra<G, F>(
101    graph: &G,
102    source: G::Node,
103    target: G::Node,
104    mut edge_cost: F,
105) -> Option<WeightedPath<G::Node>>
106where
107    G: IndexGraphView,
108    F: FnMut(G::Edge) -> u64,
109{
110    dijkstra_filtered(graph, source, target, Direction::Outgoing, |edge| {
111        Some(edge_cost(edge))
112    })
113}
114
115pub fn dijkstra_filtered<G, F>(
116    graph: &G,
117    source: G::Node,
118    target: G::Node,
119    direction: Direction,
120    mut edge_cost: F,
121) -> Option<WeightedPath<G::Node>>
122where
123    G: IndexGraphView,
124    F: FnMut(G::Edge) -> Option<u64>,
125{
126    if !graph.contains_node(source) || !graph.contains_node(target) {
127        return None;
128    }
129    let bound = graph.node_bound();
130    let mut nodes = vec![None; bound];
131    for node in graph.node_indices() {
132        nodes[G::node_slot(node)] = Some(node);
133    }
134    let mut costs = vec![u64::MAX; bound];
135    let mut predecessor = vec![None; bound];
136    let source_slot = G::node_slot(source);
137    costs[source_slot] = 0;
138    let mut queue = BinaryHeap::new();
139    queue.push(Reverse((0_u64, source_slot)));
140
141    while let Some(Reverse((cost, slot))) = queue.pop() {
142        if cost != costs[slot] {
143            continue;
144        }
145        let Some(node) = nodes[slot] else {
146            continue;
147        };
148        if node == target {
149            return Some(WeightedPath {
150                nodes: reconstruct::<G>(source, target, &predecessor)?,
151                total_cost: cost,
152            });
153        }
154        relax_neighbors(
155            graph,
156            node,
157            direction,
158            cost,
159            &mut edge_cost,
160            &mut costs,
161            &mut predecessor,
162            &mut queue,
163        );
164    }
165    None
166}
167
168#[allow(clippy::too_many_arguments)]
169fn relax_neighbors<G, F>(
170    graph: &G,
171    node: G::Node,
172    direction: Direction,
173    cost: u64,
174    edge_cost: &mut F,
175    costs: &mut [u64],
176    predecessor: &mut [Option<G::Node>],
177    queue: &mut BinaryHeap<Reverse<(u64, usize)>>,
178) where
179    G: IndexGraphView,
180    F: FnMut(G::Edge) -> Option<u64>,
181{
182    for_each_adjacent(graph, node, direction, &mut |_| true, |edge, neighbor| {
183        let Some(weight) = edge_cost(edge) else {
184            return;
185        };
186        let Some(candidate) = cost.checked_add(weight) else {
187            return;
188        };
189        let slot = G::node_slot(neighbor);
190        if candidate < costs[slot] {
191            costs[slot] = candidate;
192            predecessor[slot] = Some(node);
193            queue.push(Reverse((candidate, slot)));
194        }
195    });
196}
197
198pub(super) fn reconstruct<G: IndexGraphView>(
199    source: G::Node,
200    target: G::Node,
201    predecessor: &[Option<G::Node>],
202) -> Option<Vec<G::Node>> {
203    let mut path = vec![target];
204    let mut cursor = target;
205    while cursor != source {
206        cursor = predecessor[G::node_slot(cursor)]?;
207        path.push(cursor);
208    }
209    path.reverse();
210    Some(path)
211}
weavatrix_graph/algo/shortest.rs

weavatrix_graph/algo/
shortest.rs
