Skip to content

Commit 2cbe365

Browse files
author
duaraghav8@gmail
committed
Topological sort - Kahn's Algorithm
1 parent b9e3623 commit 2cbe365

File tree

4 files changed

+94
-1
lines changed

4 files changed

+94
-1
lines changed

‎algorithm/category.json

+2-1
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,8 @@
66
"bfs": "BFS",
77
"dijkstra": "Dijkstra",
88
"bellman_ford": "Bellman-Ford",
9-
"floyd_warshall": "Floyd-Warshall"
9+
"floyd_warshall": "Floyd-Warshall",
10+
"topological_sort": "Topological-Sort"
1011
}
1112
},
1213
"search": {

‎algorithm/graph_search/topological_sort/desc.json

+21
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
{
2+
"Topological-Sort": "Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. NOTE: when the graph is represented as an Adjacency Matrix, the Calculation of in-degree Array becomes O(|V|<sup>2</sup>)",
3+
"Applications": [
4+
"Job Scheduling",
5+
"Instruction Scheduling",
6+
"Logic Synthesis",
7+
"Determining the order of compilation tasks to perform in makefiles",
8+
"Data serialization"
9+
],
10+
"Complexity": {
11+
"time": "worst O(|V|+|E|)",
12+
"space": "worst O(|V|)"
13+
},
14+
"References": [
15+
"<a href='http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/'>GeeksForGeeks</a>",
16+
"<a href='http://www.geeksforgeeks.org/topological-sorting/'>GeeksForGeeks</a>"
17+
],
18+
"files": {
19+
"kahn_algorithm": "Performing Topological Sort using Queue Data Structure & an array of In-degrees"
20+
}
21+
}

‎algorithm/graph_search/topological_sort/kahn_algorithm/code.js

+59
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
tracer._pace(100);
2+
tracer._sleep(1000);
3+
4+
(function topologicalSort () {
5+
var inDegrees = Array.apply (null, Array (G.length)).map (Number.prototype.valueOf, 0); //create an Array of G.length number of 0s
6+
var Q = [], iter = 0, i;
7+
8+
tracer._print ('Calculating in-degrees for each Node...');
9+
for (var currNode = 0; currNode < G.length; currNode++) {
10+
for (var currNodeNeighbor = 0; currNodeNeighbor < G.length; currNodeNeighbor++) {
11+
if (G [currNode] [currNodeNeighbor]) {
12+
tracer._print (currNodeNeighbor + ' has an incoming edge from ' + currNode);
13+
tracer._visit (currNodeNeighbor, currNode);
14+
inDegrees [currNodeNeighbor]++;
15+
tracer._leave (currNodeNeighbor, currNode);
16+
}
17+
}
18+
}
19+
tracer._print ('Done. In-Degrees are: [ ' + String (inDegrees) + ' ]');
20+
tracer._print ('');
21+
22+
tracer._print ('Initializing queue with all the sources (nodes with no incoming edges)');
23+
inDegrees.map (function (indegrees, node) {
24+
tracer._visit (node);
25+
if (!indegrees) {
26+
tracer._print (node + ' is a source');
27+
Q.push (node);
28+
}
29+
tracer._leave (node);
30+
});
31+
tracer._print ('Done. Initial State of Queue: [ ' + String (Q) + ' ]');
32+
tracer._print ('');
33+
34+
//begin topological sort (kahn)
35+
while (Q.length > 0) {
36+
tracer._print ('Iteration #' + iter + '. Queue state: [ ' + String (Q) + ' ]');
37+
currNode = Q.shift (1);
38+
tracer._visit (currNode);
39+
40+
for (i = 0; i < G.length; i++) {
41+
if (G [currNode] [i]) {
42+
tracer._print (i + ' has an incoming edge from ' + currNode + '. Decrementing ' + i + '\'s in-degree by 1.');
43+
tracer._visit (i, currNode);
44+
inDegrees [i]--;
45+
tracer._leave (i, currNode);
46+
47+
if (!inDegrees [i]) {
48+
tracer._print (i + '\'s in-degree is now 0. Enqueuing ' + i);
49+
Q.push (i);
50+
}
51+
}
52+
}
53+
tracer._leave (currNode);
54+
tracer._print ('In-degrees are: [' + String (inDegrees) + ' ]');
55+
tracer._print ('-------------------------------------------------------------------');
56+
57+
iter++;
58+
}
59+
}) ();

‎algorithm/graph_search/topological_sort/kahn_algorithm/data.js

+12
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
var tracer = new DirectedGraphTracer ();
2+
// G[i][j] indicates whether the path from the i-th node to the j-th node exists or not. NOTE: The graph must be Directed-Acyclic
3+
var G = [
4+
[0, 0, 0, 0, 0, 0],
5+
[0, 0, 1, 0, 0, 0],
6+
[0, 0, 0, 1, 0, 0],
7+
[0, 0, 0, 0, 0, 0],
8+
[1, 0, 0, 1, 0, 0],
9+
[1, 1, 0, 0, 0, 0]
10+
];
11+
12+
tracer._setData (G);

0 commit comments

Comments
 (0)