1038 Intermediate

1038-adjacency-matrix — Adjacency Matrix Graph

Functional Programming

Tutorial

The Problem

The adjacency matrix represents a graph as a V×V boolean (or weighted) matrix where matrix[i][j] = true means there is an edge from node i to node j. Edge lookup is O(1) — a direct array access — making it ideal for dense graphs where the number of edges approaches V². It is the standard representation in network routing tables, transition matrices in Markov chains, and Floyd-Warshall all-pairs shortest path.

The trade-off is O(V²) space even for sparse graphs, which makes it unsuitable for social networks or road graphs but perfect for complete or nearly-complete graphs.

🎯 Learning Outcomes

• Represent a graph as Vec<Vec<bool>> with O(1) edge lookup

• Add directed and undirected edges

• Compute out-degree, in-degree, and find neighbors

• Implement matrix multiplication for reachability (transitive closure)

• Understand the space vs time trade-offs versus adjacency list

Code Example

#![allow(clippy::all)]
// 1038: Adjacency Matrix — Dense Graph Operations
// Vec<Vec<bool>> for O(1) edge lookup

/// Adjacency matrix graph
struct MatrixGraph {
    matrix: Vec<Vec<bool>>,
    size: usize,
}

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

    fn add_edge(&mut self, from: usize, to: usize) {
        self.matrix[from][to] = true;
    }

    fn has_edge(&self, from: usize, to: usize) -> bool {
        self.matrix[from][to]
    }

    fn neighbors(&self, node: usize) -> Vec<usize> {
        self.matrix[node]
            .iter()
            .enumerate()
            .filter_map(|(i, &connected)| if connected { Some(i) } else { None })
            .collect()
    }

    fn out_degree(&self, node: usize) -> usize {
        self.matrix[node].iter().filter(|&&c| c).count()
    }

    fn in_degree(&self, node: usize) -> usize {
        (0..self.size).filter(|&i| self.matrix[i][node]).count()
    }

    /// Warshall's transitive closure
    fn transitive_closure(&self) -> Vec<Vec<bool>> {
        let n = self.size;
        let mut tc: Vec<Vec<bool>> = self.matrix.clone();

        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    if tc[i][k] && tc[k][j] {
                        tc[i][j] = true;
                    }
                }
            }
        }
        tc
    }
}

fn basic_matrix() {
    let mut g = MatrixGraph::new(4);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 2);
    g.add_edge(2, 3);

    assert!(g.has_edge(0, 1));
    assert!(!g.has_edge(0, 3));
    assert!(g.has_edge(2, 3));
}

fn degree_and_neighbors() {
    let mut g = MatrixGraph::new(4);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 2);
    g.add_edge(2, 3);

    assert_eq!(g.out_degree(0), 2);
    assert_eq!(g.out_degree(2), 1);
    assert_eq!(g.in_degree(2), 2); // from 0 and 1
    assert_eq!(g.neighbors(0), vec![1, 2]);
}

fn transitive_closure() {
    let mut g = MatrixGraph::new(4);
    g.add_edge(0, 1);
    g.add_edge(1, 2);
    g.add_edge(2, 3);

    assert!(!g.has_edge(0, 3)); // No direct edge

    let tc = g.transitive_closure();
    assert!(tc[0][3]); // Reachable transitively
    assert!(tc[0][2]); // 0 -> 1 -> 2
    assert!(tc[1][3]); // 1 -> 2 -> 3
}

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

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

    #[test]
    fn test_degree() {
        degree_and_neighbors();
    }

    #[test]
    fn test_transitive() {
        transitive_closure();
    }

    #[test]
    fn test_undirected() {
        let mut g = MatrixGraph::new(3);
        // Undirected: add both directions
        g.add_edge(0, 1);
        g.add_edge(1, 0);
        assert!(g.has_edge(0, 1));
        assert!(g.has_edge(1, 0));
    }

    #[test]
    fn test_self_loop() {
        let mut g = MatrixGraph::new(3);
        g.add_edge(0, 0);
        assert!(g.has_edge(0, 0));
        assert_eq!(g.out_degree(0), 1);
    }
}

(* 1038: Adjacency Matrix — Dense Graph Operations *)
(* 2D boolean array for graph connectivity *)

(* Approach 1: Basic adjacency matrix *)
let basic_matrix () =
  let n = 4 in
  let matrix = Array.make_matrix n n false in
  (* Add edges: 0->1, 0->2, 1->2, 2->3 *)
  matrix.(0).(1) <- true;
  matrix.(0).(2) <- true;
  matrix.(1).(2) <- true;
  matrix.(2).(3) <- true;
  assert (matrix.(0).(1) = true);
  assert (matrix.(0).(3) = false);
  assert (matrix.(2).(3) = true)

