dependency-graph
Advanced tools
Comparing version 0.3.0 to 0.4.0
@@ -7,2 +7,9 @@ # Dependency Graph Changelog | ||
## 0.4.0 (Augh 1, 2015) | ||
- Better error messages | ||
- 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) | ||
- When calling `addDependency` if one of the nodes does not exist, the error will say which one it was (instead of saying that "one" of the two nodes did not exist and making you manually determine which one) | ||
- Calling `overallOrder` on an empty graph will no longer throw an error about a dependency cycle. It will return an empty array. | ||
## 0.3.0 (July 24, 2015) | ||
@@ -9,0 +16,0 @@ |
@@ -9,3 +9,3 @@ /** | ||
* | ||
* Detects cycles and throws an Error if one is detected | ||
* Detects cycles and throws an Error if one is detected. | ||
* | ||
@@ -17,15 +17,16 @@ * @param edges The set of edges to DFS through | ||
function createDFS(edges, leavesOnly, result) { | ||
var chain = {}; | ||
var currentPath = []; | ||
var visited = {}; | ||
return function DFS(name) { | ||
visited[name] = true; | ||
chain[name] = true; | ||
currentPath.push(name); | ||
edges[name].forEach(function (edgeName) { | ||
if (!visited[edgeName]) { | ||
DFS(edgeName); | ||
} else if (chain[edgeName]) { | ||
throw new Error('Dependency Cycle Found: ' + edgeName); | ||
} else if (currentPath.indexOf(edgeName) >= 0) { | ||
currentPath.push(edgeName); | ||
throw new Error('Dependency Cycle Found: ' + currentPath.join(' -> ')); | ||
} | ||
}); | ||
chain[name] = false; | ||
currentPath.pop(); | ||
if ((!leavesOnly || edges[name].length === 0) && result.indexOf(name) === -1) { | ||
@@ -87,13 +88,15 @@ result.push(name); | ||
addDependency:function (from, to) { | ||
if (this.hasNode(from) && this.hasNode(to)) { | ||
if (this.outgoingEdges[from].indexOf(to) === -1) { | ||
this.outgoingEdges[from].push(to); | ||
} | ||
if (this.incomingEdges[to].indexOf(from) === -1) { | ||
this.incomingEdges[to].push(from); | ||
} | ||
return true; | ||
} else { | ||
throw new Error('One of the nodes does not exist: ' + from + ', ' + to); | ||
if (!this.hasNode(from)) { | ||
throw new Error('Node does not exist: ' + from); | ||
} | ||
if (!this.hasNode(to)) { | ||
throw new Error('Node does not exist: ' + to); | ||
} | ||
if (this.outgoingEdges[from].indexOf(to) === -1) { | ||
this.outgoingEdges[from].push(to); | ||
} | ||
if (this.incomingEdges[to].indexOf(from) === -1) { | ||
this.incomingEdges[to].push(from); | ||
} | ||
return true; | ||
}, | ||
@@ -166,13 +169,18 @@ /** | ||
var keys = Object.keys(this.nodes); | ||
keys.filter(function (node) { | ||
return self.incomingEdges[node].length === 0; | ||
}).forEach(function (n) { | ||
DFS(n); | ||
}); | ||
if (keys.length > 0 && result.length === 0) { | ||
// Special case when there are no nodes with no dependants | ||
throw new Error('Dependency Cycle Found'); | ||
if (keys.length === 0) { | ||
return result; // Empty graph | ||
} else { | ||
keys.filter(function (node) { | ||
return self.incomingEdges[node].length === 0; | ||
}).forEach(function (n) { | ||
DFS(n); | ||
}); | ||
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; | ||
} | ||
return result; | ||
} | ||
}; |
{ | ||
"name": "dependency-graph", | ||
"description": "Simple dependency graph.", | ||
"version": "0.3.0", | ||
"version": "0.4.0", | ||
"author": "Jim Riecken <jriecken@gmail.com>", | ||
@@ -6,0 +6,0 @@ "keywords": [ |
@@ -26,2 +26,4 @@ # Dependency Graph | ||
Dependency Cycles are detected when running `dependenciesOf`, `dependantsOf`, and `overallOrder` and if one is found, an error will be thrown that includes what the cycle was in the message: e.g. `Dependency Cycle Found: a -> b -> c -> a`. | ||
## Examples | ||
@@ -28,0 +30,0 @@ |
@@ -66,3 +66,3 @@ var DepGraph = require('../lib/dep_graph').DepGraph; | ||
graph.addDependency('a','b'); | ||
}).toThrow(); | ||
}).toThrow(new Error('Node does not exist: b')); | ||
}); | ||
@@ -76,2 +76,3 @@ | ||
graph.addNode('c'); | ||
graph.addNode('d'); | ||
@@ -81,8 +82,43 @@ graph.addDependency('a', 'b'); | ||
graph.addDependency('c', 'a'); | ||
graph.addDependency('d', 'a'); | ||
expect(function () { | ||
graph.dependenciesOf('a'); | ||
}).toThrow(); | ||
graph.dependenciesOf('b'); | ||
}).toThrow(new Error('Dependency Cycle Found: b -> c -> a -> b')); | ||
}); | ||
it('should detect cycles in overall order', function () { | ||
var graph = new DepGraph(); | ||
graph.addNode('a'); | ||
graph.addNode('b'); | ||
graph.addNode('c'); | ||
graph.addNode('d'); | ||
graph.addDependency('a', 'b'); | ||
graph.addDependency('b', 'c'); | ||
graph.addDependency('c', 'a'); | ||
graph.addDependency('d', 'a'); | ||
expect(function () { | ||
graph.overallOrder(); | ||
}).toThrow(new Error('Dependency Cycle Found: d -> a -> b -> c -> a')); | ||
}); | ||
it('should detect cycles in overall order when all nodes have dependants (incoming edges)', function () { | ||
var graph = new DepGraph(); | ||
graph.addNode('a'); | ||
graph.addNode('b'); | ||
graph.addNode('c'); | ||
graph.addDependency('a', 'b'); | ||
graph.addDependency('b', 'c'); | ||
graph.addDependency('c', 'a'); | ||
expect(function () { | ||
graph.overallOrder(); | ||
}).toThrow(new Error('Dependency Cycle Found: a -> b -> c -> a')); | ||
}); | ||
it('should retrieve dependencies and dependants in the correct order', function () { | ||
@@ -146,2 +182,8 @@ var graph = new DepGraph(); | ||
it('should give an empty overall order for an empty graph', function () { | ||
var graph = new DepGraph(); | ||
expect(graph.overallOrder()).toEqual([]); | ||
}); | ||
it('should still work after nodes are removed', function () { | ||
@@ -148,0 +190,0 @@ var graph = new DepGraph(); |
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
15674
324
45