Function pathfinding::bfs

pub fn bfs<N, FN, IN, FS>(
    start: &N, 
    neighbours: FN, 
    success: FS
) -> Option<Vec<N>> where
    N: Eq + Hash + Clone,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = N>,
    FS: FnMut(&N) -> bool, 

Compute a shortest path using the breadth-first search algorithm.

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);