Socket
Socket
Sign inDemoInstall

dependency-graph

Package Overview
Dependencies
0
Maintainers
1
Versions
19
Alerts
File Explorer

Advanced tools

npm Scripts

Install Socket

Detect and block malicious and high-risk dependencies

Install

Comparing version 0.8.1 to 0.9.0

10

CHANGELOG.md
# Dependency Graph Changelog
## 0.9.0 (February 10, 2020)
- Rewrite the topological sort DFS to be more efficient (and work!) on large graphs.
- No longer uses recursion to avoid stack overflows with large/deep graphs
- No longer is accidentally `O(N^2)` (thanks [willtennien](https://github.com/willtennien) for pointing this out!)
## 0.8.1 (December 3, 2019)

@@ -49,4 +55,4 @@

- 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)
- 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.

@@ -53,0 +59,0 @@

165

lib/dep_graph.js

@@ -6,6 +6,6 @@ /**

/**
* Helper for creating a Depth-First-Search on
* a set of edges.
* Helper for creating a Topological Sort using Depth-First-Search on a set of edges.
*
* Detects cycles and throws an Error if one is detected.
* Detects cycles and throws an Error if one is detected (unless the "circular"
* parameter is "true" in which case it ignores them).
*

@@ -18,20 +18,49 @@ * @param edges The set of edges to DFS through

function createDFS(edges, leavesOnly, result, circular) {
var currentPath = [];
var visited = {};
return function DFS(currentNode) {
visited[currentNode] = true;
currentPath.push(currentNode);
edges[currentNode].forEach(function (node) {
if (!visited[node]) {
DFS(node);
} else if (currentPath.indexOf(node) >= 0) {
currentPath.push(node);
if (!circular) {
return function(start) {
if (visited[start]) {
return;
}
var inCurrentPath = {};
var currentPath = [];
var todo = []; // used as a stack
todo.push({ node: start, processed: false });
while (todo.length > 0) {
var current = todo[todo.length - 1]; // peek at the todo stack
var processed = current.processed;
var node = current.node;
if (!processed) {
// Haven't visited edges yet (visiting phase)
if (visited[node]) {
todo.pop();
continue;
} else if (inCurrentPath[node]) {
// It's not a DAG
if (circular) {
todo.pop();
// If we're tolerating cycles, don't revisit the node
continue;
}
currentPath.push(node);
throw new DepGraphCycleError(currentPath);
}
inCurrentPath[node] = true;
currentPath.push(node);
var nodeEdges = edges[node];
// (push edges onto the todo stack in reverse order to be order-compatible with the old DFS implementation)
for (var i = nodeEdges.length - 1; i >= 0; i--) {
todo.push({ node: nodeEdges[i], processed: false });
}
current.processed = true;
} else {
// Have visited edges (stack unrolling phase)
todo.pop();
currentPath.pop();
inCurrentPath[node] = false;
visited[node] = true;
if (!leavesOnly || edges[node].length === 0) {
result.push(node);
}
}
});
currentPath.pop();
if ((!leavesOnly || edges[currentNode].length === 0) && result.indexOf(currentNode) === -1) {
result.push(currentNode);
}

@@ -44,3 +73,3 @@ };

*/
var DepGraph = exports.DepGraph = function DepGraph(opts) {
var DepGraph = (exports.DepGraph = function DepGraph(opts) {
this.nodes = {}; // Node -> Node/Data (treated like a Set)

@@ -50,3 +79,3 @@ this.outgoingEdges = {}; // Node -> [Dependency Node]

this.circular = opts && !!opts.circular; // Allows circular deps
};
});
DepGraph.prototype = {

@@ -56,3 +85,3 @@ /**

*/
size: function () {
size: function() {
return Object.keys(this.nodes).length;

@@ -63,3 +92,3 @@ },

*/
addNode: function (node, data) {
addNode: function(node, data) {
if (!this.hasNode(node)) {

@@ -79,3 +108,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)) {

@@ -85,4 +114,4 @@ delete this.nodes[node];

delete this.incomingEdges[node];
[this.incomingEdges, this.outgoingEdges].forEach(function (edgeList) {
Object.keys(edgeList).forEach(function (key) {
[this.incomingEdges, this.outgoingEdges].forEach(function(edgeList) {
Object.keys(edgeList).forEach(function(key) {
var idx = edgeList[key].indexOf(node);

@@ -99,3 +128,3 @@ if (idx >= 0) {

*/
hasNode: function (node) {
hasNode: function(node) {
return this.nodes.hasOwnProperty(node);

@@ -106,7 +135,7 @@ },

*/
getNodeData: function (node) {
getNodeData: function(node) {
if (this.hasNode(node)) {
return this.nodes[node];
} else {
throw new Error('Node does not exist: ' + node);
throw new Error("Node does not exist: " + node);
}

@@ -117,7 +146,7 @@ },

*/
setNodeData: function (node, data) {
setNodeData: function(node, data) {
if (this.hasNode(node)) {
this.nodes[node] = data;
} else {
throw new Error('Node does not exist: ' + node);
throw new Error("Node does not exist: " + node);
}

@@ -129,8 +158,8 @@ },

*/
addDependency: function (from, to) {
addDependency: function(from, to) {
if (!this.hasNode(from)) {
throw new Error('Node does not exist: ' + from);
throw new Error("Node does not exist: " + from);
}
if (!this.hasNode(to)) {
throw new Error('Node does not exist: ' + to);
throw new Error("Node does not exist: " + to);
}

@@ -148,3 +177,3 @@ if (this.outgoingEdges[from].indexOf(to) === -1) {

*/
removeDependency: function (from, to) {
removeDependency: function(from, to) {
var idx;

@@ -169,7 +198,7 @@ if (this.hasNode(from)) {

*/
clone: function () {
clone: function() {
var source = this;
var result = new DepGraph();
var keys = Object.keys(source.nodes);
keys.forEach(function (n) {
keys.forEach(function(n) {
result.nodes[n] = source.nodes[n];

@@ -189,6 +218,11 @@ result.outgoingEdges[n] = source.outgoingEdges[n].slice(0);

*/
dependenciesOf: function (node, leavesOnly) {
dependenciesOf: function(node, leavesOnly) {
if (this.hasNode(node)) {
var result = [];
var DFS = createDFS(this.outgoingEdges, leavesOnly, result, this.circular);
var DFS = createDFS(
this.outgoingEdges,
leavesOnly,
result,
this.circular
);
DFS(node);

@@ -200,6 +234,5 @@ var idx = result.indexOf(node);

return result;
} else {
throw new Error("Node does not exist: " + node);
}
else {
throw new Error('Node does not exist: ' + node);
}
},

@@ -213,6 +246,11 @@ /**

*/
dependantsOf: function (node, leavesOnly) {
dependantsOf: function(node, leavesOnly) {
if (this.hasNode(node)) {
var result = [];
var DFS = createDFS(this.incomingEdges, leavesOnly, result, this.circular);
var DFS = createDFS(
this.incomingEdges,
leavesOnly,
result,
this.circular
);
DFS(node);

@@ -225,3 +263,3 @@ var idx = result.indexOf(node);

} else {
throw new Error('Node does not exist: ' + node);
throw new Error("Node does not exist: " + node);
}

@@ -236,3 +274,3 @@ },

*/
overallOrder: function (leavesOnly) {
overallOrder: function(leavesOnly) {
var self = this;

@@ -248,3 +286,3 @@ var result = [];

var CycleDFS = createDFS(this.outgoingEdges, false, [], this.circular);
keys.forEach(function (n) {
keys.forEach(function(n) {
CycleDFS(n);

@@ -254,10 +292,17 @@ });

var DFS = createDFS(this.outgoingEdges, leavesOnly, result, this.circular);
var DFS = createDFS(
this.outgoingEdges,
leavesOnly,
result,
this.circular
);
// 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) {
return self.incomingEdges[node].length === 0;
}).forEach(function (n) {
DFS(n);
});
keys
.filter(function(node) {
return self.incomingEdges[node].length === 0;
})
.forEach(function(n) {
DFS(n);
});

@@ -268,7 +313,9 @@ // If we're allowing cycles - we need to run the DFS against any remaining

if (this.circular) {
keys.filter(function (node) {
return result.indexOf(node) === -1;
}).forEach(function (n) {
DFS(n);
});
keys
.filter(function(node) {
return result.indexOf(node) === -1;
})
.forEach(function(n) {
DFS(n);
});
}

@@ -284,4 +331,4 @@

*/
var DepGraphCycleError = exports.DepGraphCycleError = function (cyclePath) {
var message = 'Dependency Cycle Found: ' + cyclePath.join(' -> ')
var DepGraphCycleError = (exports.DepGraphCycleError = function(cyclePath) {
var message = "Dependency Cycle Found: " + cyclePath.join(" -> ");
var instance = new Error(message);

@@ -294,3 +341,3 @@ instance.cyclePath = cyclePath;

return instance;
}
});
DepGraphCycleError.prototype = Object.create(Error.prototype, {

@@ -297,0 +344,0 @@ constructor: {

2

package.json
{
"name": "dependency-graph",
"description": "Simple dependency graph.",
"version": "0.8.1",
"version": "0.9.0",
"author": "Jim Riecken <jriecken@gmail.com>",

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

533

specs/dep_graph_spec.js

@@ -1,22 +0,21 @@

var dep_graph = require('../lib/dep_graph');
var dep_graph = require("../lib/dep_graph");
var DepGraph = dep_graph.DepGraph;
describe('DepGraph', function () {
it('should be able to add/remove nodes', function () {
describe("DepGraph", function() {
it("should be able to add/remove nodes", function() {
var graph = new DepGraph();
graph.addNode('Foo');
graph.addNode('Bar');
graph.addNode("Foo");
graph.addNode("Bar");
expect(graph.hasNode('Foo')).toBeTrue();
expect(graph.hasNode('Bar')).toBeTrue();
expect(graph.hasNode('NotThere')).toBeFalse();
expect(graph.hasNode("Foo")).toBeTrue();
expect(graph.hasNode("Bar")).toBeTrue();
expect(graph.hasNode("NotThere")).toBeFalse();
graph.removeNode('Bar');
graph.removeNode("Bar");
expect(graph.hasNode('Bar')).toBeFalse();
expect(graph.hasNode("Bar")).toBeFalse();
});
it('should calculate its size', function () {
it("should calculate its size", function() {
var graph = new DepGraph();

@@ -26,8 +25,8 @@

graph.addNode('Foo');
graph.addNode('Bar');
graph.addNode("Foo");
graph.addNode("Bar");
expect(graph.size()).toBe(2);
graph.removeNode('Bar');
graph.removeNode("Bar");

@@ -37,305 +36,322 @@ expect(graph.size()).toBe(1);

it('should treat the node data parameter as optional and use the node name as data if node data was not given', function () {
it("should treat the node data parameter as optional and use the node name as data if node data was not given", function() {
var graph = new DepGraph();
graph.addNode('Foo');
graph.addNode("Foo");
expect(graph.getNodeData('Foo')).toBe('Foo');
expect(graph.getNodeData("Foo")).toBe("Foo");
});
it('should be able to associate a node name with data on node add', function () {
it("should be able to associate a node name with data on node add", function() {
var graph = new DepGraph();
graph.addNode('Foo', 'data');
graph.addNode("Foo", "data");
expect(graph.getNodeData('Foo')).toBe('data');
expect(graph.getNodeData("Foo")).toBe("data");
});
it('should be able to add undefined as node data', function () {
it("should be able to add undefined as node data", function() {
var graph = new DepGraph();
graph.addNode('Foo', undefined);
graph.addNode("Foo", undefined);
expect(graph.getNodeData('Foo')).toBeUndefined();
expect(graph.getNodeData("Foo")).toBeUndefined();
});
it('should return true when using hasNode with a node which has falsy data', function () {
it("should return true when using hasNode with a node which has falsy data", function() {
var graph = new DepGraph();
var falsyData = ['', 0, null, undefined, false];
graph.addNode('Foo');
var falsyData = ["", 0, null, undefined, false];
graph.addNode("Foo");
falsyData.forEach(function (data) {
graph.setNodeData('Foo', data);
falsyData.forEach(function(data) {
graph.setNodeData("Foo", data);
expect(graph.hasNode('Foo')).toBeTrue();
expect(graph.hasNode("Foo")).toBeTrue();
// Just an extra check to make sure that the saved data is correct
expect(graph.getNodeData('Foo')).toBe(data);
expect(graph.getNodeData("Foo")).toBe(data);
});
});
it('should be able to set data after a node was added', function () {
it("should be able to set data after a node was added", function() {
var graph = new DepGraph();
graph.addNode('Foo', 'data');
graph.setNodeData('Foo', 'data2');
graph.addNode("Foo", "data");
graph.setNodeData("Foo", "data2");
expect(graph.getNodeData('Foo')).toBe('data2');
expect(graph.getNodeData("Foo")).toBe("data2");
});
it('should throw an error if we try to set data for a non-existing node', function () {
it("should throw an error if we try to set data for a non-existing node", function() {
var graph = new DepGraph();
expect(function () {
graph.setNodeData('Foo', 'data');
}).toThrow(new Error('Node does not exist: Foo'));
expect(function() {
graph.setNodeData("Foo", "data");
}).toThrow(new Error("Node does not exist: Foo"));
});
it('should throw an error if the node does not exists and we try to get data', function () {
it("should throw an error if the node does not exists and we try to get data", function() {
var graph = new DepGraph();
expect(function () {
graph.getNodeData('Foo');
}).toThrow(new Error('Node does not exist: Foo'));
expect(function() {
graph.getNodeData("Foo");
}).toThrow(new Error("Node does not exist: Foo"));
});
it('should do nothing if creating a node that already exists', function () {
it("should do nothing if creating a node that already exists", function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode("a");
graph.addNode("b");
graph.addDependency('a', 'b');
graph.addDependency("a", "b");
graph.addNode('a');
graph.addNode("a");
expect(graph.dependenciesOf('a')).toEqual(['b']);
expect(graph.dependenciesOf("a")).toEqual(["b"]);
});
it('should do nothing if removing a node that does not exist', function () {
it("should do nothing if removing a node that does not exist", function() {
var graph = new DepGraph();
graph.addNode('a');
expect(graph.hasNode('a')).toBeTrue();
graph.addNode("a");
expect(graph.hasNode("a")).toBeTrue();
graph.removeNode('a');
expect(graph.hasNode('Foo')).toBeFalse();
graph.removeNode("a");
expect(graph.hasNode("Foo")).toBeFalse();
graph.removeNode('a');
expect(graph.hasNode('Foo')).toBeFalse();
graph.removeNode("a");
expect(graph.hasNode("Foo")).toBeFalse();
});
it('should be able to add dependencies between nodes', function () {
it("should be able to add dependencies between nodes", function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');
graph.addNode("a");
graph.addNode("b");
graph.addNode("c");
graph.addDependency('a', 'b');
graph.addDependency('a', 'c');
graph.addDependency("a", "b");
graph.addDependency("a", "c");
expect(graph.dependenciesOf('a')).toEqual(['b', 'c']);
expect(graph.dependenciesOf("a")).toEqual(["b", "c"]);
});
it('should throw an error if a node does not exist and a dependency is added', function () {
it("should throw an error if a node does not exist and a dependency is added", function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode("a");
expect(function () {
graph.addDependency('a', 'b');
}).toThrow(new Error('Node does not exist: b'));
expect(function() {
graph.addDependency("a", "b");
}).toThrow(new Error("Node does not exist: b"));
});
it('should detect cycles', function () {
it("should detect cycles", function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');
graph.addNode('d');
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');
graph.addDependency("a", "b");
graph.addDependency("b", "c");
graph.addDependency("c", "a");
graph.addDependency("d", "a");
expect(function () {
graph.dependenciesOf('b');
}).toThrow(new dep_graph.DepGraphCycleError(['b', 'c', 'a', 'b']));
expect(function() {
graph.dependenciesOf("b");
}).toThrow(new dep_graph.DepGraphCycleError(["b", "c", "a", "b"]));
});
it('should allow cycles when configured', function () {
it("should allow cycles when configured", function() {
var graph = new DepGraph({ circular: true });
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');
graph.addNode('d');
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');
graph.addDependency("a", "b");
graph.addDependency("b", "c");
graph.addDependency("c", "a");
graph.addDependency("d", "a");
expect(graph.dependenciesOf('b')).toEqual(['a', 'c']);
expect(graph.overallOrder()).toEqual(['c', 'b', 'a', 'd']);
expect(graph.dependenciesOf("b")).toEqual(["a", "c"]);
expect(graph.overallOrder()).toEqual(["c", "b", "a", "d"]);
});
it('should include all nodes in overall order even from ' +
'cycles in disconnected subgraphs when circular is true', function () {
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("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.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');
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']);
});
expect(graph.overallOrder()).toEqual([
"1d",
"1c",
"1b",
"1a",
"1e",
"2c",
"2b",
"2a"
]);
}
);
it('should detect cycles in overall order', function () {
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.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');
graph.addDependency("a", "b");
graph.addDependency("b", "c");
graph.addDependency("c", "a");
graph.addDependency("d", "a");
expect(function () {
expect(function() {
graph.overallOrder();
}).toThrow(new dep_graph.DepGraphCycleError(['a', 'b', 'c', 'a']));
}).toThrow(new dep_graph.DepGraphCycleError(["a", "b", "c", "a"]));
});
it('should detect cycles in overall order when all nodes have dependants (incoming edges)', function () {
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.addNode("a");
graph.addNode("b");
graph.addNode("c");
graph.addDependency('a', 'b');
graph.addDependency('b', 'c');
graph.addDependency('c', 'a');
graph.addDependency("a", "b");
graph.addDependency("b", "c");
graph.addDependency("c", "a");
expect(function () {
expect(function() {
graph.overallOrder();
}).toThrow(new dep_graph.DepGraphCycleError(['a', 'b', 'c', 'a']));
}).toThrow(new dep_graph.DepGraphCycleError(["a", "b", "c", "a"]));
});
it('should detect cycles in overall order when there are several ' +
'disconnected subgraphs (with one that does not have a cycle', function () {
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.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 () {
expect(function() {
graph.overallOrder();
}).toThrow(new dep_graph.DepGraphCycleError(['b_1', 'b_2', 'b_3', 'b_1']));
});
}).toThrow(
new dep_graph.DepGraphCycleError(["b_1", "b_2", "b_3", "b_1"])
);
}
);
it('should retrieve dependencies and dependants in the correct order', function () {
it("should retrieve dependencies and dependants in the correct order", function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');
graph.addNode('d');
graph.addNode("a");
graph.addNode("b");
graph.addNode("c");
graph.addNode("d");
graph.addDependency('a', 'd');
graph.addDependency('a', 'b');
graph.addDependency('b', 'c');
graph.addDependency('d', 'b');
graph.addDependency("a", "d");
graph.addDependency("a", "b");
graph.addDependency("b", "c");
graph.addDependency("d", "b");
expect(graph.dependenciesOf('a')).toEqual(['c', 'b', 'd']);
expect(graph.dependenciesOf('b')).toEqual(['c']);
expect(graph.dependenciesOf('c')).toEqual([]);
expect(graph.dependenciesOf('d')).toEqual(['c', 'b']);
expect(graph.dependenciesOf("a")).toEqual(["c", "b", "d"]);
expect(graph.dependenciesOf("b")).toEqual(["c"]);
expect(graph.dependenciesOf("c")).toEqual([]);
expect(graph.dependenciesOf("d")).toEqual(["c", "b"]);
expect(graph.dependantsOf('a')).toEqual([]);
expect(graph.dependantsOf('b')).toEqual(['a', 'd']);
expect(graph.dependantsOf('c')).toEqual(['a', 'd', 'b']);
expect(graph.dependantsOf('d')).toEqual(['a']);
expect(graph.dependantsOf("a")).toEqual([]);
expect(graph.dependantsOf("b")).toEqual(["a", "d"]);
expect(graph.dependantsOf("c")).toEqual(["a", "d", "b"]);
expect(graph.dependantsOf("d")).toEqual(["a"]);
});
it('should be able to resolve the overall order of things', function () {
it("should be able to resolve the overall order of things", function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');
graph.addNode('d');
graph.addNode('e');
graph.addNode("a");
graph.addNode("b");
graph.addNode("c");
graph.addNode("d");
graph.addNode("e");
graph.addDependency('a', 'b');
graph.addDependency('a', 'c');
graph.addDependency('b', 'c');
graph.addDependency('c', 'd');
graph.addDependency("a", "b");
graph.addDependency("a", "c");
graph.addDependency("b", "c");
graph.addDependency("c", "d");
expect(graph.overallOrder()).toEqual(['d', 'c', 'b', 'a', 'e']);
expect(graph.overallOrder()).toEqual(["d", "c", "b", "a", "e"]);
});
it('should be able to only retrieve the "leaves" in the overall order', function () {
it('should be able to only retrieve the "leaves" in the overall order', function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');
graph.addNode('d');
graph.addNode('e');
graph.addNode("a");
graph.addNode("b");
graph.addNode("c");
graph.addNode("d");
graph.addNode("e");
graph.addDependency('a', 'b');
graph.addDependency('a', 'c');
graph.addDependency('b', 'c');
graph.addDependency('c', 'd');
graph.addDependency("a", "b");
graph.addDependency("a", "c");
graph.addDependency("b", "c");
graph.addDependency("c", "d");
expect(graph.overallOrder(true)).toEqual(['d', 'e']);
expect(graph.overallOrder(true)).toEqual(["d", "e"]);
});
it('should be able to give the overall order for a graph with several disconnected subgraphs', function () {
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.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("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']);
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 () {
it("should give an empty overall order for an empty graph", function() {
var graph = new DepGraph();

@@ -346,19 +362,19 @@

it('should still work after nodes are removed', function () {
it("should still work after nodes are removed", function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');
graph.addDependency('a', 'b');
graph.addDependency('b', 'c');
graph.addNode("a");
graph.addNode("b");
graph.addNode("c");
graph.addDependency("a", "b");
graph.addDependency("b", "c");
expect(graph.dependenciesOf('a')).toEqual(['c', 'b']);
expect(graph.dependenciesOf("a")).toEqual(["c", "b"]);
graph.removeNode('c');
graph.removeNode("c");
expect(graph.dependenciesOf('a')).toEqual(['b']);
expect(graph.dependenciesOf("a")).toEqual(["b"]);
});
it('should clone an empty graph', function () {
it("should clone an empty graph", function() {
var graph = new DepGraph();

@@ -372,10 +388,10 @@ expect(graph.size()).toEqual(0);

it('should clone a non-empty graph', function () {
it("should clone a non-empty graph", function() {
var graph = new DepGraph();
graph.addNode('a');
graph.addNode('b');
graph.addNode('c');
graph.addDependency('a', 'b');
graph.addDependency('b', 'c');
graph.addNode("a");
graph.addNode("b");
graph.addNode("c");
graph.addDependency("a", "b");
graph.addDependency("b", "c");

@@ -385,48 +401,89 @@ var cloned = graph.clone();

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']);
expect(cloned.dependantsOf('c')).toEqual(['a', 'b']);
expect(cloned.hasNode("a")).toBeTrue();
expect(cloned.hasNode("b")).toBeTrue();
expect(cloned.hasNode("c")).toBeTrue();
expect(cloned.dependenciesOf("a")).toEqual(["c", "b"]);
expect(cloned.dependantsOf("c")).toEqual(["a", "b"]);
// Changes to the original graph shouldn't affect the clone
graph.removeNode('c');
expect(graph.dependenciesOf('a')).toEqual(['b']);
expect(cloned.dependenciesOf('a')).toEqual(['c', 'b']);
graph.removeNode("c");
expect(graph.dependenciesOf("a")).toEqual(["b"]);
expect(cloned.dependenciesOf("a")).toEqual(["c", "b"]);
graph.addNode('d');
graph.addDependency('b', 'd');
expect(graph.dependenciesOf('a')).toEqual(['d', 'b']);
expect(cloned.dependenciesOf('a')).toEqual(['c', 'b']);
graph.addNode("d");
graph.addDependency("b", "d");
expect(graph.dependenciesOf("a")).toEqual(["d", "b"]);
expect(cloned.dependenciesOf("a")).toEqual(["c", "b"]);
});
it('should only be a shallow clone', function () {
it("should only be a shallow clone", function() {
var graph = new DepGraph();
var data = { a: 42 };
graph.addNode('a', data);
graph.addNode("a", data);
var cloned = graph.clone();
expect(graph === cloned).toBeFalse();
expect(graph.getNodeData('a') === cloned.getNodeData('a')).toBeTrue();
expect(graph.getNodeData("a") === cloned.getNodeData("a")).toBeTrue();
graph.getNodeData('a').a = 43;
expect(cloned.getNodeData('a').a).toBe(43);
graph.getNodeData("a").a = 43;
expect(cloned.getNodeData("a").a).toBe(43);
cloned.setNodeData('a', { a: 42 });
expect(cloned.getNodeData('a').a).toBe(42);
expect(graph.getNodeData('a') === cloned.getNodeData('a')).toBeFalse();
cloned.setNodeData("a", { a: 42 });
expect(cloned.getNodeData("a").a).toBe(42);
expect(graph.getNodeData("a") === cloned.getNodeData("a")).toBeFalse();
});
});
describe('DepGraphCycleError', function () {
describe("DepGraph Performance", function() {
it("should not exceed max call stack with a very deep graph", function() {
var g = new DepGraph();
var expected = [];
for (var i = 0; i < 100000; i++) {
var istr = i.toString();
g.addNode(istr);
expected.push(istr);
if (i > 0) {
g.addDependency(istr, (i - 1).toString());
}
}
var order = g.overallOrder();
expect(order).toEqual(expected);
});
it("should run an a reasonable amount of time for a very large graph", function() {
var randInt = function(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
};
var g = new DepGraph();
var nodes = [];
// Create a graph with 100000 nodes in it with 10 random connections to
// lower numbered nodes
for (var i = 0; i < 100000; i++) {
nodes.push(i.toString());
g.addNode(i.toString());
for (var j = 0; j < 10; j++) {
var dep = randInt(0, i);
if (i !== dep) {
g.addDependency(i.toString(), dep.toString());
}
}
}
var start = new Date().getTime();
g.overallOrder();
var end = new Date().getTime();
expect(start - end).toBeLessThan(1000);
});
});
describe("DepGraphCycleError", function() {
var DepGraphCycleError = dep_graph.DepGraphCycleError;
it('should have a message', function () {
var err = new DepGraphCycleError(['a', 'b', 'c', 'a']);
expect(err.message).toEqual('Dependency Cycle Found: a -> b -> c -> a');
it("should have a message", function() {
var err = new DepGraphCycleError(["a", "b", "c", "a"]);
expect(err.message).toEqual("Dependency Cycle Found: a -> b -> c -> a");
});
it('should be an instanceof DepGraphCycleError', function () {
var err = new DepGraphCycleError(['a', 'b', 'c', 'a']);
it("should be an instanceof DepGraphCycleError", function() {
var err = new DepGraphCycleError(["a", "b", "c", "a"]);
expect(err instanceof DepGraphCycleError).toBeTrue();

@@ -436,4 +493,4 @@ expect(err instanceof Error).toBeTrue();

it('should have a cyclePath', function () {
var cyclePath = ['a', 'b', 'c', 'a'];
it("should have a cyclePath", function() {
var cyclePath = ["a", "b", "c", "a"];
var err = new DepGraphCycleError(cyclePath);

@@ -440,0 +497,0 @@ expect(err.cyclePath).toEqual(cyclePath);

LICENSE

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

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

About

Packages

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc