I Tried to Build a Graph in Rust. Rc and RefCell Were Waiting for Me.

#rust #softwareengineering #programming #computerscience

How Rust’s ownership model pushes you toward index-based graph design

Part of the Data Structures in Rust series.

A dependency manager is a graph. Package A depends on B, B depends on C, and a circular dependency creates a cycle the package manager has to detect and reject. A routing table is also a graph: each location stores connections to neighbouring locations, and finding the shortest path means traversing those connections efficiently. The data structure underlying both is the same, and implementing it in Rust exposes something worth understanding about how ownership shapes design decisions.

Pointer-based linked lists are one of the worst fits for Rust’s ownership model because they require nodes to hold mutable links in both directions. Graphs have the same problem, amplified. A graph node can have any number of edges pointing to any other node, including back to itself. There is no hierarchy, no single direction of ownership, no clean parent-child relationship the compiler can reason about statically. Node A might point to Node B, which points to Node C, which points back to Node A.

Expressing this in Rust forces a choice: reach for Rc> and accept runtime borrow checking, or change the representation entirely and use integer indices into a Vec. The first works for limited cases. The second is how production Rust graph code actually works, and understanding why requires first seeing what goes wrong with the pointer approach.

The Rc> approach and what it costs you

A graph node needs to hold edges to other nodes. Since multiple nodes can share ownership of a single node (A points to B and C also points to B), Box is off the table: it enforces single ownership. Rc solves the sharing problem by keeping a reference count and dropping the allocation when that count reaches zero.

The problem is that graph edges are usually relationships, not ownership relationships. Rc treats every edge as ownership, which is why cycles become memory leaks. After all external references disappear, each node in a cycle still owns the other through its edge list, leaving both reference counts above zero. Neither allocation ever gets cleaned up. Rc is reference counting only, not a cycle-detecting garbage collector.

Rc is also immutable by default. Mutating the value inside an Rc through a shared reference requires RefCell, which moves the borrow check from compile time to runtime and panics if you violate it.

use std::rc::Rc;
use std::cell::RefCell;

type NodeRef = Rc<RefCell<Node>>;
#[derive(Debug)]
struct Node {
    value: i32,
    edges: Vec<NodeRef>,
}
impl Node {
    fn new(value: i32) -> NodeRef {
        Rc::new(RefCell::new(Node {
            value,
            edges: Vec::new(),
        }))
    }
}
struct Graph {
    nodes: Vec<NodeRef>,
}
impl Graph {
    fn new() -> Self {
        Graph { nodes: Vec::new() }
    }
    fn add_node(&mut self, value: i32) -> NodeRef {
        let node = Node::new(value);
        self.nodes.push(Rc::clone(&node));
        node
    }
    fn add_edge(&self, from: &NodeRef, to: &NodeRef) {
        from.borrow_mut().edges.push(Rc::clone(to));
    }
}