graphlib - npm Package Compare versions

Comparing version 0.5.10 to 0.5.11

CHANGELOG.md

@@ -0,1 +1,6 @@
+v0.5.11
+=======
+
+* ~5x speedup for filterNodes.
+
 v0.5.10
@@ -2,0 +7,0 @@ =======

lib/BaseGraph.js

@@ -150,8 +150,14 @@ var Set = require("./data/Set");
 BaseGraph.prototype.filterNodes = function(filter) {
-  var copy = this.copy();
-  this.nodes().forEach(function(u) {
-    if (!filter(u)) {
-      copy.delNode(u);
+  var copy = new this.constructor();
+  copy.graph(this.graph());
+  this.eachNode(function(u, value) {
+    if (filter(u)) {
+      copy.addNode(u, value);
     }
   });
+  this.eachEdge(function(e, u, v, value) {
+    if (copy.hasNode(u) && copy.hasNode(v)) {
+      copy.addEdge(e, u, v, value);
+    }
+  });
   return copy;
@@ -158,0 +164,0 @@ };

lib/compoundify.js

@@ -80,3 +80,25 @@ // This file provides a helper function that mixes-in Dot behavior to an
 
+  Constructor.prototype.filterNodes = function(filter) {
+    var self = this,
+        copy = SuperConstructor.prototype.filterNodes.call(this, filter);
+
+    var parents = {};
+    function findParent(u) {
+      var parent = self.parent(u);
+      if (parent === null || copy.hasNode(parent)) {
+        parents[u] = parent;
+        return parent;
+      } else if (parent in parents) {
+        return parents[parent];
+      } else {
+        return findParent(parent);
+      }
+    }
+
+    copy.eachNode(function(u) { copy.parent(u, findParent(u)); });
+
+    return copy;
+  };
+
   return Constructor;
 }

lib/data/Set.js

@@ -56,7 +56,17 @@ var util = require("../util");
 Set.unionAll = function(sets) {
-  var result = new Set();
-  sets.forEach(function(set) {
-    result = result.union(set);
-  });
-  return result;
+  var totalElems = sets.reduce(function(lhs, rhs) {
+    return lhs + (rhs.size ? rhs.size() : rhs.length);
+  }, 0);
+  var arr = new Array(totalElems);
+
+  var k = 0;
+  for (var i = 0, il = sets.length; i < il; ++i) {
+    var cur = sets[i],
+        keys = cur.keys ? cur.keys() : cur;
+    for (var j = 0, jl = keys.length; j < jl; ++j) {
+      arr[k++] = keys[j];
+    }
+  }
+
+  return new Set(arr);
 };
@@ -63,0 +73,0 @@

lib/version.js

@@ -1,1 +0,1 @@
-module.exports = '0.5.10';
+module.exports = '0.5.11';

package.json

 {
   "name": "graphlib",
-  "version": "0.5.10",
+  "version": "0.5.11",
   "description": "A directed and undirected multi-graph library",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -8,4 +8,2 @@ # Graphlib
 
-[![browser support](https://ci.testling.com/cpettitt/graphlib.png)](https://ci.testling.com/cpettitt/graphlib)
-
 Note that graphlib is current a pre-1.0.0 library. We will do our best to
@@ -12,0 +10,0 @@ maintain backwards compatibility for patch level increases (e.g. 0.0.1 to

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

66101

increased by1.49%

Lines of code

1788

increased by1.82%

Worsened metrics

Number of lines in readme file

127

decreased by-1.55%

No dependency changes