378 Intermediate

378: Graph — Adjacency Matrix

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "378: Graph — Adjacency Matrix" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Some graph algorithms require O(1) edge existence queries. Key difference from OCaml: 1. **Index syntax**: Rust uses `matrix[u][v]` with bounds

Tutorial

The Problem

Some graph algorithms require O(1) edge existence queries. For dense graphs where most pairs of vertices are connected — circuit boards, protein interaction networks, game adjacency grids — storing edges as a 2D boolean matrix provides constant-time lookup at the cost of O(V²) space. Transitive closure algorithms (Floyd-Warshall), adjacency matrix multiplication for path counting, and spectral graph analysis all operate naturally on matrix form.

Adjacency matrices appear in network routing tables, game AI pathfinding on grid maps, social influence modeling, and scientific computing (graph Laplacian for mesh simulation).

🎯 Learning Outcomes

• Understand when adjacency matrices outperform adjacency lists (dense graphs, O(1) edge queries)

• Learn how to represent a 2D adjacency structure using Vec<Vec<bool>> in Rust

• Understand degree computation, edge counting, and neighbor enumeration over matrix form

• See the trade-off: O(1) has_edge vs. O(V) neighbor enumeration

• Learn to implement both directed and undirected edges in matrix form

Code Example

#![allow(clippy::all)]
//! Graph - Adjacency Matrix Representation
//!
//! O(1) edge lookup, O(V²) storage.

/// Graph with adjacency matrix representation
pub struct Graph {
    vertices: usize,
    matrix: Vec<Vec<bool>>,
}

impl Graph {
    pub fn new(n: usize) -> Self {
        Self {
            vertices: n,
            matrix: vec![vec![false; n]; n],
        }
    }

    pub fn add_edge(&mut self, u: usize, v: usize) {
        self.matrix[u][v] = true;
        self.matrix[v][u] = true;
    }

    pub fn add_directed_edge(&mut self, u: usize, v: usize) {
        self.matrix[u][v] = true;
    }

    pub fn has_edge(&self, u: usize, v: usize) -> bool {
        self.matrix[u][v]
    }

    pub fn neighbors(&self, u: usize) -> Vec<usize> {
        (0..self.vertices).filter(|&v| self.matrix[u][v]).collect()
    }

    pub fn degree(&self, u: usize) -> usize {
        self.neighbors(u).len()
    }

    pub fn vertex_count(&self) -> usize {
        self.vertices
    }

    pub fn edge_count(&self) -> usize {
        let mut count = 0;
        for i in 0..self.vertices {
            for j in i + 1..self.vertices {
                if self.matrix[i][j] {
                    count += 1;
                }
            }
        }
        count
    }
}

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

    #[test]
    fn test_add_edge() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert!(g.has_edge(0, 1));
        assert!(g.has_edge(1, 0));
        assert!(!g.has_edge(0, 3));
    }

    #[test]
    fn test_neighbors() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(0, 3);
        let n = g.neighbors(0);
        assert_eq!(n.len(), 3);
    }

    #[test]
    fn test_degree() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert_eq!(g.degree(0), 2);
        assert_eq!(g.degree(1), 1);
    }

    #[test]
    fn test_edge_count() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(1, 2);
        g.add_edge(2, 3);
        assert_eq!(g.edge_count(), 3);
    }

    #[test]
    fn test_directed() {
        let mut g = Graph::new(3);
        g.add_directed_edge(0, 1);
        assert!(g.has_edge(0, 1));
        assert!(!g.has_edge(1, 0));
    }
}

(* Graph as adjacency matrix in OCaml *)

type graph = {
  vertices: int;
  matrix: bool array array;
}

let create_graph n =
  { vertices = n; matrix = Array.make_matrix n n false }

let add_edge g u v =
  g.matrix.(u).(v) <- true;
  g.matrix.(v).(u) <- true  (* undirected *)

let has_edge g u v = g.matrix.(u).(v)

