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?
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:
&mut Graph
as long as there is &Graph
borrow. That's why it doesn't compile here.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);
}
}