Implementacja graficznej struktury danych w Rust

Question

Mam strukturę danych, która może być reprezentowana jako jednokierunkowy wykres między niektórymi strukturami powiązanymi z obiektami łącza, ponieważ łącza zawierają metadane.

Wygląda to mniej więcej tak:

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

Cała konstrukcja musi być zmienny, ponieważ muszę mieć możliwość dodawania i usuwania linków i zasobów w czasie wykonywania. Z tego powodu nie mogę użyć normalnego modelu życia i powiązać zasoby z czasem życia nadrzędnej struktury.

Rozumiem, że potrzebuję to "choose my own guarantee" wybierając odpowiedni typ, ale nie jestem pewien, jaki jest najlepszy sposób rozwiązania tego problemu.

Answer 1

W rzeczywistości, dla struktury podobnej do wykresu, najprostszym rozwiązaniem jest użycie areny, takiej jak TypedArena.

Żywotność węzłów będzie wtedy zależna tylko od czasu trwania instancji wpisanej areny, z której zostały utworzone, co znacznie uprości zarządzanie zasobami.

Ostrzeżenie: uniknąć sytuacji, w której dynamicznie dodawać/usuwać węzły na wykresie, jak węzły NIE zostanie usunięty z rzędu, aż powiedział arena jest odrzucany, a więc wielkość rzędu będzie rosnąć, nieograniczonego.

---

Jeśli jesteś w sytuacji, w której można dodawać/usuwać węzły w czasie wykonywania, innym rozwiązaniem jest:

• posiada kolekcję Resources
• mieć krawędzie tylko pośrednio odnoszą się do Resources (nie właściciele, a nie kredytobiorcy albo)

dwa przykłady:

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

w obu przypadkach, użytkownik jest odpowiedzialny za sprzątanie brzegów podczas usuwania zasobu, a zapominanie może doprowadzić do wycieku pamięci i paniki (gdy wyłuskania) ale w przeciwnym razie jest bezpieczny.

Istnieją, prawdopodobnie, nieskończone warianty powyższego.

Answer 2

Modelowanie struktur graficznych w Rust nie jest prostym problemem. Tutaj są dwa cenne dyskusje z Nickiem Cameron i Niko Matsakisa (dwa główne deweloperzy Rust w Mozilli.)

Graphs and arena allocation

Modeling Graphs in Rust Using Vector Indices

Answer 3

Najprostszym rozwiązaniem dla konstrukcji wykresu podobny jest do użyć biblioteka, która modeluje wykresy.petgraph jest dobrym wyborem:

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

gwarantuje, że masz do wyboru tutaj koncentrują się wokół członka ResourceList. Zakładam, że chcesz mieć jednowątkowe wspólne niezmienne Resource s.

• jeśli trzeba podzielić je przez wątków, użyć Vec<Arc<Resource>>
• jeśli nie są one udostępniane tylko ich właścicielem - Vec<Resource>
• jeśli muszą być zmienny, użyj Vec<Rc<RefCell<Resource>>> (lub jeśli Mutex również wielowątkowe)