let neighbors g u =
  Array.to_list (Array.init g.vertices (fun v ->
    if g.matrix.(u).(v) then Some v else None))
  |> List.filter_map (fun x -> x)

let print_matrix g =
  Printf.printf "  ";
  for i = 0 to g.vertices - 1 do
    Printf.printf "%d " i
  done;
  print_newline ();
  for i = 0 to g.vertices - 1 do
    Printf.printf "%d " i;
    for j = 0 to g.vertices - 1 do
      Printf.printf "%s " (if g.matrix.(i).(j) then "1" else "0")
    done;
    print_newline ()
  done

let degree g u =
  List.length (neighbors g u)

let () =
  let g = create_graph 5 in
  add_edge g 0 1;
  add_edge g 0 2;
  add_edge g 1 3;
  add_edge g 2 3;
  add_edge g 3 4;
  Printf.printf "Graph adjacency matrix (5 vertices):\n";
  print_matrix g;
  Printf.printf "\nNeighbors of vertex 3: ";
  List.iter (fun v -> Printf.printf "%d " v) (neighbors g 3);
  print_newline ();
  Printf.printf "Has edge 0-1: %b\n" (has_edge g 0 1);
  Printf.printf "Has edge 0-4: %b\n" (has_edge g 0 4);
  Printf.printf "Degree of vertex 3: %d\n" (degree g 3)

Key Differences

Index syntax: Rust uses matrix[u][v] with bounds-checked indexing (panics on OOB); OCaml uses matrix.(u).(v) which also raises Invalid_argument on OOB.

Initialization: Rust uses vec![vec![false; n]; n]; OCaml uses Array.make_matrix n n false — equivalent performance, different ergonomics.

Neighbor iteration: Rust uses (0..n).filter(|&v| self.matrix[u][v]).collect(); OCaml would use Array.to_seqi or a recursive fold.

Mutability: Rust requires &mut self for edge insertion enforced by the borrow checker; OCaml arrays are mutable by default with no compile-time tracking.

OCaml Approach

OCaml uses bool array array for the adjacency matrix, initialized with Array.make_matrix. Edge checking is matrix.(u).(v). Neighbor enumeration uses Array.to_seq with Seq.filter_mapi. The matrix representation integrates naturally with OCaml's array performance, which matches Rust's since both compile to contiguous memory.

Full Source

#![allow(clippy::all)]
//! Graph - Adjacency Matrix Representation
//!
//! O(1) edge lookup, O(V²) storage.

/// Graph with adjacency matrix representation
pub struct Graph {
    vertices: usize,
    matrix: Vec<Vec<bool>>,
}

impl Graph {
    pub fn new(n: usize) -> Self {
        Self {
            vertices: n,
            matrix: vec![vec![false; n]; n],
        }
    }

    pub fn add_edge(&mut self, u: usize, v: usize) {
        self.matrix[u][v] = true;
        self.matrix[v][u] = true;
    }

    pub fn add_directed_edge(&mut self, u: usize, v: usize) {
        self.matrix[u][v] = true;
    }

    pub fn has_edge(&self, u: usize, v: usize) -> bool {
        self.matrix[u][v]
    }

    pub fn neighbors(&self, u: usize) -> Vec<usize> {
        (0..self.vertices).filter(|&v| self.matrix[u][v]).collect()
    }

    pub fn degree(&self, u: usize) -> usize {
        self.neighbors(u).len()
    }

    pub fn vertex_count(&self) -> usize {
        self.vertices
    }

