Last active
November 15, 2022 23:18
-
-
Save HopefulLlama/dacf9f5b26ddfebbac6e to your computer and use it in GitHub Desktop.
JavaScript implementation of Tarjan's strongly connected components 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 Vertex(name) { | |
this.name = name; | |
this.index = null; | |
this.lowlink = null; | |
this.onStack = false; | |
this.children = []; | |
} | |
function TarjanRunner() { | |
var _this = this; | |
this.indexCounter = 0; | |
this.stack = []; | |
this.execute = function(vertices) { | |
for(var vertex of vertices) { | |
if(vertex.index === null) { | |
_this.strongConnect(vertex); | |
} | |
} | |
}; | |
this.strongConnect = function(vertex) { | |
vertex.index = _this.indexCounter; | |
vertex.lowlink = _this.indexCounter; | |
_this.indexCounter++; | |
_this.stack.push(vertex); | |
vertex.onStack = true; | |
for(var child of vertex.children) { | |
if(child.index === null) { | |
_this.strongConnect(child); | |
vertex.lowlink = Math.min(vertex.lowlink, child.lowlink); | |
} else if (child.onStack) { | |
vertex.lowlink = Math.min(vertex.lowlink, child.lowlink); | |
} | |
} | |
if(vertex.lowlink === vertex.index) { | |
var stronglyConnectedComponents = []; | |
var w = null; | |
while(vertex != w) { | |
w = _this.stack.pop(); | |
w.onStack = false; | |
stronglyConnectedComponents.push(w); | |
} | |
var output = "Strongly connected component: "; | |
for(var scc of stronglyConnectedComponents) { | |
output += scc.name + ", "; | |
} | |
console.log(output); | |
} | |
}; | |
} | |
var v1 = new Vertex("v1"); | |
var v2 = new Vertex("v2"); | |
var v3 = new Vertex("v3"); | |
var v4 = new Vertex("v4"); | |
var v5 = new Vertex("v5"); | |
var v6 = new Vertex("v6"); | |
var v7 = new Vertex("v7"); | |
v7.children.push(v6); | |
v7.children.push(v5); | |
v6.children.push(v4); | |
v6.children.push(v3); | |
v5.children.push(v2); | |
v5.children.push(v1); | |
/** Above graph visualized: | |
* | |
* v1 \ | |
* > v5 \ | |
* v2 / \ | |
* > v7 | |
* v3 \ / | |
* > v6 / | |
* v4 / | |
* | |
*/ | |
/** Test loops | |
* v1.children.push(v7); | |
* v5.children.push(v7); | |
*/ | |
var graph = [v7, v6, v5, v4, v3, v2, v1]; | |
var tr = new TarjanRunner(); | |
tr.execute(graph); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This will output the name of each vertex in a strongly connected component (SCC) to the console.
As is, each vertex will be in its own SCC, as there are no loops or back edges.
Uncommenting the 'Test loops' will create a 3 vertex SCC consisting of v7, v5 and v1.