如何修改过滤的Petgraph图的边权重？

Question

我正在对我的图使用边缘过滤器，并希望更新边权重：

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);
        }
    }
}

但这是错误的，因为EdgeFiltered没有update_edge函数：

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}>`

如果我改为引用原始graph，它会出现借用检查器错误(与Dfs不同，不幸的是，EdgeFiltered的设计不允许您访问原始图形)：

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是非常小的，并且看起来没有任何用于可变图形操作的东西。有没有办法用Petgraph附带的东西来做到这一点，或者我必须编写我自己版本的update_edge showhow？

Answer 1

FilteredGraph借用了Graph，因此只要Graph存在，就不能获得对FilteredGraph的可变引用。

您可以在每次dfs.next()调用时重新创建一个FilteredGraph来解决此问题，例如，这是可行的：

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;
        }
    }
}

注意:这将基于graph中存在的边，而不是filtered_graph中存在的边，获取给定节点的邻居。

您可以通过丢弃EdgeFiltered并在遍历中手动处理它来解决此问题，例如：

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;
            }
        }
    }
}