1036 Advanced

1036-arena-graph — Graph with Arena Allocation

Functional Programming

Tutorial

The Problem

Graphs are notoriously difficult to represent in Rust's ownership model because nodes can have multiple incoming edges, violating the single-owner rule. The arena allocation pattern sidesteps this by storing all nodes in a Vec<Node> (the "arena") and using integer indices as edge references instead of direct pointers. Index-based references have no ownership semantics and cannot dangle as long as the arena lives.

This pattern is the recommended idiomatic approach for graphs in Rust, used in the petgraph crate, LLVM's IR (which uses integer node IDs), and compiler intermediate representations.

🎯 Learning Outcomes

• Represent a graph as Vec<Node> with integer index edges

• Add nodes and directed edges using indices

• Implement BFS and DFS over an arena-based graph

• Understand why Vec<Box<Node>> with pointer edges does not work in safe Rust

• Connect arena allocation to petgraph's NodeIndex type

Code Example

#![allow(clippy::all)]
// 1036: Graph with Arena Allocation
// Vec<Node> indexed by usize — the idiomatic Rust graph pattern

use std::collections::VecDeque;

/// A graph node stored in an arena (Vec)
#[derive(Debug)]
struct Node {
    label: String,
    edges: Vec<usize>, // indices into the arena
}

/// Arena-based graph
struct Graph {
    nodes: Vec<Node>,
}

impl Graph {
    fn new() -> Self {
        Graph { nodes: Vec::new() }
    }

    fn add_node(&mut self, label: &str) -> usize {
        let idx = self.nodes.len();
        self.nodes.push(Node {
            label: label.to_string(),
            edges: Vec::new(),
        });
        idx
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.nodes[from].edges.push(to);
    }

    fn neighbors(&self, idx: usize) -> &[usize] {
        &self.nodes[idx].edges
    }

    fn label(&self, idx: usize) -> &str {
        &self.nodes[idx].label
    }

    fn bfs(&self, start: usize) -> Vec<usize> {
        let mut visited = vec![false; self.nodes.len()];
        let mut queue = VecDeque::new();
        let mut order = Vec::new();

        visited[start] = true;
        queue.push_back(start);

        while let Some(idx) = queue.pop_front() {
            order.push(idx);
            for &neighbor in self.neighbors(idx) {
                if !visited[neighbor] {
                    visited[neighbor] = true;
                    queue.push_back(neighbor);
                }
            }
        }
        order
    }

    fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = vec![false; self.nodes.len()];
        let mut order = Vec::new();
        self.dfs_helper(start, &mut visited, &mut order);
        order
    }

    fn dfs_helper(&self, idx: usize, visited: &mut [bool], order: &mut Vec<usize>) {
        visited[idx] = true;
        order.push(idx);
        for &neighbor in self.neighbors(idx) {
            if !visited[neighbor] {
                self.dfs_helper(neighbor, visited, order);
            }
        }
    }
}

fn basic_arena_graph() {
    let mut g = Graph::new();
    let a = g.add_node("A");
    let b = g.add_node("B");
    let c = g.add_node("C");

    g.add_edge(a, b);
    g.add_edge(a, c);
    g.add_edge(b, c);
    g.add_edge(c, a);

    assert_eq!(g.label(a), "A");
    let neighbors: Vec<&str> = g.neighbors(a).iter().map(|&i| g.label(i)).collect();
    assert_eq!(neighbors, vec!["B", "C"]);
}

fn bfs_test() {
    let mut g = Graph::new();
    let start = g.add_node("start");
    let mid1 = g.add_node("mid1");
    let mid2 = g.add_node("mid2");
    let end_node = g.add_node("end");

    g.add_edge(start, mid1);
    g.add_edge(start, mid2);
    g.add_edge(mid1, end_node);
    g.add_edge(mid2, end_node);

    let order: Vec<&str> = g.bfs(start).iter().map(|&i| g.label(i)).collect();
    assert_eq!(order, vec!["start", "mid1", "mid2", "end"]);
}

