Matrix Layer

The matrix layer adds two dense representations on top of the existing vertex/edge sets:

• an adjacency matrix that stores reachability in a V x V grid
• an incidence matrix that stores edge direction in a V x E grid (-1 at the source, +1 at the target, 1/1 for undirected edges)

The set-based structures remain untouched and continue to be the source of truth for mutations, serialization, and custom extensions. The matrices exist purely as an optional acceleration layer for read-heavy workloads such as traversals and connectivity checks.

Why matrices exist

Adjacency sets are optimal for sparse graphs because they only store existing edges, but repeated lookups require pointer chasing through Set instances. Dense graphs (thousands of vertices with high degrees) spend more time traversing Set objects than processing results. The dense matrix representation trades memory for predictable access:

• constant-time membership checks for any (i, j) pair
• cache-friendly iteration across rows/columns
• direct column slicing for incidence-driven algorithms such as strongly connected components or flow preparation

When useMatrixLayer is enabled, the graph keeps the matrices in sync with every mutation (addVertex, addEdge, removals, and clear). Algorithms such as BFS, DFS, Dijkstra, topological sort, and the connected-components routines automatically route through the matrices when present.

Why matrices win on dense graphs

On dense graphs the matrix layer now wins consistently:

• BFS on 1k/4k/8k fixtures is up to ~70× faster than the set-based variant (see test/benchmarks/matrix-vs-sets.benchmark.ts).
• Dijkstra runs ∼3–10× faster because each relaxation is pure array math instead of iterating Set objects.
• SCC benefits from column scans on the incidence matrix, yielding ~5× speedups even on mid-sized graphs.

Prefer the set-based representation when the graph is sparse, the workload is mutation-heavy, or the environment is too memory-constrained for a V × V adjacency grid. Benchmark representative data before choosing either representation.

Complexity surface

Operation	Set-based structure	Matrix layer
BFS / DFS	O(V + E) but incurs iterator overhead for each outgoing edge	O(V^2) worst-case, but constant-time row scans and predictable cache access benefit dense graphs
Dijkstra	O((V + E) log V) with heap, but each relax scans outgoing sets	O(V^2 log V) for dense matrices yet with faster neighbor reads
Topological sort	O(V + E) with neighbor set iteration	O(V^2) indegree updates without touching vertex objects
Strongly connected components	O(V * (V + E)) with repeated DFS	O(V^3) upper bound but avoids Set allocations and benefits from column slicing

In practice, dense graphs reach break-even quickly because scanning a tight matrix row is cheaper than iterating hundreds of Set handles spread across memory.

Enabling and disabling

import { Graph } from '@avensio/graph'
import { comparator } from './factories/graph'

// Matrix layer turned on
const denseGraph = new Graph({ useMatrixLayer: true }, comparator)

// Matrix layer off (default)
const sparseGraph = new Graph({}, comparator)

Algorithms automatically detect the layer. No additional API calls are required.

Dual-structure diagram

           +-------------------------+
           |        Graph API        |
           +-------------------------+
                     |   |
     +---------------+   +----------------+
     |                                   |
Adjacency/edge sets               Matrix layer
(Vertex.outgoingEdges,            + AdjacencyMatrix
 Vertex.incomingEdges)            + IncidenceMatrix

Both arms stay live: writes go through the set structures, while reads can draw from the matrices once enabled.