如何修改已过滤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

上述的游乐场链接

Edgefiltered是非常小的，并且似乎并没有任何用于可变图操作的内容。Petgraph有什么方法可以做到这一点吗？或者我必须编写自己版本的update_edge演示吗？

Answer 1

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

您可以在每个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;
}
}
}
}