1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
use ordermap::OrderMap; use ordermap::Entry::Vacant; use std::collections::VecDeque; use std::hash::Hash; use std::usize; use super::reverse_path; /// Compute a shortest path using the [breadth-first search /// algorithm](https://en.wikipedia.org/wiki/Breadth-first_search). /// /// The shortest path starting from `start` up to a node for which `success` returns `true` is /// computed and returned in a `Some`. If no path can be found, `None` /// is returned instead. /// /// - `start` is the starting node. /// - `neighbours` returns a list of neighbours for a given node. /// - `success` checks whether the goal has been reached. It is not a node as some problems require /// a dynamic solution instead of a fixed node. /// /// A node will never be included twice in the path as determined by the `Eq` relationship. /// /// The returned path comprises both the start and end node. /// /// # Example /// /// We will search the shortest path on a chess board to go from (1, 1) to (4, 6) doing only knight /// moves. /// /// The first version uses an explicit type `Pos` on which the required traits are derived. /// /// ``` /// use pathfinding::bfs; /// /// #[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)] /// struct Pos(i32, i32); /// /// impl Pos { /// fn neighbours(&self) -> Vec<Pos> { /// let &Pos(x, y) = self; /// vec![Pos(x+1,y+2), Pos(x+1,y-2), Pos(x-1,y+2), Pos(x-1,y-2), /// Pos(x+2,y+1), Pos(x+2,y-1), Pos(x-2,y+1), Pos(x-2,y-1)] /// } /// } /// /// static GOAL: Pos = Pos(4, 6); /// let result = bfs(&Pos(1, 1), |p| p.neighbours(), |p| *p == GOAL); /// assert_eq!(result.expect("no path found").len(), 5); /// ``` /// /// The second version does not declare a `Pos` type, makes use of more closures, /// and is thus shorter. /// /// ``` /// use pathfinding::bfs; /// /// static GOAL: (i32, i32) = (4, 6); /// let result = bfs(&(1, 1), /// |&(x, y)| vec![(x+1,y+2), (x+1,y-2), (x-1,y+2), (x-1,y-2), /// (x+2,y+1), (x+2,y-1), (x-2,y+1), (x-2,y-1)], /// |&p| p == GOAL); /// assert_eq!(result.expect("no path found").len(), 5); /// ``` pub fn bfs<N, FN, IN, FS>(start: &N, mut neighbours: FN, mut success: FS) -> Option<Vec<N>> where N: Eq + Hash + Clone, FN: FnMut(&N) -> IN, IN: IntoIterator<Item = N>, FS: FnMut(&N) -> bool, { let mut to_see = VecDeque::new(); let mut parents: OrderMap<N, usize> = OrderMap::new(); to_see.push_back(0); parents.insert(start.clone(), usize::MAX); while let Some(i) = to_see.pop_front() { let neighbours = { let node = parents.get_index(i).unwrap().0; if success(node) { let path = reverse_path(&parents, |&p| p, i); return Some(path); } neighbours(node) }; for neighbour in neighbours { if let Vacant(e) = parents.entry(neighbour) { to_see.push_back(e.index()); e.insert(i); } } } None }