What is topological sort ?
- We need to schedule a series of tasks, such as classes or construction jobs, where we cannot start one task until after its prerequisites are completed.
- We want to organize such tasks into a linear order that allows us to complete it one at a time, without violating any prerequisites.
- This problem can be modeled with DAG, directed acyclic graph
- Graph is directed since one task is dependent on another, so that means the relation between tasks is directed.
- Acyclic - We cannot have cycles in the graph, since that would mean conflicting series of prerequisite tasks that could not be completed without violating any prerequisites.
- The process of laying out the vertices of a DAG in a linear order to meet the prerequisite rule is called topological sort.
How to do it ?
2 ways to implement a topological sort
- BFS approach (Kahn's algorithm)
- DFS approach
BFS approach:
- In BFS approach we visit every node and find in-degree for each node (in-degree -> no of edges/ how many nodes are connected to that node)
- Finding in-degree in case of DAG is simply loop through all the nodes and increase the in-degree count for each adjacent node by 1.
- We keep the nodes with in-degree 0 into a queue, and start processing the queue.
DFS approach:
- In DFS approach we visit each node and its adjacent nodes, we only push the node to a stack once all the dependencies are visited first, so we naturally we are visiting all the dependencies first and then the node itself, so we end up ordered items naturally.
Working code
BFS approach
const graph = {
7: [11, 8],
5: [11],
3: [10, 8],
11: [2, 9, 10],
8: [9],
2: [],
9: [],
10: [],
};
function toposortBFS(graph) {
const order = [];
const indgree = {};
/*Set indegrees for all node to 0*/
for (let node of Object.keys(graph)) {
indgree[node] = 0;
}
/*Increment in-degrees of all adjacent nodes of all nodes in graph -> get in-degree for all the nodes in a graph*/
for (let node of Object.keys(graph)) {
for (let adjNode of graph[node]) {
/*IMP: (?? 0) is necessary in case of connected components in the graph*/
indgree[adjNode] = (indgree[adjNode] ?? 0) + 1;
}
}
const queue = [];
/*Push all nodes with 0 in-degree to a queue*/
for (let node of Object.keys(indgree)) {
if (indgree[node] === 0) {
queue.push(node);
}
}
/*Process queue such that we keep pushing adj node with 0 in-degree, decrement indegrees of adj node, dequeued elements are in sorted order*/
while (queue.length > 0) {
const currentNode = queue.shift();
order.push(currentNode);
for (let adjNode of graph[currentNode]) {
indgree[adjNode] -= 1;
if (indgree[adjNode] === 0) {
queue.push(adjNode);
}
}
}
/*We need to check if all the items are processed from the graph - if not, we have a cycle in the graph - this could be used to detect cycles as well*/
return order.length === Object.keys(graph).length ? order : [];
}
DFS approach
const graph = {
7:[11,8],
5:[11],
3:[10,8],
11:[2,9,10],
8:[9],
2:[],
9:[],
10:[]
};
function toposortDFS (graph) {
const order = [];
const visited = {};
for (let node of Object.keys(graph)) {
visited[node] = 0;
}
function dfs(node) {
if(visited[node]){ return; }
visited[node] = 1;
for(let adjNode of graph[node]) {
dfs(adjNode);
}
order.push(node);
}
for(let node of Object.keys(graph)) {
if(!visited[node]) {
dfs(node);
}
}
return order.reverse();
}
Applications
- Representing course pre-requisites
- Detecting dead locks
- Pipeline of computing jobs
- Checking for symbolic link loops
- Evaluating formulae in spreadsheets
