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

• How to use
  • Create Graph
  • Minimum spanning tree
  • Depth-first search
  • Breadth-first search
  • Bidirectional breadth-first search
  • Dijkstra path search

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

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

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.

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);
}

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 {}) as Box<dyn PathFinding> /* used algorithm */
    );
}

Breadth-first search

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

Bidirectional breadth-first search

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

Dijkstra path search

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