# Best practices for Use of Rc and Ref

This is a solution for finding all possible paths from 1st node to last node of graph , the graph is represented as vector of vector

Input graph is assumed to have no self loops , no closed loops and a maximum of 15 nodes

Want to know where i can improve , want to know the best practices as
RefCell and Rc are quite different to me as Rust Beginner

Any help would be appreciated !

``````use std::{cell::RefCell, rc::Rc, vec,convert::TryInto};

#[derive(Debug)]
struct Node {
data: u32,
visited: bool,
paths: Vec<Vec<i32>>,
}

impl Solution {
pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = graph.len();
let mut nodes: Vec<Rc<RefCell<Node>>> = Vec::with_capacity(n);
let mut paths: Vec<Vec<i32>> = Vec::new();

for i in 0..n {
nodes.push(Rc::new(RefCell::new(Node {
data: i as u32,
visited: false,
paths: vec![],
})))
}

nodes[n - 1].borrow_mut().visited = true;
nodes[n - 1].borrow_mut().paths = vec![vec![(n - 1).try_into().unwrap()]];

Solution::find_path(&nodes, &nodes[n - 1]);

let mut p = vec!;
p.extend(path);
paths.push(p);
}
}

paths
}

fn make_links(graph: &Vec<Vec<i32>>, nodes: &Vec<Rc<RefCell<Node>>>) {
for i in 0..graph.len() {
for j in graph[i].iter() {
nodes[i]
.borrow_mut()
.push(Rc::clone(&nodes[*j as usize]));
}
}
}

fn find_path(from: &Rc<RefCell<Node>>, to: &Rc<RefCell<Node>>) {
if !from.as_ref().borrow().visited {
let mut set: Vec<Vec<i32>> = Vec::new();
{
let from_ref: &Node = &from.as_ref().borrow();
}

let mut a: Vec<i32> = vec![from_ref.data as i32];
a.extend(path);
set.push(a);
}
}
}
}

from.borrow_mut().paths.extend(set);
}
}
}

``````

Your code smashes the stack when given a complete graph (no self loops) on three vertices. So, there's either a problem with the algorithm or I don't understand the input parameters.

(Similarly for a complete graph (with self loops) on two vertices.)

Sorry my bad , actually the input graph is assumed to have no self loops , no closed loops and a maximum of 15 nodes

Unlike how most CS courses structure their lessons, you normally don't want to start with graph problems when learning Rust. They inherently contain multiple ownership and mutation (you typically add nodes in one pass then set their edges in another) so you run headlong into borrow checker issues, forcing you to reach for `Rc<RefCell<_>>` and causing a lot of confusion. When you don't have a GC, a graph's ownership story gets pretty tricky.

This was actually mentioned in the How not to learn Rust post that came out recently.

To answer the title's question, the easiest way is to structure a graph in Rust is to not use pointers (e.g. `Rc`) for the edges between nodes. Instead, you will find it easier using an index-based representation like an adjacency list.

3 Likes

Let me give some feedback that's not `Rc` or `RefCell` specific.

## Cleaning up `all_paths_source_target`

You can clean up your code a little bit by matching the `i32` type in your `Node` (poor fit for indices though it may be), and by making a constructor for `Node`. We can also utilize iterators a bit more.

``````#[derive(Default, Debug)]
struct Node {
data: i32,
visited: bool,
paths: Vec<Vec<i32>>,
}

impl Node {
fn new(data: i32) -> Self {
Node {
data, ..<_>::default()
}
}

fn new_rc(data: i32) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Self::new(data)))
}
}
``````

(We've potentially lost some small optimization by not pre-allocating the `links` vector, but let's just accept that for now.)

Then in `all_paths_source_target`:

``````        let nodes: Vec<_> = (0..n).map(|i| Node::new_rc(i as i32)).collect();
// ...

// You had a `&mut nodes` here, but don't need the `mut`
``````

You then index using `n-1` a couple times, but never check to see if `n` is 0. So if someone passes in an empty `Vec`, you panic. Instead, you can detect this case and just return an empty `Vec` yourself.

``````        let last = match nodes.last() {
None => return Vec::new(),
Some(thing) => thing,
};

// Uses last now
last.borrow_mut().visited = true;
last.borrow_mut().paths = vec![vec![(n - 1).try_into().unwrap()]];

Solution::find_path(&nodes, last); // <-- and here
``````

After that, there's no reason for `n` to be a `usize` anymore, and we can clean up just a little more.

