 # Graph data structure and lifetimes

New rustacean here. I'm trying to implement a directed graph data structure but I can't find a way to satisfy borrow checker.

I spent a decent amount of time on The Rust Programming Language - Lifetimes and I try to understand compiler hints without any success.

Relevant code:

``````#[derive(Debug, PartialEq, Eq)]
struct Vertex {
name: String
}

#[derive(Debug, PartialEq, Eq)]
struct Edge<'a> {
weight: u32,
from: &'a Vertex,
to: &'a Vertex
}

#[derive(Debug, PartialEq, Eq)]
struct Graph<'a> {
vertices: Vec<Vertex>,
edges: Vec<Edge<'a>>,
}

impl <'a> Graph<'a> {
fn new() -> Graph<'a> {
Graph {
vertices: Vec::new(),
edges: Vec::new(),
}
}

fn add_vertex(&mut self, name: String) {
self.vertices.push(Vertex{name});
}

fn get_vertex(&self, name: &str) -> Option<&Vertex> {
self.vertices.iter().find(|x| x.name == name)
}

fn add_edge(&mut self, weight: u32, v1: &str, v2: &str) {
let v1 = self.get_vertex(v1).unwrap();
let v2 = self.get_vertex(v2).unwrap();
self.edges.push(Edge{
weight,
from: &v1,
to: &v2
});
}

fn get_edges(&self, name: &str) -> Vec<&Edge> {
let v = self.get_vertex(name).unwrap();
self.edges.iter().filter(|edge| edge.from == v).collect()
}
}
``````

Compiler error:

``````error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
--> 2015/day09/src/lib.rs:49:23
|
49 |         let v1 = self.get_vertex(v1).unwrap();
|                       ^^^^^^^^^^
|
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 48:5...
--> 2015/day09/src/lib.rs:48:5
|
48 | /     fn add_edge(&mut self, weight: u32, v1: &str, v2: &str) {
49 | |         let v1 = self.get_vertex(v1).unwrap();
50 | |         let v2 = self.get_vertex(v2).unwrap();
51 | |         self.edges.push(Edge{
...  |
55 | |         });
56 | |     }
| |_____^
note: ...so that reference does not outlive borrowed content
--> src/lib.rs:49:18
|
49 |         let v1 = self.get_vertex(v1).unwrap();
|                  ^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 32:7...
--> src/lib.rs:32:7
|
32 | impl <'a> Graph<'a> {
|       ^^
note: ...so that the expression is assignable
--> 2015/day09/src/lib.rs:51:25
|
51 |           self.edges.push(Edge{
|  _________________________^
52 | |             weight,
53 | |             from: &v1,
54 | |             to: &v2
55 | |         });
| |_________^
= note: expected  `Edge<'a>`
found  `Edge<'_>`

error: aborting due to previous error

``````

I read rustc hint (`rustc --explain E0495`) but couldn't transpose it to my case.

Can you explain me what is the problem in other words and help me satisfy the borrow checker pls ?
Thanks

It is not possible to build self-referential types. Unless you do something like explicitly use reference counting, the ownership structure must be a tree. The usual recommendation is to store the nodes in a vector and to use indexes.

What do you mean with `self-referential` ?
No struct definition refers to itself.
Thanks.

Because of your references, the verticies are referenced by more than one thing, which is not allowed. Basically you're trying to have multiple ownership, but things can only be owned in one place.

To be more specific, one field is not allowed to contain references to other fields in the same struct.

Ok I think I understand.
How I'm supposed to use `Rc` ?

First try

``````#[derive(Debug, PartialEq, Eq)]
struct Vertex {
name: String
}

#[derive(Debug, PartialEq, Eq)]
struct Edge {
weight: u32,
from: Rc<Vertex>,
to: Rc<Vertex>,
}

#[derive(Debug, PartialEq, Eq)]
struct Graph {
vertices: Vec<Vertex>,
edges: Vec<Edge>,
}

impl Graph {
fn new() -> Graph {
Graph {
vertices: Vec::new(),
edges: Vec::new(),
}
}

fn add_vertex(&mut self, name: String) {
self.vertices.push(Vertex{name});
}

fn get_vertex(&self, name: &str) -> Option<&Vertex> {
self.vertices.iter().find(|x| x.name == name)
}

fn add_edge(&mut self, weight: u32, v1: &str, v2: &str) {
let v1 = self.get_vertex(v1).unwrap();
let v2 = self.get_vertex(v2).unwrap();
self.edges.push(Edge{
weight,
from: Rc::new(*v1),
to: Rc::new(*v2),
});
}

fn get_edges(&self, name: &str) -> Vec<&Edge> {
let v = self.get_vertex(name).unwrap();
self.edges.iter().filter(|edge| edge.from == v).collect()
}
}``````

If you want a clone, you should use `Rc::clone`. In the comparison you can use `&*edge.from` to reborrow the edge as ` &Vertex`. Keep in mind that anything behind an `Rc` is immutable unless you add a `RefCell`.

Alternatively allocate all nodes elsewhere using a memory pool/arena, and then you can build the graph out of the references (temporary borrows). It won't be self-referential, because the references will be bound to the arena, not to the graph.

But `Rc<RefCell<Node>>` is generally preferred. This is similar to what most GC/ARC languages actually do behind the scenes, but don't make it visible in the syntax.

Also have a look at petgraph. It is a graph library that perhaps might provide the functionality you need.

Thanks for all answers I will try implementation and report them here !

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.