Graph Representations: Adjacency Lists, Bit Matrices & Compressed Sparse Row (CSR)

The Three Canonical Graph Layouts

Given a directed or undirected graph $G = (V, E)$ with $|V| = n$ vertices and $|E| = m$ edges, an algorithm interacts with the graph through three primary operations: testing edge existence $\text{hasEdge}(u, v)$, enumerating incident edges $\text{neighbors}(u)$, and mutating topology $\text{addEdge}(u, v)$. No single memory layout optimizes all three simultaneously.

1. Vector-of-Vectors Adjacency List vs. Linked-Star Forward Star

In naive C++ or Java implementations, developers represent graphs as vector<vector<Edge>> adj(n). While convenient for incremental push_back mutations, this layout incurs two levels of indirection: first indexing the outer spine array to load a 24-byte std::vector control block (pointer, size, capacity), and second dereferencing its heap pointer into a fragmented allocator arena. When $n = 10^6$ and average degree is 4, allocator metadata and geometric overallocation waste over $60\%$ of RAM.

When dynamic edge insertion is required without sorting, competitive programmers and high-performance solvers use the Adjacency Forward Star (array-backed intrusive singly linked list): three flat arrays head[V], to[E], and next[E]. Adding edge $e = (u, v)$ sets to[e] = v; next[e] = head[u]; head[u] = e; in $O(1)$ worst-case time with zero heap allocations after initial reservation.

2. Compressed Sparse Row (CSR) Construction via Prefix Sums

When the edge list is known upfront (or ingested in batches), CSR eliminates even the next[E] pointer array of the forward star. Construction proceeds in two linear passes over the raw edge buffer:

1. Degree Histogram & Exclusive Prefix Sum: Count the out-degree of each vertex $u$ in $\text{head}[u+1]$, then compute the cumulative sum $\text{head}[i] = \sum_{k=0}^{i-1} \text{deg}(k)$.
2. Scatter Pass: Copy $\text{head}$ into a temporary cursor array $\text{cur}[0 \dots n-1]$. For each edge $(u, v)$, write $\text{to}[\text{cur}[u]++] = v$.

3. Word-Packed Bitset Adjacency Matrices

For dense graphs ($E = \Theta(V^2)$) or transitive closure / triangle counting on medium-sized graphs ($V \le 5000$), a boolean byte matrix wastes $7/8$ of every byte. Packing 64 edges into each uint64_t word reduces memory to $V^2 / 8$ bytes (just $3.1\text{ MB}$ for $V = 5000$) and unlocks word-level parallelism ($O(V / w)$ where $w = 64$):

• Common Neighbors / Triangle Counting: The number of common neighbors of $u$ and $v$ is $\sum_{k=0}^{\lceil V/64 \rceil - 1} \text{popcount}(\text{row}[u][k] \,\&\, \text{row}[v][k])$, executing 64 vertex intersections per single POPCNT instruction.
• Bitset BFS / Unvisited Neighbor Discovery: Maintaining a bitset unvisited of remaining vertices allows BFS from $u$ to find and clear all unvisited neighbors in $O(V / 64)$ via mask = row[u][k] & unvisited[k] and iterating set bits with __builtin_ctzll(mask), reducing dense BFS from $O(V^2)$ to $O(V^2 / 64)$.

Asymptotic & Hardware Complexity Matrix

Production Implementation: CSR Graph & Bitset Intersection

#include <vector>
#include <cstdint>
#include <utility>

struct CSRGraph {
    int n, m;
    std::vector<int> head;
    std::vector<int> to;

    CSRGraph(int vertices, const std::vector<std::pair<int, int>>& edges)
        : n(vertices), m(static_cast<int>(edges.size())), head(vertices + 1, 0), to(edges.size()) {
        for (const auto& [u, v] : edges) {
            ++head[u + 1];
        }
        for (int i = 1; i <= n; ++i) {
            head[i] += head[i - 1];
        }
        std::vector<int> cursor(head.begin(), head.end() - 1);
        for (const auto& [u, v] : edges) {
            to[cursor[u]++] = v;
        }
    }

    struct NeighborRange {
        const int* b;
        const int* e;
        const int* begin() const noexcept { return b; }
        const int* end() const noexcept { return e; }
    };

    NeighborRange neighbors(int u) const noexcept {
        return {to.data() + head[u], to.data() + head[u + 1]};
    }
};

// Triangle counting on a 64-bit word-packed bitset adjacency matrix in O(V^3 / 64)
uint64_t countTrianglesBitset(int n, const std::vector<std::vector<uint64_t>>& adjBits) {
    const int words = (n + 63) / 64;
    uint64_t total = 0;
    for (int u = 0; u < n; ++u) {
        for (int v = u + 1; v < n; ++v) {
            if ((adjBits[u][v >> 6] >> (v & 63)) & 1ULL) {
                for (int w = 0; w < words; ++w) {
                    total += __builtin_popcountll(adjBits[u][w] & adjBits[v][w]);
                }
            }
        }
    }
    return total / 3;
}