``````        let n = graph.len() as i32;
let nodes: Vec<_> = (0..n).map(Node::new_rc).collect();
// ...
last.borrow_mut().paths.push(vec![n - 1]);
``````

Finally, as I understand the algorithm, the `paths` you build up to return is the almost always the same as the `paths` that get built up in `nodes` within the `find_path` function. It would be possible but verbose to deconstruct your data structure and get it back out. However, we can just `clone` it and it will probably still be an improvement over rebuilding it entirely.

``````        let paths = nodes.as_ref().borrow().paths.clone();
paths
``````

Note that this does give a different result when passed in a DAG with a single node. Your version says there is no path, this version says there's one path (`vec![vec!]`). I believe this is the only difference, but didn't thoroughly test things. If I'm wrong, don't worry for now -- I'll revisit how to rectify things at the end of this post.

Here's what we have after those changes.

## Altering `make_links`

Looping over indices and immediately using them to index into a collection is usually a sign that you should iterate over the collection instead. Let's try that here:

``````        for (i, links) in graph.iter().enumerate() {
nodes[i] /* ... */
}
}
``````

If we iterate over `nodes` at the same time, we won't need `i` at all:

``````        for (links, node) in graph.iter().zip(nodes.iter()) {
node /* ... */
}
}
``````

On the inside of the inner loop, you're repeatedly borrowing `node` and pushing into `node.links`. Instead, you can just build up the entire vector in one go (since we know `links` is empty to start):

``````        for (links, node) in graph.iter().zip(nodes.iter()) {
.iter()
.map(|&j| Rc::clone(&nodes[j as usize]))
.collect();
}
``````

And with that, we've regained the small optimization of pre-allocating `links` that we took away earlier.

Playground.

## Cleaning up `find_path`

You check the length of `paths` before iterating. However, creating an empty iterator is cheap in this case -- potentially cheaper than performing the extra check and branch. Additionally, references to `Vec` (or to slices) implement `IntoIterator` in the same way that calling `.iter()` gets you. Putting those together:

``````// No surrounding `if`
for path in &link.as_ref().borrow().paths { /* ... */ }
``````

Just above this, you check if `link` has been visited, and then make a recursive call if it has not, with `link` as the first parameter. But the entire function is wrapped in an `if` checking if the first parameter has been visited or not. So you're checking twice every time.

The `if` inside the loop can be removed. Additionally, the setting of `visited` to `true` can be performed on `from` just before returning, instead of inside the loop on `link` after each call.

Playground with these changes.

Another approach would have been to remove the outer `if`, and to make sure you never call the function when `from.visited` is true everywhere, not just in this loop. The only other place you call the function is with `node` as `from`, and the only time that can have `visited == true` is when you have a DAG of size 1 (when `node` is the last node).

It made more sense to me to remove the inner `if` and avoid a condition that all callers have to maintain. But if you needed to special-case the size 1 DAG anyway -- e.g. you need to special case the return for a DAG of size 1 -- this may be an option. However, see also the "one last note" below.

## Refactoring `find_path`

Moving on, at this point I'd probably factor the building of `set` into it's own function.

``````    // n.b. doesn't do any mutation to the parameters
fn build_paths(from_ref: &Node, to: &Rc<RefCell<Node>>) -> Vec<Vec<i32>> {
let mut set: Vec<Vec<i32>> = Vec::new();
set
}

fn find_path(from: &Rc<RefCell<Node>>, to: &Rc<RefCell<Node>>) {
if !from.as_ref().borrow().visited {
let set = Self::build_paths(&from.as_ref().borrow(), to);
from.borrow_mut().paths.extend(set);
from.borrow_mut().visited = true;
}
}
``````

Here's the one place where the change is sensitive to `RefCell`. You had an extra lexical block here originally, as you had to make the borrow of the `RefCell` shorter by making `from_ref` drop before you called `from.borrow_mut()` to avoid a run-time panic. Here, I've hidden that necessity in the function boundaries -- the borrow that needs to be limited is now a temporary created in the call to `build_paths`.

Final playground for this post.

And one last note: with `build_paths` factored out, if you need the "rebuild and return" behavior that I replaced with a `clone`, you can get it back like so:

``````// let paths = nodes.as_ref().borrow().paths.clone();
let paths = Self::build_paths(&nodes.as_ref().borrow(), &nodes);
``````

`nodes` has definitely been visited at this point, so the execution will be the same as your original rebuild loop, albeit slightly less efficient.

2 Likes

Thank you

`Thank You for this much Idiomatic Code `, Helped a lot

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.