(* Approach 2: Degree counting and neighbor listing *)
let degree_and_neighbors () =
  let n = 4 in
  let matrix = Array.make_matrix n n false in
  matrix.(0).(1) <- true;
  matrix.(0).(2) <- true;
  matrix.(1).(2) <- true;
  matrix.(2).(3) <- true;
  (* Out-degree of node 0 *)
  let out_degree node =
    Array.fold_left (fun acc connected -> if connected then acc + 1 else acc)
      0 matrix.(node)
  in
  assert (out_degree 0 = 2);
  assert (out_degree 2 = 1);
  (* List neighbors *)
  let neighbors node =
    Array.to_list matrix.(node)
    |> List.mapi (fun i c -> (i, c))
    |> List.filter_map (fun (i, c) -> if c then Some i else None)
  in
  assert (neighbors 0 = [1; 2])

(* Approach 3: Transitive closure (Warshall's algorithm) *)
let transitive_closure () =
  let n = 4 in
  let m = Array.make_matrix n n false in
  m.(0).(1) <- true;
  m.(1).(2) <- true;
  m.(2).(3) <- true;
  (* Copy matrix *)
  let tc = Array.init n (fun i -> Array.copy m.(i)) in
  (* Warshall's algorithm *)
  for k = 0 to n - 1 do
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        if tc.(i).(k) && tc.(k).(j) then
          tc.(i).(j) <- true
      done
    done
  done;
  (* Now 0 can reach 3 transitively *)
  assert (not m.(0).(3));  (* Direct: no *)
  assert (tc.(0).(3));     (* Transitive: yes *)
  assert (tc.(0).(2));     (* 0 -> 1 -> 2 *)

let () =
  basic_matrix ();
  degree_and_neighbors ();
  transitive_closure ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Array access syntax: OCaml uses arr.(i).(j) for 2D array access; Rust uses matrix[i][j].

Initialization: OCaml's Array.make_matrix n n false is a one-liner; Rust uses vec![vec![false; n]; n].

Flat vs nested: Rust often uses a flat Vec<bool> with manual index calculation (i * n + j) for better cache locality; OCaml's nested arrays are standard.

Weighted graphs: Changing bool to Option<f64> or f64 with f64::INFINITY for no-edge handles weighted adjacency matrices in both languages.

OCaml Approach

OCaml uses a 2D array:

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

let make n = { matrix = Array.make_matrix n n false; size = n }
let add_edge g i j = g.matrix.(i).(j) <- true
let has_edge g i j = g.matrix.(i).(j)

OCaml arrays are mutable by default, making the update syntax cleaner. The semantics are identical to Rust's Vec<Vec<bool>>.

Full Source

#![allow(clippy::all)]
// 1038: Adjacency Matrix — Dense Graph Operations
// Vec<Vec<bool>> for O(1) edge lookup

/// Adjacency matrix graph
struct MatrixGraph {
    matrix: Vec<Vec<bool>>,
    size: usize,
}

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

    fn add_edge(&mut self, from: usize, to: usize) {
        self.matrix[from][to] = true;
    }

    fn has_edge(&self, from: usize, to: usize) -> bool {
        self.matrix[from][to]
    }

    fn neighbors(&self, node: usize) -> Vec<usize> {
        self.matrix[node]
            .iter()
            .enumerate()
            .filter_map(|(i, &connected)| if connected { Some(i) } else { None })
            .collect()
    }

    fn out_degree(&self, node: usize) -> usize {
        self.matrix[node].iter().filter(|&&c| c).count()
    }

    fn in_degree(&self, node: usize) -> usize {
        (0..self.size).filter(|&i| self.matrix[i][node]).count()
    }

    /// Warshall's transitive closure
    fn transitive_closure(&self) -> Vec<Vec<bool>> {
        let n = self.size;
        let mut tc: Vec<Vec<bool>> = self.matrix.clone();

        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    if tc[i][k] && tc[k][j] {
                        tc[i][j] = true;
                    }
                }
            }
        }
        tc
    }
}

fn basic_matrix() {
    let mut g = MatrixGraph::new(4);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 2);
    g.add_edge(2, 3);

    assert!(g.has_edge(0, 1));
    assert!(!g.has_edge(0, 3));
    assert!(g.has_edge(2, 3));
}

fn degree_and_neighbors() {
    let mut g = MatrixGraph::new(4);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 2);
    g.add_edge(2, 3);

    assert_eq!(g.out_degree(0), 2);
    assert_eq!(g.out_degree(2), 1);
    assert_eq!(g.in_degree(2), 2); // from 0 and 1
    assert_eq!(g.neighbors(0), vec![1, 2]);
}

fn transitive_closure() {
    let mut g = MatrixGraph::new(4);
    g.add_edge(0, 1);
    g.add_edge(1, 2);
    g.add_edge(2, 3);

    assert!(!g.has_edge(0, 3)); // No direct edge

    let tc = g.transitive_closure();
    assert!(tc[0][3]); // Reachable transitively
    assert!(tc[0][2]); // 0 -> 1 -> 2
    assert!(tc[1][3]); // 1 -> 2 -> 3
}

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

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

    #[test]
    fn test_degree() {
        degree_and_neighbors();
    }

    #[test]
    fn test_transitive() {
        transitive_closure();
    }

    #[test]
    fn test_undirected() {
        let mut g = MatrixGraph::new(3);
        // Undirected: add both directions
        g.add_edge(0, 1);
        g.add_edge(1, 0);
        assert!(g.has_edge(0, 1));
        assert!(g.has_edge(1, 0));
    }

    #[test]
    fn test_self_loop() {
        let mut g = MatrixGraph::new(3);
        g.add_edge(0, 0);
        assert!(g.has_edge(0, 0));
        assert_eq!(g.out_degree(0), 1);
    }
}

