#path-finding #graph #path #mst #graph-node #graph-algorithms #search-algorithms

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
0.2.1 Mar 16, 2023
0.1.6 Mar 14, 2023

#1716 in Algorithms

Download history 5/week @ 2024-03-29

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

Dependencies

~3MB
~58K SLoC