Skip to content

Instantly share code, notes, and snippets.

@lancejpollard
Forked from HopefulLlama/tarjans.js
Created November 15, 2022 23:18
Show Gist options
  • Save lancejpollard/8e4d641130f337a087de49bc883f2a18 to your computer and use it in GitHub Desktop.
Save lancejpollard/8e4d641130f337a087de49bc883f2a18 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment