Pathfinding library for rust
Clone or download
bors[bot] and samueltardieu Merge #206
206: Cleanup r=samueltardieu a=samueltardieu



Co-authored-by: Samuel Tardieu <sam@rfc1149.net>
Latest commit 59e50fd Jan 15, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.github Remove appveyor CI Jan 8, 2019
benches Remove macro_use usages Dec 6, 2018
examples Remove macro_use usages Dec 6, 2018
src Merge #200 #201 #202 #203 Jan 8, 2019
tests Cleanup Jan 15, 2019
.gitignore Add .gitignore Dec 27, 2016
.gitlab-ci.yml Test only tests and examples in CI, not benches Oct 10, 2018
.travis.yml Test only tests and examples on Travis Oct 10, 2018
Cargo.toml Merge #200 #201 #202 #203 Jan 8, 2019
README.md Merge #200 #201 #202 #203 Jan 8, 2019
release.toml Use release.toml for release information Jul 18, 2018

README.md

pathfinding

Build Status Current Version Documentation License: Apache-2.0/MIT

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

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:

[dependencies]
pathfinding = "2"

You can then pull your preferred algorithm (BFS in this example) using:

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.

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 (available as the rustfmt-preview component of rustup).

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