cannot borrow as mutable because it is already borrowed, when implementing graph

Question

I am trying to implement a graph structure by having each node store references to its neighbors. Specifically, I am trying to make a grid where each node has references to up to 4 neighbors - like a "2D linked list".

But I get an error when assigning the references. This minimalistic example reproduces my issue:

#[derive(Clone)]
struct Node<'a> {
    neighbor: Option<&'a Node<'a>>, // optional reference to another Node
}

fn main() {

    // a bunch of nodes:
    let mut nodes: Vec<Node> = vec![ Node{neighbor: None}; 100];

    // I want node 0 to have a reference to node 1
    nodes[0].neighbor = Some(&nodes[1]);

}

The following error is produced:

error[E0502]: cannot borrow `nodes` as mutable because it is also borrowed as immutable
  --> src/main.rs:12:5
   |
12 |     nodes[0].neighbor = Some(&nodes[1]);
   |     ^^^^^------------------------------
   |     |                         |
   |     |                         immutable borrow occurs here
   |     mutable borrow occurs here
   |     immutable borrow later used here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.

I am struggling to figure out how this is supposed to be done in Rust. Should I be using pointers instead?

Answer 1

You cannot implement such data structure exactly for the reason the borrow checker was created. It tells you that your data structure cannot be safe.

The reason it is not safe is quite simple.

Let's say you created a graph with two elements, and the first one references the second one. Now you want the second one to reference the first one. To modify your graph, you will need to gain mutable access to the structure. But if you get the mutable access to it, nothing can stop you from removing the second node from the graph, making the reference in the first node invalid.

Thus, borrow checker won't allow you to do that.

The way to go for you is to use indexes instead of references. This will have additional advantage: when you want to serialize/deserialize your structure, you will have no problems at all doing it.