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

Question

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

作业的规范要求我使用 DFS 和记忆，但在执行 DFS 时会出现多个可变引用。还有其他方法可以做到这一点吗？

我考虑过使用 HashMap s 而不是内部 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 neighbour = graph.node(index).neighbours[ni];：在每个迭代步骤中获取当前索引处的邻居

与复制方法一样，此解决方案基于以下约束：您正在迭代的neighbours向量不会因调用 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_neighbour(v);

Answer 2

您正在修改graph结构，同时循环访问其中包含的向量。编译器无法验证您在迭代期间是否未在向量中添加或删除，这将使迭代器无效。这是错误的直观原因。

避免这种情况的最简单方法是在迭代向量之前获取向量的副本，以便编译器可以看到迭代器没有更改。这有点次优，但现在可以解决错误。另一个生命周期错误可以通过类似的方式(但没有太多成本(解决，方法是在进行比较之前将深度复制到变量中。

use std::io;
use std::env;
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 => {
                let neighbours = graph.node(index).neighbours.clone();
                for &i in neighbours.iter() {
                    // multiple mutable references
                    Graph::dfs(graph, i);
                }
                graph.node(index).depth = 1
                    + neighbours
                        .iter()
                        .map(|&x| graph.node(x).depth)
                        .max()
                        .unwrap();
            }
        }
        let depth = graph.node(index).depth;
        if depth > graph.depth {
            graph.depth = graph.node(index).depth;
        }
    }
}
fn main() {
    env::set_var("RUST_BACKTRACE", "1");
    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);
}

操场

如果您要修改方法，以便在搜索过程中不会改变结构(即您将访问的数据存储在其他地方(，则代码无需此副本即可工作。这也对并发使用更友好。