Part 07•Chapter 2 of 6•Intermediate

Graph Storage Architectures & Data Structures

Adjacency Matrix vs Adjacency List vs Edge List trade-offs, Compressed Sparse Row (CSR) for HPC, and incidence representations.

~10 min read

1,983 words

17 Sections

Reviewed & Verified (2024 Syllabus)

Keys: [ Prev • ] Next

Space vs Lookup Trade-offsCompressed Sparse Row (CSR)Edge List for Greedy MST

The physical representation of a graph in computer memory dictates algorithmic time complexity, hardware cache locality, and memory overhead. Understanding trade-offs between dense adjacency matrices, sparse adjacency lists, and pointerless Compressed Sparse Row (CSR) arrays bridges theoretical graph traversal with high-performance systems engineering.

1. Executive Summary & Learning Objectives

Representing a graph $G = (V, E)$ in digital memory requires balancing the trade-off between edge existence lookup latency ( $O (1)$ ) and neighbor iteration cost ( $Θ (de g (u))$ ). While dense matrices optimize edge queries for complete topologies, real-world graphs (the Web, highway networks, social graphs) are overwhelmingly sparse, requiring memory-compact adjacency lists and cache-aligned Compressed Sparse Row (CSR) formats.

By the end of this chapter, you will be able to:

Analyze memory and time trade-offs across Adjacency Matrices, Adjacency Lists, Edge Lists, and Compressed Sparse Row (CSR) representations.
Apply matrix multiplication powers ( $A^{k}$ ) to compute exact path counts of length $k$ between vertex pairs in $O (V^{3} lo g k)$ time.
Construct a Compressed Sparse Row (CSR) layout from raw edge lists and query contiguous neighbor slices with zero pointer chasing.
Evaluate CPU L1/L2 cache line utilization and SIMD vectorization characteristics across graph storage models.
Select the mathematically and hardware-optimal graph data structure given vertex count $∣ V ∣$ , edge count $∣ E ∣$ , and query workload.

2. Graph Storage Architectures Overview

Architecture Category	Storage Model	Memory Complexity	Best Algorithmic Fit
Dense Representation	Adjacency Matrix ( $V \times V$ 2D Array)	$Θ (V^{2})$	Dense graphs ( $∣ E ∣ \approx ∣ V ∣^{2}$ ), Warshall transitive closure, Floyd-Warshall all-pairs shortest paths
Sparse Representation	Adjacency List (Array of dynamic vectors)	$Θ (V + E)$	General graph software, BFS, DFS, Dijkstra, Tarjan SCC
Relational Representation	Edge List (Array of edge triplets)	$Θ (E)$	Kruskal's Minimum Spanning Tree, Bellman-Ford edge relaxation
High-Performance (HPC)	Compressed Sparse Row (CSR) (3 flat arrays)	$Θ (V + E)$	Graph Neural Networks (PyTorch Geometric), GPU graph analytics (NVIDIA cuGraph), GraphBLAS
Incidence Representation	Incidence Matrix ( $V \times E$ 2D Array)	$Θ (V \cdot E)$	Algebraic topology, Kirchhoff circuit laws, network flow matrices

3. Architecture 1: Adjacency Matrix

An Adjacency Matrix is a 2D array Adj[V][V] where:

Adj[u][v] = 1 (or edge weight $w$ ) if $(u, v) \in E$ .
Adj[u][v] = 0 (or $\infty$ for weighted graphs) if no edge exists.

Sample Adjacency Matrix (4 Vertices, Undirected Cycle)

Consider an undirected graph with edges ${(0, 1), (0, 2), (1, 3), (2, 3)}$ :

Vertex	Column $0$	Column $1$	Column $2$	Column $3$	Vertex Degree $de g (u)$
Row $0$	$0$	$1$	$1$	$0$	$2$
Row $1$	$1$	$0$	$0$	$1$	$2$
Row $2$	$1$	$0$	$0$	$1$	$2$
Row $3$	$0$	$1$	$1$	$0$	$2$

Symmetric Invariant: For undirected graphs, $Adj [u] [v] = Adj [v] [u]$ across the main diagonal.

Mathematical Superpower: Matrix Powers Count Paths

Let $A$ be the unweighted adjacency matrix of graph $G$ . The $(i, j)$ -th entry of the $k$ -th matrix power $A^{k}$ :

(A^{k})_{i, j} = x_{1} \sum x_{2} \sum \dots x_{k - 1} \sum A_{i, x_{1}} A_{x_{1}, x_{2}} \dots A_{x_{k - 1}, j}

equals the exact number of distinct paths of length $k$ from vertex $i$ to vertex $j$ . Using binary matrix exponentiation, this can be computed in $O (V^{3} lo g k)$ time!

4. Architecture 2: Adjacency List

An Adjacency List stores an array of size $∣ V ∣$ where index $u$ contains a dynamic array (or list) of all adjacent neighbors incident to $u$ :

Vertex $u$	Unweighted Neighbor List	Weighted Neighbor List (`(Neighbor, Weight)`)	Neighbor Iteration Complexity
$0$	`[1, 2]`	`[(1, 10), (2, 25)]`	$Θ (de g (0)) = Θ (2)$
$1$	`[0, 3]`	`[(0, 10), (3, 14)]`	$Θ (de g (1)) = Θ (2)$
$2$	`[0, 3]`	`[(0, 25), (3, 30)]`	$Θ (de g (2)) = Θ (2)$
$3$	`[1, 2]`	`[(1, 14), (2, 30)]`	$Θ (de g (3)) = Θ (2)$

Engineering Rule: In production software, prefer dynamic contiguous arrays (std::vector in C++, dynamic arrays in TypeScript/Java) over linked list nodes. Linked list nodes incur heavy memory fragmentation and CPU cache misses during traversal.

5. Architecture 3: Edge List

An Edge List represents a graph as a flat array of edge records:

typescript

export interface Edge<T> {
  u: number;
  v: number;
  weight: T;
}

export const sampleEdgeList: Edge<number>[] = [
  { u: 0, v: 1, weight: 10 },
  { u: 0, v: 2, weight: 25 },
  { u: 1, v: 3, weight: 14 },
  { u: 2, v: 3, weight: 30 },
];

