Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implement graph-like data structure in Rust

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.

like image 832
Lorenz Avatar asked Jan 12 '16 15:01

Lorenz


People also ask

Are graphs hard in Rust?

So, are some graph representations hard in Rust? No, but pointer & struct graphs need 'unsafe' and tests. But you shouldn't be using pointer & struct graphs anyway. For representations that you _should_ use, Rust code looks a lot like C++ code.

What is graph storage structure?

A graph is a non-linear kind of data structure made up of nodes or vertices and edges. The edges connect any two nodes in the graph, and the nodes are also known as vertices. This graph has a set of vertices V= { 1,2,3,4,5} and a set of edges E= { (1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(4,50 }.

What is adjacency list representation of a graph?

An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.


2 Answers

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

like image 114
eulerdisk Avatar answered Oct 12 '22 19:10

eulerdisk


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.

like image 35
Matthieu M. Avatar answered Oct 12 '22 20:10

Matthieu M.