Implement graph-like data structure in Rust

Question

I have a data structure which can be represented as a unidirectional graph between some structs linked with link objects because links contain metadata.

It looks something like this:

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

The whole structure needs to be mutable because I need to be able to add and remove links and resources at runtime. Because of this, I cannot use the normal lifetime model and bind the resources to the parent struct's lifetime.

I understand that I need to "choose my own guarantee" by picking the appropriate type, but I'm not sure what's the best way to solve this problem.

Answer 1

Modeling graph-like structures in Rust is not a simple problem. Here there are two valuable discussions from Nick Cameron and Niko Matsakis (two main Rust developers at Mozilla.)

Graphs and arena allocation

Modeling Graphs in Rust Using Vector Indices