graph-data-structure - npm Package Compare versions

Comparing version 0.7.0 to 0.8.0

index.js

@@ -12,2 +12,4 @@ // A graph data structure with depth-first search and topological sort.
     removeEdge: removeEdge,
+    indegree: indegree,
+    outdegree: outdegree,
     depthFirstSearch: depthFirstSearch,
@@ -19,3 +21,2 @@ topologicalSort: topologicalSort,
 
-  
   // The adjacency list of the graph.
@@ -97,2 +98,22 @@ // Keys are node ids.
 
+  // Computes the indegree for the given node.
+  // Not very efficient, costs O(E) where E = number of edges.
+  function indegree(node){
+    var degree = 0;
+    function check(v){
+      if(v === node){
+        degree++;
+      }
+    }
+    Object.keys(edges).forEach(function (u){
+      edges[u].forEach(check);
+    });
+    return degree;
+  }
+
+  // Computes the outdegree for the given node.
+  function outdegree(node){
+    return node in edges ? edges[node].length : 0;
+  }
+
   // Depth First Search algorithm, inspired by
@@ -99,0 +120,0 @@ // Cormen et al. "Introduction to Algorithms" 3rd Ed. p. 604

package.json

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

README.md

@@ -83,2 +83,3 @@ # graph-data-structure
 * [Querying the Graph](#querying-the-graph)
+* [Serialization](#serialization)
 * [Graph Algorithms](#graph-algorithms)
@@ -126,2 +127,12 @@
 
+<a name="indegree" href="#indegree">#</a> <i>graph</i>.<b>indegree</b>(<i>node</i>)
+
+Computes the [indegree](https://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) (number of incoming edges) for the specified *node*.
+
+<a name="outdegree" href="#outdegree">#</a> <i>graph</i>.<b>outdegree</b>(<i>node</i>)
+
+Computes the [outdegree](https://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree) (number of outgoing edges) for the specified *node*.
+
+### Serialization
+
 <a name="serialize" href="#serialize">#</a> <i>graph</i>.<b>serialize</b>()
@@ -128,0 +139,0 @@

test.js

@@ -118,2 +118,22 @@
 
+    it("Should compute indegree.", function (){
+      var graph = Graph();
+      graph.addEdge("a", "b");
+      assert.equal(graph.indegree("a"), 0);
+      assert.equal(graph.indegree("b"), 1);
+
+      graph.addEdge("c", "b");
+      assert.equal(graph.indegree("b"), 2);
+    });
+
+    it("Should compute outdegree.", function (){
+      var graph = Graph();
+      graph.addEdge("a", "b");
+      assert.equal(graph.outdegree("a"), 1);
+      assert.equal(graph.outdegree("b"), 0);
+
+      graph.addEdge("a", "c");
+      assert.equal(graph.outdegree("a"), 2);
+    });
+
   });
@@ -237,2 +257,12 @@
 
+    it("Should return indegree of 0 for unknown nodes.", function (){
+      var graph = Graph();
+      assert.equal(graph.indegree("z"), 0);
+    });
+
+    it("Should return outdegree of 0 for unknown nodes.", function (){
+      var graph = Graph();
+      assert.equal(graph.outdegree("z"), 0);
+    });
+
   });
@@ -239,0 +269,0 @@

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

26354

increased by7.8%

Lines of code

431

increased by11.37%

Number of lines in readme file

198

increased by5.88%

No dependency changes