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

| Platform | 57K nodes × 179K edges | Notes | |------------|----------------------|---------------------------| | 16-core | ~3s | Rayon par_iter across 16 threads | | 1-core | ~70s | auto-fallback to iter |

The 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, and merged histograms use worker-local counters before reduction.

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