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

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.70.0.

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: