Created
October 4, 2021 17:03
-
-
Save dmitriypereverza/c25e3d9d99a762b547085a5248c8b100 to your computer and use it in GitHub Desktop.
Kosaraju algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function createGraph(nodes, edges) { | |
| const result = nodes.reduce((acc, el) => { | |
| acc[el] = []; | |
| return acc; | |
| }, {}); | |
| for (let edge of edges) { | |
| result[edge[0]].push(edge[1]); | |
| } | |
| return result; | |
| } | |
| function dfsWithMark(graph, currentNode) { | |
| const visited = {}; | |
| const marks = {}; | |
| let step = 1; | |
| const pathForReverse = []; | |
| const inner = function (node) { | |
| let nextEl = graph[node].find(el => !visited[el]); | |
| if (nextEl !== undefined) { | |
| visited[nextEl] = 1; | |
| pathForReverse.push(node); | |
| } else { | |
| nextEl = pathForReverse.pop(); | |
| } | |
| if (nextEl === undefined) return; | |
| marks[nextEl] = ++step; | |
| inner(nextEl); | |
| } | |
| inner(currentNode); | |
| return marks; | |
| } | |
| function reverseGraph(graph) { | |
| const result = nodes.reduce((acc, el) => { | |
| acc[el] = []; | |
| return acc; | |
| }, {}) | |
| for (let node in graph) { | |
| for (let child of graph[node]) { | |
| if (!result[child]) { | |
| result[child] = []; | |
| } | |
| result[child].push(node); | |
| } | |
| } | |
| return result; | |
| } | |
| function kosaraju(nodes, edges) { | |
| const graph = createGraph(nodes, edges); | |
| const reversedGraph = reverseGraph(graph); | |
| const marks = dfsWithMark(graph, nodes[0]); | |
| const sortedMarks = Object.entries(marks).sort((a, b) => b[1] - a[1]); | |
| const stronglyConnectedComponents = []; | |
| let groupIndex = 0; | |
| let next = undefined; | |
| let visited = {}; | |
| for (let node of sortedMarks) { | |
| if (visited[node[0]]) continue; | |
| visited[node[0]] = 1; | |
| stronglyConnectedComponents[groupIndex] = [node[0]]; | |
| next = reversedGraph[node[0]].find(el => !visited[el]); | |
| if (next === undefined) { | |
| groupIndex++; | |
| continue; | |
| } | |
| while (next !== undefined) { | |
| visited[next] = 1; | |
| stronglyConnectedComponents[groupIndex].push(next); | |
| next = reversedGraph[next].find(el => !visited[el]) | |
| } | |
| groupIndex++; | |
| } | |
| return stronglyConnectedComponents; | |
| } | |
| const nodes = [0, 1, 2, 3, 4, 5, 6, 7, 20]; | |
| const edges = [ | |
| [0, 1], | |
| [1, 2], | |
| [1, 3], | |
| [3, 1], | |
| [3, 4], | |
| [4, 20], | |
| [4, 5], | |
| [5, 6], | |
| [6, 3], | |
| [6, 7], | |
| ]; | |
| const r = kosaraju(nodes, edges); | |
| console.log(r); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment