安全遍历有向无环图

Question

我正在尝试构建和遍历 DAG。似乎有两种可行的方法：对边缘使用 Rc<RefCell<Node>>，或使用竞技场分配器和一些 unsafe 代码。 (See details here.)

我选择前者，但很难遍历图的边缘，因为子节点的任何借用都依赖于对其父节点的借用：

use std::cell::RefCell;
use std::rc::Rc;

// See: https://aminb.gitbooks.io/rust-for-c/content/graphs/index.html,
//      https://github.com/nrc/r4cppp/blob/master/graphs/src/ref_graph.rs
pub type Link<T> = Rc<RefCell<T>>;

pub struct DagNode {
    /// Each node can have several edges flowing *into* it, i.e. several owners,
    /// hence the use of Rc. RefCell is used so we can have mutability
    /// while building the graph.
    pub edge: Option<Link<DagNode>>,

    // Other data here
}

// Attempt to walk down the DAG until we reach a leaf.
fn walk_to_end(node: &Link<DagNode>) -> &Link<DagNode> {
    let nb = node.borrow();
    match nb.edge {
        Some(ref prev) => walk_to_end(prev),
        // Here be dragons: the borrow relies on all previous borrows,
        // so this fails to compile.
        None => node
    }
}

我可以修改引用计数，即

fn walk_to_end(node: Link<HistoryNode>) -> Link<HistoryNode> {
    let nb = node.borrow();
    match nb.previous {
        Some(ref prev) => walk_to_end(prev.clone()),
        None => node.clone()
    }
}

但是每次遍历节点时都增加引用计数似乎很麻烦。这里的惯用方法是什么？

Answer 1

Rc 在这里并不是真正的问题：如果您摆脱 RefCells，一切都会编译。实际上，在某些情况下，这可能是一个解决方案：如果您需要改变节点的内容，而不是边，您可以只更改数据结构，使边不在 RefCell 内。

争论也不是真正的问题；这编译：

fn walk_to_end(node: &Link<DagNode>) -> Link<DagNode> {
    let nb = node.borrow();
    match nb.edge {
        Some(ref prev) => walk_to_end(prev),
        None => node.clone()
    }
}

这里的问题实际上是return结果。基本上，没有任何方法可以编写您想要的 return 值。我的意思是，理论上你可以让你的方法 return 成为 Vec<Ref<T>> 的包装器，但这比仅仅增加结果的引用计数要昂贵得多。

更一般地说，Rc<RefCell<T>> 很难使用，因为它是一个复杂的数据结构：您可以安全地同时改变多个节点，并且它会准确跟踪每个节点引用了多少条边。

请注意，您不必深入研究不安全代码即可使用竞技场。 https://crates.io/crates/typed-arena 为竞技场提供安全的 API。我不确定为什么您链接到的示例使用 UnsafeCell；当然没有必要。

安全遍历有向无环图

Safely traversing a directed acyclic graph

lifetime

graph-traversal

directed-acyclic-graphs

rust