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.4.0 to 0.4.1

6

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)

30

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;
}
}
},
};
{
"name": "dependency-graph",
"description": "Simple dependency graph.",
"version": "0.4.0",
"version": "0.4.1",
"author": "Jim Riecken <jriecken@gmail.com>",

@@ -6,0 +6,0 @@ "keywords": [

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

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