trekhleb / javascript-algorithms

📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
MIT License
188.23k stars 30.25k forks source link

[BUG] Strongly connected components function breaks when adding edges on opposite directions #873

Open jackap opened 2 years ago

jackap commented 2 years ago

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
itsamirhn commented 2 years ago

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.

itsamirhn commented 2 years ago

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