126 releases (71 stable)
4.11.0 | Aug 31, 2024 |
---|---|
4.10.0 | Jun 18, 2024 |
4.9.1 | Feb 12, 2024 |
4.8.0 | Dec 22, 2023 |
0.1.5 | Dec 30, 2016 |
#24 in Algorithms
37,137 downloads per month
Used in 38 crates
(30 directly)
190KB
3.5K
SLoC
pathfinding
This crate implements several pathfinding, flow, and graph algorithms in Rust. The algorithms are generic over their arguments. See the documentation for more information about the various algorithms.
Using this crate
In your Cargo.toml
, put:
[dependencies]
pathfinding = "4.11.0"
You can then pull your preferred algorithm (BFS in this example) using:
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.
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);
License
This code is released under a dual Apache 2.0 / MIT free software license.
Contributing
You are welcome to contribute by opening issues or submitting pull requests. Please open an issue before implementing a new feature, in case it is a work in progress already or it is fit for this repository.
In order to pass the continuous integration tests, your code must be formatted using the latest
rustfmt
with the nightly rust toolchain, and pass cargo clippy
and pre-commit
checks.
Those will run automatically when you submit a pull request. You can install pre-commit
to your
checked out version of the repository by running:
$ pre-commit install --hook-type commit-msg
This repository uses the conventional commits commit message style, such as:
- feat(matrix): add
Matrix::transpose()
- fix(tests): remove unused imports
If a pull-request should automatically close an open issue, please include "Fix #xxx# or "Close #xxx" in the pull-request cover-letter.
Dependencies
~1.2–2MB
~37K SLoC