Resolving Task Dependencies with Topological Sort in JavaScript

Whenever software systems manage task execution order—such as module bundlers resolving ESM imports, package managers installing dependencies, or build pipelines compiling source files—they must resolve dependencies modeled as a Directed Acyclic Graph (DAG).

Topological Sort produces a linear ordering of graph vertices such that for every directed edge (u \to v), vertex (u) precedes vertex (v).

Example #

// Task dependencies: { task: [prerequisites] }
const buildTasks = {
  bundle: ['compile', 'lint'],
  compile: ['lint', 'types'],
  lint: [],
  types: [],
  test: ['bundle']
};

Implementation #

Using Kahn's Algorithm with an in-degree counter:

function topologicalSort(graph) {
  const inDegree = {};
  const adjList = {};

  for (const node of Object.keys(graph)) {
    inDegree[node] = 0;
    adjList[node] = [];
  }

  // Build adjacency list and calculate in-degrees
  for (const [node, prerequisites] of Object.entries(graph)) {
    for (const prereq of prerequisites) {
      adjList[prereq].push(node);
      inDegree[node]++;
    }
  }

  // Queue of nodes with no incoming dependencies
  const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);
  const order = [];

  while (queue.length > 0) {
    const current = queue.shift();
    order.push(current);

    for (const neighbor of adjList[current]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // If order does not contain all nodes, a cycle exists
  if (order.length !== Object.keys(graph).length) {
    throw new Error('Circular dependency detected in graph');
  }

  return order;
}

console.log(topologicalSort(buildTasks)); // ['lint', 'types', 'compile', 'bundle', 'test']

Main Point: Kahn's Algorithm resolves DAG execution orders in (O(V + E)) time and reliably detects cyclic dependency deadlocks.

Credits #

Photo by Simone Hutsch on Unsplash

← Home