rust - 具有类似图形的数据结构的多个可变借用

Question

我正在尝试编写一个程序，为始终是有根树或多根树的有向图找到图中最长的路径(即最大深度)。

作业规范要求我使用 DFS 和内存，但在执行 DFS 时会出现多个可变引用。还有其他方法吗？

我考虑过使用 HashMap 而不是内部 Graph 字段，但它只会在 HashMap 的可变性方面产生相同的错误。我在 Rust 用户论坛和此处发现了其他几个问题，但没有一个提供有关如何解决此问题的建议。我应该使用“不安全”代码还是其他一些策略？

use std::io;

struct Node {
    neighbours: Vec<usize>,
    depth: usize,
    visited: bool,
}

impl Node {
    fn new() -> Node { Node { neighbours: Vec::new(), depth: 0, visited: false } }
    fn add_neighbour(&mut self, node: usize) { self.neighbours.push(node); }
    fn neighbourhood_size(&self) -> usize { self.neighbours.len() }
}

struct Graph {
    nodes: Vec<Node>,
    depth: usize,
}

impl Graph {
    fn new() -> Graph { Graph { nodes: Vec::new(), depth: 0} }
    fn nodes_number(&self) -> usize { self.nodes.len()}
    fn add_node(&mut self) { self.nodes.push(Node::new()); }
    fn node(&mut self, i: usize) -> &mut Node { &mut self.nodes[i] }

    fn dfs(graph: &mut Graph, index: usize) {
        if !graph.node(index).visited {
            graph.node(index).visited = true;
        }
        match graph.node(index).neighbourhood_size() == 0 {
            true => { graph.node(index).depth = 1; },
            false => {
                for &i in graph.node(index).neighbours.iter() {
                    // multiple mutable references 
                    Graph::dfs(graph, i);
                }
                graph.node(index).depth = 
                    1 + graph.node(index).
                    neighbours.iter().
                    map(|&x| graph.node(x).depth).
                    max().unwrap();
            }
        }
        if graph.node(index).depth > graph.depth {
            graph.depth = graph.node(index).depth;
        }
    }
}


fn main() {
    let mut input_line = String::new();
    io::stdin().read_line(&mut input_line);
    let n = input_line.trim().parse::<usize>().unwrap();
    // to avoid counting from 0 or excessive use of (-1)
    let mut graph = Graph::new(); graph.add_node();
    for _ in 0 .. n {
        let mut input_line = String::new();
        io::stdin().read_line(&mut input_line);
        let separated = input_line.
            split(" ").
            collect::<Vec<_>>();
        let u = separated[0].trim().parse::<usize>().unwrap();
        let v = separated[1].trim().parse::<usize>().unwrap();
        if graph.nodes_number() <= u { graph.add_node(); }
        if graph.nodes_number() <= v { graph.add_node(); }
        graph.node(u).add_neighbour(v);
    }
    let n = graph.nodes_number();
    for i in 1 .. n {
        if !graph.node(i).visited { Graph::dfs(&mut graph, i); }
    }
    println!("{}", graph.depth);
}

Answer 1

除了在迭代之前获取向量的副本，您还可以迭代索引:

for ni in 0..graph.node(index).neighbours.len() {
    let neighbour = graph.node(index).neighbours[ni];
    Graph::dfs(graph, neighbour);
}

neighbours 向量仍然被借用来执行迭代，但不是在整个迭代过程中:

1. graph.node(index).neighbours.len():迭代开始时获取长度一次
2. let neighbor = graph.node(index).neighbours[ni];:在每个迭代步骤中获取当前索引处的邻居

与复制方法一样，此解决方案基于以下约束:您正在迭代的 neighbors 向量不会因调用 dfs 而改变。

您可以通过提供对图形节点的不可变访问来解决与代码中的多个引用有关的剩余问题:

fn node_mut(&mut self, i: usize) -> &mut Node {
    &mut self.nodes[i]
}
fn node(&self, i: usize) -> &Node {
    &self.nodes[i]
}

仅在必要时通过 node_mut 使用可变访问。例如，添加邻居时:graph.node_mut(u).add_neighbor(v);