Skip to content

Instantly share code, notes, and snippets.

@HopefulLlama
Last active November 15, 2022 23:18
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save HopefulLlama/dacf9f5b26ddfebbac6e to your computer and use it in GitHub Desktop.
Save HopefulLlama/dacf9f5b26ddfebbac6e to your computer and use it in GitHub Desktop.
JavaScript implementation of Tarjan's strongly connected components algorithm
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);
@HopefulLlama
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment