dependency-graph

dependency-graph is a small, zero-dependency library for modeling directed graphs of named nodes and the relationships between them. It exposes a single DepGraph class backed by three Map/Set structures — nodes, outgoing edges, and incoming edges — so callers can add nodes with optional associated data, wire up dependency edges between them, and then ask the graph questions: what does this node depend on (directly or transitively), what depends on it, and in what overall order should everything be processed.

The library’s core value is its topological sort implementation: overallOrder() walks the graph and returns nodes in dependency-safe processing order, throwing a DepGraphCycleError (which carries the exact cycle path) if a cycle is detected — unless the graph was constructed with circular: true, in which case cycles are tolerated instead of rejected. Because the traversal is implemented as an iterative depth-first search using an explicit stack rather than recursion, it avoids call-stack overflows on very large or deep graphs, a deliberate rewrite the maintainers made specifically to handle bigger real-world dependency sets.

It’s widely used as an internal building block inside other tools — build systems, module bundlers, task runners, and package managers — anywhere something needs to figure out “what order do these things need to happen in” or “what will break if I change this.”

What You Get

• A DepGraph class for adding nodes (with optional attached data) and wiring directed dependency edges between them
• Transitive queries — dependenciesOf() and dependantsOf() (aliased dependentsOf()) — plus direct-only variants directDependenciesOf()/directDependantsOf()
• overallOrder() for computing a full topological processing order, with a leavesOnly option to return only nodes with no further dependencies
• Automatic cycle detection that throws a DepGraphCycleError carrying the exact cyclePath, or an opt-in circular: true mode that tolerates cycles instead
• clone() for cheaply duplicating a graph (shallow-copying any attached node data), and entryNodes() for finding nodes nothing depends on
• Hand-written TypeScript declarations (lib/index.d.ts) shipped alongside the plain-JS implementation, with zero runtime dependencies

Common Use Cases

• Ordering build/compile steps in a bundler or task runner so each module is processed only after everything it depends on
• Determining safe migration or deployment order for a set of interdependent services or database changes
• Detecting circular dependencies in a module graph or plugin system before they cause runtime errors
• Computing which packages or tasks are affected (transitively) when one node changes, to drive incremental rebuilds
• Modeling any DAG-shaped scheduling problem — job pipelines, workflow steps, or feature-flag prerequisite chains

Under The Hood

Architecture dependency-graph ships as a single CommonJS module (lib/dep_graph.js) exporting a DepGraph constructor built on the classic prototype pattern, plus a DepGraphCycleError subclass of Error. Internally it keeps three parallel Map structures — nodes (name to attached data), outgoingEdges, and incomingEdges (each name to an array of adjacent node names) — so direction-specific queries never have to walk the whole graph. All traversal-based methods (dependenciesOf, dependantsOf, overallOrder, and internal cycle detection) delegate to a single shared closure factory, createDFS, which returns a depth-first-search function parameterized by which edge map to walk, whether to collect only leaf nodes, and whether cycles should be tolerated. Because every traversal path funnels through this one factory, a change to its stack-based algorithm would ripple through every public query method at once — it is the one abstraction the whole library is built around.

Tech Stack The implementation is plain JavaScript (using ES6 Map/Set, a hard requirement introduced in the 1.0.0 rewrite) with zero runtime dependencies, distributed as a CommonJS module with a hand-maintained TypeScript declaration file (lib/index.d.ts, referenced via the types field) rather than a generated one. There is no build/transpilation step — the published package is the source as-is. The only devDependency is the Jasmine test framework, and CI runs via a GitHub Actions workflow (npm ci && npm test) on pushes and pull requests against master.

Code Quality The project ships a genuinely thorough Jasmine test suite (specs/dep_graph_spec.js) covering node and dependency CRUD, direct and transitive dependency/dependant queries with their leavesOnly variants, cloning, overallOrder, entryNodes, and both cycle-throwing and circular-tolerant behavior. Error handling is explicit rather than swallowed: missing nodes throw descriptive Errors, and cycles throw a dedicated DepGraphCycleError carrying the actual cyclePath for debugging. Naming is consistent and self-documenting (addNode/removeNode/hasNode, directDependenciesOf/directDependantsOf with a dependentsOf alias for spelling preference). There is no linter or formatter configuration in the repository, and the implementation itself has no compile-time type safety — type guarantees exist only in the separately maintained .d.ts file consumers see.

What Makes It Unique The library doesn’t do anything algorithmically novel — it’s a standard topological sort over a directed graph — but its refinements are deliberate and documented: the DFS was rewritten from a recursive to an iterative, explicit-stack implementation specifically to avoid stack overflows and quadratic blowup on large, deep dependency graphs, and the optional circular: true mode plus cycle-path-carrying errors reflect lessons learned from real consumers embedding it inside larger tools rather than a from-scratch design exercise.