CODEWITHSUNDEEP
rustborrow-checkerpetgraph
curiousdannii
curiousdannii

Reputation: 2010

How can you modify edge weights for a filtered Petgraph graph?

I am using an edge filter for my graph and want to update an edge weight:

use petgraph::prelude::*;
use petgraph::graph;
use petgraph::visit::{Dfs, EdgeFiltered, IntoEdges};

fn filter_edges(edge: graph::EdgeReference<u32>) -> bool {
    match edge.weight() {
        0 => true,
        _ => false,
    }
}

fn main() {
    let mut graph: graph::Graph<u32, u32> = graph::Graph::new();
    let a = graph.add_node(1);
    let b = graph.add_node(2);
    let e = graph.add_edge(a, b, 0);
    let mut filtered_graph = EdgeFiltered::from_fn(&graph, filter_edges);
    let mut dfs = Dfs::new(&filtered_graph, a);
    while let Some(node_index) = dfs.next(&filtered_graph) {
        for edge in filtered_graph.edges(node_index) {
            filtered_graph.update_edge(edge.source(), edge.target(), 1);
            //graph.update_edge(edge.source(), edge.target(), 1);
        }
    }
}

But this errors because EdgeFiltered doesn't have an update_edge function:

error[E0599]: no method named `update_edge` found for struct `EdgeFiltered<&Graph<u32, u32>, for<'r> fn(petgraph::graph::EdgeReference<'r, u32>) -> bool {filter_edges}>` in the current scope
  --> src/main.rs:22:28
   |
22 |             filtered_graph.update_edge(edge.source(), edge.target(), 1);
   |                            ^^^^^^^^^^^ method not found in `EdgeFiltered<&Graph<u32, u32>, for<'r> fn(petgraph::graph::EdgeReference<'r, u32>) -> bool {filter_edges}>`

If I switch to refer to the original graph instead, it has a borrow checker error (unlike Dfs, unfortunately EdgeFiltered isn't designed to let you access the original graph):

error[E0502]: cannot borrow `graph` as mutable because it is also borrowed as immutable
  --> src/main.rs:21:13
   |
17 |     let mut filtered_graph = EdgeFiltered::from_fn(&graph, filter_edges);
   |                                                    ------ immutable borrow occurs here
18 |     let mut dfs = Dfs::new(&filtered_graph, a);
19 |     while let Some(node_index) = dfs.next(&filtered_graph) {
   |                                           --------------- immutable borrow later used here
20 |         for edge in filtered_graph.edges(node_index) {
21 |             graph.update_edge(edge.source(), edge.target(), 1);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

Playground link for the above

Edgefiltered is pretty minimal, and doesn't really seem to have anything intended for mutable graph manipulation. Is there any way to do this with what Petgraph comes with, or will I have to write my own version of update_edge showhow?

Upvotes: 0

Views: 1003

Answers (1)

sebpuetz
sebpuetz

Reputation: 2618

FilteredGraph borrows the Graph, therefore you cannot get a mutable reference to the Graph as long as FilteredGraph exists.

You can re-create a FilteredGraph on each dfs.next() call to work around this, e.g. this works:

use petgraph::graph;
use petgraph::visit::{Dfs, EdgeFiltered};

fn filter_edges(edge: graph::EdgeReference<u32>) -> bool {
    match edge.weight() {
        0 => true,
        _ => false,
    }
}

fn main() {
    let mut graph: graph::Graph<u32, u32> = graph::Graph::new();
    let a = graph.add_node(1);
    let b = graph.add_node(2);
    let e = graph.add_edge(a, b, 0);
    let filtered_graph = EdgeFiltered::from_fn(&graph, filter_edges);
    let mut dfs = Dfs::new(&filtered_graph, a);
    while let Some(node_index) = dfs.next(&EdgeFiltered::from_fn(&graph, filter_edges)) {
        let mut neighbors = graph.neighbors(node_index).detach();
        while let Some((edge_idx, _)) = neighbors.next(&graph) {
            graph[edge_idx] = 1;
        }
    }
}

Note: This will take the neighbors of the given node based on the edges present in graph, not by those present in filtered_graph.

You can solve that by ditching EdgeFiltered and manually handling it in the traversal, e.g. like this:

fn main() {
    let mut graph: graph::Graph<u32, u32> = graph::Graph::new();
    let a = graph.add_node(1);
    let b = graph.add_node(2);
    let e = graph.add_edge(a, b, 0);
    let mut dfs = Dfs::new(&graph, a);
    while let Some(node_index) = dfs.next(&graph) {
        let mut neighbors = graph.neighbors(node_index).detach();
        while let Some((edge_idx, _)) = neighbors.next(&graph) {
            let edge_weight = &mut graph[edge_idx]; 
            if *edge_weight == 0 {
                *edge_weight = 1;
            }
        }
    }
}

Upvotes: 1

Related Questions