Graph structure with Rc and RefCell

I know I'm probably biting off more than I can chew, but what the heck. If I can reach the point of understanding this, maybe a lot of things will start making sense. I'm trying to implement a simple graph structure where a node can have any number of child nodes. I think I need to use RefCell so I can have "interior mutability". I think I also need reference counting to get this to work. And of course lifetimes come into play. This is a fairly short piece of code and maybe it's close to being correct, but after an hour or so of trying I cannot get it to compile. See rust-graph-data-structure/main.rs at master · mvolkmann/rust-graph-data-structure · GitHub.

Here is the code:

use std::cell::RefCell;
use std::fmt::Display;
use std::rc::Rc;
use std::vec::Vec;

// Lifetime annotations must precede generic types in the angle brackets.
#[derive(Debug)]
struct Node<'a, T> {
    data: T,
    children: RefCell<Vec<&'a Node<'a, T>>>
}

impl<'a, T: Display> Node<'a, T> {
    fn add_child(&mut self, child: &'a Rc<Node<'a, T>>) {
        self.children.borrow_mut().push(child);
    }

    fn new(data: T) -> Node<'a, T> {
        Node { data, children: RefCell::new(Vec::new()) }
    }

    fn depth_first(&self) {
        println!("node {}", self.data);
        for child in self.children.borrow().iter() {
            child.depth_first();
        }
    }
}

fn main() {
    let mut a: Rc<Node<char>> = Rc::new(Node::new('A'));
    let mut b: Rc<Node<char>> = Rc::new(Node::new('B'));
    let c: Rc<Node<char>> = Rc::new(Node::new('C'));
    let d: Rc<Node<char>> = Rc::new(Node::new('D'));

    a.add_child(&Rc::clone(&b));
    a.add_child(&Rc::clone(&c));
    b.add_child(&Rc::clone(&d));
    a.depth_first();
}

I've taken this sample and got in a working state. Here is a link to the rust playground with a few comments. Rust Playground

1 Like

Typically when you think I need something needs shared ownership and mutability you typical would reach for Rc<RefCell<T>>. In this case this would be each Node and the children each node references.

You need the combination because by itself Rc can't mutate whatever it holds onto. It's effectively read only. To get around this you would pair it with Cell or RefCell so you get "interior mutability". In RefCells case this materialized in the form of a runtime check that it isn't already borrowed.

1 Like

Thank you SO much! Glad to see you didn't need explicit lifetime annotations.

1 Like

Looks like I can also make Node<T> part of the wrapper as shown below. Is this better or worse?
I guess a downside is that Wrapper can now only be used with Node instances.

I'm surprised that I cannot remove .iter() from the for loop. I expected it would automatically get the iterator from the vector. Why can't it do that?

use std::cell::RefCell;
use std::fmt::Display;
use std::rc::Rc;
use std::vec::Vec;

// This is a common combination of types.
// Rc can't mutate what it holds.
// RefCell provides "interior mutability" which
// allows a mutable borrow while immutable borrows exist.
// Normally this is allowed by the compiler, but using RefCell
// moves the checking of correct usage to runtime.
type Wrapper<T> = Rc<RefCell<Node<T>>>;

fn wrap<T: Display>(data: T) -> Wrapper<T> {
    Rc::new(RefCell::new(Node::new(data)))
}

#[derive(Debug)]
struct Node<T> {
    data: T,
    children: Vec<Wrapper<T>>
}

impl<T: Display> Node<T> {
    fn add_child(&mut self, child: Wrapper<T>) {
        self.children.push(child);
    }

    fn new(data: T) -> Node<T> {
        Node { data, children: Vec::new() }
    }

    fn depth_first(&self) {
        println!("node {}", self.data);
        for child in self.children.iter() {
            child.borrow().depth_first();
        }
    }
}

fn main() {
    let a = wrap('A');
    let b = wrap('B');
    let c = wrap('C');
    let d = wrap('D');

    a.borrow_mut().add_child(Rc::clone(&b));
    a.borrow_mut().add_child(Rc::clone(&c));
    b.borrow_mut().add_child(Rc::clone(&d));
    a.borrow_mut().depth_first();
}

for loops utilize the IntoIterator trait, and into_iter consumes self (which is what the error is about if you remove the .iter()). Alternatively, you can do this:

        for child in &self.children {
            child.borrow().depth_first();
        }

As the &Vec coerces to a &[T] which implements IntoIterator in a fashion that returns &Ts (similar to what you get from Vec::iter()).

1 Like

Usually, there’s no need for lifetime annotations in Rc/Arc-based code: They provide a form of shared ownership, but lifetime annotations are for accessing things that you have borrowed (and therefore don’t own).

2 Likes