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.

• Measured: 2026-06-12 on an Apple M1 Max (10 cores), Node v25.9.0 (darwin/arm64). Library versions: graphology 0.26, ngraph.graph 20.1 / ngraph.path 1.6, @dagrejs/graphlib 4.0, cytoscape 3.34.

• Numbers are medians (milliseconds) of ≥5 runs after warmup, within a 1.5 s sampling budget per cell.

• Machine specifics matter. Reproduce on your own hardware with:

  pnpm bench:compare           # 1k / 10k / 100k nodes
  pnpm bench:compare -- --quick  # 1k / 10k only

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.

Methodology

Source: bench/compare/run.ts, bench/compare/generate.ts, bench/compare/adapters.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).