rust - 进行 BFS 时的借用检查器问题

问题描述

我正在编写一个小程序来计算生锈的PERT图（ https://en.wikipedia.org/wiki/Program_evaluation_and_review_technique ）上的关键路径。

我将Task对象存储在哈希图中。hashmap 由一个名为的对象拥有Pert。每个Task对象拥有两个Vec<String>对象，标识任务的先决条件和后继者，并有一个 i32 来指定其持续时间。这些任务在 main.rs 中创建并通过add函数添加到 Pert 对象。

任务.rs：

pub struct Task {
    name: String,
    i32: duration,
    followers: Vec<String>,
    prerequisites: Vec<String>
// Additional fields, not relevant for the example
}

impl Task {
    pub fn new(name: &str, duration: i32) -> Task {
        Task {
            name: String::from(name),
            duration: duration,
            followers: Vec::new(),
            prerequisites: Vec::new(),
        }
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    pub fn duration(&self) -> i32 {
        self.duration
    }

    pub fn get_prerequisites(&self) -> & Vec<String> {
        &self.prerequisites
    }

    pub fn get_followers(&self) -> & Vec<String> {
        &self.followers
    }
}

为了评估关键路径，需要计算所有任务的最大持续时间总和，并记录每个任务的最早开始和结束时间，以及最晚开始和结束时间。可以做的方法是添加一个“开始”和一个“结束”任务，分别标记图表的开始和结束。从“开始”任务开始，在图上执行 BFS，直到我们到达“结束”任务。completion_timeBFS在对象的方法内部完成Pert。

在我当前的实现中，我遇到了借用检查器的问题，因为我不止一次地可变地借用了包含任务的哈希图。除了借用两次之外，我没有看到其他方法可以做到这一点，但我对 rust 很陌生，没有函数式编程经验，所以如果有一种简单的方法可以用函数式编程做到这一点，我看不到任何一个。

pert.rs：

pub struct Pert {
    tasks: HashMap<String, Task>
}

impl Pert {
    pub fn completion_time(&mut self) -> i32 {
        let mut time = 0;
        let mut q = VecDeque::<&mut Task>::new();

        // put "begin" task at the top of the queue, first mutable borrow of self.tasks
        q.push_back(self.tasks.get_mut("begin").unwrap());
        while !q.is_empty() {
            let old_time = time;
            let mut curr_task = q.pop_front().unwrap();
            for x in curr_task.get_followers() {
                // second mutable borrow of self.tasks happens here
                let task = self.tasks.get_mut(x).unwrap();

                // additional piece of code here modifying other task properties
                time = std::cmp::max(old_time, old_time + task.duration())
            }
        }

        time
    }
}

使用空 main.rs 构建项目应该足以触发以下错误消息：

error[E0499]: cannot borrow `self.tasks` as mutable more than once at a time
  --> src/pert.rs:84:28
   |
79 |         q.push_back(self.tasks.get_mut("begin").unwrap());
   |                     ---------- first mutable borrow occurs here
80 |         while !q.is_empty() {
   |                - first borrow later used here
...
84 |                 let task = self.tasks.get_mut(x).unwrap();
   |                            ^^^^^^^^^^ second mutable borrow occurs here

标签： rustbreadth-first-searchborrow-checker

rust - 进行 BFS 时的借用检查器问题

问题描述

解决方案

推荐阅读