pathfinding

Pathfinding, flow, and graph algorithms

113 releases(58 stable)

 new 4.3.2 Sep 22, 2023 May 30, 2023 Jan 17, 2023 Dec 25, 2022 Dec 30, 2016

#24 in Algorithms

Used in 25 crates (22 directly)

Apache-2.0/MIT

175KB
3K SLoC

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.
• BFS: explore nearest successors first, then widen the search.
• Brent: find a cycle in an infinite sequence.
• 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.
• Floyd: find a cycle in an infinite sequence.
• 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.
• IDDFS: explore longer and longer paths in an unweighted 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.
• Yen: find k-shortest paths using Dijkstra.

Matching

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

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.

Using this crate

In your `Cargo.toml`, put:

``````[dependencies]
pathfinding = "4.3.2"
``````

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);
``````

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

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.

This repository use the imperative mode in commit messages, such as "Add IDDFS", "Fix #xxx". This style is preferred over "Added IDDFS" or "Fixed #xxx".

~1.3–1.9MB
~38K SLoC