bmssp

Install

npm install bmssp

The package is ESM-only. Graphs are arrays of [from, to, weight] edges with finite numeric node IDs and finite, non-negative weights — or, equivalently, an adjacency Map/object or a Graph builder (see below).

Quick start

import { BMSSP } from "bmssp";

const graph = new BMSSP([
  [0, 1, 50],
  [1, 2, 75],
  [0, 2, 25],
]);

graph.calculateShortestPaths(0);
graph.shortestPaths;      // Map(3) { 0 => 0, 1 => 50, 2 => 25 }
graph.reconstructPath(1); // [0, 1]

Public API

The package has exactly four exports: BMSSP, Graph, dijkstra, and constantDegreeTransform. This surface is stable since 2.0.0 (3.0.0 removed only the little-used graph/adjacency instance fields — use getEdges(id) instead) — see the migration note and the runnable examples gallery. Anything not listed here (the block list, the indexed heap, BaseCase/FindPivots, and the BMSSP class's dense-index engine members) is internal and may change in a minor release.

new BMSSP(input)

Accepts any of four input shapes and reduces them to a canonical graph: an array of [from, to, weight] edges, an adjacency Map (Map<from, [[to, weight], …]>), a plain adjacency object ({ from: [[to, weight], …] }, numeric-string keys coerced to numbers), or a Graph builder instance. Node IDs must be finite numbers and weights finite and non-negative; malformed edges throw an Error identifying the offending index. An empty graph in any shape is valid (it then has no nodes, so any start node is rejected later).

new Graph()

A small mutable input builder. addVertex(id) declares a vertex — including an isolated one (present but with no incident edges), which a bare edge list can't express — and addEdge(from, to, weight) adds a directed weighted edge, auto-declaring its endpoints. Both validate eagerly and chain; pass the instance to new BMSSP(graph).

import { BMSSP, Graph } from "bmssp";

const g = new Graph()
  .addEdge(0, 1, 50)
  .addEdge(0, 2, 25)
  .addVertex(9); // an isolated vertex — present, but unreachable

const graph = new BMSSP(g);
graph.calculateShortestPaths(0);
graph.shortestPaths.get(9); // Infinity

graph.calculateShortestPaths(source)

Computes shortest distances from source via the paper's method (FindPivots → block list → recursive BMSSP with the bounded base case — not by calling Dijkstra). Throws if source is not a node of the graph. Results land in graph.shortestPaths, a Map<nodeId, distance> holding a value for every node — Infinity where unreachable. Distances and predecessor pointers are canonical: deterministic regardless of edge-list order, even with ties and zero-weight edges. Calling it again with a different source resets state and recomputes.

graph.calculateShortestPathsFrom(sources, { bound })

The paper's multi-source, bounded generalization as public API: runs from a set of sources, each with an initial distance, optionally under a strict distance bound B. sources accepts a Map<id, dist>, an object { id: dist }, an array of [id, dist] pairs, or a bare array of ids (each seeded at distance 0). Single-source SSSP is the special case calculateShortestPathsFrom([start]). Results land in shortestPaths exactly like calculateShortestPaths. Under a finite bound, only the completed set — vertices with distance < B — is exposed; BMSSP's above-B over-estimates are pruned to Infinity. bound defaults to Infinity.

const g = new BMSSP([[0, 1, 2], [1, 2, 3], [5, 2, 1]]);

g.calculateShortestPathsFrom([0, 5]);          // nearest of two sources
g.shortestPaths.get(2);                         // 1  (via 5 -> 2)

g.calculateShortestPathsFrom([0], { bound: 4 }); // bounded
g.shortestPaths.get(2);                         // Infinity  (distance 5 ≥ 4)

graph.reconstructPath(target)

Returns the canonical shortest path from the most recent source to target as an array of node IDs ([source, …, target]). Returns [] when target is unreachable or no run has completed yet; throws for a node that is not in the graph.

dijkstra(graph, nodeIDs, source)

The reference Dijkstra implementation used as the test suite's ground-truth oracle, exported for comparison and independent checking. Takes the raw edge array, a Set of node IDs, and a source; returns a Map<nodeId, distance> (Infinity if unreachable).

constantDegreeTransform(graph)

Opt-in preprocessing that rewrites any graph so every vertex has in-degree and out-degree ≤ 2 (the paper's preliminary assumption) by splitting each vertex into a zero-weight cycle of “port” copies. Distance-preserving and never required for correctness — BMSSP is validated on arbitrary graphs. Returns { edges, copiesOf, originalOf, sourceCopy, collapse }:

import { BMSSP, constantDegreeTransform } from "bmssp";

const t = constantDegreeTransform([
  [0, 1, 50],
  [0, 2, 25],
  [1, 2, 75],
]);

const g = new BMSSP(t.edges);              // in/out-degree ≤ 2 everywhere
g.calculateShortestPaths(t.sourceCopy(0)); // start from a copy of node 0
t.collapse(g.shortestPaths);               // Map(3) { 0 => 0, 1 => 50, 2 => 25 }

Correctness & performance

Every release is validated node-by-node against the Dijkstra oracle on thousands of seeded graphs (up to 2 million nodes). The paper's win is asymptotic: measured head-to-head, Dijkstra still wins wall-clock at practical sizes (the dense-index engine narrowed the sparse gap to ~1.4×), but in the paper's own metric — comparisons between path lengths — this implementation does fewer comparisons than Dijkstra from well under n = 50k on sparse graphs. See benchmarks/HEAD-TO-HEAD.md for the data and methodology.