Benchmarks

Cross-library comparison of @statelyai/graph against graphology, ngraph, @dagrejs/graphlib, and cytoscape (headless) on seven workloads: graph construction, BFS reachability, single-pair shortest path, PageRank, connected components, betweenness centrality, and a full degree sweep.

Machine specifics matter — the absolute numbers below are from one machine on one day. Reproduce them on your own hardware with the commands in Reproduce these results; the tables in this file are generated from that run's JSON, not hand-written.

• Measured: 2026-06-12 on Apple M1 Max (10 cores), node v25.9.0 (darwin/arm64). Library versions: graphology 0.26.0, ngraph 20.1.2, @dagrejs/graphlib 4.0.1, cytoscape 3.34.0.
• Numbers are medians (milliseconds) of ≥5 runs after warmup, within a 1.5 s sampling budget per cell.

Cell legend: bold = fastest for that row; (n.n×) = multiple of the fastest; — = the library has no equivalent API; >10s = skipped after a prior run exceeded 10 s; crash = the library threw (the error is recorded in the JSON results).

Sub-millisecond caveat: cells under ~0.1 ms (notably scaleFree traversals, which reach few nodes from the start node) are dominated by call overhead. Treat their ratios as noise, in either direction.

Build

Construct the graph from an identical node/edge list.

BFS

Full directed reachability sweep from node 0. Libraries without a built-in traversal get a minimal queue loop over their neighbor API.

The scaleFree rows are sub-millisecond for everyone (few nodes are reachable from node 0); their ratios are noise.

Single-pair shortest path (sssp)

Weighted shortest path from node 0 to node n−1. @statelyai/graph uses getShortestPath (bidirectional Dijkstra); graphology uses dijkstra.bidirectional; ngraph uses ngraph.path A*. graphlib's only shortest-path API is full single-source Dijkstra, so its cell pays the all-targets cost — that is the cost a graphlib user pays for one query.

graphology wins the scaleFree rows; on those graphs node n−1 is typically unreachable from node 0 and the search terminates almost immediately, so the cells are sub-millisecond for both bidirectional implementations.

PageRank

ngraph and graphlib have no PageRank. cytoscape's PageRank threw Invalid array length on three of the four 100k graphs.

Connected components

graphlib's alg.components uses recursive DFS and overflowed the call stack (Maximum call stack size exceeded) at 10,000 nodes on the random, grid, and layeredDag graphs, and at 100,000 on scaleFree. Where it survived, it was 17–50× slower; the remaining 100k cells were skipped after exceeding 10 s.

Betweenness centrality

Run only at n=1,000 — Brandes is O(V·E) for every library, so larger sizes are capped for everyone.

Degree sweep

Sum the degree of every node via each library's degree API.

Reading the numbers

Where @statelyai/graph is fastest:

• Build — fastest in every cell, 1.5–87× ahead. Plain-object graphs with lazy WeakMap indexing have very little construction overhead.
• BFS — fastest on every non-degenerate row, 4–15× ahead of the next library at 10k–100k.
• Connected components — fastest in every cell, 7–85× ahead of graphology (the next-fastest with the API).
• Single-pair shortest path — fastest on every row where the search does real work; bidirectional Dijkstra is why random 100,000 completes in 0.93 ms while full single-source Dijkstra (graphlib) takes 501 ms.
• PageRank and betweenness — fastest in most cells, but only by 1.2–3.9× over graphology on PageRank (1.5–5.1× on betweenness), and graphology wins grid PageRank at 10,000 (5.3 vs 5.5 ms — effectively a tie). PageRank is at rough parity with graphology at small sizes, pulling ahead 2–4× at 100,000.

Where it is not fastest:

• Degree sweep — now at parity rather than a blowout: with getDegree made O(1), every cell lands within 1.1–2.3× of the fastest, where the previous run was 4–23× behind. ngraph is still the fastest library in 11 of the 12 degree cells (graphology takes random 100,000); @statelyai/graph wins no cell outright, though it now edges out graphology in three of the four 100k cells (scaleFree, grid, layeredDag). If per-node degree queries in a tight loop dominate your workload, ngraph remains the fastest choice — but the gap is now small.
• scaleFree traversal/sssp cells — graphlib posts the fastest BFS times and graphology the fastest sssp times on the scaleFree rows. These cells terminate after touching a handful of nodes and are mostly call overhead, but the raw numbers are what they are.

Other findings worth knowing regardless of which library you pick:

• graphlib's recursive-DFS components overflows the Node call stack at 10,000 nodes on three of the four graph shapes.
• cytoscape's PageRank throws Invalid array length at 100,000 nodes on three of the four shapes; headless cytoscape is generally 2–4 orders of magnitude slower across the board, which is unsurprising — it is a visualization toolkit, not an algorithms library.
• ngraph has no built-in PageRank, components, or betweenness; graphlib has no PageRank or betweenness.

Reproduce these results

Everything needed to reproduce this is in the repo — there are no hidden steps and nothing is installed implicitly. The competitor libraries are ordinary devDependencies, so a single pnpm install at the repo root fetches them alongside the toolchain.

git clone https://github.com/statelyai/graph.git
cd graph
pnpm install            # installs @statelyai/graph's toolchain + every competitor lib

pnpm bench:compare:quick   # 1k + 10k sizes — finishes in a couple of minutes
pnpm bench:compare         # full 1k + 10k + 100k — several minutes, canonical sizes

