~2x speedup for components

kkowar · Sep 24, 2014 · 5bb25c4 · 5bb25c4
1 parent dfc3adf
commit 5bb25c4
Showing 1 changed file with 11 additions and 11 deletions.
diff --git a/lib/alg/components.js b/lib/alg/components.js
@@ -4,23 +4,23 @@ module.exports = components;
 
 function components(g) {
   var visited = {},
-      cmpts = [];
+      cmpts = [],
+      cmpt;
 
-  function dfs(v, cmpt) {
+  function dfs(v) {
+    if (_.has(visited, v)) return;
     visited[v] = true;
     cmpt.push(v);
-    _.each(g.neighbors(v), function(w) {
-      if (!_.has(visited, w)) {
-        dfs(w, cmpt);
-      }
-    });
+    _.each(g.successors(v), dfs);
+    _.each(g.predecessors(v), dfs);
   }
 
   _.each(g.nodes(), function(v) {
-    if (_.has(visited, v)) return;
-    var cmpt = [];
-    dfs(v, cmpt);
-    cmpts.push(cmpt);
+    cmpt = [];
+    dfs(v);
+    if (cmpt.length) {
+      cmpts.push(cmpt);
+    }
   });
 
   return cmpts;