Skip to content

Instantly share code, notes, and snippets.

@dmitriypereverza

dmitriypereverza/Kosaraju.js

Created October 4, 2021 17:03
Show Gist options
  • Save dmitriypereverza/c25e3d9d99a762b547085a5248c8b100 to your computer and use it in GitHub Desktop.
Save dmitriypereverza/c25e3d9d99a762b547085a5248c8b100 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dmitriypereverza created this gist Oct 4, 2021.
    98 changes: 98 additions & 0 deletions Kosaraju.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,98 @@
    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);