dependency-graph - npm Package Compare versions

Comparing version 0.4.0 to 0.4.1

CHANGELOG.md

@@ -7,4 +7,8 @@ # Dependency Graph Changelog
 
-## 0.4.0 (Augh 1, 2015)
+## 0.4.1 (Sept 3, 2015)
 
+- Check all nodes for potential cycles when calculating overall order. (Fixes #8)
+
+## 0.4.0 (Aug 1, 2015)
+
 - Better error messages
@@ -11,0 +15,0 @@ - When a cycle is detected, the error message will now include the cycle in it. E.g `Dependency Cycle Found: a -> b -> c -> a` (Fixes #7)

lib/dep_graph.js

@@ -121,2 +121,5 @@ /**
    * Get an array containing the nodes that the specified node depends on (transitively).
+   *
+   * Throws an Error if the graph has a cycle, or the specified node does not exist.
+   *
    * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned
@@ -142,2 +145,5 @@ * in the array.
    * get an array containing the nodes that depend on the specified node (transitively).
+   *
+   * Throws an Error if the graph has a cycle, or the specified node does not exist.
+   *
    * If `leavesOnly` is true, only nodes that do not have any dependants will be returned in the array.
@@ -161,2 +167,5 @@ */
    * Construct the overall processing order for the dependency graph.
+   *
+   * Throws an Error if the graph has a cycle.
+   *
    * If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned.
@@ -167,3 +176,2 @@ */
     var result = [];
-    var DFS = createDFS(this.outgoingEdges, leavesOnly, result);
     var keys = Object.keys(this.nodes);
@@ -173,2 +181,12 @@ if (keys.length === 0) {
     } 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, []);
+      keys.forEach(function(n) {
+        CycleDFS(n);
+      });
+
+      var DFS = createDFS(this.outgoingEdges, leavesOnly, result);
+      // Find all potential starting points (nodes with nothing depending on them) an
+      // run a DFS starting at these points to get the order
       keys.filter(function (node) {
@@ -179,10 +197,8 @@ return self.incomingEdges[node].length === 0;
       });
-      if (result.length === 0) {
-        // There's definitely a cycle somewhere - run the DFS on the first node
-        // so that it constructs the cycle and reports it.
-        DFS(keys[0]);
-      }
+
       return result;
     }
-  }
+  },
+
+
 };

package.json

 {
   "name": "dependency-graph",
   "description": "Simple dependency graph.",
-  "version": "0.4.0",
+  "version": "0.4.1",
   "author": "Jim Riecken <[e-mail]>",
@@ -6,0 +6,0 @@ "keywords": [

specs/dep_graph_spec.js

@@ -102,3 +102,3 @@ var DepGraph = require('../lib/dep_graph').DepGraph;
       graph.overallOrder();
-    }).toThrow(new Error('Dependency Cycle Found: d -> a -> b -> c -> a'));
+    }).toThrow(new Error('Dependency Cycle Found: a -> b -> c -> a'));
   });
@@ -122,2 +122,22 @@
 
+  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();
+
+    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');
+
+    expect(function () {
+      graph.overallOrder();
+    }).toThrow(new Error('Dependency Cycle Found: b_1 -> b_2 -> b_3 -> b_1'));
+  });
+
   it('should retrieve dependencies and dependants in the correct order', function () {
@@ -181,2 +201,18 @@ var graph = new DepGraph();
 
+  it('should be able to give the overall order for a graph with several disconnected subgraphs', 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.addDependency('a_1', 'a_2');
+    graph.addDependency('b_1', 'b_2');
+    graph.addDependency('b_2', 'b_3');
+
+    expect(graph.overallOrder()).toEqual(['a_2', 'a_1', 'b_3', 'b_2', 'b_1']);
+  });
+
   it('should give an empty overall order for an empty graph', function () {
@@ -183,0 +219,0 @@ var graph = new DepGraph();

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

17350

increased by10.69%

Lines of code

364

increased by12.35%

No dependency changes