Function pathfinding::directed::fringe::fringe

pub fn fringe<N, C, FN, IN, FH, FS>(
    start: &N, 
    successors: FN, 
    heuristic: FH, 
    success: FS
) -> Option<(Vec<N>, C)> where
    N: Eq + Hash + Clone,
    C: Bounded + Zero + Ord + Copy,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = (N, C)>,
    FH: FnMut(&N) -> C,
    FS: FnMut(&N) -> bool, 

Compute a shortest path using the Fringe search algorithm.

The shortest path starting from start up to a node for which success returns true is computed and returned along with its total cost, in a Some. If no path can be found, None is returned instead.

• start is the starting node.
• successors returns a list of successors for a given node, along with the cost for moving from the node to the successor.
• heuristic returns an approximation of the cost from a given node to the goal. The approximation must not be greater than the real cost, or a wrong shortest path may be returned.
• 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::prelude::fringe;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
  fn distance(&self, other: &Pos) -> u32 {
    (self.0.abs_diff(other.0) + self.1.abs_diff(other.1)) as u32
  }

  fn successors(&self) -> Vec<(Pos, u32)> {
    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)]
         .into_iter().map(|p| (p, 1)).collect()
  }
}

static GOAL: Pos = Pos(4, 6);
let result = fringe(&Pos(1, 1),
                    |p| p.successors(),
                    |p| p.distance(&GOAL) / 3,
                    |p| *p == GOAL);
assert_eq!(result.expect("no path found").1, 4);

The second version does not declare a Pos type, makes use of more closures, and is thus shorter.

use pathfinding::prelude::fringe;

static GOAL: (i32, i32) = (4, 6);
let result = fringe(&(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)]
                               .into_iter().map(|p| (p, 1)),
                    |&(x, y)| (GOAL.0.abs_diff(x) + GOAL.1.abs_diff(y)) / 3,
                    |&p| p == GOAL);
assert_eq!(result.expect("no path found").1, 4);