0

我正在为我的图使用边缘过滤器并想要更新边缘权重：

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_edgeshowhow 版本？

4

1 回答 1

1

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

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

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;
            }
        }
    }
}
于 2021-03-24T09:32:54.680 回答