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