Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

dependency-graph

Package Overview
Dependencies
Maintainers
1
Versions
19
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

dependency-graph - npm Package Compare versions

Comparing version 0.3.0 to 0.4.0

7

CHANGELOG.md

@@ -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 @@

58

lib/dep_graph.js

@@ -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();

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc