Crate pathfinding

pathfinding

This crate implements several pathfinding, flow, and graph algorithms in Rust.

Algorithms

The algorithms are generic over their arguments.

Directed graphs

• A*: find the shortest path in a weighted graph using an heuristic to guide the process (⇒ Wikipedia)
• BFS: explore nearest successors first, then widen the search (⇒ Wikipedia)
• Bidirectional search: simultaneously explore paths forwards from the start and backwards from the goal (=> Wikipedia)
• Brent: find a cycle in an infinite sequence (⇒ Wikipedia)
• DFS: explore a graph by going as far as possible, then backtrack (⇒ Wikipedia)
• Dijkstra: find the shortest path in a weighted graph (⇒ Wikipedia)
• Edmonds Karp: find the maximum flow in a weighted graph (⇒ Wikipedia)
• Floyd: find a cycle in an infinite sequence (⇒ Wikipedia)
• Fringe: find the shortest path in a weighted graph using an heuristic to guide the process (⇒ Wikipedia)
• IDA*: explore longer and longer paths in a weighted graph at the cost of multiple similar examinations (⇒ Wikipedia)
• IDDFS: explore longer and longer paths in an unweighted graph at the cost of multiple similar examinations (⇒ Wikipedia)
• paths counting: count the paths to the destination in an acyclic graph
• strongly connected components: find strongly connected components in a directed graph (⇒ Wikipedia)
• topological sorting: find an acceptable topological order in a directed graph (⇒ Wikipedia)
• Yen: find k-shortest paths using Dijkstra (⇒ Wikipedia)

Undirected graphs

• connected components: find disjoint connected sets of vertices (⇒ Wikipedia)
• Kruskal: find a minimum-spanning-tree (⇒ Wikipedia)
• Prim: find a minimum-spanning-tree (⇒ Wikipedia)
• [cliques]: find maximum cliques in a graph (= Wikipedia)

Matching

• Kuhn-Munkres (Hungarian algorithm): find the maximum (or minimum) matching in a weighted bipartite graph (⇒ Wikipedia)

Miscellaneous structures

• A Grid type representing a rectangular grid in which vertices can be added or removed, with automatic creation of edges between adjacent vertices.
• A Matrix type to store data of arbitrary types, with neighbour-aware methods.

Example

We will search the shortest path on a chess board to go from (1, 1) to (4, 6) doing only knight moves.

use pathfinding::prelude::bfs;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
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 = bfs(&Pos(1, 1), |p| p.successors(), |p| *p == GOAL);
assert_eq!(result.expect("no path found").len(), 5);

Note on floating-point types

Several algorithms require that the numerical types used to describe edge weights implement Ord. If you wish to use Rust built-in floating-point types (such as f32) that implement PartialOrd in this context, you can wrap them into compliant types using the ordered-float crate.

The minimum supported Rust version (MSRV) is Rust 1.77.2.

Re-exports

pub use num_traits;

Modules

cycle_detectionDeprecated

Deprecated: moved into the directed module.

directed

Algorithms for directed graphs.

grid

Rectangular grid in which vertices can be added or removed, with or without diagonal links.

kuhn_munkres

Compute a maximum weight maximum matching between two disjoints sets of vertices using the Kuhn-Munkres algorithm (also known as Hungarian algorithm).

matrix

Matrix of an arbitrary type and utilities to rotate, transpose, etc.

prelude

Export all public functions and structures for an easy access.

undirected

Algorithms for undirected graphs.

utils

Miscellaneous utilities

Macros

matrix

The matrix! macro allows the declaration of a Matrix from static data. All rows must have the same number of columns. The data will be copied into the matrix. There exist two forms: