378: Graph as Adjacency Matrix

Difficulty: 3 Level: Advanced Represent a graph as a 2D boolean matrix — optimal for dense graphs and constant-time edge queries.

The Problem This Solves

You have a graph with N nodes and need to answer "is there an edge between node A and node B?" frequently. An adjacency list (`Vec<Vec<usize>>`) answers this in `O(degree(A))` — you scan A's neighbor list. For a dense graph where most nodes connect to most others, that's expensive. An adjacency matrix answers it in `O(1)`: just check `matrix[a][b]`. The tradeoff is space: `O(N²)` bits regardless of edge count. For a 1000-node graph, that's 1 million bits (~125KB) — fine. For a 100,000-node sparse graph, that's 10 billion bits (~1.25GB) — not fine. The decision rule: dense graphs (E ≈ N²) → matrix. Sparse graphs (E ≈ N) → adjacency list. Adjacency matrices shine in graph algorithms that need constant-time edge queries: Floyd-Warshall all-pairs shortest paths, transitive closure, dense graph clique detection.

The Intuition

An adjacency matrix for N nodes is an `N × N` array where `matrix[i][j] = true` means "there is an edge from node i to node j." For undirected graphs, the matrix is symmetric: `matrix[i][j] == matrix[j][i]`. For weighted graphs, store weights instead of booleans: `matrix[i][j] = Some(weight)` or `f64::INFINITY` for no edge. For large N, use a bit matrix (`Vec<u64>` where each u64 holds 64 bits) to reduce memory by 64× compared to `Vec<Vec<bool>>`.

How It Works in Rust

struct AdjMatrix {
 edges: Vec<Vec<bool>>,
 n: usize,
}

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

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

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

 fn neighbors(&self, node: usize) -> impl Iterator<Item = usize> + '_ {
     (0..self.n).filter(move |&j| self.edges[node][j])
 }
}

let mut g = AdjMatrix::new(4);
g.add_edge(0, 1);
g.add_edge(0, 2);
g.add_edge(2, 3);

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

For production use, the `petgraph` crate provides both matrix and adjacency-list representations with graph algorithm implementations.

What This Unlocks

All-pairs shortest paths — Floyd-Warshall runs in O(N³) with O(1) edge access, no adjacency scanning.
Transitive closure — multiply boolean matrices to find reachability.
Dense graph algorithms — clique detection, graph coloring are simpler with matrix representation.

Key Differences

Concept	OCaml	Rust
2D array	`Array2D` or `array.(i).(j)`	`Vec<Vec<T>>` or `[T; N*N]` flat with index math
Graph library	`ocamlgraph`	`petgraph`
Edge query	`O(degree)` in adjacency list	`O(1)` with matrix
Memory	Not typed for graphs	Explicit: `N²` bools or `N²` floats

// Graph as adjacency matrix in Rust
use std::fmt;

struct Graph {
    vertices: usize,
    matrix: Vec<Vec<bool>>,
}

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

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

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

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

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

impl fmt::Display for Graph {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "  ")?;
        for i in 0..self.vertices {
            write!(f, "{} ", i)?;
        }
        writeln!(f)?;
        for i in 0..self.vertices {
            write!(f, "{} ", i)?;
            for j in 0..self.vertices {
                write!(f, "{} ", if self.matrix[i][j] { 1 } else { 0 })?;
            }
            writeln!(f)?;
        }
        Ok(())
    }
}

fn main() {
    let mut g = Graph::new(5);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 3);
    g.add_edge(2, 3);
    g.add_edge(3, 4);

    println!("Graph adjacency matrix (5 vertices):");
    print!("{}", g);

    println!("Neighbors of vertex 3: {:?}", g.neighbors(3));
    println!("Has edge 0-1: {}", g.has_edge(0, 1));
    println!("Has edge 0-4: {}", g.has_edge(0, 4));
    println!("Degree of vertex 3: {}", g.degree(3));
}

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

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

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

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

(* 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)