Bug fix for source/sink caching on node removal

kkowar · Sep 24, 2014 · 2240f3f · 2240f3f
1 parent 051eecc
commit 2240f3f
Show file tree

Hide file tree

Showing 4 changed files with 54 additions and 26 deletions.
diff --git a/lib/digraph.js b/lib/digraph.js
@@ -46,13 +46,21 @@ Digraph.prototype.degree = function(v) {
 };
 
 Digraph.prototype._onRemoveNode = function(v) {
-  _.forIn(this._inEdges[v], function(_, u) {
+  _.forIn(this._inEdges[v], function(_value, u) {
+    var outU = this._outEdges[u];
     --this._edgeCount;
-    delete this._outEdges[u][v];
+    delete outU[v];
+    if (_.isEmpty(outU)) {
+      this._sinks[u] = true;
+    }
   }, this);
-  _.forIn(this._outEdges[v], function(_, w) {
+  _.forIn(this._outEdges[v], function(_value, w) {
+    var inW = this._inEdges[w];
     --this._edgeCount;
-    delete this._inEdges[w][v];
+    delete inW[v];
+    if (_.isEmpty(inW)) {
+      this._sources[w] = true;
+    }
   }, this);
 };
 

diff --git a/lib/graph.js b/lib/graph.js
@@ -49,14 +49,22 @@ Graph.prototype.inDegree = Graph.prototype.degree;
 Graph.prototype.outDegree = Graph.prototype.degree;
 
 Graph.prototype._onRemoveNode = function(v) {
-  _.forIn(this._inEdges[v], function(_, u) {
+  _.forIn(this._inEdges[v], function(_value, u) {
+    var outU = this._outEdges[u];
     --this._edgeCount;
-    delete this._outEdges[u][v];
+    delete outU[v];
+    if (_.isEmpty(outU)) {
+      this._sinks[u] = true;
+    }
   }, this);
 
   // On the second pass we do not decrement the graph count. These are the
   // inverse elements of the edges already deleted.
-  _.forIn(this._outEdges[v], function(_, w) {
-    delete this._inEdges[w][v];
+  _.forIn(this._outEdges[v], function(_value, w) {
+    var inW = this._inEdges[w];
+    delete inW[v];
+    if (_.isEmpty(inW)) {
+      this._sources[w] = true;
+    }
   }, this);
 };
diff --git a/test/base-graph-test.js b/test/base-graph-test.js
@@ -60,6 +60,36 @@ exports.tests = function(GraphConstructor) {
       });
     });
 
+    describe("sources", function() {
+      it("includes a nodes whose only in-edge has been removed", function() {
+        g.setEdge("a", "b");
+        g.removeNode("a");
+        expect(g.sources()).to.include("b");
+      });
+
+      it("does not include a node if only one of its in-edges is removed", function() {
+        g.setEdge("a", "b");
+        g.setEdge("c", "b");
+        g.removeNode("a");
+        expect(g.sources()).to.not.include("b");
+      });
+    });
+
+    describe("sinks", function() {
+      it("includes a nodes whose only out-edge has been removed", function() {
+        g.setEdge("a", "b");
+        g.removeNode("b");
+        expect(g.sinks()).to.include("a");
+      });
+
+      it("does not include a node if only one of its out-edges is removed", function() {
+        g.setEdge("a", "b");
+        g.setEdge("a", "c");
+        g.removeNode("b");
+        expect(g.sinks()).to.not.include("a");
+      });
+    });
+
     describe("hasNode", function() {
       it("returns false if the node is not in the graph", function() {
         expect(g.hasNode("node-not-in-graph")).to.be.false;

diff --git a/test/digraph-test.js b/test/digraph-test.js
@@ -33,15 +33,6 @@ function tests(GraphConstructor) {
         g.setNode("n5");
         expect(_.sortBy(g.sources())).to.eql(["n1", "n4", "n5"]);
       });
-
-      it("recognizes a new source when in-edges are removed", function() {
-        g.setEdge("n1", "n1");
-        g.setEdge("n1", "n2");
-        expect(g.sources()).to.be.empty;
-
-        g.removeEdge("n1", "n2");
-        expect(g.sources()).to.eql(["n2"]);
-      });
     });
 
     describe("sinks", function() {
@@ -52,15 +43,6 @@ function tests(GraphConstructor) {
         g.setNode("n5");
         expect(_.sortBy(g.sinks())).to.eql(["n2", "n4", "n5"]);
       });
-
-      it("recognizes a new sink when out-edges are removed", function() {
-        g.setEdge("n2", "n2");
-        g.setEdge("n1", "n2");
-        expect(g.sinks()).to.be.empty;
-
-        g.removeEdge("n1", "n2");
-        expect(g.sinks()).to.eql(["n1"]);
-      });
     });
 
     describe("successors", function() {