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};

type Links = Vec<Rc<RefCell<Node>>>;

struct Node {
    data: u32,
    links: Links,
    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,
                links: Vec::with_capacity(graph[i].len()),
                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::make_links(&graph, &mut nodes);

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

        for link in &nodes[0].as_ref().borrow().links {
            for path in &link.as_ref().borrow().paths {
                let mut p = vec![0];

    fn make_links(graph: &Vec<Vec<i32>>, nodes: &Vec<Rc<RefCell<Node>>>) {
        for i in 0..graph.len() {
            for j in graph[i].iter() {
                    .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();
                for link in from_ref.links.iter() {
                    if !link.as_ref().borrow().visited {
                        Solution::find_path(link, to);
                        link.borrow_mut().visited = true;
                    if link.as_ref().borrow().paths.len() != 0{
                        for path in (&link.as_ref().borrow().paths).iter() {
                            let mut a: Vec<i32> = vec![ as i32];

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.


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,
    links: Links,
    visited: bool,
    paths: Vec<Vec<i32>>,

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

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

(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`
        Solution::make_links(&graph, &nodes);

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::make_links(&graph, &nodes);
        Solution::find_path(&nodes[0], 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[0] 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[0].as_ref().borrow().paths.clone();

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![0]]). 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() {
            for j in links {
                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()) {
            for j in links {
                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()) {
            node.borrow_mut().links = links
                .map(|&j| Rc::clone(&nodes[j as usize]))

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


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[0] as from, and the only time that can have visited == true is when you have a DAG of size 1 (when node[0] 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();
        for link in from_ref.links.iter() { /* ... */ }

    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().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[0].as_ref().borrow().paths.clone();
let paths = Self::build_paths(&nodes[0].as_ref().borrow(), &nodes[0]);

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


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.