|
| 1 | +/** |
| 2 | + * Author: Adrito Mukherjee |
| 3 | + * Kosaraju's Algorithm implementation in Javascript |
| 4 | + * Kosaraju's Algorithm finds all the connected components in a Directed Acyclic Graph (DAG) |
| 5 | + * It uses Stack data structure to store the Topological Sorted Order of vertices and also Graph data structure |
| 6 | + * |
| 7 | + * Wikipedia: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm |
| 8 | + * |
| 9 | + */ |
| 10 | + |
| 11 | +classKosaraju{ |
| 12 | +constructor(graph){ |
| 13 | +this.connections={} |
| 14 | +this.reverseConnections={} |
| 15 | +this.stronglyConnectedComponents=[] |
| 16 | +for(const[i,j]ofgraph){ |
| 17 | +this.addEdge(i,j) |
| 18 | +} |
| 19 | +this.topoSort() |
| 20 | +returnthis.kosaraju() |
| 21 | +} |
| 22 | + |
| 23 | +addNode(node){ |
| 24 | +// Function to add a node to the graph (connection represented by set) |
| 25 | +this.connections[node]=newSet() |
| 26 | +this.reverseConnections[node]=newSet() |
| 27 | +this.topoSorted=[] |
| 28 | +} |
| 29 | + |
| 30 | +addEdge(node1,node2){ |
| 31 | +// Function to add an edge (adds the node too if they are not present in the graph) |
| 32 | +if(!(node1inthis.connections)||!(node1inthis.reverseConnections)){ |
| 33 | +this.addNode(node1) |
| 34 | +} |
| 35 | +if(!(node2inthis.connections)||!(node2inthis.reverseConnections)){ |
| 36 | +this.addNode(node2) |
| 37 | +} |
| 38 | +this.connections[node1].add(node2) |
| 39 | +this.reverseConnections[node2].add(node1) |
| 40 | +} |
| 41 | + |
| 42 | +dfsTopoSort(node,visited){ |
| 43 | +visited.add(node) |
| 44 | +for(constchildofthis.connections[node]){ |
| 45 | +if(!visited.has(child))this.dfsTopoSort(child,visited) |
| 46 | +} |
| 47 | +this.topoSorted.push(node) |
| 48 | +} |
| 49 | + |
| 50 | +topoSort(){ |
| 51 | +// Function to perform topological sorting |
| 52 | +constvisited=newSet() |
| 53 | +constnodes=Object.keys(this.connections).map((key)=>Number(key)) |
| 54 | +for(constnodeofnodes){ |
| 55 | +if(!visited.has(node))this.dfsTopoSort(node,visited) |
| 56 | +} |
| 57 | +} |
| 58 | + |
| 59 | +dfsKosaraju(node,visited){ |
| 60 | +visited.add(node) |
| 61 | +this.stronglyConnectedComponents[ |
| 62 | +this.stronglyConnectedComponents.length-1 |
| 63 | +].push(node) |
| 64 | +for(constchildofthis.reverseConnections[node]){ |
| 65 | +if(!visited.has(child))this.dfsKosaraju(child,visited) |
| 66 | +} |
| 67 | +} |
| 68 | + |
| 69 | +kosaraju(){ |
| 70 | +// Function to perform Kosaraju Algorithm |
| 71 | +constvisited=newSet() |
| 72 | +while(this.topoSorted.length>0){ |
| 73 | +constnode=this.topoSorted.pop() |
| 74 | +if(!visited.has(node)){ |
| 75 | +this.stronglyConnectedComponents.push([]) |
| 76 | +this.dfsKosaraju(node,visited) |
| 77 | +} |
| 78 | +} |
| 79 | +returnthis.stronglyConnectedComponents |
| 80 | +} |
| 81 | +} |
| 82 | + |
| 83 | +functionkosaraju(graph){ |
| 84 | +conststronglyConnectedComponents=newKosaraju(graph) |
| 85 | +returnstronglyConnectedComponents |
| 86 | +} |
| 87 | + |
| 88 | +export{kosaraju} |
| 89 | + |
| 90 | +// kosaraju([ |
| 91 | +// [1, 2], |
| 92 | +// [2, 3], |
| 93 | +// [3, 1], |
| 94 | +// [2, 4], |
| 95 | +// [4, 5], |
| 96 | +// [5, 6], |
| 97 | +// [6, 4], |
| 98 | +// ]) |
| 99 | + |
| 100 | +// [ [ 1, 3, 2 ], [ 4, 6, 5 ] ] |