English | 中文

@xingwangzhe/bfs-rs

Fast, exact BFS (Breadth-First Search) for large-scale graphs, written in Rust with Rayon parallelism. Uses CSR plus a cached transpose, epoch-stamped visitation, bitset frontiers, and direction-optimising push/pull traversal.

• 16-core parallel bfsAllHistogram: 57K nodes in ~3s
• Single-core auto-fallback: sequential path with zero Rayon overhead
• Histogram-only API: no full distance arrays, O(histogram) memory per source

Installation

npm install @xingwangzhe/bfs-rs

Data Format

Uses CSR (Compressed Sparse Row):

adj     = [1, 2, 0, 2, 0, 1, 3, 2]   // all neighbor IDs flattened
offsets = [0, 2, 4, 7, 8]            // node offset range (length = n + 1)

| Node | Neighbors | | ---- | --------------------- | | 0 | adj[0..2] = [1, 2] | | 1 | adj[2..4] = [0, 2] | | 2 | adj[4..7] = [0, 1, 3] | | 3 | adj[7..8] = [2] |

API

Full Distance API — when you need per-node distances

bfsOne(adj, offsets, n, source)

Single-source BFS, returns distances array.

import { bfsOne } from "@xingwangzhe/bfs-rs";
const r = bfsOne(adj, offsets, n, 0);
// r.distances → [0, 1, 1, 2]
// r.maxDistance → 2
// r.histogram → [2, 1]

bfsBatch(adj, offsets, n, sources)

Parallel BFS from multiple sources.

import { bfsBatch } from "@xingwangzhe/bfs-rs";
const r = bfsBatch(adj, offsets, n, [0, 3]);
// r.processed → 2, r.results → [BfsOneResult, BfsOneResult]

bfsAll(adj, offsets, n)

All-pairs BFS (every node as source).

import { bfsAll } from "@xingwangzhe/bfs-rs";
const r = bfsAll(adj, offsets, n);
// r.results.length === n

bfsPath(adj, offsets, n, source, target)

Shortest path between two nodes. Stops early at target.

import { bfsPath } from "@xingwangzhe/bfs-rs";
const r = bfsPath(adj, offsets, n, 0, 3);
// r.path → [0, 2, 3], r.distance → 2

Histogram-Only API — memory-efficient for large graphs

These return only the distance histogram per source (no full distances array), making them ideal for six-degree / diameter stats on graphs with 50K+ nodes.

bfsOneHistogram / bfsBatchHistogram / bfsAllHistogram

Same usage as above, but result type is BfsHistogramResult:

import { bfsAllHistogram } from "@xingwangzhe/bfs-rs";
const r = bfsAllHistogram(adj, offsets, n);
// r.results[i].histogram → [count_at_dist_1, count_at_dist_2, ...]
// r.results[i].maxDistance → number

Memory per source: ~(diameter × 4) bytes instead of ~(n × 4) bytes.

Prepared typed-array graph

For repeated queries on the same graph, build the transpose and reusable traversal buffers once:

import { createBfsGraph } from "@xingwangzhe/bfs-rs";

const graph = createBfsGraph(new Uint32Array(adj), new Uint32Array(offsets), n);
const one = graph.one(0);
const all = graph.allHistogram();
const merged = graph.mergedHistogram();

The prepared API keeps every result exact. Existing array-based functions remain available for compatibility.

Performance

Single-source traversal switches between top-down push and bottom-up pull when the frontier becomes broad. Visitation stamps avoid clearing an n-element distance array for histogram-only calls; sparse levels do not build bitmaps.

Merged histograms share adjacency visits across 64 exact source traversals and parallelize independent batches with Rayon. Verified undirected graphs can also collapse equal neighbor sets into weighted vertices while preserving all ordered pair counts. Small graphs and graphs with maximum outgoing degree at most two use independent BFSs. The merged histogram retains at least 128 bins and grows when a shortest path exceeds 128 edges.

Runtime depends on graph structure and CPU topology. See performance methodology and reproducible consumer-fixture benchmarks for algorithm details, fallbacks, source references, memory measurement, and PGO selection. No host-specific CPU instruction flags are needed.

Full Example

import { bfsOne, bfsBatch, bfsAll, bfsPath, bfsAllHistogram } from "@xingwangzhe/bfs-rs";

// Graph: 0--1--2, 0--3--4--2
const adj = [1, 3, 0, 2, 1, 4, 0, 4, 2, 3];
const offsets = [0, 2, 4, 6, 8, 10];
const n = 5;

// Full distances
const r1 = bfsOne(adj, offsets, n, 0);
console.log(r1.distances); // [0, 1, 2, 1, 2]

// Shortest path
const r2 = bfsPath(adj, offsets, n, 0, 4);
console.log(r2.path); // [0, 1, 2, 4] or [0, 3, 4, 2]

// Histogram-only (memory efficient)
const r3 = bfsAllHistogram(adj, offsets, n);
// Aggregate in JS:
const degreeDist = {};
for (const h of r3.results) {
  for (let d = 0; d < h.histogram.length; d++) {
    degreeDist[d + 1] = (degreeDist[d + 1] || 0) + h.histogram[d];
  }
}
// degreeDist[1] = divide by 2 for undirected pair count

License

MIT

Runtime-focused release builds

Native CI artifacts use full LTO, one code-generation unit, and O3, while preserving the existing CPU instruction baseline. CI trains a profile-guided optimization (PGO) candidate using representative graph workloads and publishes it only when the runtime comparison passes; otherwise it publishes the unprofiled release. bun run build:pgo produces the optimized addon; bun run benchmark:pgo compares it with an unprofiled release. Install llvm-tools-preview with the same Rust toolchain first. Details and measurement limits: scripts/PERFORMANCE.md.