Merging two nodes: cannot borrow graph becuase it is also borrowed as immutable

Question

I have a struct that contains a graph as a member; specifically, a StableGraph from the petgraph crate. I am trying to implement a function that merges two nodes in this graph.

fn merge(&mut self, to_keep: NodeIndex<Ix>, to_drop: NodeIndex<Ix>) {
    let outs:Vec<EdgeReference<(EdgeType,Jump),Ix>> =self.graph.edges_directed(to_drop, EdgeDirection::Outgoing).collect::<Vec<EdgeReference<(EdgeType,Jump),Ix>>>().clone();
    for e in outs{
        self.graph.add_edge(to_keep, e.target(), *e.weight());
    }


    self.graph.edges_directed(to_drop, EdgeDirection::Incoming).for_each(|e|{
        self.graph.add_edge(e.source(), to_keep, *e.weight());
    });

    self.graph.remove_node(to_drop);
}

However, this gives the errors:

error[E0502]: cannot borrow `self.graph` as mutable because it is also borrowed as immutable
   --> src\movespec.rs:240:13
    |
238 |         let outs:Vec<EdgeReference<(EdgeType,Jump),Ix>> =self.graph.edges_directed(to_drop, EdgeDirection::Outgoing).collect::<Vec<EdgeRe...
    |                                                          ----------------------------------------------------------- immutable borrow occurs here
239 |         for e in outs{
    |                  ---- immutable borrow later used here
240 |             self.graph.add_edge(to_keep, e.target(), *e.weight());
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error[E0500]: closure requires unique access to `self.graph` but it is already borrowed
   --> src\movespec.rs:244:78
    |
244 |         self.graph.edges_directed(to_drop, EdgeDirection::Incoming).for_each(|e|{
    |         ----------------------------------------------------------- -------- ^^^ closure construction occurs here
    |         |                                                           |
    |         |                                                           first borrow later used by call
    |         borrow occurs here
245 |             self.graph.add_edge(e.source(), to_keep, *e.weight());
    |             ---------- second borrow occurs due to use of `self.graph` in closure

If I am to understand correctly, this is because creating outs requires an reference to self.graph, which is still alive when the mutable reference to self.graph is required by the add_edge() call. I thought that collecting and cloning the iterator of edges would solve mean that the immutable reference is no longer alive by the add_edge() call, but clearly this is wrong. How can such a merge function be implemented?

Answer 1

The problem is that EdgeReference<'a, ..> has a lifetime of your graph so you can't use a mut graph as long as you hold them. The reason for this is quite simple and you should be happy to have Rust not compile it, than any other language give you nasty runtime errors or even undefined behavior:

• Rust says, that you can't have a &mut Graph as long as there is &Graph borrow. That's why it doesn't compile here.
• What is the deal here then? The Graph struct knowns, that you can have an EdgeReference, but you cannot call any remove_(&mut self, ..) or add_(&mut self, ..) functions in the meanwhile, so it can contain references into the graph without any indirection.

Here is some code, that should work, but maybe there is a better, faster way, because we create 2 temporary vectors here.

Inside of the vectors we don't have EdgeReference but, NodeIndex and weights, which doesn't have a memory reference into the graph, so after we build the Vec our &Graph lifetime is over. We can then have &mut Graph borrows.

use petgraph::{
    stable_graph::{NodeIndex, StableGraph},
    visit::EdgeRef,
    Direction,
};

struct G {
    graph: StableGraph<(), f32>,
}

impl G {
    pub fn merge(&mut self, to_keep: NodeIndex, to_drop: NodeIndex) {
        let drop_outgoing: Vec<(NodeIndex, f32)> = self
            .graph
            .edges_directed(to_drop, Direction::Outgoing)
            .map(|r| (r.target(), *r.weight()))
            .collect();

        for (target, weight) in drop_outgoing {
            self.graph.add_edge(to_keep, target, weight);
        }

        let drop_incoming: Vec<(NodeIndex, f32)> = self
            .graph
            .edges_directed(to_drop, Direction::Incoming)
            .map(|r| (r.source(), *r.weight()))
            .collect();

        for (source, weight) in drop_incoming {
            self.graph.add_edge(source, to_keep, weight);
        }

        let _ = self.graph.remove_node(to_drop);
    }
}