(* 1038: Adjacency Matrix — Dense Graph Operations *)
(* 2D boolean array for graph connectivity *)

(* Approach 1: Basic adjacency matrix *)
let basic_matrix () =
  let n = 4 in
  let matrix = Array.make_matrix n n false in
  (* Add edges: 0->1, 0->2, 1->2, 2->3 *)
  matrix.(0).(1) <- true;
  matrix.(0).(2) <- true;
  matrix.(1).(2) <- true;
  matrix.(2).(3) <- true;
  assert (matrix.(0).(1) = true);
  assert (matrix.(0).(3) = false);
  assert (matrix.(2).(3) = true)

(* Approach 2: Degree counting and neighbor listing *)
let degree_and_neighbors () =
  let n = 4 in
  let matrix = Array.make_matrix n n false in
  matrix.(0).(1) <- true;
  matrix.(0).(2) <- true;
  matrix.(1).(2) <- true;
  matrix.(2).(3) <- true;
  (* Out-degree of node 0 *)
  let out_degree node =
    Array.fold_left (fun acc connected -> if connected then acc + 1 else acc)
      0 matrix.(node)
  in
  assert (out_degree 0 = 2);
  assert (out_degree 2 = 1);
  (* List neighbors *)
  let neighbors node =
    Array.to_list matrix.(node)
    |> List.mapi (fun i c -> (i, c))
    |> List.filter_map (fun (i, c) -> if c then Some i else None)
  in
  assert (neighbors 0 = [1; 2])

(* Approach 3: Transitive closure (Warshall's algorithm) *)
let transitive_closure () =
  let n = 4 in
  let m = Array.make_matrix n n false in
  m.(0).(1) <- true;
  m.(1).(2) <- true;
  m.(2).(3) <- true;
  (* Copy matrix *)
  let tc = Array.init n (fun i -> Array.copy m.(i)) in
  (* Warshall's algorithm *)
  for k = 0 to n - 1 do
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        if tc.(i).(k) && tc.(k).(j) then
          tc.(i).(j) <- true
      done
    done
  done;
  (* Now 0 can reach 3 transitively *)
  assert (not m.(0).(3));  (* Direct: no *)
  assert (tc.(0).(3));     (* Transitive: yes *)
  assert (tc.(0).(2));     (* 0 -> 1 -> 2 *)

let () =
  basic_matrix ();
  degree_and_neighbors ();
  transitive_closure ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

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

    #[test]
    fn test_degree() {
        degree_and_neighbors();
    }

    #[test]
    fn test_transitive() {
        transitive_closure();
    }

    #[test]
    fn test_undirected() {
        let mut g = MatrixGraph::new(3);
        // Undirected: add both directions
        g.add_edge(0, 1);
        g.add_edge(1, 0);
        assert!(g.has_edge(0, 1));
        assert!(g.has_edge(1, 0));
    }

    #[test]
    fn test_self_loop() {
        let mut g = MatrixGraph::new(3);
        g.add_edge(0, 0);
        assert!(g.has_edge(0, 0));
        assert_eq!(g.out_degree(0), 1);
    }
}

Deep Comparison

Adjacency Matrix — Comparison

Core Insight

A 2D boolean matrix is the simplest graph representation: matrix[i][j] = true means edge from i to j. Both languages use the same approach — mutable 2D arrays. The key difference is OCaml's Array.make_matrix vs Rust's vec![vec![false; n]; n].

OCaml Approach

• Array.make_matrix n n false creates the matrix

• Direct indexing: matrix.(i).(j)

• Array.fold_left for degree counting

• Triple nested loop for Warshall's algorithm

• Array.copy for non-destructive operations

Rust Approach

• vec![vec![false; n]; n] macro for initialization

• Direct indexing: matrix[i][j]

• Iterator methods: .filter(|&&c| c).count() for degree

• .enumerate().filter_map() for neighbor listing

• .clone() on outer Vec for non-destructive copy

Comparison Table

Feature	OCaml	Rust
Creation	`Array.make_matrix n n false`	`vec![vec![false; n]; n]`
Edge check	`m.(i).(j)`	`m[i][j]`
Edge add	`m.(i).(j) <- true`	`m[i][j] = true`
Copy	`Array.init n (fun i -> Array.copy m.(i))`	`m.clone()`
Neighbor list	`filter_map` on array	`.enumerate().filter_map()`
Memory	O(n²)	O(n²)
Edge lookup	O(1)	O(1)

Exercises

Implement Floyd-Warshall all-pairs shortest path on a weighted Vec<Vec<f64>> matrix with f64::INFINITY for no-edge.

Write transpose(g: &MatrixGraph) -> MatrixGraph that reverses all edge directions.

Compute the transitive closure by matrix squaring: keep multiplying the boolean matrix by itself (using OR instead of AND) until it stabilizes.

Open Source Repos

functional-rust

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

Rust