Search algorithmsCTRL K
In what order does npm install?
· a dependency graph sorted topologically, cycles caught/signatures/npm-install-orderbuilt on Topological sortPACKAGES
15
nodes of the graphDEPENDENCY LINKS
21
edges, package → dependencyINSTALLED
0/ 15
in topological orderQUEUE
0
ready, waiting for nothingCYCLE
—
what stops the installready (in the queue)installinginstalledstuck in a cycle15 packages · 21 links · 18 steps
step 0 / 17
PACKAGE.JSON, ONE PER LINEname: dep, dep
npm
> npm install
resolving 15 packages, 21 dependency links
CURRENT STEPqueue: ∅
15 packages, 21 dependency links. Each package's in-degree is the number of dependencies still not installed.
In what order does npm install?
A package can only be installed after everything it depends on, so the dependency graph has to be walked in topological order. Kahn's algorithm counts the dependencies of each package, starts with the ones that have none, and every time a package is installed it lowers the count of the packages that were waiting for it; whoever reaches zero joins the queue.
If the queue empties before every package is installed, the ones left form a cycle: each is waiting for another. Package managers, build systems (make, Gradle), task schedulers and spreadsheet recalculation all run this same algorithm; a cycle is the error they report.
What to notice
Several valid orders exist: the queue order decides which; npm also parallelises everything in the queue at once.
The in-degree label on each package is its unmet dependencies; it only goes down.
A single cycle edge is enough to strand every package downstream of it.