toposort

toposort is a small, dependency-free JavaScript library for topologically sorting directed acyclic graphs (DAGs). Given a list of edges describing relationships between arbitrary nodes, it returns those nodes ordered so that every prerequisite appears before the thing that depends on it — the classic problem behind build systems, package managers, and task runners.

The API is deliberately minimal: a single function that takes an edge list and returns a sorted array, plus a toposort.array() variant for including nodes that aren’t connected to anything. It detects cycles and unknown nodes at runtime and throws descriptive errors rather than silently returning bad output, which makes it a safe building block to drop into larger dependency-resolution or task-ordering systems.

What You Get

• A single default export function that sorts an edge list into dependency order
• A toposort.array() convenience method for including isolated, unconnected nodes in the result
• Cycle detection that throws a descriptive error identifying the offending node
• Unknown-node validation that fails fast instead of producing a partial or silently wrong result
• Zero runtime dependencies and a tiny (~2KB) source footprint

Common Use Cases

• Ordering build or task-runner steps so each step’s dependencies run before it does
• Resolving module or package load order from a declared dependency graph
• Sequencing database migrations that reference each other’s schema objects
• Determining a safe processing or deletion order for records with foreign-key-style relationships

Under The Hood

Architecture The entire library is a single file, index.js (~90 lines), exporting one function plus a .array() variant. Internally it builds two lookup structures from the input edges — a Map of outgoing edges per node and a Map from node to its index — then runs a depth-first traversal (visit) over each unvisited node, writing results into a pre-sized array from the end (cursor decrements on each write) so the final array comes out in topological order without a separate reverse step. Cycle detection rides along in the same traversal via a predecessors Set passed down the recursion, so a node revisited within its own ancestor chain throws immediately. There’s no internal layering beyond this one function — appropriate for a single-purpose algorithm library, and the whole call graph is traceable in one read.

Tech Stack Plain, dependency-free JavaScript using CommonJS (module.exports) and ES6 Set/Map, with no build step, bundler, or transpilation. The only devDependency is vows (a legacy BDD-style test framework), and tests run via node test.js directly. A .travis.yml config indicates it once ran on Travis CI, and a component.json file shows it was also historically published for Component.js, a now-defunct browser package format from the early-2010s JS ecosystem.

Code Quality The test suite (test.js, via vows) covers the two behaviors that matter most for a sorting algorithm — correct ordering of an acyclic graph (checked against a list of valid permutations, since topological order isn’t unique) and correct throwing on a cyclic graph — though coverage is limited to a handful of cases rather than being extensive. Error handling is explicit: cycles and unknown nodes throw Error objects with descriptive messages rather than failing silently. There are no TypeScript types, no linter/formatter configuration, and no active CI (the Travis badge points at a service that has since shut down for open-source projects), so quality signals rely on the small test suite and the code’s own simplicity rather than tooling.

What Makes It Unique Topological sorting is a well-known, textbook graph algorithm, and this library doesn’t attempt anything novel algorithmically — its value is being a minimal, well-tested, dependency-free reference implementation with a very small API surface (one function, one convenience variant) rather than a general-purpose graph library with traversal, weighting, or visualization features.