pathfinding

Path finding library for Rust

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.

Undirected graphs

connected components: find disjoint connected sets of vertices.
Kruskal: find a minimum-spanning-tree.

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 pathfinding

In order to use pathfinding, you can add it to your Cargo.toml as a dependency

[dependencies]
pathfinding = "4.8"

The package documentation is available online.

Getting pathfinding

Published version (4.8)

You can access the crate from

and the

Development version

You can get the current development version of pathfinding using git:

git clone https://github.com/evenfurther/pathfinding.git

This will create a pathfinding directory in which you will be able to record your own changes. You can also browse the pathfinding repository on GitHub.

Contributing to pathfinding

Reporting bugs and asking for features

If you find a bug or have an idea for a new feature, you might consider adding a new issue. The more precise you will be in your description, the more useful it will be.

Submitting patches

Patches are gladly accepted from their original author. Along with any patches, please state that the patch is your original work and that you license the work to the pathfinding project under a license compatible with the current one (Apache 2.0 license / MIT license).

To propose a patch, you may fork the pathfinding repository on GitHub, and issue a pull request. You may also send patches and pull requests by email.