pathfinding/directed/
fringe.rs

1//! Compute a shortest path using the [Fringe search
2//! algorithm](https://en.wikipedia.org/wiki/Fringe_search).
3
4use super::reverse_path;
5use crate::FxIndexMap;
6use indexmap::map::Entry::{Occupied, Vacant};
7use num_traits::{Bounded, Zero};
8use std::collections::VecDeque;
9use std::hash::Hash;
10use std::mem;
11
12/// Compute a shortest path using the [Fringe search
13/// algorithm](https://en.wikipedia.org/wiki/Fringe_search).
14///
15/// The shortest path starting from `start` up to a node for which `success` returns `true` is
16/// computed and returned along with its total cost, in a `Some`. If no path can be found, `None`
17/// is returned instead.
18///
19/// - `start` is the starting node.
20/// - `successors` returns a list of successors for a given node, along with the cost for moving
21///   from the node to the successor. This cost must be non-negative.
22/// - `heuristic` returns an approximation of the cost from a given node to the goal. The
23///   approximation must not be greater than the real cost, or a wrong shortest path may be returned.
24/// - `success` checks whether the goal has been reached. It is not a node as some problems require
25///   a dynamic solution instead of a fixed node.
26///
27/// A node will never be included twice in the path as determined by the `Eq` relationship.
28///
29/// The returned path comprises both the start and end node.
30///
31/// # Example
32///
33/// We will search the shortest path on a chess board to go from (1, 1) to (4, 6) doing only knight
34/// moves.
35///
36/// The first version uses an explicit type `Pos` on which the required traits are derived.
37///
38/// ```
39/// use pathfinding::prelude::fringe;
40///
41/// #[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
42/// struct Pos(i32, i32);
43///
44/// impl Pos {
45///   fn distance(&self, other: &Pos) -> u32 {
46///     (self.0.abs_diff(other.0) + self.1.abs_diff(other.1)) as u32
47///   }
48///
49///   fn successors(&self) -> Vec<(Pos, u32)> {
50///     let &Pos(x, y) = self;
51///     vec![Pos(x+1,y+2), Pos(x+1,y-2), Pos(x-1,y+2), Pos(x-1,y-2),
52///          Pos(x+2,y+1), Pos(x+2,y-1), Pos(x-2,y+1), Pos(x-2,y-1)]
53///          .into_iter().map(|p| (p, 1)).collect()
54///   }
55/// }
56///
57/// static GOAL: Pos = Pos(4, 6);
58/// let result = fringe(&Pos(1, 1),
59///                     |p| p.successors(),
60///                     |p| p.distance(&GOAL) / 3,
61///                     |p| *p == GOAL);
62/// assert_eq!(result.expect("no path found").1, 4);
63/// ```
64///
65/// The second version does not declare a `Pos` type, makes use of more closures,
66/// and is thus shorter.
67///
68/// ```
69/// use pathfinding::prelude::fringe;
70///
71/// static GOAL: (i32, i32) = (4, 6);
72/// let result = fringe(&(1, 1),
73///                     |&(x, y)| vec![(x+1,y+2), (x+1,y-2), (x-1,y+2), (x-1,y-2),
74///                                    (x+2,y+1), (x+2,y-1), (x-2,y+1), (x-2,y-1)]
75///                                .into_iter().map(|p| (p, 1)),
76///                     |&(x, y)| (GOAL.0.abs_diff(x) + GOAL.1.abs_diff(y)) / 3,
77///                     |&p| p == GOAL);
78/// assert_eq!(result.expect("no path found").1, 4);
79/// ```
80#[expect(clippy::missing_panics_doc)]
81pub fn fringe<N, C, FN, IN, FH, FS>(
82    start: &N,
83    mut successors: FN,
84    mut heuristic: FH,
85    mut success: FS,
86) -> Option<(Vec<N>, C)>
87where
88    N: Eq + Hash + Clone,
89    C: Bounded + Zero + Ord + Copy,
90    FN: FnMut(&N) -> IN,
91    IN: IntoIterator<Item = (N, C)>,
92    FH: FnMut(&N) -> C,
93    FS: FnMut(&N) -> bool,
94{
95    let mut now = VecDeque::new();
96    let mut later = VecDeque::new();
97    let mut parents: FxIndexMap<N, (usize, C)> = FxIndexMap::default();
98    let mut flimit = heuristic(start);
99    now.push_back(0);
100    parents.insert(start.clone(), (usize::MAX, Zero::zero()));
101
102    loop {
103        if now.is_empty() {
104            return None;
105        }
106        let mut fmin = C::max_value();
107        while let Some(i) = now.pop_front() {
108            let (g, successors) = {
109                let (node, &(_, g)) = parents.get_index(i).unwrap(); // Cannot fail
110                let f = g + heuristic(node);
111                if f > flimit {
112                    if f < fmin {
113                        fmin = f;
114                    }
115                    later.push_back(i);
116                    continue;
117                }
118                if success(node) {
119                    let path = reverse_path(&parents, |&(p, _)| p, i);
120                    return Some((path, g));
121                }
122                (g, successors(node))
123            };
124            for (successor, cost) in successors {
125                let g_successor = g + cost;
126                let n; // index for successor
127                match parents.entry(successor) {
128                    Vacant(e) => {
129                        n = e.index();
130                        e.insert((i, g_successor));
131                    }
132                    Occupied(mut e) => {
133                        if e.get().1 > g_successor {
134                            n = e.index();
135                            e.insert((i, g_successor));
136                        } else {
137                            continue;
138                        }
139                    }
140                }
141                if !remove(&mut later, &n) {
142                    remove(&mut now, &n);
143                }
144                now.push_front(n);
145            }
146        }
147        mem::swap(&mut now, &mut later);
148        flimit = fmin;
149    }
150}
151
152fn remove<T: Eq>(v: &mut VecDeque<T>, e: &T) -> bool {
153    v.iter().position(|x| x == e).is_some_and(|index| {
154        v.remove(index);
155        true
156    })
157}
pathfinding/directed/fringe.rs

pathfinding/directed/
fringe.rs
