pathfinding Rust Library

The pathfinding library uses a functional approach rather than requiring specific graph data structures. Instead, all algorithms rely on a successor function that defines how to navigate from one node to its neighbors. This allows you to use any representation (adjacency lists, matrices, edge lists, or implicit graphs).

Depending on the algorithm type, the successor function must return different types:

• For weighted algorithms (e.g., dijkstra, astar): The function must return an iterator or collection of (neighbor_node, cost) pairs.
• For unweighted algorithms (e.g., bfs, dfs): The function must return an iterator or collection of just the neighbor_nodes.

This design implicitly defines your graph structure through the logic of the function itself.

// For weighted graphs (Dijkstra, A*, Fringe, etc.)
fn successors(node: &Node) -> impl IntoIterator<Item = (Node, Cost)>

// For unweighted graphs (BFS, DFS, etc.)
fn successors(node: &Node) -> impl IntoIterator<Item = Node>

Check if a path exists

Use dijkstra and check if the result is is_some().

let path_exists = dijkstra(&start, successors, |&n| n == goal).is_some();

Find all reachable nodes and costs

Use dijkstra_all to get a map of all reachable nodes and their minimum costs from the start.

use pathfinding::prelude::dijkstra_all;
let result = dijkstra_all(&start, successors);

Check against multiple goals

Pass a closure to the goal parameter that checks if the current node is contained in a list of goals.

let goals = vec![goal1, goal2, goal3];
let result = dijkstra(&start, successors, |node| goals.contains(node));

Filter nodes within a cost budget

Use dijkstra_all and then filter the resulting iterator by cost.

use pathfinding::prelude::dijkstra_all;
let reachable = dijkstra_all(&start, successors);
let within_budget: Vec<_> = reachable
    .into_iter()
    .filter(|(_, cost)| *cost <= budget)
    .collect();

You can use the astar function to find the shortest path in spatial graphs (like GIS or mapping applications). This requires defining a Location struct for nodes, a distance_to method for the heuristic, and a successor function that returns neighbors and their associated costs. For A* to be effective, the heuristic must be admissible (it must never overestimate the true cost to the goal).

use pathfinding::prelude::astar;
use std::collections::HashMap;

#[derive(Debug, Clone, Hash, Eq, PartialEq)]
struct Location {
    id: u32,
    x: f64,
    y: f64,
}

impl Location {
    fn distance_to(&self, other: &Location) -> u32 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        ((dx * dx + dy * dy).sqrt() * 100.0) as u32 // Scale for integer costs
    }
}

struct SpatialGraph {
    locations: HashMap<u32, Location>,
    edges: HashMap<u32, Vec<(u32, u32)>>, // node_id -> vec of (neighbor_id, cost)
}

impl SpatialGraph {
    // ... (new, add_location, add_edge methods) ...

    fn find_shortest_path(&self, start_id: u32, goal_id: u32) -> Option<(Vec<u32>, u32)> {
        let goal_location = self.locations.get(&goal_id)?;

        astar(
            &start_id,
            |&node_id| {
                self.edges
                    .get(&node_id)
                    .cloned()
                    .unwrap_or_default()
            },
            |&node_id| {
                // Heuristic: straight-line distance to goal
                self.locations
                    .get(&node_id)
                    .map(|loc| loc.distance_to(goal_location))
                    .unwrap_or(u32::MAX)
            },
            |&node_id| node_id == goal_id,
        )
    }
}

The iddfs (Iterative Deepening Depth-First Search) function computes the shortest path from a start node to a node that satisfies the success condition. It is useful for finding shortest paths in unweighted graphs while maintaining the memory efficiency of depth-first search.

Parameters

• start: The starting node of type N.
• successors: A closure FnMut(&N) -> IN that returns an iterator of successor nodes for a given node.
• success: A closure FnMut(&N) -> bool that returns true if the given node is the goal. Note that the goal does not have to be a specific node; it can be a dynamic condition.

Behavior

• Returns Some(Vec<N>) containing the shortest path (including both the start and end nodes) if a path is found.
• Returns None if no path can be found.
• A node will never be included twice in the path (it avoids cycles based on the Eq relationship).
• The start node's ownership is taken by iddfs as no clones are made.

use pathfinding::prelude::iddfs;

// Example 1: Using a custom struct
#[derive(Eq, PartialEq, Clone, Debug)]
struct Pos(i32, i32);

impl Pos {
  fn successors(&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 = iddfs(Pos(1, 1), |p| p.successors(), |p| *p == GOAL);
assert_eq!(result.expect("no path found").len(), 5);

// Example 2: Using closures and tuples for brevity
static GOAL_TUPLE: (i32, i32) = (4, 6);
let result = iddfs((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_TUPLE);
assert_eq!(result.expect("no path found").len(), 5);