标签: petgraph

我有一个有向图，想找到从节点 A 到节点 B 的最短路径。我在crates.io上搜索并找到了petgraph，它看起来像是最受欢迎的 crate。它实现了许多算法，但没有一个能解决我的任务。我错过了什么？

例如，Dijkstra 算法返回路径成本，但哪条路径的成本最低？该Bellman-Ford算法返回路径成本和节点，但没有路径。

这是我发现从图中打印路径的最简单方法：

extern crate petgraph;
use petgraph::prelude::*;
use petgraph::algo::dijkstra;

fn main() {
    let mut graph = Graph::<&str, i32>::new();
    let a = graph.add_node("a");
    let b = graph.add_node("b");
    let c = graph.add_node("c");
    let d = graph.add_node("d");

    graph.extend_with_edges(&[(a, b, 1), (b, c, 1), (c, d, 1), (a, b, 1), (b, d, 1)]);
    let paths_cost = dijkstra(&graph, a, Some(d), |e| *e.weight());
    println!("dijkstra {:?}", paths_cost);

    let …

Petgraph 文档暗示了 Serde 支持。在“当前功能”下：

serde-1 - 默认关闭。使用 serde 1.0 启用 Graph、StableGraph 的序列化。可能需要比单独的 petgraph 更新版本的 Rust。

我可以在源代码中看到该文件serde_utils.rs，但我没有找到显示如何使 Serde 支持正常工作的示例。

我知道如何启用可选的板条箱功能。我的问题旨在使序列化和反序列化正常工作。

我正在尝试Graph从 JSON 数据创建一个 petgraph 。JSON 包含图的边，键代表起始顶点，值是相邻顶点的列表。可以生成带有边向量的图。

我设法创建了一个Vec<(String, String))>但不是Vec<(&str, &str)>预期的。

extern crate petgraph;
extern crate serde_json;

use petgraph::prelude::*;
use serde_json::{Value, Error};

fn main() {
    let data = r#"{
      "A": [ "B" ],
      "B": [ "C", "D" ],
      "D": [ "E", "F" ]
    }"#;
    let json_value: Value = serde_json::from_str(data).unwrap();
    let mut edges: Vec<(String, String)> = vec![];
    if let Value::Object(map) = json_value {
        for (from_edge, array) in &map {
            if let &Value::Array(ref array_value) = array …

edgesPetgraph Graph 的函数返回边的迭代器。然后，每次迭代都会返回一个EdgeReference，它可以轻松存储节点和边权重，如果您调试打印一个，您可以看到它。但不幸的是，这些EdgeReference成员都是私有的，因此您无法在代码中访问它们。

那么如何迭代连接到节点的边和节点呢？这看起来应该很简单，但我还没有找到任何示例代码。

我正在使用 Petgraph 的toposort函数来获取图表节点的排序列表。toposort然而，不保证同一级别的所有节点都将以一致的确定性顺序返回。Petgraph 中是否还有其他选项可以按确定性顺序返回节点，或者我需要编写自己的函数吗？（如果是的话，有什么指示吗？）