fn weighted_arena() {
    struct WNode {
        label: &'static str,
        edges: Vec<(usize, f64)>,
    }

    let nodes = vec![
        WNode {
            label: "A",
            edges: vec![(1, 1.0), (2, 4.0)],
        },
        WNode {
            label: "B",
            edges: vec![(2, 2.0)],
        },
        WNode {
            label: "C",
            edges: vec![],
        },
    ];

    let total: f64 = nodes[0].edges.iter().map(|(_, w)| w).sum();
    assert!((total - 5.0).abs() < f64::EPSILON);
    assert_eq!(nodes[0].label, "A");
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_arena_graph();
    }

    #[test]
    fn test_bfs() {
        bfs_test();
    }

    #[test]
    fn test_weighted() {
        weighted_arena();
    }

    #[test]
    fn test_dfs() {
        let mut g = Graph::new();
        let a = g.add_node("A");
        let b = g.add_node("B");
        let c = g.add_node("C");
        let d = g.add_node("D");
        g.add_edge(a, b);
        g.add_edge(a, c);
        g.add_edge(b, d);
        let order: Vec<&str> = g.dfs(a).iter().map(|&i| g.label(i)).collect();
        assert_eq!(order, vec!["A", "B", "D", "C"]);
    }
}

(* 1036: Graph with Arena Allocation *)
(* Use arrays as arenas — index-based graph representation *)

(* Approach 1: Array-based arena graph *)
type node = {
  label: string;
  edges: int list;  (* indices into the arena *)
}

let arena_graph () =
  (* Build a graph: 0:A -> 1:B, 2:C; 1:B -> 2:C; 2:C -> 0:A *)
  let arena = [|
    { label = "A"; edges = [1; 2] };
    { label = "B"; edges = [2] };
    { label = "C"; edges = [0] };
  |] in
  assert (arena.(0).label = "A");
  assert (arena.(0).edges = [1; 2]);
  (* Follow edges from A *)
  let neighbors_of_a = List.map (fun i -> arena.(i).label) arena.(0).edges in
  assert (neighbors_of_a = ["B"; "C"])

(* Approach 2: Build graph incrementally *)
let build_graph () =
  let nodes = Array.make 4 { label = ""; edges = [] } in
  nodes.(0) <- { label = "start"; edges = [1; 2] };
  nodes.(1) <- { label = "mid1"; edges = [3] };
  nodes.(2) <- { label = "mid2"; edges = [3] };
  nodes.(3) <- { label = "end"; edges = [] };
  (* BFS from node 0 *)
  let visited = Array.make 4 false in
  let queue = Queue.create () in
  Queue.push 0 queue;
  visited.(0) <- true;
  let order = ref [] in
  while not (Queue.is_empty queue) do
    let idx = Queue.pop queue in
    order := nodes.(idx).label :: !order;
    List.iter (fun neighbor ->
      if not visited.(neighbor) then begin
        visited.(neighbor) <- true;
        Queue.push neighbor queue
      end
    ) nodes.(idx).edges
  done;
  let bfs_order = List.rev !order in
  assert (bfs_order = ["start"; "mid1"; "mid2"; "end"])

(* Approach 3: Weighted edges *)
type weighted_node = {
  w_label: string;
  w_edges: (int * float) list;  (* (target_index, weight) *)
}

let weighted_graph () =
  let arena = [|
    { w_label = "A"; w_edges = [(1, 1.0); (2, 4.0)] };
    { w_label = "B"; w_edges = [(2, 2.0)] };
    { w_label = "C"; w_edges = [] };
  |] in
  let total_weight_from_a =
    List.fold_left (fun acc (_, w) -> acc +. w) 0.0 arena.(0).w_edges
  in
  assert (total_weight_from_a = 5.0)

let () =
  arena_graph ();
  build_graph ();
  weighted_graph ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Pointer vs index: Rust requires index-based edges to avoid ownership problems; OCaml can use direct mutable pointers (GC prevents dangling).

Cycle safety: Rust's arena cannot have reference cycles (indices are just integers); OCaml's GC handles pointer cycles automatically.

Memory locality: Both approaches benefit from arena allocation (all nodes in one Vec/array), but Rust's index approach is idiomatic.

petgraph: Rust's petgraph crate abstracts over NodeIndex types and is the production graph library; OCaml's ocamlgraph uses a similar design.

OCaml Approach

OCaml graphs can use mutable node records with ref pointers (GC handles cycles) or the same index-based approach:

type node = { label: string; mutable edges: int list }
type graph = { nodes: node array }

let add_edge g from_ to_ =
  g.nodes.(from_).edges <- to_ :: g.nodes.(from_).edges

The mutable pointer approach is natural in OCaml because the GC handles cycles. The index approach is also used for performance-critical code.

Full Source

#![allow(clippy::all)]
// 1036: Graph with Arena Allocation
// Vec<Node> indexed by usize — the idiomatic Rust graph pattern

use std::collections::VecDeque;

