An interesting reference problem about implementing a graph in rust

struct Node<'a> {
    visited: bool,
    out: Vec<&'a RefCell<Node<'a>>>,
}

fn mark(node: &RefCell<Node>) {
    if node.borrow().visited {
        return;
    }
    node.borrow_mut().visited = true;
    for out in &node.borrow().out {
        mark(out);
    }
}

Here is a simple code, which defined a graph and try to traverse it with DFS , but it needs a RefCell for it.

But now I'm trying to avoid using Cell-Type

Without using Cell-Type, we must avoid the ownership problem, so I tried to use a simple arena.

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

fn mark(node: usize, arena: &mut [Node]) {
    if arena[node].visited {
        return;
    }
    arena[node].visited = true;
    for &out in &arena[node].out {
        mark(out, arena);
    }
}

The problem is that, in DFS, sometimes you have to pass down the mutable reference to call another mark recursively, and it occurs the borrow problem, since that the upper story of the recursion must hold at least shared reference to traverse the out field.

We tried couples of ways to avoid it, like taking out the out field when we have to traverse it or traverse the out field by index instead of Iterator .

But they are not seem to be a general solutions for more complex problem.

It seems that it essential to use a Cell-Type, looking for some good ways to solve it.

Thanks !

5 posts - 4 participants

Read full topic