public
Last active

Tarjan's strongly connected components algorithm in Javascript - followed pseudocode from http://en.wikipedia.org/wiki/Tarjan%E2%80%99s_strongly_connected_components_algorithm

  • Download Gist
gistfile1.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
window.onload = function() {
 
var v0 = new Vertex("0");
var v1 = new Vertex("1");
var v2 = new Vertex("2");
var v3 = new Vertex("3");
var v4 = new Vertex("4");
var v5 = new Vertex("5");
var v6 = new Vertex("6");
var v7 = new Vertex("7");
var v8 = new Vertex("8");
var v9 = new Vertex("9");
var v10 = new Vertex("10");
var v11 = new Vertex("11");
var v12 = new Vertex("12");
 
v0.connections.push(v1);
v0.connections.push(v5);
v2.connections.push(v0);
v2.connections.push(v3);
v3.connections.push(v2);
v3.connections.push(v5);
v4.connections.push(v2);
v4.connections.push(v2);
v5.connections.push(v4);
v6.connections.push(v0);
v6.connections.push(v9);
v7.connections.push(v6);
v7.connections.push(v8);
v8.connections.push(v7);
v8.connections.push(v9);
v9.connections.push(v10);
v9.connections.push(v11);
v10.connections.push(v12);
v11.connections.push(v4);
v11.connections.push(v12);
v12.connections.push(v9);
 
var vertices = [v0,v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12];
var graph = new Graph(vertices);
var tarjan = new Tarjan(graph);
var scc = tarjan.run();
console.log(scc);
};
 
function Graph(vertices){
this.vertices = vertices || [];
}
 
function Vertex(name){
this.name = name || null;
this.connections = [];
// used in tarjan algorithm
// went ahead and explicity initalized them
this.index= -1;
this.lowlink = -1;
}
Vertex.prototype = {
equals: function(vertex){
// equality check based on vertex name
return (vertex.name && this.name==vertex.name);
}
};
 
function VertexStack(vertices) {
this.vertices = vertices || [];
}
VertexStack.prototype = {
contains: function(vertex){
for (var i in this.vertices){
if (this.vertices[i].equals(vertex)){
return true;
}
}
return false;
}
};
 
function Tarjan(graph) {
this.index = 0;
this.stack = new VertexStack();
this.graph = graph;
this.scc = [];
}
Tarjan.prototype = {
run: function(){
for (var i in this.graph.vertices){
if (this.graph.vertices[i].index<0){
this.strongconnect(this.graph.vertices[i]);
}
}
return this.scc;
},
strongconnect: function(vertex){
// Set the depth index for v to the smallest unused index
vertex.index = this.index;
vertex.lowlink = this.index;
this.index = this.index + 1;
this.stack.vertices.push(vertex);
// Consider successors of v
// aka... consider each vertex in vertex.connections
for (var i in vertex.connections){
var v = vertex;
var w = vertex.connections[i];
if (w.index<0){
// Successor w has not yet been visited; recurse on it
this.strongconnect(w);
v.lowlink = Math.min(v.lowlink,w.lowlink);
} else if (this.stack.contains(w)){
// Successor w is in stack S and hence in the current SCC
v.lowlink = Math.min(v.lowlink,w.index);
}
}
// If v is a root node, pop the stack and generate an SCC
if (vertex.lowlink==vertex.index){
// start a new strongly connected component
var vertices = [];
var w = null;
if (this.stack.vertices.length>0){
do {
w = this.stack.vertices.pop();
// add w to current strongly connected component
vertices.push(w);
} while (!vertex.equals(w));
}
// output the current strongly connected component
// ... i'm going to push the results to a member scc array variable
if (vertices.length>0){
this.scc.push(vertices);
}
}
}
};

what's the license?

I haven't considered putting a license on a gist, but I can see why that would make sense. I have no issue with anyone using, modifying, selling, distributing this code. It's simply an implementation of an established algorithm: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

What would you suggest for something like this?

MIT License is a good one if that's your goal. Just a suggestion :)

I'm quite new to graph algorithms but I think I've noticed a problem with this implementation of Tarjan's SCCs.

It is explicitly stated that "The test for whether w is on the stack should be done in constant time".
While provided implementation violates this requirement since it iterates over all nodes already in stack. Which makes overall worst case running time to be O(n^2+n*m).

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.