simple_graph_algorithms

这个库旨在为在图上运行的算法提供简单易用的实现。

算法

该库目前实现了以下算法：

• 迪杰斯特拉算法
• 贝尔曼-福特算法

文档

一旦第一个版本发布到 crates.io，文档将托管在 docs.rs 上。

性能

这些测试是在 Ryzen 5 7600x 上进行的。在较旧的硬件上性能可能会更慢。

要运行这些测试，请输入 cargo bench，完整运行将需要几分钟。

lib.rs:

概览

该包中的所有算法都使用 Graph 结构运行。它用于组织使用加权边连接的节点，并提供简单易用的接口。

点击 这里 查看已实现的算法列表。

最小工作示例

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

功能