Implement graph-like data structure in Rust

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

Actually, for a graph like structure, the simplest solution is to use an arena such as TypedArena.

The lifetime of the nodes will then be only dependent on the lifetime of the instance of the typed arena they were created from, which will greatly simplify resource management.

Warning: avoid a scenario where you dynamically add/remove nodes to the graph, as the nodes will NOT be removed from the arena until said arena is dropped, so the size of the arena would grow, unbounded.

If you are in a situation where you will add/remove nodes at runtime, another solution is to:

• have a collection of Resources
• have the edges only indirectly refer to the Resources (not owners, and not borrowers either)

Two examples:

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

in either case, you are responsible for cleaning up the edges when removing a resource, and forgetting may lead to a memory leak and panics (when dereferencing) but is otherwise safe.

There are, probably, infinite variations on the above.

The simplest solution for a graph-like structure is to use a library which models graphs. petgraph is a good choice:

use petgraph::Graph; // 0.5.1
use std::{collections::HashMap, rc::Rc};

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

The guarantees that you have to choose here center around the member of ResourceList. I assume that you wish to have single-threaded shared immutable Resources.

• if you need to share them across threads, use a Vec<Arc<Resource>>
• if they aren't shared, you can own them — Vec<Resource>
• if they need to be mutable, use a Vec<Rc<RefCell<Resource>>> (Or a Mutex or RwLock if also multithreaded)