toposort - npm Package Compare versions

Comparing version 1.0.4 to 1.0.5

index.js

@@ -20,5 +20,8 @@
     , i = cursor
+    // Better data structures make algorithm much faster.
+    , outgoingEdges = makeOutgoingEdges(edges)
+    , nodesHash = makeNodesHash(nodes)
 
   while (i--) {
-    if (!visited[i]) visit(nodes[i], i, [])
+    if (!visited[i]) visit(nodes[i], i, {})
   }
@@ -29,7 +32,7 @@
   function visit(node, i, predecessors) {
-    if(predecessors.indexOf(node) >= 0) {
+    if(predecessors.hasOwnProperty(node)) {
       throw new Error('Cyclic dependency: '+JSON.stringify(node))
     }
 
-    if (!~nodes.indexOf(node)) {
+    if (!nodesHash.hasOwnProperty(node)) {
       throw new Error('Found unknown node. Make sure to provided all involved nodes. Unknown node: '+JSON.stringify(node))
@@ -41,12 +44,11 @@ }
 
-    // outgoing edges
-    var outgoing = edges.filter(function(edge){
-      return edge[0] === node
-    })
+    var outgoing = Object.keys(outgoingEdges[node] || {})
+
     if (i = outgoing.length) {
-      var preds = predecessors.concat(node)
+      predecessors[node] = true
       do {
-        var child = outgoing[--i][1]
-        visit(child, nodes.indexOf(child), preds)
+        var child = outgoing[--i]
+        visit(child, nodesHash[child], predecessors)
       } while (i)
+      delete predecessors[node]
     }
@@ -59,9 +61,28 @@
 function uniqueNodes(arr){
-  var res = []
+  var res = {}
   for (var i = 0, len = arr.length; i < len; i++) {
     var edge = arr[i]
-    if (res.indexOf(edge[0]) < 0) res.push(edge[0])
-    if (res.indexOf(edge[1]) < 0) res.push(edge[1])
+    res[edge[0]] = true
+    res[edge[1]] = true
   }
+  return Object.keys(res)
+}
+
+function makeOutgoingEdges(arr){
+  var edges = {}
+  for (var i = 0, len = arr.length; i < len; i++) {
+    var edge = arr[i]
+    edges[edge[0]] = edges[edge[0]] || {}
+    edges[edge[1]] = edges[edge[1]] || {}
+    edges[edge[0]][edge[1]] = true
+  }
+  return edges
+}
+
+function makeNodesHash(arr){
+  var res = {}
+  for (var i = 0, len = arr.length; i < len; i++) {
+    res[arr[i]] = i
+  }
   return res
 }

package.json

 {
   "name": "toposort",
-  "version": "1.0.4",
+  "version": "1.0.5",
   "description": "Topological sort of directed ascyclic graphs (like dependecy lists)",
@@ -5,0 +5,0 @@ "main": "index.js",

test.js

@@ -135,2 +135,19 @@ var vows = require('vows')
   }
+, 'giant graphs':
+  {
+    topic: function() {
+      var graph = []
+      for (var i = 0; i < 100000; i++) {
+        graph.push([i, i + 1])
+      }
+      return graph
+    }
+  , 'should sort quickly': function(er, result){
+     var start = (new Date).getTime()
+     var sorted = toposort(result)
+     var end = (new Date).getTime()
+     var elapsedSeconds = (end - start) / 1000
+     assert(elapsedSeconds < 1)
+    }
+  }
 })
@@ -137,0 +154,0 @@ .run(null, function() {

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

15736

increased by6.1%

Lines of code

247

increased by16.51%

No dependency changes