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.
- breadth-first search (BFS): explore nearest neighbours first, then widen the search.
- depth-first search (DFS): explore a graph by going as far as possible, then backtrack.
- Dijkstra: find the shortest path in a weighted graph.
- Edmonds Karp: find the maximum flow in a weighted graph.
- Fringe: find the shortest path in a weighted graph using an heuristic to guide the process.
- IDA*: explore longer and longer paths in a weighted graph at the cost of multiple similar examinations.
- strongly connected components: find strongly connected components in a directed graph.
- topological sorting: find an acceptable topological order in a directed graph.
Undirected graphs
Matching
- Kuhn-Munkres (Hungarian algorithm): find the maximum (or minimum) matching
in a weighted bipartite graph.
Using this crate
In your Cargo.toml, put:
ini
[dependencies]
pathfinding = "0.8"
You can then pull your preferred algorithm (BFS in this example) using:
``` rust
extern crate pathfinding;
use pathfinding::prelude::bfs;
```
Example
We will search the shortest path on a chess board to go from (1, 1) to (4, 6) doing only knight
moves.
``` rust
use pathfinding::prelude::bfs;
[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);
impl Pos {
fn neighbours(&self) -> Vec {
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);
```
License
This code is released under a dual Apache 2.0 / MIT free software license.