Project 3: Build a Graph Data Structure (Fighting the Borrow Checker)

A directed graph where nodes contain data and edges connect nodes, exploring multiple solutions: arena-based, index-based, and Rc-based.

Quick Reference

Attribute Value
Primary Language Rust
Alternative Languages None (this is Rust-specific)
Difficulty Level 4: Expert
Time Estimate 2-3 weeks
Knowledge Area Data Structures / Ownership Patterns
Tooling Rust
Prerequisites Projects 1-2, frustration tolerance

What You Will Build

A directed graph where nodes contain data and edges connect nodes, exploring multiple solutions: arena-based, index-based, and Rc-based.

Why It Matters

This project builds core skills that appear repeatedly in real-world systems and tooling.

Core Challenges

  • Representing edges without references → maps to understanding when ownership fights you
  • Choosing between indices, Rc, or unsafe → maps to design trade-offs in Rust
  • Implementing graph traversal without self-references → maps to working with the borrow checker
  • Handling graph mutations → maps to when you need RefCell or unsafe

Key Concepts

  • Idiomatic Graphs in Rust: “Too Many Lists” - Alexis Beingessner
  • Arena Pattern: “Rust Design Patterns” book
  • Graph Implementations: “Programming Rust” Chapter 8
  • Interior Mutability: “The Rust Programming Language” Chapter 15.5

Real-World Outcome

Deliver a working demo with observable output that proves the feature is correct.

Implementation Guide

  1. Reproduce the simplest happy-path scenario.
  2. Build the smallest working version of the core feature.
  3. Add input validation and error handling.
  4. Add instrumentation/logging to confirm behavior.
  5. Refactor into clean modules with tests.

Milestones

  • Milestone 1: Minimal working program that runs end-to-end.
  • Milestone 2: Correct outputs for typical inputs.
  • Milestone 3: Robust handling of edge cases.
  • Milestone 4: Clean structure and documented usage.

Validation Checklist

  • Output matches the real-world outcome example
  • Handles invalid inputs safely
  • Provides clear errors and exit codes
  • Repeatable results across runs

References

  • Main guide: RUST_BORROW_CHECKER_LIFETIME_PHILOSOPHY.md
  • “Too Many Lists” by Alexis Beingessner