javascript-algorithms

javascript-algorithms copied to clipboard

Computing strongly connected components fails when adding edges in opposite direction. Minimal example:

        const vertexA = new GraphVertex('A');
        const vertexB = new GraphVertex('B');
        const vertexC = new GraphVertex('C');
        const vertexD = new GraphVertex('D');

        const edgeAB = new GraphEdge(vertexA, vertexB);
        const edgeBA = new GraphEdge(vertexB, vertexA);
        const edgeBC = new GraphEdge(vertexB, vertexC);
        const edgeCA = new GraphEdge(vertexC, vertexA);
        const edgeCD = new GraphEdge(vertexC, vertexD);

        const graph = new Graph(true);

        graph
            .addEdge(edgeAB)
            .addEdge(edgeBA)
            .addEdge(edgeBC)
            .addEdge(edgeCA)
            .addEdge(edgeCD);

        const components = stronglyConnectedComponents(graph);

Gives the following output:

Uncaught Error: Edge has already been added before
    at Graph.addEdge (Graph.js:74:1)
    at Graph.js:149:1

I think this error is for reverse function in graph. Because as written here, edges reverse one by one and for example if we have both AB and BA edges, on reversing AB, BA will be exist and cause error.

I'm going to create a PR and fix this issue.

@trekhleb, Would you please take a look at this?