    pub fn edge_count(&self) -> usize {
        let mut count = 0;
        for i in 0..self.vertices {
            for j in i + 1..self.vertices {
                if self.matrix[i][j] {
                    count += 1;
                }
            }
        }
        count
    }
}

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

    #[test]
    fn test_add_edge() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert!(g.has_edge(0, 1));
        assert!(g.has_edge(1, 0));
        assert!(!g.has_edge(0, 3));
    }

    #[test]
    fn test_neighbors() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(0, 3);
        let n = g.neighbors(0);
        assert_eq!(n.len(), 3);
    }

    #[test]
    fn test_degree() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert_eq!(g.degree(0), 2);
        assert_eq!(g.degree(1), 1);
    }

    #[test]
    fn test_edge_count() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(1, 2);
        g.add_edge(2, 3);
        assert_eq!(g.edge_count(), 3);
    }

    #[test]
    fn test_directed() {
        let mut g = Graph::new(3);
        g.add_directed_edge(0, 1);
        assert!(g.has_edge(0, 1));
        assert!(!g.has_edge(1, 0));
    }
}

(* Graph as adjacency matrix in OCaml *)

type graph = {
  vertices: int;
  matrix: bool array array;
}

let create_graph n =
  { vertices = n; matrix = Array.make_matrix n n false }

let add_edge g u v =
  g.matrix.(u).(v) <- true;
  g.matrix.(v).(u) <- true  (* undirected *)

let has_edge g u v = g.matrix.(u).(v)

let neighbors g u =
  Array.to_list (Array.init g.vertices (fun v ->
    if g.matrix.(u).(v) then Some v else None))
  |> List.filter_map (fun x -> x)

let print_matrix g =
  Printf.printf "  ";
  for i = 0 to g.vertices - 1 do
    Printf.printf "%d " i
  done;
  print_newline ();
  for i = 0 to g.vertices - 1 do
    Printf.printf "%d " i;
    for j = 0 to g.vertices - 1 do
      Printf.printf "%s " (if g.matrix.(i).(j) then "1" else "0")
    done;
    print_newline ()
  done

let degree g u =
  List.length (neighbors g u)

let () =
  let g = create_graph 5 in
  add_edge g 0 1;
  add_edge g 0 2;
  add_edge g 1 3;
  add_edge g 2 3;
  add_edge g 3 4;
  Printf.printf "Graph adjacency matrix (5 vertices):\n";
  print_matrix g;
  Printf.printf "\nNeighbors of vertex 3: ";
  List.iter (fun v -> Printf.printf "%d " v) (neighbors g 3);
  print_newline ();
  Printf.printf "Has edge 0-1: %b\n" (has_edge g 0 1);
  Printf.printf "Has edge 0-4: %b\n" (has_edge g 0 4);
  Printf.printf "Degree of vertex 3: %d\n" (degree g 3)

✓ Tests Rust test suite

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

    #[test]
    fn test_add_edge() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert!(g.has_edge(0, 1));
        assert!(g.has_edge(1, 0));
        assert!(!g.has_edge(0, 3));
    }

    #[test]
    fn test_neighbors() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(0, 3);
        let n = g.neighbors(0);
        assert_eq!(n.len(), 3);
    }

    #[test]
    fn test_degree() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        assert_eq!(g.degree(0), 2);
        assert_eq!(g.degree(1), 1);
    }

    #[test]
    fn test_edge_count() {
        let mut g = Graph::new(4);
        g.add_edge(0, 1);
        g.add_edge(1, 2);
        g.add_edge(2, 3);
        assert_eq!(g.edge_count(), 3);
    }

    #[test]
    fn test_directed() {
        let mut g = Graph::new(3);
        g.add_directed_edge(0, 1);
        assert!(g.has_edge(0, 1));
        assert!(!g.has_edge(1, 0));
    }
}

Deep Comparison

OCaml vs Rust: Adjacency Matrix

Both use 2D array of booleans or weights.

Exercises

Transitive closure: Implement Floyd-Warshall's algorithm to compute the transitive closure matrix — closure[u][v] = true if there is any path from u to v.

Matrix multiplication for path counting: Implement matrix boolean multiplication and use it to count whether paths of exactly length k exist between any two vertices.

Graph complement: Write a function that returns the complement graph (edges where original has none, no edges where original has some), and verify it using a known complete graph.

Open Source Repos

functional-rust

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

Rust