graph-data-structure - npm Package Compare versions

Comparing version 0.0.1 to 0.1.0

index.js

@@ -9,11 +9,63 @@ // A graph data structure with depth-first search and topological sort.
 
-  // Gets or creates the adjacent node list for node u.
+  // Adds a node to the graph.
+  // If node was already added, this function does nothing.
+  // If node was not already added, this function sets up an empty adjacency list.
+  function addNode(node){
+    edges[node] = adjacent(node);
+  }
+
+  // Removes a node from the graph.
+  // Also removes all of the node's incoming and outgoing edges.
+  function removeNode(node){
+    
+    // Remove incoming edges.
+    Object.keys(edges).forEach(function (u){
+      edges[u].forEach(function (v){
+        if(v === node){
+          removeEdge(u, v);
+        }
+      });
+    });
+
+    // Remove outgoing edges (and signal that the node no longer exists).
+    delete edges[node];
+  }
+
+  // Gets the list of nodes that have been added to the graph.
+  function nodes(){
+    var nodeSet = {};
+    Object.keys(edges).forEach(function (u){
+      nodeSet[u] = true;
+      edges[u].forEach(function (v){
+        nodeSet[v] = true;
+      });
+    });
+    return Object.keys(nodeSet);
+  }
+
+  // Gets the adjacent node list for node u.
+  // Returns an empty array for unknown nodes.
   function adjacent(u){
-    return edges[u] || (edges[u] = []);
+    return edges[u] || [];
   }
 
+  // Adds an edge between nodes u and v.
+  // Implicitly adds the nodes if they were not already added.
   function addEdge(u, v){
+    addNode(u);
+    addNode(v);
     adjacent(u).push(v);
   }
 
+  // Removes the edge between nodes u and v.
+  // Does not remove the nodes.
+  // Does nothing if the edge does not exist.
+  function removeEdge(u, v){
+    if(edges[u]){
+      edges[u] = adjacent(u).filter(function (_v){
+        return _v !== v;
+      });
+    }
+  }
+
   // Depth First Search algorithm, inspired by
@@ -51,2 +103,5 @@ // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604
   return {
+    addNode: addNode,
+    removeNode: removeNode,
+    nodes: nodes,
     adjacent: adjacent,
@@ -53,0 +108,0 @@ addEdge: addEdge,

package.json

 {
   "name": "graph-data-structure",
-  "version": "0.0.1",
+  "version": "0.1.0",
   "description": "A graph data structure with topological sort.",
@@ -5,0 +5,0 @@ "main": "index.js",

test.js

@@ -11,11 +11,142 @@
 
-  describe("Data Structure", function() {
+  describe("Data structure", function() {
+
+    it("Should add nodes and list them.", function (){
+      var graph = Graph();
+      graph.addNode("a");
+      graph.addNode("b");
+      assert.equal(graph.nodes().length, 2);
+      assert(contains(graph.nodes(), "a"));
+      assert(contains(graph.nodes(), "b"));
+    });
+
+    it("Should remove nodes.", function (){
+      var graph = Graph();
+      graph.addNode("a");
+      graph.addNode("b");
+      graph.removeNode("a");
+      graph.removeNode("b");
+      assert.equal(graph.nodes().length, 0);
+    });
+
     it("Should add edges and query for adjacent nodes.", function (){
       var graph = Graph();
+      graph.addNode("a");
+      graph.addNode("b");
       graph.addEdge("a", "b");
-      assert(graph.adjacent("a").length === 1);
-      assert(graph.adjacent("a")[0] === "b");
+      assert.equal(graph.adjacent("a").length, 1);
+      assert.equal(graph.adjacent("a")[0], "b");
     });
+
+    it("Should implicitly add nodes when edges are added.", function (){
+      var graph = Graph();
+      graph.addEdge("a", "b");
+      assert.equal(graph.adjacent("a").length, 1);
+      assert.equal(graph.adjacent("a")[0], "b");
+      assert.equal(graph.nodes().length, 2);
+      assert(contains(graph.nodes(), "a"));
+      assert(contains(graph.nodes(), "b"));
+    });
+
+    it("Should remove edges.", function (){
+      var graph = Graph();
+      graph.addEdge("a", "b");
+      graph.removeEdge("a", "b");
+      assert.equal(graph.adjacent("a").length, 0);
+    });
+
+    it("Should not remove nodes when edges are removed.", function (){
+      var graph = Graph();
+      graph.addEdge("a", "b");
+      graph.removeEdge("a", "b");
+      assert.equal(graph.nodes().length, 2);
+      assert(contains(graph.nodes(), "a"));
+      assert(contains(graph.nodes(), "b"));
+    });
+
+    it("Should remove outgoing edges when a node is removed.", function (){
+      var graph = Graph();
+      graph.addEdge("a", "b");
+      graph.removeNode("a");
+      assert.equal(graph.adjacent("a").length, 0);
+    });
+
+    it("Should remove incoming edges when a node is removed.", function (){
+      var graph = Graph();
+      graph.addEdge("a", "b");
+      graph.removeNode("b");
+      assert.equal(graph.adjacent("a").length, 0);
+    });
+
   });
 
+  describe("Algorithms", function() {
+
+    it("Should compute topological sort.", function (){
+      var graph = Graph();
+      graph.addEdge("a", "b");
+      graph.addEdge("b", "c");
+      var sorted = graph.topologicalSort(["a"]);
+      assert.equal(sorted.length, 2);
+      assert.equal(sorted[0], "b");
+      assert.equal(sorted[1], "c");
+    });
+
+    it("Should compute topological sort tricky case.", function (){
+
+      var graph = Graph();     //      a
+                               //     / \
+      graph.addEdge("a", "b"); //    b   |
+      graph.addEdge("a", "d"); //    |   d
+      graph.addEdge("b", "c"); //    c   |
+      graph.addEdge("d", "e"); //     \ /
+      graph.addEdge("c", "e"); //      e   
+      
+      var sorted = graph.topologicalSort(["a"]);
+      assert.equal(sorted.length, 4);
+      assert(contains(sorted, "b"));
+      assert(contains(sorted, "c"));
+      assert(contains(sorted, "d"));
+      assert.equal(sorted[sorted.length - 1], "e");
+
+      assert(comesBefore(sorted, "b", "c"));
+      assert(comesBefore(sorted, "b", "e"));
+      assert(comesBefore(sorted, "c", "e"));
+      assert(comesBefore(sorted, "d", "e"));
+
+    });
+
+  });
+
+  describe("Edge cases and error handling", function() {
+
+    it("Should return empty array of adjacent nodes for unknown nodes.", function (){
+      var graph = Graph();
+      assert.equal(graph.adjacent("a").length, 0);
+      assert.equal(graph.nodes(), 0);
+    });
+
+    it("Should do nothing if removing an edge that does not exist.", function (){
+      assert.doesNotThrow(function (){
+        var graph = Graph();
+        graph.removeEdge("a", "b");
+      });
+    });
+
+  });
 });
+
+function contains(arr, item){
+  return arr.filter(function (d){
+    return d === item;
+  }).length > 0;
+}
+
+function comesBefore(arr, a, b){
+  var aIndex, bIndex;
+  arr.forEach(function (d, i){
+    if(d === a){ aIndex = i; }
+    if(d === b){ bIndex = i; }
+  });
+  return aIndex < bIndex;
+}

No alert changes

Improved metrics

Total package byte prevSize

9123

increased by138.26%

Lines of code

219

increased by259.02%

No dependency changes