simple_graph_algorithms

This library aims to provide simple to use implementations for various algorithms run on graphs.

Algorithms

The following algorithms are currently implemented in this library:

• Dijkstra's algorithm
• Bellman-Ford algorithm

Documentation

The documentation will be hosted on docs.rs once the first version has been released to crates.io.

Performance

These tests where performed on a Ryzen 5 7600x. Performance might be slower on older hardware.

To run these tests yourself type cargo bench, a full run will take a few minutes.

lib.rs:

Overview

All algorithms in this crate are run using the Graph struct. It is used to organize nodes that are connected to each other using weighted edges and to provide a simple to use interface.

Click here to see a list of implemented algorithms.

Minimal working example

use simple_graph_algorithms::{Graph, algorithms::{dijkstra, RunAlgorithmError}};

fn main() -> Result<(), RunAlgorithmError> {
    // Create empty graph
    let mut graph = Graph::new();

    // Add new nodes to the graph
    graph.add_node("a");
    graph.add_node("b");
    graph.add_node("c");
    graph.add_node("d");
    graph.add_node("e");

    // Add edges to the graph
    graph.add_edge(1, &"a", &"b"); // Adds an edge that leads from a to b with weight 1
    graph.add_edge(2, &"a", &"c");
    graph.add_edge(5, &"b", &"d");
    graph.add_edge(3, &"c", &"a");
    graph.add_edge(4, &"d", &"a");
    graph.add_edge(2, &"d", &"c");
    graph.add_edge(3, &"c", &"e");
    
    // Calculate the shortest path tree starting at node "a" using Dijkstra's algorithm
    let spt = dijkstra(&mut graph, &"a")?;

    // Get the shortest distance from "a" to other nodes
    assert_eq!(spt.shortest_distance(&"d"), Some(6));
    assert_eq!(spt.shortest_distance(&"c"), Some(2));
    assert_eq!(spt.shortest_distance(&"e"), Some(5));

    Ok(())
}

Features