Skip to main content
Topological sorting orders nodes in a directed acyclic graph (DAG) such that for every edge from node A to node B, A appears before B in the ordering.

​
getTopologicalSort

function getTopologicalSort<N>(
  graph: Graph<N>
): GraphNode<N>[] | null
Returns a topological ordering of nodes, or null if the graph is cyclic. Complexity: O(V + E) When to use:
  • Build systems (compile dependencies in order)
  • Task scheduling (prerequisite tasks)
  • Package dependency resolution
  • State machine ordering
  • Course prerequisite planning
Algorithm: Uses Kahn’s algorithm (in-degree based BFS)

​
Example

import { createGraph, getTopologicalSort } from '@statelyai/graph';

const graph = createGraph({
  nodes: [{ id: 'a' }, { id: 'b' }, { id: 'c' }],
  edges: [
    { id: 'ab', sourceId: 'a', targetId: 'b' },
    { id: 'bc', sourceId: 'b', targetId: 'c' },
  ],
});

const sorted = getTopologicalSort(graph);
// [nodeA, nodeB, nodeC]

​
Detecting cycles

const sorted = getTopologicalSort(graph);

if (sorted === null) {
  console.error('Graph contains cycles - cannot sort topologically');
} else {
  console.log('Processing order:', sorted.map(n => n.id));
}

​
Use Cases

​
Build system

Determine compilation order for source files with dependencies: 
import { createGraph, getTopologicalSort } from '@statelyai/graph';

const dependencies = createGraph({
  nodes: [
    { id: 'utils.ts' },
    { id: 'types.ts' },
    { id: 'api.ts' },
    { id: 'app.ts' },
  ],
  edges: [
    { id: '1', sourceId: 'types.ts', targetId: 'utils.ts' },
    { id: '2', sourceId: 'types.ts', targetId: 'api.ts' },
    { id: '3', sourceId: 'utils.ts', targetId: 'api.ts' },
    { id: '4', sourceId: 'api.ts', targetId: 'app.ts' },
  ],
});

const buildOrder = getTopologicalSort(dependencies);

if (buildOrder) {
  console.log('Build files in this order:');
  buildOrder.forEach(node => console.log(`  - ${node.id}`));
  // types.ts -> utils.ts -> api.ts -> app.ts
} else {
  console.error('Circular dependency detected!');
}

​
Task scheduling

Schedule tasks respecting prerequisites: 
const tasks = createGraph({
  nodes: [
    { id: 'design', data: { duration: 2 } },
    { id: 'implement', data: { duration: 5 } },
    { id: 'test', data: { duration: 3 } },
    { id: 'deploy', data: { duration: 1 } },
  ],
  edges: [
    { id: '1', sourceId: 'design', targetId: 'implement' },
    { id: '2', sourceId: 'implement', targetId: 'test' },
    { id: '3', sourceId: 'test', targetId: 'deploy' },
  ],
});

const schedule = getTopologicalSort(tasks);

if (schedule) {
  let currentDay = 0;
  schedule.forEach(task => {
    console.log(`Day ${currentDay}: Start ${task.id}`);
    currentDay += task.data.duration;
  });
}

​
Course prerequisites

Determine valid course ordering: 
const courses = createGraph({
  nodes: [
    { id: 'CS101', data: { name: 'Intro to CS' } },
    { id: 'CS201', data: { name: 'Data Structures' } },
    { id: 'CS301', data: { name: 'Algorithms' } },
    { id: 'CS401', data: { name: 'Advanced Algorithms' } },
  ],
  edges: [
    { id: '1', sourceId: 'CS101', targetId: 'CS201' },
    { id: '2', sourceId: 'CS201', targetId: 'CS301' },
    { id: '3', sourceId: 'CS301', targetId: 'CS401' },
  ],
});

const order = getTopologicalSort(courses);

if (order) {
  console.log('Take courses in this order:');
  order.forEach((course, i) => {
    console.log(`${i + 1}. ${course.id}: ${course.data.name}`);
  });
}

​
Package manager

Resolve installation order for package dependencies: 
const packages = createGraph({
  nodes: [
    { id: 'lodash' },
    { id: 'react' },
    { id: 'react-dom' },
    { id: 'my-app' },
  ],
  edges: [
    { id: '1', sourceId: 'react', targetId: 'react-dom' },
    { id: '2', sourceId: 'react', targetId: 'my-app' },
    { id: '3', sourceId: 'react-dom', targetId: 'my-app' },
    { id: '4', sourceId: 'lodash', targetId: 'my-app' },
  ],
});

const installOrder = getTopologicalSort(packages);

if (installOrder) {
  console.log('Install packages in this order:');
  installOrder.forEach(pkg => console.log(`  npm install ${pkg.id}`));
} else {
  console.error('Circular dependency detected in packages!');
}

​
Properties

​
Multiple valid orderings

A DAG can have multiple valid topological orderings: 
const graph = createGraph({
  nodes: [{ id: 'a' }, { id: 'b' }, { id: 'c' }],
  edges: [
    { id: 'ab', sourceId: 'a', targetId: 'c' },
    { id: 'bc', sourceId: 'b', targetId: 'c' },
  ],
});

const sorted = getTopologicalSort(graph);
// Could be [a, b, c] or [b, a, c] - both are valid

​
DAGs only

Topological sorting only works on directed acyclic graphs: 
// This has a cycle: a -> b -> a
const cyclic = createGraph({
  nodes: [{ id: 'a' }, { id: 'b' }],
  edges: [
    { id: 'ab', sourceId: 'a', targetId: 'b' },
    { id: 'ba', sourceId: 'b', targetId: 'a' },
  ],
});

getTopologicalSort(cyclic); // null (cycle detected)

​
Reverse postorder

Topological sort is equivalent to the reverse of DFS postorder on a DAG: 
import { getTopologicalSort, getPostorder } from '@statelyai/graph';

const topo = getTopologicalSort(graph);
const post = getPostorder(graph);

// topo ≈ post.reverse() for DAGs