Sicheres Durchlaufen eines gerichteten azyklischen Graphen

Question

Ich versuche, eine DAG zu erstellen und zu durchlaufen. Es scheint zwei mögliche Ansätze zu geben: Verwenden Sie Rc<RefCell<Node>> für Kanten, oder verwenden Sie einen Arena-Allokator und einen Code von unsafe. (See details here.)

Ich bin für das ehemalige entscheiden, aber Schwierigkeiten haben, um die Grafik zu seinen Rändern durchqueren, wie jeder borrow eines Kindes Knoten verlässt sich leiht seinen Eltern:

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

ich das ändern könnte Referenz-Zähler, dh

aber stoßen die Referenz zählt jedes Mal, wenn Sie einen Knoten durchqueren scheint wie der Hack. Was ist der idiomatische Ansatz hier?

Answer 1

Rc ist nicht wirklich ein Problem hier: Wenn Sie die RefCells loswerden, kompiliert alles nur. In manchen Situationen kann dies eine Lösung sein: Wenn Sie den Inhalt des Knotens mutieren müssen, aber nicht die Kanten, können Sie einfach Ihre Datenstruktur ändern, sodass die Kanten nicht in einer RefCell enthalten sind.

Das Argument ist auch nicht wirklich das Problem; dies kompiliert:

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

Das Problem hier ist wirklich das Ergebnis zurück. Grundsätzlich gibt es keine Möglichkeit, den gewünschten Rückgabewert zu schreiben. Ich meine, Sie könnten theoretisch Ihre Methode einen Wrapper um eine Vec<Ref<T>> zurückgeben, aber das ist viel teurer als nur die Referenzzahl auf das Ergebnis stoßen.

Im Allgemeinen ist Rc<RefCell<T>> schwierig zu arbeiten, weil es eine komplizierte Datenstruktur ist: Sie können mehrere Knoten gleichzeitig sicher mutieren, und es verfolgt genau, wie viele Kanten auf jeden Knoten verweisen.

Beachten Sie, dass Sie nicht in unsicheren Code eintauchen müssen, um eine Arena zu verwenden. https://crates.io/crates/typed-arena bietet eine sichere API für Arenen. Ich bin mir nicht sicher, warum das Beispiel, zu dem Sie eine Verknüpfung hergestellt haben, UnsafeCell verwendet. es ist sicherlich nicht notwendig.