An interesting reference problem about implementing a graph in rust

help
1 
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 !

2

Is this the kind of thing you’re looking for?

struct Node {
    visited: bool,
    out: Vec<Node>, // RefCell likely isn't needed here
}

fn mark(node: &mut Node) { // Neither is a &[Node]
    if node.visited {
        return;
    }
    node.visited = true;
    for out in &mut node.out { // Not &out, because it isn't mutable
        mark(out); // And this needs &mut out
    }
}
3

It's a graph, so it definitely doesn't have a clear ownership relationship

4

You mean "it's a general graph, not necessarily a tree/DAG", right?

5

Don't pass a reference to a single node. Pass a reference to the whole graph, and the index of the current node.

1 Like
7

in this type of situation, you usually want to just iterate over the indices the same way you would in C, that way you're not holding a borrow any longer than strictly necessary.

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

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