rust_igraph/algorithms/paths/
get_shortest_path_astar.rs

1//! Single-pair shortest path via A* (`ALGO-SP-036`).
2//!
3//! Port of `igraph_get_shortest_path_astar()` from
4//! `references/igraph/src/paths/astar.c`. A* finds one shortest path from
5//! `from` to `to` by exploring vertices in order of an *estimated* total
6//! path length: the actual distance from the source plus a heuristic
7//! estimate of the remaining distance to the target. When the heuristic is
8//! admissible (never overestimates the true remaining distance) the result
9//! is a genuine shortest path; with the null heuristic A* degenerates to
10//! Dijkstra's algorithm.
11//!
12//! The path is returned as both the vertex sequence (including `from` and
13//! `to`) and the edge sequence along it, sharing the [`ShortestPath`]
14//! struct with [`super::get_shortest_path`]. Empty vectors signal an
15//! unreachable target; `from == to` yields `[from]` with no edges, exactly
16//! as upstream.
17//!
18//! Unlike [`super::get_shortest_path`], A* supports only **non-negative**
19//! weights (there is no Bellman-Ford fallback): a negative weight is an
20//! error. Edges with positive-infinite weight are ignored, matching
21//! upstream.
22//!
23//! When several shortest paths of equal length exist, an arbitrary one is
24//! returned; the exact choice depends on heap tie-breaking and is not a
25//! stable cross-implementation observable. The total path *length* is.
26
27use std::cmp::Ordering;
28use std::collections::BinaryHeap;
29
30use crate::core::graph::EdgeId;
31use crate::core::{Graph, IgraphError, IgraphResult, VertexId};
32
33use super::dijkstra::DijkstraMode;
34use super::get_shortest_path::ShortestPath;
35
36/// A heuristic estimating the distance from a candidate vertex (first
37/// argument) to the target vertex (second argument). Must be admissible
38/// (never overestimate the true remaining distance) for the result to be
39/// a true shortest path.
40pub type AstarHeuristic<'a> = dyn Fn(VertexId, VertexId) -> f64 + 'a;
41
42/// Mode-aware incident edges, mirroring upstream's lazy incidence list
43/// (`igraph_lazy_inclist_init(_, _, mode, IGRAPH_LOOPS_TWICE)`). For
44/// undirected graphs every mode collapses to the merged adjacency.
45fn incident_for_mode(graph: &Graph, v: VertexId, mode: DijkstraMode) -> IgraphResult<Vec<EdgeId>> {
46    if !graph.is_directed() {
47        return graph.incident(v);
48    }
49    match mode {
50        DijkstraMode::Out => graph.incident(v),
51        DijkstraMode::In => graph.incident_in(v),
52        DijkstraMode::All => {
53            let mut out = graph.incident(v)?;
54            out.extend(graph.incident_in(v)?);
55            Ok(out)
56        }
57    }
58}
59
60/// An open-set entry: the priority is `est` (g + heuristic) ordered so the
61/// smallest estimate pops first; `g` is the actual `from -> vertex`
62/// distance recorded at push time, used to drop stale entries.
63struct State {
64    est: f64,
65    g: f64,
66    vertex: VertexId,
67}
68
69impl PartialEq for State {
70    fn eq(&self, other: &Self) -> bool {
71        self.est.total_cmp(&other.est) == Ordering::Equal
72    }
73}
74impl Eq for State {}
75impl Ord for State {
76    fn cmp(&self, other: &Self) -> Ordering {
77        // Reverse so `BinaryHeap` (a max-heap) yields the smallest estimate.
78        other.est.total_cmp(&self.est)
79    }
80}
81impl PartialOrd for State {
82    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
83        Some(self.cmp(other))
84    }
85}
86
87/// Calculate a single shortest path from `from` to `to` using A*.
88///
89/// Returns the path as both its vertex sequence (source first, target
90/// last) and the edge sequence along it. If several shortest paths exist,
91/// an arbitrary one is returned. The path is empty when `to` is
92/// unreachable; when `from == to` the vertex sequence is `[from]` and the
93/// edge sequence is empty.
94///
95/// `weights` are optional edge weights; `None` treats every edge as weight
96/// `1` (an unweighted graph). All weights must be non-negative and
97/// non-NaN; positive-infinite weights mark unusable edges. On directed
98/// graphs `mode` selects the followed adjacency
99/// ([`DijkstraMode::Out`] / [`DijkstraMode::In`] / [`DijkstraMode::All`]);
100/// it is ignored on undirected graphs.
101///
102/// `heuristic`, if given, estimates the remaining distance from a
103/// candidate vertex to `to`. It must be *admissible* (never overestimate)
104/// for the returned path to be a true shortest path. `None` uses the null
105/// heuristic (always `0`), making A* equivalent to Dijkstra.
106///
107/// # Errors
108///
109/// Returns [`IgraphError::VertexOutOfRange`] if `from` or `to` is not a
110/// valid vertex, or [`IgraphError::InvalidArgument`] if `weights` is
111/// provided and its length differs from the edge count, contains NaN, or
112/// contains a negative value.
113///
114/// # Examples
115///
116/// ```
117/// use rust_igraph::{Graph, get_shortest_path_astar, DijkstraMode};
118///
119/// let mut g = Graph::new(4, false).unwrap();
120/// g.add_edge(0, 1).unwrap(); // edge 0
121/// g.add_edge(1, 2).unwrap(); // edge 1
122/// g.add_edge(2, 3).unwrap(); // edge 2
123///
124/// // Null heuristic (None) behaves exactly like Dijkstra.
125/// let p = get_shortest_path_astar(&g, 0, 3, None, DijkstraMode::Out, None).unwrap();
126/// assert_eq!(p.vertices, vec![0, 1, 2, 3]);
127/// assert_eq!(p.edges, vec![0, 1, 2]);
128///
129/// // An admissible heuristic (here: |target - v|, a lower bound on the
130/// // number of hops) yields the same shortest path.
131/// let h = |v: u32, to: u32| f64::from(to.abs_diff(v));
132/// let q = get_shortest_path_astar(&g, 0, 3, None, DijkstraMode::Out, Some(&h)).unwrap();
133/// assert_eq!(q.vertices, vec![0, 1, 2, 3]);
134/// ```
135pub fn get_shortest_path_astar(
136    graph: &Graph,
137    from: VertexId,
138    to: VertexId,
139    weights: Option<&[f64]>,
140    mode: DijkstraMode,
141    heuristic: Option<&AstarHeuristic<'_>>,
142) -> IgraphResult<ShortestPath> {
143    let n = graph.vcount();
144    if from >= n {
145        return Err(IgraphError::VertexOutOfRange { id: from, n });
146    }
147    if to >= n {
148        return Err(IgraphError::VertexOutOfRange { id: to, n });
149    }
150
151    if let Some(w) = weights {
152        let m = graph.ecount();
153        if w.len() != m {
154            return Err(IgraphError::InvalidArgument(format!(
155                "get_shortest_path_astar: weights length {} != edge count {m}",
156                w.len()
157            )));
158        }
159        for (e, &x) in w.iter().enumerate() {
160            if x.is_nan() {
161                return Err(IgraphError::InvalidArgument(format!(
162                    "get_shortest_path_astar: weight at edge {e} is NaN"
163                )));
164            }
165            if x < 0.0 {
166                return Err(IgraphError::InvalidArgument(format!(
167                    "get_shortest_path_astar: weight at edge {e} is negative ({x})"
168                )));
169            }
170        }
171    }
172
173    let h = |v: VertexId| heuristic.map_or(0.0, |f| f(v, to));
174
175    let n_usize = n as usize;
176    let mut dists = vec![f64::INFINITY; n_usize];
177    // parent_eids[v] = 1 + edge id of v's inbound tree edge; 0 = unreached.
178    let mut parent_eids: Vec<EdgeId> = vec![0; n_usize];
179
180    dists[from as usize] = 0.0;
181    let mut queue: BinaryHeap<State> = BinaryHeap::new();
182    queue.push(State {
183        est: h(from),
184        g: 0.0,
185        vertex: from,
186    });
187
188    let mut found = false;
189    while let Some(State { g, vertex: u, .. }) = queue.pop() {
190        // Stale entry: a cheaper route to `u` was found after this was
191        // pushed. Skip it (lazy deletion in place of decrease-key).
192        if g > dists[u as usize] {
193            continue;
194        }
195        if u == to {
196            found = true;
197            break;
198        }
199        for edge in incident_for_mode(graph, u, mode)? {
200            let weight = match weights {
201                Some(w) => {
202                    let x = w[edge as usize];
203                    if x.is_infinite() {
204                        continue;
205                    }
206                    x
207                }
208                None => 1.0,
209            };
210            let v = graph.edge_other(edge, u)?;
211            let altdist = dists[u as usize] + weight;
212            if altdist < dists[v as usize] {
213                dists[v as usize] = altdist;
214                parent_eids[v as usize] = edge + 1;
215                queue.push(State {
216                    est: altdist + h(v),
217                    g: altdist,
218                    vertex: v,
219                });
220            }
221        }
222    }
223
224    if !found {
225        // `to` unreachable from `from` (and `from != to`): empty path.
226        return Ok(ShortestPath {
227            vertices: Vec::new(),
228            edges: Vec::new(),
229        });
230    }
231
232    // Reconstruct by walking parent edges back from `to`.
233    let mut size = 0_usize;
234    let mut act = to;
235    while parent_eids[act as usize] != 0 {
236        size += 1;
237        let edge = parent_eids[act as usize] - 1;
238        act = graph.edge_other(edge, act)?;
239    }
240
241    let mut vertices = vec![0 as VertexId; size + 1];
242    let mut edges = vec![0 as EdgeId; size];
243    vertices[size] = to;
244
245    let mut idx = size;
246    let mut act = to;
247    while parent_eids[act as usize] != 0 {
248        idx -= 1;
249        let edge = parent_eids[act as usize] - 1;
250        act = graph.edge_other(edge, act)?;
251        vertices[idx] = act;
252        edges[idx] = edge;
253    }
254
255    Ok(ShortestPath { vertices, edges })
256}
257
258#[cfg(test)]
259#[allow(clippy::float_cmp)]
260mod tests {
261    use super::*;
262
263    /// Admissible heuristic for a path/grid where vertex ids are laid out
264    /// so `|to - v|` lower-bounds the hop count.
265    fn linear_h(to: VertexId) -> impl Fn(VertexId, VertexId) -> f64 {
266        move |v: VertexId, _to: VertexId| f64::from(to.abs_diff(v))
267    }
268
269    #[test]
270    fn from_equals_to() {
271        let mut g = Graph::new(3, false).unwrap();
272        g.add_edge(0, 1).unwrap();
273        let p = get_shortest_path_astar(&g, 1, 1, None, DijkstraMode::Out, None).unwrap();
274        assert_eq!(p.vertices, vec![1]);
275        assert!(p.edges.is_empty());
276    }
277
278    #[test]
279    fn simple_path_unweighted_null_heuristic() {
280        let mut g = Graph::new(4, false).unwrap();
281        g.add_edge(0, 1).unwrap(); // 0
282        g.add_edge(1, 2).unwrap(); // 1
283        g.add_edge(2, 3).unwrap(); // 2
284        let p = get_shortest_path_astar(&g, 0, 3, None, DijkstraMode::Out, None).unwrap();
285        assert_eq!(p.vertices, vec![0, 1, 2, 3]);
286        assert_eq!(p.edges, vec![0, 1, 2]);
287    }
288
289    #[test]
290    fn admissible_heuristic_matches_dijkstra() {
291        let mut g = Graph::new(4, false).unwrap();
292        g.add_edge(0, 1).unwrap(); // 0
293        g.add_edge(1, 2).unwrap(); // 1
294        g.add_edge(2, 3).unwrap(); // 2
295        let h = linear_h(3);
296        let p = get_shortest_path_astar(&g, 0, 3, None, DijkstraMode::Out, Some(&h)).unwrap();
297        assert_eq!(p.vertices, vec![0, 1, 2, 3]);
298        assert_eq!(p.edges, vec![0, 1, 2]);
299    }
300
301    #[test]
302    fn picks_shortcut() {
303        let mut g = Graph::new(4, false).unwrap();
304        g.add_edge(0, 1).unwrap(); // 0
305        g.add_edge(1, 3).unwrap(); // 1
306        g.add_edge(0, 3).unwrap(); // 2 shortcut
307        let p = get_shortest_path_astar(&g, 0, 3, None, DijkstraMode::Out, None).unwrap();
308        assert_eq!(p.vertices, vec![0, 3]);
309        assert_eq!(p.edges, vec![2]);
310    }
311
312    #[test]
313    fn weighted_prefers_cheaper_route() {
314        let mut g = Graph::new(4, false).unwrap();
315        g.add_edge(0, 1).unwrap(); // 0
316        g.add_edge(1, 3).unwrap(); // 1
317        g.add_edge(0, 3).unwrap(); // 2 direct but expensive
318        let w = vec![1.0, 1.0, 10.0];
319        let p = get_shortest_path_astar(&g, 0, 3, Some(&w), DijkstraMode::Out, None).unwrap();
320        assert_eq!(p.vertices, vec![0, 1, 3]);
321        assert_eq!(p.edges, vec![0, 1]);
322    }
323
324    #[test]
325    fn infinite_weight_edge_ignored() {
326        let mut g = Graph::new(3, false).unwrap();
327        g.add_edge(0, 2).unwrap(); // 0 direct, but infinite
328        g.add_edge(0, 1).unwrap(); // 1
329        g.add_edge(1, 2).unwrap(); // 2
330        let w = vec![f64::INFINITY, 1.0, 1.0];
331        let p = get_shortest_path_astar(&g, 0, 2, Some(&w), DijkstraMode::Out, None).unwrap();
332        assert_eq!(p.vertices, vec![0, 1, 2]);
333        assert_eq!(p.edges, vec![1, 2]);
334    }
335
336    #[test]
337    fn unreachable_returns_empty() {
338        let mut g = Graph::new(3, true).unwrap();
339        g.add_edge(0, 1).unwrap();
340        let p = get_shortest_path_astar(&g, 0, 2, None, DijkstraMode::Out, None).unwrap();
341        assert!(p.vertices.is_empty());
342        assert!(p.edges.is_empty());
343    }
344
345    #[test]
346    fn directed_mode_in_follows_reverse() {
347        let mut g = Graph::new(3, true).unwrap();
348        g.add_edge(0, 1).unwrap(); // 0
349        g.add_edge(1, 2).unwrap(); // 1
350        let out = get_shortest_path_astar(&g, 0, 2, None, DijkstraMode::Out, None).unwrap();
351        assert_eq!(out.vertices, vec![0, 1, 2]);
352        let none = get_shortest_path_astar(&g, 2, 0, None, DijkstraMode::Out, None).unwrap();
353        assert!(none.vertices.is_empty());
354        let inp = get_shortest_path_astar(&g, 2, 0, None, DijkstraMode::In, None).unwrap();
355        assert_eq!(inp.vertices, vec![2, 1, 0]);
356        assert_eq!(inp.edges, vec![1, 0]);
357    }
358
359    #[test]
360    fn directed_mode_all_ignores_direction() {
361        let mut g = Graph::new(3, true).unwrap();
362        g.add_edge(0, 1).unwrap();
363        g.add_edge(1, 2).unwrap();
364        let p = get_shortest_path_astar(&g, 2, 0, None, DijkstraMode::All, None).unwrap();
365        assert_eq!(p.vertices, vec![2, 1, 0]);
366    }
367
368    #[test]
369    fn invalid_endpoints_error() {
370        let g = Graph::new(2, false).unwrap();
371        assert!(get_shortest_path_astar(&g, 5, 0, None, DijkstraMode::Out, None).is_err());
372        assert!(get_shortest_path_astar(&g, 0, 5, None, DijkstraMode::Out, None).is_err());
373    }
374
375    #[test]
376    fn weights_length_mismatch_errors() {
377        let mut g = Graph::new(2, false).unwrap();
378        g.add_edge(0, 1).unwrap();
379        let w = vec![1.0, 2.0];
380        assert!(get_shortest_path_astar(&g, 0, 1, Some(&w), DijkstraMode::Out, None).is_err());
381    }
382
383    #[test]
384    fn weights_nan_errors() {
385        let mut g = Graph::new(2, false).unwrap();
386        g.add_edge(0, 1).unwrap();
387        let w = vec![f64::NAN];
388        assert!(get_shortest_path_astar(&g, 0, 1, Some(&w), DijkstraMode::Out, None).is_err());
389    }
390
391    #[test]
392    fn weights_negative_errors() {
393        let mut g = Graph::new(2, false).unwrap();
394        g.add_edge(0, 1).unwrap();
395        let w = vec![-1.0];
396        assert!(get_shortest_path_astar(&g, 0, 1, Some(&w), DijkstraMode::Out, None).is_err());
397    }
398}
399
400#[cfg(all(test, feature = "proptest-harness"))]
401mod proptests {
402    use super::*;
403    use crate::algorithms::paths::get_shortest_path::get_shortest_path;
404    use crate::create;
405    use proptest::prelude::*;
406
407    fn arb_graph(max_v: u32) -> impl Strategy<Value = Graph> {
408        (2..=max_v).prop_flat_map(|n| {
409            let max_e = (n as usize)
410                .saturating_mul(n.saturating_sub(1) as usize)
411                .min(20);
412            proptest::collection::vec((0..n, 0..n), 0..=max_e).prop_map(move |edges| {
413                let edge_tuples: Vec<(u32, u32)> = edges.into_iter().collect();
414                create(&edge_tuples, n, false).expect("arb graph")
415            })
416        })
417    }
418
419    proptest! {
420        /// A non-empty A* result is a genuine simple walk from `from` to
421        /// `to`: endpoints match, edges join consecutive vertices, and no
422        /// vertex repeats.
423        #[test]
424        fn path_is_a_valid_simple_walk(
425            g in arb_graph(6),
426            from in 0u32..6,
427            to in 0u32..6,
428        ) {
429            let n = g.vcount();
430            prop_assume!(from < n && to < n);
431            let p = get_shortest_path_astar(&g, from, to, None, DijkstraMode::All, None)
432                .expect("ok");
433            if p.vertices.is_empty() {
434                return Ok(());
435            }
436            prop_assert_eq!(p.vertices[0], from);
437            prop_assert_eq!(*p.vertices.last().expect("non-empty"), to);
438            prop_assert_eq!(p.edges.len() + 1, p.vertices.len());
439
440            let mut seen = vec![false; n as usize];
441            for &v in &p.vertices {
442                prop_assert!(!seen[v as usize], "vertex {} repeats", v);
443                seen[v as usize] = true;
444            }
445            for (i, &e) in p.edges.iter().enumerate() {
446                let (a, b) = g.edge(e).expect("edge id valid");
447                let (u, v) = (p.vertices[i], p.vertices[i + 1]);
448                prop_assert!(
449                    (a == u && b == v) || (a == v && b == u),
450                    "edge {} = ({},{}) does not join {} and {}",
451                    e, a, b, u, v
452                );
453            }
454        }
455
456        /// A* with the null heuristic must agree with Dijkstra
457        /// (`get_shortest_path`) on path length, and on reachability.
458        #[test]
459        fn astar_null_matches_dijkstra_length(
460            g in arb_graph(6),
461            from in 0u32..6,
462            to in 0u32..6,
463        ) {
464            let n = g.vcount();
465            prop_assume!(from < n && to < n);
466            let ones = vec![1.0_f64; g.ecount()];
467            let astar = get_shortest_path_astar(&g, from, to, Some(&ones), DijkstraMode::All, None)
468                .expect("astar");
469            let dij = get_shortest_path(&g, from, to, Some(&ones), DijkstraMode::All)
470                .expect("dijkstra");
471            prop_assert_eq!(astar.vertices.is_empty(), dij.vertices.is_empty());
472            prop_assert_eq!(astar.edges.len(), dij.edges.len());
473        }
474
475        /// An admissible heuristic must not change the shortest-path
476        /// length found with the null heuristic.
477        #[test]
478        fn admissible_heuristic_preserves_length(
479            g in arb_graph(6),
480            from in 0u32..6,
481            to in 0u32..6,
482        ) {
483            let n = g.vcount();
484            prop_assume!(from < n && to < n);
485            let null = get_shortest_path_astar(&g, from, to, None, DijkstraMode::All, None)
486                .expect("null");
487            // h(v,to) = 1 for v!=to, 0 for v==to: always admissible on
488            // unweighted graphs since any path uses at least one edge.
489            let h = |v: VertexId, t: VertexId| if v == t { 0.0 } else { 1.0 };
490            let heur = get_shortest_path_astar(&g, from, to, None, DijkstraMode::All, Some(&h))
491                .expect("heur");
492            prop_assert_eq!(null.vertices.is_empty(), heur.vertices.is_empty());
493            prop_assert_eq!(null.edges.len(), heur.edges.len());
494        }
495    }
496}
rust_igraph/algorithms/paths/get_shortest_path_astar.rs

rust_igraph/algorithms/paths/
get_shortest_path_astar.rs
