Crate dijkstra_suite 

A Dijkstra’s algorithm implementation that aims to be simple to use and fast to run

simple. nodes id and its cost are defined by yuor own types

fast. ok, it’s still a work-in-progress, but the goal is a fast computing with as less allocations as possible

[dependencies]
dijkstra-suite = "0.1.0-beta.3"

Usage

Create a Graph, define the start and the end node ids, then call dijkstra_path() function. Returned result is a path of Path type, represented as an ordinated sequence of node ids along with the total weight of the path (the sum of all node weights of the path)

Errors

All errors convolute to DijkstraError, import it from error module and handle every error of the library. See error for further usage information

Example

use dijkstra_suite::dijkstra::dijkstra_path;
use dijkstra_suite::graph::Graph;
use dijkstra_suite::path::Path;
use dijkstra_suite::node::{Node, NodeConnection};

let mut graph: Graph<&str, f32> = Graph::default();
let node_a = Node {
    id: "A",
    weight: 0.0,
    neighbours: vec![
        NodeConnection {
            from: "A",
            to: "B",
            weight: 7.0,
        },
        NodeConnection {
            from: "A",
            to: "E",
            weight: 1.0,
        },
    ],
};

let node_b = Node {
    id: "B",
    weight: 0.0,
    neighbours: vec![
        NodeConnection {
            from: "B",
            to: "A",
            weight: 7.0,
        },
        NodeConnection {
            from: "B",
            to: "C",
            weight: 3.0,
        },
        NodeConnection {
            from: "B",
            to: "E",
            weight: 8.0,
        },
    ],
};

let node_c = Node {
    id: "C",
    weight: 0.0,
    neighbours: vec![
        NodeConnection {
            from: "C",
            to: "B",
            weight: 3.0,
        },
        NodeConnection {
            from: "C",
            to: "D",
            weight: 6.0,
        },
        NodeConnection {
            from: "C",
            to: "E",
            weight: 2.0,
        },
    ],
};

let node_d = Node {
    id: "D",
    weight: 0.0,
    neighbours: vec![
        NodeConnection {
            from: "D",
            to: "C",
            weight: 6.0,
        },
        NodeConnection {
            from: "D",
            to: "E",
            weight: 7.0,
        },
    ],
};

let node_e = Node {
    id: "E",
    weight: 0.0,
    neighbours: vec![
        NodeConnection {
            from: "E",
            to: "A",
            weight: 1.0,
        },
        NodeConnection {
            from: "E",
            to: "B",
            weight: 8.0,
        },
        NodeConnection {
            from: "E",
            to: "C",
            weight: 2.0,
        },
        NodeConnection {
            from: "E",
            to: "D",
            weight: 7.0,
        },
    ],
};

graph.insert(node_a.id, node_a);
graph.insert(node_b.id, node_b);
graph.insert(node_c.id, node_c);
graph.insert(node_d.id, node_d);
graph.insert(node_e.id, node_e);

let result = dijkstra_path(&graph, "B", "D");

let expected_path: Path<&str, f32> = Path {
    weight: 9.0,
    steps: vec!["B", "C", "D"],
};

assert_eq!(result.unwrap(), expected_path)

Re-exports

pub use dijkstra::*;

Modules

compute

Core computing-related types

dijkstra

A Dijkstra’s algorithm implementation that aims to be simple to use and fast to run

error

customized library-wide error handling

graph

This modules defines types and traits for a graph

node

This modules defines types and traits for a graph node

path

Standardized path types and behaviours

strategy

Strategy traits to handle multiple implementation logics