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

Each commit must be self-sufficient and clean. If during inspection or code review you need to make further changes to a commit, please squash it. You may use git rebase -i, or more convenient tools such as jj or git-branchless, in order to manipulate your git commits.

If a pull-request should automatically close an open issue, please include "Fix #xxx# or "Close #xxx" in the pull-request cover-letter.