path-finding-lib 0.2.0

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

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

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 dfs = 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 dfs = path::find(
        4 /* source */, 
        1 /* target */, 
        &graph, 
        Box::from(BiBreadthFirstSearch {}) as Box<dyn PathFinding> /* used algorithm */
    );
}

Dijkstra path search

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