Trade-offs: Consumes minimal memory ( $Θ (E)$ ). Highly optimal for global edge-sorting algorithms (Kruskal's MST, Bellman-Ford), but inefficient for neighbor queries ( $Θ (E)$ linear scan).

6. Architecture 4: Compressed Sparse Row (CSR) in HPC & AI

⚙️

Hardware Bottleneck of Standard Adjacency Lists

In standard vector<vector<int>> adjacency lists, each inner vector represents an independent heap allocation scattered across RAM. Traversing neighbors induces severe pointer-chasing and CPU cache invalidations, crippling GPU memory throughput.

⚙️

The CSR Solution: Zero Pointers, Flat Memory

Compressed Sparse Row (CSR) packs the entire graph into three contiguous 1D arrays:

row_ptr[]: Array of length $∣ V ∣ + 1$ storing index offsets into col_ind where each vertex's neighbor list begins.
col_ind[]: Flat array of length $∣ E ∣$ containing the destination neighbor IDs.
values[]: Flat array of length $∣ E ∣$ containing edge weights.

Sample CSR Representation

Consider a directed graph with 3 vertices and 4 directed edges:

$0 \to 1$ ( $w = 5$ )
$0 \to 2$ ( $w = 8$ )
$1 \to 2$ ( $w = 3$ )
$2 \to 0$ ( $w = 9$ )

Array	Stored Primitive Values	Array Length	Semantic Meaning
`row_ptr`	`[0, 2, 3, 4]`	$∣ V ∣ + 1 = 4$	Vertex $0$ starts at idx $0$ ; Vertex $1$ starts at idx $2$ ; Vertex $2$ starts at idx $3$ ; Total edges $= 4$ .
`col_ind`	`[1, 2, 2, 0]`	$∣ E ∣ = 4$	Destination vertices for all outgoing edges in sequential row order.
`values`	`[5, 8, 3, 9]`	$∣ E ∣ = 4$	Numerical edge weights corresponding directly to `col_ind`.

Neighbor Slice Extraction in CSR

The outgoing neighbors of vertex $u$ reside in the contiguous array slice:

col_ind [row_ptr [u] \dots row_ptr [u + 1] - 1]

de g^{+} (u) = row_ptr [u + 1] - row_ptr [u] in strictly O (1) time!

7. Step-by-Step Dry Run State Trace: Building CSR from Edge List

Consider converting directed edge list $E = [(0, 1, 5), (0, 2, 8), (1, 2, 3), (2, 0, 9)]$ for $V = 3$ into a CSR structure:

Step	Operation	Intermediate Data Structure State	Explanation
1	Count Out-Degrees	$degree = [2, 1, 1]$	Vertex $0$ has 2 edges; Vertex $1$ has 1 edge; Vertex $2$ has 1 edge.
2	Compute Prefix Sums for `row_ptr`	$row_ptr = [0, 0 + 2, 2 + 1, 3 + 1] = [0, 2, 3, 4]$	Computes starting index offsets into `col_ind` for each vertex.
3	Populate Edge $(0, 1, 5)$	`col_ind[0] = 1`, `values[0] = 5`	First edge of vertex $0$ placed at index offset $0$ .
4	Populate Edge $(0, 2, 8)$	`col_ind[1] = 2`, `values[1] = 8`	Second edge of vertex $0$ placed at index offset $1$ .
5	Populate Edge $(1, 2, 3)$	`col_ind[2] = 2`, `values[2] = 3`	Edge of vertex $1$ placed at index offset $2$ .
6	Populate Edge $(2, 0, 9)$	`col_ind[3] = 0`, `values[3] = 9`	Edge of vertex $2$ placed at index offset $3$ .
Final	Verification	`row_ptr = [0, 2, 3, 4]` `col_ind = [1, 2, 2, 0]` `values = [5, 8, 3, 9]`	Construction complete in strictly $O (V + E)$ time!

8. Complete Implementation: CSR Graph Query Engine

typescript

export class CSRGraph {
  public readonly numVertices: number;
  public readonly numEdges: number;
  public readonly rowPtr: Int32Array;
  public readonly colInd: Int32Array;
  public readonly values: Float64Array;

  constructor(
    numVertices: number,
    edges: { u: number; v: number; weight: number }[]
  ) {
    this.numVertices = numVertices;
    this.numEdges = edges.length;

    this.rowPtr = new Int32Array(numVertices + 1);
    this.colInd = new Int32Array(this.numEdges);
    this.values = new Float64Array(this.numEdges);

    // Step 1: Count out-degrees
    for (const edge of edges) {
      this.rowPtr[edge.u + 1]++;
    }

    // Step 2: Compute prefix sums
    for (let i = 0; i < numVertices; i++) {
      this.rowPtr[i + 1] += this.rowPtr[i];
    }

    // Step 3: Fill colInd and values
    const currentOffset = new Int32Array(this.rowPtr);
    for (const edge of edges) {
      const idx = currentOffset[edge.u]++;
      this.colInd[idx] = edge.v;
      this.values[idx] = edge.weight;
    }
  }

  public getDegree(u: number): number {
    return this.rowPtr[u + 1] - this.rowPtr[u];
  }

  public getNeighbors(u: number): { neighbor: number; weight: number }[] {
    const start = this.rowPtr[u];
    const end = this.rowPtr[u + 1];
    const result = [];

    for (let i = start; i < end; i++) {
      result.push({ neighbor: this.colInd[i], weight: this.values[i] });
    }

    return result;
  }
}

9. Master Storage Benchmark & Hardware Cache Analysis

Metric / Operation	Adjacency Matrix	Adjacency List (Dynamic Arrays)	Edge List	Compressed Sparse Row (CSR)
Total Memory Space	$Θ (V^{2})$	$Θ (V + E)$	$Θ (E)$	$Θ (V + E)$ (Zero pointers)
Check Edge $(u, v)$	$O (1)$	$O (de g (u))$	$O (E)$	$O (lo g (de g (u)))$ (via binary search)
Iterate Neighbors of $u$	$Θ (V)$	$Θ (de g (u))$	$Θ (E)$	$Θ (de g (u))$ (Contiguous slice)
Add an Edge	$O (1)$	$O (1)$ amortized	$O (1)$	$O (E)$ (Requires array shift; static)
CPU Cache Efficiency	Moderate	Good (vectors) / Poor (pointers)	Excellent (flat scan)	OPTIMAL (Hardware SIMD & Prefetch)
Primary Industry Role	Dense graphs, all-pairs shortest paths	Standard application software, dynamic graphs	Global edge processing (Kruskal, Bellman)	GraphBLAS, HPC, PyTorch Geometric, GNNs

10. Common Traps, Edge Cases & Implementation Pitfalls

Allocating Matrix for Sparse Graphs:
- Creating a $100, 000 \times 100, 000$ 32-bit integer matrix consumes $\approx 40 GB$ of RAM and triggers an immediate Out-Of-Memory (OOM) crash. Always check the sparsity threshold ( $∣ E ∣ ≪ ∣ V ∣^{2}$ ) before selecting matrix storage.
CSR Immutability:
- CSR is an immutable (or static) structure. Dynamically inserting an edge requires shifting all subsequent entries in col_ind and values, costing $O (E)$ time. For dynamic workloads, build with an Adjacency List and compile to CSR once topology stabilizes.
Double Counting in Undirected Edge Lists:
- In undirected graphs, each undirected edge ${u, v}$ must either be stored once as a single pair or twice as $(u, v)$ and $(v, u)$ depending on the algorithm's contract. Mixing conventions causes duplicate iterations in Kruskal's or Prim's routines.

11. References & Academic Attribution

Saad, Y. (2003). Iterative Methods for Sparse Linear Systems (2nd ed.). Society for Industrial and Applied Mathematics (SIAM).
Kepner, J., et al. (2016). Mathematical foundations of the GraphBLAS. IEEE High Performance Extreme Computing Conference (HPEC), 1–9.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 20 (Elementary Graph Algorithms). MIT Press.