Реализация графоподобной структуры данных в Rust

Question

У меня есть структура данных, которая может быть представлена ​​как однонаправленный граф между некоторыми структурами, связанными с объектами ссылок, потому что ссылки содержат метаданные.

Это выглядит примерно так:

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

Вся структура должна быть изменяемым, потому что мне нужно, чтобы иметь возможность добавлять и удалять ссылки и ресурсы во время выполнения. Из-за этого я не могу использовать обычную модель времени жизни и привязывать ресурсы к жизни родительской структуры.

Я понимаю, что мне нужен to "choose my own guarantee", выбрав подходящий тип, но я не уверен, что это лучший способ решить эту проблему.

Answer 1

На самом деле, для структуры, подобной графику, самым простым решением является использование арены, такой как TypedArena.

Продолжительность жизни узлов будет зависеть только от времени жизни экземпляра типизированной арены, из которой они были созданы, что значительно упростит управление ресурсами.

Предупреждение: избегать сценария, при котором вы динамически добавлять/удалять узлы графа, так как узлы не будут удалены с арены, пока не сказал арен отбрасывается, так что размер арены будет расти, неограниченной.

---

Если вы находитесь в ситуации, когда вы будете добавлять/удалять узлы во время выполнения, другое решение состоит в следующем:

• есть коллекция Resources
• имеют края лишь косвенно относится к Resources (не собственники, а не заемщики либо)

Два примера:

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

в любом случае, вы несете ответственность за очистку краев при удалении ресурса, и забывание может привести к утечке памяти и панике (при разыменовании) но в противном случае безопасен.

Есть, вероятно, бесконечные вариации вышеизложенного.

Answer 2

Моделирование графоподобных структур в Rust - не простая проблема. Здесь есть два ценные обсуждения от Ник Камерона и Niko Мацакис (два основных разработчики Руст в Mozilla.)

Graphs and arena allocation

Modeling Graphs in Rust Using Vector Indices

Answer 3

Самое простое решение для графа-подобной структуры является использовать библиотека, которая моделирует графики.petgraph является хорошим выбором:

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

гарантирует, что вы должны выбрать здесь центр вокруг члена ResourceList. Я предполагаю, что вы хотите иметь однопоточный общий неизменяемый Resource.

• , если вам нужно разделить их между потоками, используйте Vec<Arc<Resource>>
• , если они не являются общими только владеть ими - Vec<Resource>
• , если они должны быть изменяемым, используйте Vec<Rc<RefCell<Resource>>> (Или Mutex если также многопоточно)