Custom sizes without editing anything:

BENCH_SIZES=1000,25000 pnpm bench:compare

Each run writes three artifacts and never touches the network:

• bench/compare/results/<date>.json — machine-readable: every cell plus the captured environment (node version, OS/arch, CPU model, core count) and library versions.
• bench/compare/results/<date>.md — a self-contained snapshot table for that run.
• docs/benchmarks.md — the tables in this file are regenerated in place (between the BENCH:TABLES markers). The prose around them is preserved.

To rebuild the tables from an already-recorded JSON without re-running the benchmark (e.g. after editing the surrounding prose):

pnpm bench:report bench/compare/results/2026-06-12.json

Expected runtime (Apple M1 Max, node 24): quick ≈ 1–2 min, full ≈ 4–8 min. Slower machines scale roughly linearly; the 100k PageRank/components cells for cytoscape dominate the tail (cytoscape self-skips after exceeding 10 s).

Note on CI: a GitHub Actions workflow (.github/workflows/bench.yml) runs the quick variant on manual dispatch and uploads the JSON as an artifact. Shared CI runners are noisy and their absolute numbers are not canonical — that workflow exists to prove the harness runs end-to-end from a clean checkout, not to publish timings.

Fairness notes

The benchmark tries hard not to flatter @statelyai/graph. Every adapter (see bench/compare/adapters.ts) builds from the same neutral integer edge list and calls each library through its idiomatic public API — the code a user would actually write, not a hand-tuned port. Where a library has no equivalent API, the cell is — rather than a home-grown reimplementation counted against the competitor. Per-library specifics:

• @statelyai/graph — BFS uses the public bfs generator; sssp uses getShortestPath (bidirectional Dijkstra); PageRank/components/betweenness/degree use their public functions. getDegree is O(1) after the recent index change; the degree-sweep numbers reflect that (and it still does not win the degree sweep).
• graphology — sssp uses dijkstra.bidirectional (a like-for-like single-pair search, its best-case API here). BFS is a minimal queue loop over forEachOutNeighbor because graphology has no built-in directed BFS; that is the same loop a graphology user would write, so it is a fair representation, not a handicap. PageRank and betweenness run with getEdgeWeight: null (unweighted), matching the unweighted call on our side.
• ngraph — sssp uses ngraph.path's A* with an admissible zero heuristic (oriented: true), its idiomatic pathfinder. ngraph ships no PageRank, connected-components, or betweenness, so those cells are —. Its degree sweep reads getLinks(id).size, which counts both directions — the closest public analogue to a degree query.
• @dagrejs/graphlib — its only shortest-path API is full single-source Dijkstra (alg.dijkstra), so the sssp cell pays the all-targets cost. This looks unflattering, but it is exactly what a graphlib user pays for one query — there is no single-pair shortcut to call. Its recursive-DFS alg.components genuinely overflows the stack at 10k+ nodes on most shapes; that is recorded as crash, a real result, not a harness bug. No PageRank or betweenness → —.
• cytoscape (headless) — run in headless: true mode so no rendering is timed. It is a visualization toolkit, not an algorithms library, and its 2–4 orders-of-magnitude slower numbers reflect the overhead of its element/collection model — included for completeness because people do reach for it as a graph library.

Two workloads are deliberately constrained for everyone to keep the comparison honest:

• Betweenness is capped at n=1,000 because Brandes is O(V·E) for every library — running it at 100k would just measure who allocates slightly less, over minutes.
• The sub-millisecond scaleFree traversal/sssp cells are noise: those searches touch a handful of nodes and are dominated by call overhead. The doc flags them explicitly rather than quietly claiming wins or losses there.

If you spot an adapter that misrepresents a library's best idiomatic API, that is a bug worth an issue or PR — the goal is numbers that survive scrutiny.

Methodology

Source: bench/compare/run.ts, bench/compare/generate.ts, bench/compare/adapters.ts, bench/compare/report.ts. Raw output: bench/compare/results/2026-06-12.md and 2026-06-12.json.

• Identical inputs. Seeded generators emit a neutral edge list (integer endpoints, weights); every library builds from the same list. Simple directed graphs only (no parallel edges or self-loops) — the lowest common denominator across libraries.
• Four shapes × three sizes (1,000 / 10,000 / 100,000 nodes):
  • random — uniform random, ~3 edges/node, with a spanning chain so traversals reach most of the graph
  • scaleFree — preferential attachment (k=3); hub-heavy, with most nodes unreachable from node 0
  • grid — square lattice with right/down directed edges
  • layeredDag — layered DAG with local fanout and occasional skip edges (statechart/workflow-like)
• Idiomatic usage. Each library runs through a thin adapter calling its public API the way a user would — no hand-tuned ports. Libraries lacking a built-in BFS get a minimal queue loop over their neighbor API. — means no equivalent API exists.
• Timing. One warmup run, then samples until ≥5 runs or a 1.5 s budget; the table reports the median.
• crash means the library threw during the workload (e.g. stack overflow, Invalid array length); the error message is recorded in the JSON. A crash is treated as a result, not a harness failure.
• >10s means a single run exceeded 10 s, so the workload was skipped for that library at that and larger sizes.
• Fairness notes. graphlib's only shortest-path API is full single-source Dijkstra, so its sssp cells pay the all-targets cost. Betweenness is capped at n=1,000 for every library because Brandes is O(V·E). See Fairness notes above for the full per-library breakdown.