dependency-graph - npm Package Compare versions

Comparing version 0.8.0 to 0.8.1

CHANGELOG.md

 # Dependency Graph Changelog
 
+## 0.8.1 (December 3, 2019)
+
+- Ensure all nodes are included in overallOrder when cycles are allowed. (Fixes #33)
+
 ## 0.8.0 (December 11, 2018)
@@ -4,0 +8,0 @@

lib/dep_graph.js

@@ -52,3 +52,3 @@ /**
    */
-  size:function () {
+  size: function () {
     return Object.keys(this.nodes).length;
@@ -59,3 +59,3 @@ },
    */
-  addNode:function (node, data) {
+  addNode: function (node, data) {
     if (!this.hasNode(node)) {
@@ -75,3 +75,3 @@ // Checking the arguments length allows the user to add a node with undefined data
    */
-  removeNode:function (node) {
+  removeNode: function (node) {
     if (this.hasNode(node)) {
@@ -94,3 +94,3 @@ delete this.nodes[node];
    */
-  hasNode:function (node) {
+  hasNode: function (node) {
     return this.nodes.hasOwnProperty(node);
@@ -101,3 +101,3 @@ },
    */
-  getNodeData:function (node) {
+  getNodeData: function (node) {
     if (this.hasNode(node)) {
@@ -112,3 +112,3 @@ return this.nodes[node];
    */
-  setNodeData:function (node, data) {
+  setNodeData: function (node, data) {
     if (this.hasNode(node)) {
@@ -124,3 +124,3 @@ this.nodes[node] = data;
    */
-  addDependency:function (from, to) {
+  addDependency: function (from, to) {
     if (!this.hasNode(from)) {
@@ -143,3 +143,3 @@ throw new Error('Node does not exist: ' + from);
    */
-  removeDependency:function (from, to) {
+  removeDependency: function (from, to) {
     var idx;
@@ -164,3 +164,3 @@ if (this.hasNode(from)) {
    */
-  clone:function () {
+  clone: function () {
     var source = this;
@@ -184,3 +184,3 @@ var result = new DepGraph();
    */
-  dependenciesOf:function (node, leavesOnly) {
+  dependenciesOf: function (node, leavesOnly) {
     if (this.hasNode(node)) {
@@ -207,3 +207,3 @@ var result = [];
    */
-  dependantsOf:function (node, leavesOnly) {
+  dependantsOf: function (node, leavesOnly) {
     if (this.hasNode(node)) {
@@ -229,3 +229,3 @@ var result = [];
    */
-  overallOrder:function (leavesOnly) {
+  overallOrder: function (leavesOnly) {
     var self = this;
@@ -237,8 +237,10 @@ var result = [];
     } else {
-      // Look for cycles - we run the DFS starting at all the nodes in case there
-      // are several disconnected subgraphs inside this dependency graph.
-      var CycleDFS = createDFS(this.outgoingEdges, false, [], this.circular);
-      keys.forEach(function(n) {
-        CycleDFS(n);
-      });
+      if (!this.circular) {
+        // Look for cycles - we run the DFS starting at all the nodes in case there
+        // are several disconnected subgraphs inside this dependency graph.
+        var CycleDFS = createDFS(this.outgoingEdges, false, [], this.circular);
+        keys.forEach(function (n) {
+          CycleDFS(n);
+        });
+      }
 
@@ -254,2 +256,13 @@ var DFS = createDFS(this.outgoingEdges, leavesOnly, result, this.circular);
 
+      // If we're allowing cycles - we need to run the DFS against any remaining
+      // nodes that did not end up in the initial result (as they are part of a
+      // subgraph that does not have a clear starting point)
+      if (this.circular) {
+        keys.filter(function (node) {
+          return result.indexOf(node) === -1;
+        }).forEach(function (n) {
+          DFS(n);
+        });
+      }
+
       return result;
@@ -256,0 +269,0 @@ }

package.json

 {
   "name": "dependency-graph",
   "description": "Simple dependency graph.",
-  "version": "0.8.0",
+  "version": "0.8.1",
   "author": "Jim Riecken <[e-mail]>",
@@ -10,6 +10,3 @@ "keywords": [
   ],
-  "license": {
-    "type": "MIT",
-    "url": "http://github.com/jriecken/dependency-graph/raw/master/LICENSE"
-  },
+  "license": "MIT",
   "repository": {
@@ -24,3 +21,3 @@ "type": "git",
   "scripts": {
-    "test": "jasmine-node specs"
+    "test": "jasmine specs/**/*.js"
   },
@@ -30,3 +27,3 @@ "dependencies": {},
   "devDependencies": {
-    "jasmine-node": "2.0.1"
+    "jasmine": "3.5.0"
   },
@@ -33,0 +30,0 @@ "engines": {

specs/dep_graph_spec.js

@@ -12,9 +12,9 @@ var dep_graph = require('../lib/dep_graph');
 
-    expect(graph.hasNode('Foo')).toBe(true);
-    expect(graph.hasNode('Bar')).toBe(true);
-    expect(graph.hasNode('NotThere')).toBe(false);
+    expect(graph.hasNode('Foo')).toBeTrue();
+    expect(graph.hasNode('Bar')).toBeTrue();
+    expect(graph.hasNode('NotThere')).toBeFalse();
 
     graph.removeNode('Bar');
 
-    expect(graph.hasNode('Bar')).toBe(false);
+    expect(graph.hasNode('Bar')).toBeFalse();
   });
@@ -25,3 +25,3 @@
 
-    expect(graph.size()).toEqual(0);
+    expect(graph.size()).toBe(0);
 
@@ -31,7 +31,7 @@ graph.addNode('Foo');
 
-    expect(graph.size()).toEqual(2);
+    expect(graph.size()).toBe(2);
 
     graph.removeNode('Bar');
 
-    expect(graph.size()).toEqual(1);
+    expect(graph.size()).toBe(1);
   });
@@ -60,3 +60,3 @@
 
-    expect(graph.getNodeData('Foo')).toBe(undefined);
+    expect(graph.getNodeData('Foo')).toBeUndefined();
   });
@@ -70,6 +70,6 @@
 
-    falsyData.forEach(function(data) {
+    falsyData.forEach(function (data) {
       graph.setNodeData('Foo', data);
 
-      expect(graph.hasNode('Foo')).toBe(true);
+      expect(graph.hasNode('Foo')).toBeTrue();
 
@@ -112,3 +112,3 @@ // Just an extra check to make sure that the saved data is correct
 
-    graph.addDependency('a','b');
+    graph.addDependency('a', 'b');
 
@@ -124,9 +124,9 @@ graph.addNode('a');
     graph.addNode('a');
-    expect(graph.hasNode('a')).toBe(true);
+    expect(graph.hasNode('a')).toBeTrue();
 
     graph.removeNode('a');
-    expect(graph.hasNode('Foo')).toBe(false);
+    expect(graph.hasNode('Foo')).toBeFalse();
 
     graph.removeNode('a');
-    expect(graph.hasNode('Foo')).toBe(false);
+    expect(graph.hasNode('Foo')).toBeFalse();
   });
@@ -141,4 +141,4 @@
 
-    graph.addDependency('a','b');
-    graph.addDependency('a','c');
+    graph.addDependency('a', 'b');
+    graph.addDependency('a', 'c');
 
@@ -154,3 +154,3 @@ expect(graph.dependenciesOf('a')).toEqual(['b', 'c']);
     expect(function () {
-      graph.addDependency('a','b');
+      graph.addDependency('a', 'b');
     }).toThrow(new Error('Node does not exist: b'));
@@ -194,2 +194,27 @@ });
 
+  it('should include all nodes in overall order even from ' +
+    'cycles in disconnected subgraphs when circular is true', function () {
+      var graph = new DepGraph({ circular: true });
+
+      graph.addNode('2a');
+      graph.addNode('2b');
+      graph.addNode('2c');
+      graph.addDependency('2a', '2b');
+      graph.addDependency('2b', '2c');
+      graph.addDependency('2c', '2a');
+
+      graph.addNode('1a');
+      graph.addNode('1b');
+      graph.addNode('1c');
+      graph.addNode('1d');
+      graph.addNode('1e');
+
+      graph.addDependency('1a', '1b');
+      graph.addDependency('1a', '1c');
+      graph.addDependency('1b', '1c');
+      graph.addDependency('1c', '1d');
+
+      expect(graph.overallOrder()).toEqual(['1d', '1c', '1b', '1a', '1e', '2c', '2b', '2a']);
+    });
+
   it('should detect cycles in overall order', function () {
@@ -230,20 +255,20 @@ var graph = new DepGraph();
   it('should detect cycles in overall order when there are several ' +
-     'disconnected subgraphs (with one that does not have a cycle', function () {
-    var graph = new DepGraph();
+    'disconnected subgraphs (with one that does not have a cycle', function () {
+      var graph = new DepGraph();
 
-    graph.addNode('a_1');
-    graph.addNode('a_2');
-    graph.addNode('b_1');
-    graph.addNode('b_2');
-    graph.addNode('b_3');
+      graph.addNode('a_1');
+      graph.addNode('a_2');
+      graph.addNode('b_1');
+      graph.addNode('b_2');
+      graph.addNode('b_3');
 
-    graph.addDependency('a_1', 'a_2');
-    graph.addDependency('b_1', 'b_2');
-    graph.addDependency('b_2', 'b_3');
-    graph.addDependency('b_3', 'b_1');
+      graph.addDependency('a_1', 'a_2');
+      graph.addDependency('b_1', 'b_2');
+      graph.addDependency('b_2', 'b_3');
+      graph.addDependency('b_3', 'b_1');
 
-    expect(function () {
-      graph.overallOrder();
-    }).toThrow(new dep_graph.DepGraphCycleError(['b_1', 'b_2', 'b_3', 'b_1']));
-  });
+      expect(function () {
+        graph.overallOrder();
+      }).toThrow(new dep_graph.DepGraphCycleError(['b_1', 'b_2', 'b_3', 'b_1']));
+    });
 
@@ -269,4 +294,4 @@ it('should retrieve dependencies and dependants in the correct order', function () {
     expect(graph.dependantsOf('a')).toEqual([]);
-    expect(graph.dependantsOf('b')).toEqual(['a','d']);
-    expect(graph.dependantsOf('c')).toEqual(['a','d','b']);
+    expect(graph.dependantsOf('b')).toEqual(['a', 'd']);
+    expect(graph.dependantsOf('c')).toEqual(['a', 'd', 'b']);
     expect(graph.dependantsOf('d')).toEqual(['a']);
@@ -353,3 +378,3 @@ });
 
-    expect(graph === cloned).toBe(false);
+    expect(graph === cloned).toBeFalse();
   });
@@ -368,6 +393,6 @@
 
-    expect(graph === cloned).toBe(false);
-    expect(cloned.hasNode('a')).toBe(true);
-    expect(cloned.hasNode('b')).toBe(true);
-    expect(cloned.hasNode('c')).toBe(true);
+    expect(graph === cloned).toBeFalse();
+    expect(cloned.hasNode('a')).toBeTrue();
+    expect(cloned.hasNode('b')).toBeTrue();
+    expect(cloned.hasNode('c')).toBeTrue();
     expect(cloned.dependenciesOf('a')).toEqual(['c', 'b']);
@@ -390,22 +415,22 @@ expect(cloned.dependantsOf('c')).toEqual(['a', 'b']);
 
-    var data = {a: 42};
+    var data = { a: 42 };
     graph.addNode('a', data);
 
     var cloned = graph.clone();
-    expect(graph === cloned).toBe(false);
-    expect(graph.getNodeData('a') === cloned.getNodeData('a')).toBe(true);
+    expect(graph === cloned).toBeFalse();
+    expect(graph.getNodeData('a') === cloned.getNodeData('a')).toBeTrue();
 
     graph.getNodeData('a').a = 43;
-    expect(cloned.getNodeData('a').a).toEqual(43);
+    expect(cloned.getNodeData('a').a).toBe(43);
 
-    cloned.setNodeData('a', {a: 42});
-    expect(cloned.getNodeData('a').a).toEqual(42);
-    expect(graph.getNodeData('a') === cloned.getNodeData('a')).toBe(false);
+    cloned.setNodeData('a', { a: 42 });
+    expect(cloned.getNodeData('a').a).toBe(42);
+    expect(graph.getNodeData('a') === cloned.getNodeData('a')).toBeFalse();
   });
 });
 
-describe('DepGraphCycleError', function() {
+describe('DepGraphCycleError', function () {
   var DepGraphCycleError = dep_graph.DepGraphCycleError;
-  
-  it('should have a message', function() {
+
+  it('should have a message', function () {
     var err = new DepGraphCycleError(['a', 'b', 'c', 'a']);
@@ -415,9 +440,9 @@ expect(err.message).toEqual('Dependency Cycle Found: a -> b -> c -> a');
 
-  it('should be an instanceof DepGraphCycleError', function() {
+  it('should be an instanceof DepGraphCycleError', function () {
     var err = new DepGraphCycleError(['a', 'b', 'c', 'a']);
-    expect(err instanceof DepGraphCycleError).toBe(true);
-    expect(err instanceof Error).toBe(true);
+    expect(err instanceof DepGraphCycleError).toBeTrue();
+    expect(err instanceof Error).toBeTrue();
   });
 
-  it('should have a cyclePath', function() {
+  it('should have a cyclePath', function () {
     var cyclePath = ['a', 'b', 'c', 'a'];
@@ -424,0 +449,0 @@ var err = new DepGraphCycleError(cyclePath);

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

31301

increased by4.32%

Lines of code

673

increased by4.99%

No dependency changes