/// A graph node stored in an arena (Vec)
#[derive(Debug)]
struct Node {
    label: String,
    edges: Vec<usize>, // indices into the arena
}

/// Arena-based graph
struct Graph {
    nodes: Vec<Node>,
}

impl Graph {
    fn new() -> Self {
        Graph { nodes: Vec::new() }
    }

    fn add_node(&mut self, label: &str) -> usize {
        let idx = self.nodes.len();
        self.nodes.push(Node {
            label: label.to_string(),
            edges: Vec::new(),
        });
        idx
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.nodes[from].edges.push(to);
    }

    fn neighbors(&self, idx: usize) -> &[usize] {
        &self.nodes[idx].edges
    }

    fn label(&self, idx: usize) -> &str {
        &self.nodes[idx].label
    }

    fn bfs(&self, start: usize) -> Vec<usize> {
        let mut visited = vec![false; self.nodes.len()];
        let mut queue = VecDeque::new();
        let mut order = Vec::new();

        visited[start] = true;
        queue.push_back(start);

        while let Some(idx) = queue.pop_front() {
            order.push(idx);
            for &neighbor in self.neighbors(idx) {
                if !visited[neighbor] {
                    visited[neighbor] = true;
                    queue.push_back(neighbor);
                }
            }
        }
        order
    }

    fn dfs(&self, start: usize) -> Vec<usize> {
        let mut visited = vec![false; self.nodes.len()];
        let mut order = Vec::new();
        self.dfs_helper(start, &mut visited, &mut order);
        order
    }

    fn dfs_helper(&self, idx: usize, visited: &mut [bool], order: &mut Vec<usize>) {
        visited[idx] = true;
        order.push(idx);
        for &neighbor in self.neighbors(idx) {
            if !visited[neighbor] {
                self.dfs_helper(neighbor, visited, order);
            }
        }
    }
}

fn basic_arena_graph() {
    let mut g = Graph::new();
    let a = g.add_node("A");
    let b = g.add_node("B");
    let c = g.add_node("C");

    g.add_edge(a, b);
    g.add_edge(a, c);
    g.add_edge(b, c);
    g.add_edge(c, a);

    assert_eq!(g.label(a), "A");
    let neighbors: Vec<&str> = g.neighbors(a).iter().map(|&i| g.label(i)).collect();
    assert_eq!(neighbors, vec!["B", "C"]);
}

fn bfs_test() {
    let mut g = Graph::new();
    let start = g.add_node("start");
    let mid1 = g.add_node("mid1");
    let mid2 = g.add_node("mid2");
    let end_node = g.add_node("end");

    g.add_edge(start, mid1);
    g.add_edge(start, mid2);
    g.add_edge(mid1, end_node);
    g.add_edge(mid2, end_node);

    let order: Vec<&str> = g.bfs(start).iter().map(|&i| g.label(i)).collect();
    assert_eq!(order, vec!["start", "mid1", "mid2", "end"]);
}

fn weighted_arena() {
    struct WNode {
        label: &'static str,
        edges: Vec<(usize, f64)>,
    }

    let nodes = vec![
        WNode {
            label: "A",
            edges: vec![(1, 1.0), (2, 4.0)],
        },
        WNode {
            label: "B",
            edges: vec![(2, 2.0)],
        },
        WNode {
            label: "C",
            edges: vec![],
        },
    ];

    let total: f64 = nodes[0].edges.iter().map(|(_, w)| w).sum();
    assert!((total - 5.0).abs() < f64::EPSILON);
    assert_eq!(nodes[0].label, "A");
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_arena_graph();
    }

    #[test]
    fn test_bfs() {
        bfs_test();
    }

    #[test]
    fn test_weighted() {
        weighted_arena();
    }

    #[test]
    fn test_dfs() {
        let mut g = Graph::new();
        let a = g.add_node("A");
        let b = g.add_node("B");
        let c = g.add_node("C");
        let d = g.add_node("D");
        g.add_edge(a, b);
        g.add_edge(a, c);
        g.add_edge(b, d);
        let order: Vec<&str> = g.dfs(a).iter().map(|&i| g.label(i)).collect();
        assert_eq!(order, vec!["A", "B", "D", "C"]);
    }
}

(* 1036: Graph with Arena Allocation *)
(* Use arrays as arenas — index-based graph representation *)

(* Approach 1: Array-based arena graph *)
type node = {
  label: string;
  edges: int list;  (* indices into the arena *)
}

