strongly-connected-components - npm Package Compare versions

Comparing version 1.0.0 to 1.0.1

package.json

 {
   "name": "strongly-connected-components",
-  "version": "1.0.0",
+  "version": "1.0.1",
   "description": "Computes strongly connected components of a directed graph",
@@ -5,0 +5,0 @@ "main": "scc.js",

scc.js

@@ -10,2 +10,3 @@ "use strict"
   var active = new Array(numVertices)
+  var child = new Array(numVertices)
   var scc = new Array(numVertices)
@@ -19,2 +20,3 @@ var sccLinks = new Array(numVertices)
     active[i] = false
+    child[i] = 0
     scc[i] = -1
@@ -26,3 +28,2 @@ sccLinks[i] = []
   var count = 0
-  var S = []
   var components = []
@@ -32,37 +33,60 @@ var sccAdjList = []
   function strongConnect(v) {
-    index[v] = count
-    lowValue[v] = count
+    // To avoid running out of stack space, this emulates the recursive behaviour of the normal algorithm, effectively using T as the call stack.
+    var S = [v], T = [v]
+    index[v] = lowValue[v] = count
     active[v] = true
     count += 1
-    S.push(v)
-    var e = adjList[v]
-    for(var i=0; i<e.length; ++i) {
-      var u = e[i]
-      if(index[u] < 0) {
-        strongConnect(u)
-        lowValue[v] = Math.min(lowValue[v], lowValue[u])|0
-      } else if(active[u]) {
-        lowValue[v] = Math.min(lowValue[v], lowValue[u])|0
-      }
-      if (scc[u] >= 0) {
-        // Node v is not yet assigned an scc, but once it is that scc can apparently reach scc[u].
-        sccLinks[v].push(scc[u])
-      }
-    }
-    if(lowValue[v] === index[v]) {
-      var component = []
-      var links = []
-      for(var i=S.length-1; i>=0; --i) {
-        var w = S[i]
-        active[w] = false
-        component.push(w)
-        links.push(sccLinks[w])
-        scc[w] = components.length
-        if(w === v) {
-          S.length = i
-          break
+    while(T.length > 0) {
+      v = T[T.length-1]
+      var e = adjList[v]
+      if (child[v] < e.length) { // If we're not done iterating over the children, first try finishing that.
+        for(var i=child[v]; i<e.length; ++i) { // Start where we left off.
+          var u = e[i]
+          if(index[u] < 0) {
+            index[u] = lowValue[u] = count
+            active[u] = true
+            count += 1
+            S.push(u)
+            T.push(u)
+            break // First recurse, then continue here (with the same child!).
+            // There is a slight change to Tarjan's algorithm here.
+            // Normally, after having recursed, we set lowValue like we do for an active child (although some variants of the algorithm do it slightly differently).
+            // Here, we only do so if the child we recursed on is still active.
+            // The reasoning is that if it is no longer active, it must have had a lowValue equal to its own index, which means that it is necessarily higher than our lowValue.
+          } else if (active[u]) {
+            lowValue[v] = Math.min(lowValue[v], lowValue[u])|0
+          }
+          if (scc[u] >= 0) {
+            // Node v is not yet assigned an scc, but once it is that scc can apparently reach scc[u].
+            sccLinks[v].push(scc[u])
+          }
         }
+        child[v] = i // Remember where we left off.
+      } else { // If we're done iterating over the children, check whether we have an scc.
+        if(lowValue[v] === index[v]) { // TODO: It /might/ be true that T is always a prefix of S (at this point!!!), and if so, this could be used here.
+          var component = []
+          var links = [], linkCount = 0
+          for(var i=S.length-1; i>=0; --i) {
+            var w = S[i]
+            active[w] = false
+            component.push(w)
+            links.push(sccLinks[w])
+            linkCount += sccLinks[w].length
+            scc[w] = components.length
+            if(w === v) {
+              S.length = i
+              break
+            }
+          }
+          components.push(component)
+          var allLinks = new Array(linkCount)
+          for(var i=0; i<links.length; i++) {
+            for(var j=0; j<links[i].length; j++) {
+              allLinks[--linkCount] = links[i][j]
+            }
+          }
+          sccAdjList.push(allLinks)
+        }
+        T.pop() // Now we're finished exploring this particular node (normally corresponds to the return statement)
       }
-      components.push(component)
-      sccAdjList.push(Array.prototype.concat.apply([], links))
     }
@@ -69,0 +93,0 @@ }

test/test.js

@@ -26,5 +26,7 @@ "use strict"
   
-  console.log(scc(g))
+  var sccRet = scc(g)
+  console.log(sccRet)
+  t.equal(sccRet.components.length, 3)
 
   t.end()
 })

No alert changes

Improved metrics

Total package byte prevSize

7544

increased by31.73%

Lines of code

131

increased by24.76%

No dependency changes