Implementare una struttura dati simile a un grafico in Rust

Question

Ho una struttura dati che può essere rappresentata come un grafo unidirezionale tra alcune strutture collegate con oggetti di collegamento perché i collegamenti contengono metadati.

Sembra qualcosa di simile a questo:

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

Tutta la struttura ha bisogno di essere mutevole perché ho bisogno di essere in grado di aggiungere e rimuovere i link e le risorse in fase di esecuzione. Per questo motivo, non posso usare il normale modello di durata e legare le risorse al tempo di vita della struttura genitrice.

Capisco che ho bisogno di to "choose my own guarantee" selezionando il tipo appropriato, ma non sono sicuro di quale sia il modo migliore per risolvere questo problema.

Answer 1

In realtà, per una struttura simile a un grafico, la soluzione più semplice consiste nell'utilizzare un'arena come TypedArena.

La durata dei nodi dipenderà solo dalla durata dell'istanza dell'arena tipizzata da cui sono stati creati, il che semplifica notevolmente la gestione delle risorse.

Attenzione: evitare uno scenario in cui si aggiunge in modo dinamico/rimuovere i nodi al grafico, come i nodi non verrà rimosso dalla scena fino a quando ha detto arena è caduto, quindi la dimensione dell'arena sarebbe cresciuto, senza limiti.

---

Se vi trovate in una situazione in cui si aggiungere/rimuovere i nodi in fase di esecuzione, un'altra soluzione è quella di:

• avere una collezione di Resources
• avere i bordi solo indirettamente riferimento alla Resources (non proprietari, e non debitori o)

due esempi:

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

in entrambi i casi, si sono responsabili per ripulire i bordi quando si rimuove una risorsa, e oblio può portare a una perdita di memoria e di panico (quando dereferenziazione) ma è al contrario sicuro.

Ci sono, probabilmente, infinite variazioni su quanto sopra.

Answer 2

La modellazione di strutture di tipo grafico in Rust non è un problema semplice. Qui ci sono due discussioni preziosi Nick Cameron e Niko Matsakis (due sviluppatori principali Rust a Mozilla.)

Graphs and arena allocation

Modeling Graphs in Rust Using Vector Indices

Answer 3

La soluzione più semplice per una struttura grafico simile è quello di uso di un libreria di modelli grafici.petgraph è una buona scelta:

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

Le garanzie che dovete scegliere qui il centro attorno al membro del ResourceList. Presumo che si desideri disporre di Resource s immutabili condivisi a thread singolo.

• se avete bisogno di condividerle attraverso le discussioni, utilizzare un Vec<Arc<Resource>>
• se non sono condivisi solo loro riscatto - Vec<Resource>
• se hanno bisogno di essere mutevole, utilizzare un Vec<Rc<RefCell<Resource>>> (O un Mutex se anche multithread)