## path-finding-lib

This library provides a variety of path finding and graph operations. Work in progress.

### 9 releases

 0.3.1 Mar 23, 2023 Mar 16, 2023 Mar 14, 2023

#1664 in Algorithms

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

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

## 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 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);
}
``````
``````pub fn your_function() {
let dfs = path::find(
4 /* source */,
1 /* target */,
&graph,
Box::from(DepthFirstSearch {}) /* used algorithm */
);
}
``````
``````pub fn your_function() {
let bfs = path::find(
4 /* source */,
1 /* target */,
&graph,
Box::from(BreadthFirstSearch {}) /* used algorithm */
);
}
``````
``````pub fn your_function() {
let bi_bfs = path::find(
4 /* source */,
1 /* target */,
&graph,
Box::from(BiBreadthFirstSearch {}) /* used algorithm */
);
}
``````
``````pub fn your_function() {
let dijkstra = path::find(
4 /* source */,
1 /* target */,
&graph,
Box::from(Dijkstra {}) /* used algorithm */
);
}
``````

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 */
);
}
``````

~2.5MB
~56K SLoC