Implementieren einer graphenähnlichen Datenstruktur in Rust

Question

Ich habe eine Datenstruktur, die als unidirektionales Diagramm zwischen einigen Strukturen dargestellt werden kann, die mit Verknüpfungsobjekten verknüpft sind, weil Verknüpfungen Metadaten enthalten.

Es sieht ungefähr so ​​aus:

struct StateMachine { 
    resources: Vec<Resource>, 
    links: Vec<Link>, 
} 
struct Resource { 
    kind: ResourceType, 
     // ... 
} 

enum LinkTarget { 
    ResourceList(Vec<&Resource>), 
    LabelSelector(HashMap<String, String>), 
} 

struct Link { 
    from: LinkTarget, 
    to: LinkTarget, 
    metadata: SomeMetadataStruct, 
} 

Die gesamte Struktur wandelbar sein muss, weil ich brauche zur Laufzeit Links und Ressourcen zu können, hinzufügen und entfernen. Aus diesem Grund kann ich das normale Lebensdauermodell nicht verwenden und die Ressourcen an die Lebensdauer der übergeordneten Struktur binden.

Ich verstehe, dass ich to "choose my own guarantee" durch Auswahl des entsprechenden Typs, aber ich bin mir nicht sicher, was der beste Weg, um dieses Problem zu lösen ist.

Answer 1

Eigentlich ist für eine graphartige Struktur die einfachste Lösung, eine Arena wie TypedArena zu verwenden.

Die Lebensdauer der Knoten hängt dann nur von der Lebensdauer der Instanz der typisierten Arena ab, aus der sie erstellt wurden, was die Ressourcenverwaltung erheblich vereinfacht.

Warnung: Vermeiden Sie ein Szenario, in dem Sie Knoten dynamisch zum Diagramm hinzufügen/entfernen, da die Knoten NICHT aus der Arena entfernt werden, bis diese Arena gelöscht wird. Die Größe der Arena würde also unbegrenzt wachsen.

---

Wenn Sie in einer Situation sind, wo Sie hinzufügen/entfernen Knoten zur Laufzeit, eine andere Lösung zu:

• haben eine Sammlung von Resources
• die Kanten haben nur indirekt auf die verweisen Resources (nicht Besitzer, und nicht die Kreditnehmer entweder)

Zwei Beispiele:

• HashMap<ResourceId, (Resource, Vec<ResourceId>)>
• type R = RefCell<Resource>, Vec<Rc<R>> und Vec<(Weak<R>, Vec<Weak<R>>)>

in jedem Fall sind Sie verantwortlich für die Reinigung der Kanten auf, wenn eine Ressource zu entfernen, und das Vergessen zu einem Speicherverlust und gerät in Panik führen kann (wenn dereferencing) aber ist sonst sicher.

Es gibt, wahrscheinlich, unendliche Variationen auf dem oben genannten.

Answer 2

Die Modellierung graphischer Strukturen in Rust ist kein einfaches Problem. Hier gibt es zwei wertvolle Diskussionen von Nick Cameron und Niko Matsakis (zwei Rust Entwickler bei Mozilla.)

Graphs and arena allocation

Modeling Graphs in Rust Using Vector Indices

Answer 3

Die einfachste Lösung für eine graphenartige Struktur zu Verwendung ein Bibliothek, die Graphen modelliert.petgraph ist eine gute Wahl:

extern crate petgraph; 

use std::rc::Rc; 
use std::collections::HashMap; 

use petgraph::Graph; 

struct Resource; 

enum LinkTarget { 
    ResourceList(Vec<Rc<Resource>>), 
    LabelSelector(HashMap<String, String>), 
} 

struct SomeMetadataStruct; 

fn main() { 
    let mut graph = Graph::new(); 

    let n1 = graph.add_node(LinkTarget::LabelSelector(Default::default())); 
    let n2 = graph.add_node(LinkTarget::LabelSelector(Default::default())); 

    let l2 = graph.add_edge(n1, n2, SomeMetadataStruct); 
} 

Die Garantien, die Sie rund um das Mitglied von ResourceList hier Mitte wählen müssen. Ich nehme an, dass Sie single-threaded shared unveränderliche Resource s haben möchten.

• , wenn Sie brauchen, um sie über Threads zu teilen, verwenden Sie ein Vec<Arc<Resource>>
• , wenn sie nicht nur geteilt werden, besitzen sie - Vec<Resource>
• wenn sie wandelbar sein müssen, verwenden Sie eine Vec<Rc<RefCell<Resource>>> (Oder ein Mutex wenn auch Multithread)