在 Rust 的 petgraph 中，我该如何测试一个节点是否在环中？

Question

我正在使用Rust的petgraph库，想知道如何检查节点是否属于循环。函数petgraph::algo::is_cyclic_directed可以告诉我图中是否存在任何循环，但是在查看所有文档后，我找不到任何可以告诉我节点是否属于循环的函数。我本以为这将是一个常见的任务，需要一个辅助函数。

现在我可以自己遍历图，但我能想到的代码既不是最简洁的，也不太可能高效。

这里最好的选择是什么？

- curiousdannii

---

我原本想说使用algo::has_path_connecting从节点到节点，如果返回true，则存在一个循环。不幸的是，“如果[from和to]相等，则此函数返回true。”所以这种方法行不通。 - David Sullivan

@DavidSullivan 嗯，确实有一些选项看起来很有前途，直到你读完整个描述。;) - curiousdannii

Answer 1

我认为这段代码是有效的，但如果有人知道更好的方法，我会很感激其他的替代方案！

use petgraph::{algo, visit};
fn is_node_in_cycle<G>(graph: G, node: G::NodeId) -> bool
where G: visit::IntoNeighbors + visit::Visitable {
    let mut space = algo::DfsSpace::new(&graph);
    for neighbour in graph.neighbors(node) {
        if algo::has_path_connecting(graph, neighbour, node, Some(&mut space)) {
            return true
        }
    }
    false
}

- curiousdannii