### 9 releases

0.3.1 | Mar 23, 2023 |
---|---|

0.2.1 | Mar 16, 2023 |

0.1.6 | Mar 14, 2023 |

#**505** in Algorithms

**31** downloads per month

**MIT**license

42KB

990 lines

# Path finding library

**Beginner in Rust - Feedback highly appreciated!**

This library will contain standard path finding algorithms and return the resulting path or graph object

*Table of contents generated with
markdown-toc*

**Currently supported**:

- construct graphs
- create minimum spanning tree from graph
- find path with depth-first search
- find path with breadth-first search
- find path with bidirectional breadth-first search
- find path with the dijkstra algorithm
- find path with the A* algorithm, with heuristic function:
- euclidean distance
- manhattan distance

Download the crate: https://crates.io/search?q=path-finding-lib

## How to use

At the moment, we have three major concepts:

- Edge
- Node
- Graph
- Position

You only need to pass edges to the graph. The nodes are generated automatically. Each pathfinding method will accept a graph, and return a graph that only contains the edges and nodes of the result.

Alternatively, you can also create a graph if you provide an adjacency matrix. Edges and nodes will be generated automatically.

If you want to use the A* path-finding algorithm, please make sure to provide positional information for each node.

### Create Graph

- Create Edge

`pub` `fn` `your_function``(``)`` ``{`
`graph``::``Edge``::`from`(`
`0` `/*` edge index `*/``,`
`0` `/*` source node `*/``,`
`1` `/*` destination node `*/``,`
`0.``1``,` `/*` weight `*/`
`)``;`
`}`

- Create Graph from edges

`pub` `fn` `your_function``(``)`` ``{`
`graph``::``Graph``::`from`(``Vec``::`from`(``[`edge1`,` edge2`]``)``)``;`
`}`

- Create Graph from adjacency matrix

`pub` `fn` `your_function``(``)`` ``{`
`let` `mut` matrix`:` `&``[``&``[``f32``]``]` `=` `&``[`
`&``[``0.``0``,` `4.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `8.``0``,` `0.``0``]``,`
`&``[``4.``0``,` `0.``0``,` `8.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `11.``0``,` `0.``0``]``,`
`&``[``0.``0``,` `8.``0``,` `0.``0``,` `7.``0``,` `0.``0``,` `4.``0``,` `0.``0``,` `0.``0``,` `2.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `7.``0``,` `0.``0``,` `9.``0``,` `14.``0``,` `0.``0``,` `0.``0``,` `0.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `0.``0``,` `9.``0``,` `0.``0``,` `10.``0``,` `0.``0``,` `0.``0``,` `0.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `4.``0``,` `14.``0``,` `10.``0``,` `0.``0``,` `2.``0``,` `0.``0``,` `0.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `2.``0``,` `0.``0``,` `1.``0``,` `6.``0``]``,`
`&``[``8.``0``,` `11.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `1.``0``,` `0.``0``,` `7.``0``]``,`
`&``[``0.``0``,` `0.``0``,` `2.``0``,` `0.``0``,` `0.``0``,` `0.``0``,` `6.``0``,` `7.``0``,` `0.``0``]`
`]``;`
`graph``::``Graph``::`from_adjacency_matrix`(`matrix`)``;`
`}`

### Graph operations

You may want to get some information or mutate the graph in some way. Therefore, the graph currently supports three functions for convenience operations or to provide data for a heuristic function.

#### sorted_by_weight_asc

`pub` `fn` `your_function``(``)`` ``{`
`let` edges`:` `Vec``<`Edge`>` `=` graph`.``sorted_by_weight_asc``(``)``;` `//` will return a vector with edges ascending by weight
`}`

#### offer_positions

`pub` `fn` `your_function``(``)`` ``{`
`//` provide a hashmap, mapping the node id to a position - used for a* pathfinding heuristics
graph`.``offer_positions``(``HashMap``::`from`(``[``(``1``,` `Position``::`from`(``0.``1``,` `0.``2``,` `0.``3``)``)``]``)``)``;`
`}`

### Minimum spanning tree

`pub` `fn` `your_function``(``)`` ``{`
`let` mst_graph `=` `graph``::`minimum_spanning`(`graph`)``;`
`}`

### Depth-first search

`pub` `fn` `your_function``(``)`` ``{`
`let` dfs `=` `path``::`find`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`DepthFirstSearch `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

### Breadth-first search

`pub` `fn` `your_function``(``)`` ``{`
`let` bfs `=` `path``::`find`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`BreadthFirstSearch `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

### Bidirectional breadth-first search

`pub` `fn` `your_function``(``)`` ``{`
`let` bi_bfs `=` `path``::`find`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`BiBreadthFirstSearch `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

### Dijkstra path search

`pub` `fn` `your_function``(``)`` ``{`
`let` dijkstra `=` `path``::`find`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(`Dijkstra `{``}``)` `/*` used algorithm `*/`
`)``;`
`}`

### A* path search

You can use the A* path-finding algorithm by providing either an existing heuristic function as shown below. Or you provide your own heuristic function. In case you use an existing heuristic function, make sure to provide the positional information for the nodes.

`pub` `fn` `your_function_with_euclidean_distance``(``)`` ``{`
`let` a_star `=` `path``::`find`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(` AStar `{` heuristic`:` `Box``::`from`(`euclidean_distance`)` `}``)``,` `/*` used algorithm + euclidean distance heuristic function `*/`
`)``;`
`}`

`pub` `fn` `your_function_with_manhattan_distance``(``)`` ``{`
`let` a_star `=` `path``::`find`(`
`4` `/*` source `*/``,`
`1` `/*` target `*/``,`
`&`graph`,`
`Box``::`from`(` AStar `{` heuristic`:` `Box``::`from`(`manhattan_distance`)` `}``)``,` `/*` used algorithm + manhattan distance heuristic function `*/`
`)``;`
`}`

#### Dependencies

~1.5–2MB

~46K SLoC