let arena_graph () =
  (* Build a graph: 0:A -> 1:B, 2:C; 1:B -> 2:C; 2:C -> 0:A *)
  let arena = [|
    { label = "A"; edges = [1; 2] };
    { label = "B"; edges = [2] };
    { label = "C"; edges = [0] };
  |] in
  assert (arena.(0).label = "A");
  assert (arena.(0).edges = [1; 2]);
  (* Follow edges from A *)
  let neighbors_of_a = List.map (fun i -> arena.(i).label) arena.(0).edges in
  assert (neighbors_of_a = ["B"; "C"])

(* Approach 2: Build graph incrementally *)
let build_graph () =
  let nodes = Array.make 4 { label = ""; edges = [] } in
  nodes.(0) <- { label = "start"; edges = [1; 2] };
  nodes.(1) <- { label = "mid1"; edges = [3] };
  nodes.(2) <- { label = "mid2"; edges = [3] };
  nodes.(3) <- { label = "end"; edges = [] };
  (* BFS from node 0 *)
  let visited = Array.make 4 false in
  let queue = Queue.create () in
  Queue.push 0 queue;
  visited.(0) <- true;
  let order = ref [] in
  while not (Queue.is_empty queue) do
    let idx = Queue.pop queue in
    order := nodes.(idx).label :: !order;
    List.iter (fun neighbor ->
      if not visited.(neighbor) then begin
        visited.(neighbor) <- true;
        Queue.push neighbor queue
      end
    ) nodes.(idx).edges
  done;
  let bfs_order = List.rev !order in
  assert (bfs_order = ["start"; "mid1"; "mid2"; "end"])

(* Approach 3: Weighted edges *)
type weighted_node = {
  w_label: string;
  w_edges: (int * float) list;  (* (target_index, weight) *)
}

let weighted_graph () =
  let arena = [|
    { w_label = "A"; w_edges = [(1, 1.0); (2, 4.0)] };
    { w_label = "B"; w_edges = [(2, 2.0)] };
    { w_label = "C"; w_edges = [] };
  |] in
  let total_weight_from_a =
    List.fold_left (fun acc (_, w) -> acc +. w) 0.0 arena.(0).w_edges
  in
  assert (total_weight_from_a = 5.0)

let () =
  arena_graph ();
  build_graph ();
  weighted_graph ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic() {
        basic_arena_graph();
    }

    #[test]
    fn test_bfs() {
        bfs_test();
    }

    #[test]
    fn test_weighted() {
        weighted_arena();
    }

    #[test]
    fn test_dfs() {
        let mut g = Graph::new();
        let a = g.add_node("A");
        let b = g.add_node("B");
        let c = g.add_node("C");
        let d = g.add_node("D");
        g.add_edge(a, b);
        g.add_edge(a, c);
        g.add_edge(b, d);
        let order: Vec<&str> = g.dfs(a).iter().map(|&i| g.label(i)).collect();
        assert_eq!(order, vec!["A", "B", "D", "C"]);
    }
}

Deep Comparison

Graph with Arena Allocation — Comparison

Core Insight

Graphs have shared, cyclic references — the borrow checker's nightmare. The arena pattern sidesteps this entirely: store all nodes in a Vec, use usize indices instead of pointers. Both languages can use this pattern, but it's especially important in Rust where Rc<RefCell> graphs are verbose and slow.

OCaml Approach

• Array-based arena: node array with index-based edges

• Mutable arrays for building incrementally

• GC means pointer-based graphs also work fine

• Queue module for BFS

Rust Approach

• Vec<Node> arena with usize indices as node handles

• add_node returns index, add_edge connects indices

• No lifetime issues — indices are just numbers

• Cache-friendly: nodes stored contiguously

• BFS/DFS use vec![false; n] for visited tracking

Comparison Table

Feature	OCaml (array arena)	Rust (`Vec` arena)
Node storage	`node array`	`Vec<Node>`
Edge references	`int` indices	`usize` indices
Add node	Array mutation	`push` returns index
Cycles	Free (GC or indices)	Free (indices only)
Cache locality	Array = contiguous	Vec = contiguous
Alternative	Pointer graph (GC safe)	`Rc<RefCell>` (verbose)
Recommendation	Either works	Arena strongly preferred

Exercises

Add a remove_edge(from: usize, to: usize) method that removes a directed edge.

Implement a topological sort over the arena graph using DFS post-order.

Add edge weights (to: usize, weight: i64) and implement Dijkstra's shortest path over the weighted arena graph.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust