diff options
Diffstat (limited to 'node_modules/dependency-graph')
| -rwxr-xr-x | node_modules/dependency-graph/CHANGELOG.md | 63 | ||||
| -rwxr-xr-x | node_modules/dependency-graph/LICENSE | 19 | ||||
| -rwxr-xr-x | node_modules/dependency-graph/README.md | 74 | ||||
| -rwxr-xr-x | node_modules/dependency-graph/lib/dep_graph.js | 244 | ||||
| -rwxr-xr-x | node_modules/dependency-graph/lib/index.d.ts | 89 | ||||
| -rwxr-xr-x | node_modules/dependency-graph/package.json | 67 | ||||
| -rwxr-xr-x | node_modules/dependency-graph/specs/dep_graph_spec.js | 389 |
7 files changed, 945 insertions, 0 deletions
diff --git a/node_modules/dependency-graph/CHANGELOG.md b/node_modules/dependency-graph/CHANGELOG.md new file mode 100755 index 0000000..cdbe3fc --- /dev/null +++ b/node_modules/dependency-graph/CHANGELOG.md @@ -0,0 +1,63 @@ +# Dependency Graph Changelog + +## In development + +- Nothing yet + +## 0.7.2 (August 30, 2018) + +- Make constructor parameter optional in Typescript definition. (Fixes #26) + +## 0.7.1 (June 5, 2018) + +- Fix Typescript definition to include the new constructor arguments added in `0.7.0` - thanks [tbranyen](https://github.com/tbranyen)! + +## 0.7.0 (January 17, 2018) + +- Allow circular dependencies by passing in `{circular: true}` into the constructor - thanks [tbranyen](https://github.com/tbranyen)! + +## 0.6.0 (October 22, 2017) + +- Add a `size` method that will return the number of nodes in the graph. +- Add a `clone` method that will clone the graph. Any custom node data will only be shallow-copied. (Fixes #14) + +## 0.5.2 (October 22, 2017) + +- Add missing parameter in TypeScript definition. (Fixes #19) + +## 0.5.1 (October 7, 2017) + +- Now exposes Typescript type definition - thanks [vangorra](https://github.com/vangorra)! + +## 0.5.0 (April 26, 2016) + +- Add optional data parameter for the addNode method. (Fixes #12) +- Add methods getNodeData and setNodeData to manipulate the data associated with a node name. (Fixes #12) +- Change the hasNode method to be able to cope with falsy node data. (Fixes #12) + +## 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 + - 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) + +- Fix issue where if you call `addNode` twice with the same name, it would clear all edges for that node. Now it will do nothing if a node with the specified name already exists. (Fixes #3) + +## 0.2.1 (July 3, 2015) + +- Fixed removeNode leaving references in outgoingEdges and reference to non-existent var edges - thanks [juhoha](https://github.com/juhoha)! (Fixes #2) + +## 0.2.0 (May 1, 2015) + +- Removed dependency on Underscore - thanks [myndzi](https://github.com/myndzi)! (Fixes #1) + +## 0.1.0 (May 18, 2013) + +- Initial Release - extracted out of asset-smasher diff --git a/node_modules/dependency-graph/LICENSE b/node_modules/dependency-graph/LICENSE new file mode 100755 index 0000000..fa1d24b --- /dev/null +++ b/node_modules/dependency-graph/LICENSE @@ -0,0 +1,19 @@ +Copyright (C) 2013-2015 by Jim Riecken + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE.
\ No newline at end of file diff --git a/node_modules/dependency-graph/README.md b/node_modules/dependency-graph/README.md new file mode 100755 index 0000000..29bdd82 --- /dev/null +++ b/node_modules/dependency-graph/README.md @@ -0,0 +1,74 @@ +# Dependency Graph + +Simple dependency graph + +## Overview + +This is a simple dependency graph useful for determining the order to do a list of things that depend on certain items being done before they are. + +To use, `npm install dependency-graph` and then `require('dependency-graph').DepGraph` + +## API + +### DepGraph + +Nodes in the graph are just simple strings with optional data associated with them. + + - `addNode(name, data)` - add a node in the graph with optional data. If `data` is not given, `name` will be used as data + - `removeNode(name)` - remove a node from the graph + - `hasNode(name)` - check if a node exists in the graph + - `size()` - return the number of nodes in the graph + - `getNodeData(name)` - get the data associated with a node (will throw an Error if the node does not exist) + - `setNodeData(name, data)` - set the data for an existing node (will throw an Error if the node does not exist) + - `addDependency(from, to)` - add a dependency between two nodes (will throw an Error if one of the nodes does not exist) + - `removeDependency(from, to)` - remove a dependency between two nodes + - `clone()` - return a clone of the graph. Any data attached to the nodes will only be *shallow-copied* + - `dependenciesOf(name, leavesOnly)` - get an array containing the nodes that the specified node depends on (transitively). If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned in the array. + - `dependantsOf(name, leavesOnly)` - get an array containing the nodes that depend on the specified node (transitively). If `leavesOnly` is true, only nodes that do not have any dependants will be returned in the array. + - `overallOrder(leavesOnly)` - construct the overall processing order for the dependency graph. If `leavesOnly` is true, only nodes that do not depend on any other nodes will be returned. + +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`. If you wish to silence this error, pass `circular: true` when instantiating `DepGraph` (more below). + +## Examples + + var DepGraph = require('dependency-graph').DepGraph; + + var graph = new DepGraph(); + graph.addNode('a'); + graph.addNode('b'); + graph.addNode('c'); + + graph.size() // 3 + + graph.addDependency('a', 'b'); + graph.addDependency('b', 'c'); + + graph.dependenciesOf('a'); // ['c', 'b'] + graph.dependenciesOf('b'); // ['c'] + graph.dependantsOf('c'); // ['a', 'b'] + + graph.overallOrder(); // ['c', 'b', 'a'] + graph.overallOrder(true); // ['c'] + + graph.addNode('d', 'data'); + + graph.getNodeData('d'); // 'data' + + graph.setNodeData('d', 'newData'); + + graph.getNodeData('d'); // 'newData' + + var circularGraph = new DepGraph({ circular: true }); + + circularGraph.addNode('a'); + circularGraph.addNode('b'); + circularGraph.addNode('c'); + circularGraph.addNode('d'); + + circularGraph.addDependency('a', 'b'); + circularGraph.addDependency('b', 'c'); // b depends on c + circularGraph.addDependency('c', 'a'); // c depends on a, which depends on b + circularGraph.addDependency('d', 'a'); + + circularGraph.dependenciesOf('b'); // ['a', 'c'] + circularGraph.overallOrder(); // ['c', 'b', 'a', 'd'] diff --git a/node_modules/dependency-graph/lib/dep_graph.js b/node_modules/dependency-graph/lib/dep_graph.js new file mode 100755 index 0000000..fb0e5ae --- /dev/null +++ b/node_modules/dependency-graph/lib/dep_graph.js @@ -0,0 +1,244 @@ +/** + * A simple dependency graph + */ + +/** + * Helper for creating a Depth-First-Search on + * a set of edges. + * + * Detects cycles and throws an Error if one is detected. + * + * @param edges The set of edges to DFS through + * @param leavesOnly Whether to only return "leaf" nodes (ones who have no edges) + * @param result An array in which the results will be populated + * @param circular A boolean to allow circular dependencies + */ +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) { + throw new Error('Dependency Cycle Found: ' + currentPath.join(' -> ')); + } + } + }); + currentPath.pop(); + if ((!leavesOnly || edges[currentNode].length === 0) && result.indexOf(currentNode) === -1) { + result.push(currentNode); + } + }; +} + +/** + * Simple Dependency Graph + */ +var DepGraph = exports.DepGraph = function DepGraph(opts) { + this.nodes = {}; // Node -> Node/Data (treated like a Set) + this.outgoingEdges = {}; // Node -> [Dependency Node] + this.incomingEdges = {}; // Node -> [Dependant Node] + this.circular = opts && !!opts.circular; // Allows circular deps +}; +DepGraph.prototype = { + /** + * The number of nodes in the graph. + */ + size:function () { + return Object.keys(this.nodes).length; + }, + /** + * Add a node to the dependency graph. If a node already exists, this method will do nothing. + */ + addNode:function (node, data) { + if (!this.hasNode(node)) { + // Checking the arguments length allows the user to add a node with undefined data + if (arguments.length === 2) { + this.nodes[node] = data; + } else { + this.nodes[node] = node; + } + this.outgoingEdges[node] = []; + this.incomingEdges[node] = []; + } + }, + /** + * Remove a node from the dependency graph. If a node does not exist, this method will do nothing. + */ + removeNode:function (node) { + if (this.hasNode(node)) { + delete this.nodes[node]; + delete this.outgoingEdges[node]; + delete this.incomingEdges[node]; + [this.incomingEdges, this.outgoingEdges].forEach(function (edgeList) { + Object.keys(edgeList).forEach(function (key) { + var idx = edgeList[key].indexOf(node); + if (idx >= 0) { + edgeList[key].splice(idx, 1); + } + }, this); + }); + } + }, + /** + * Check if a node exists in the graph + */ + hasNode:function (node) { + return this.nodes.hasOwnProperty(node); + }, + /** + * Get the data associated with a node name + */ + getNodeData:function (node) { + if (this.hasNode(node)) { + return this.nodes[node]; + } else { + throw new Error('Node does not exist: ' + node); + } + }, + /** + * Set the associated data for a given node name. If the node does not exist, this method will throw an error + */ + setNodeData:function (node, data) { + if (this.hasNode(node)) { + this.nodes[node] = data; + } else { + throw new Error('Node does not exist: ' + node); + } + }, + /** + * Add a dependency between two nodes. If either of the nodes does not exist, + * an Error will be thrown. + */ + addDependency:function (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; + }, + /** + * Remove a dependency between two nodes. + */ + removeDependency:function (from, to) { + var idx; + if (this.hasNode(from)) { + idx = this.outgoingEdges[from].indexOf(to); + if (idx >= 0) { + this.outgoingEdges[from].splice(idx, 1); + } + } + + if (this.hasNode(to)) { + idx = this.incomingEdges[to].indexOf(from); + if (idx >= 0) { + this.incomingEdges[to].splice(idx, 1); + } + } + }, + /** + * Return a clone of the dependency graph. If any custom data is attached + * to the nodes, it will only be shallow copied. + */ + clone:function () { + var source = this; + var result = new DepGraph(); + var keys = Object.keys(source.nodes); + keys.forEach(function (n) { + result.nodes[n] = source.nodes[n]; + result.outgoingEdges[n] = source.outgoingEdges[n].slice(0); + result.incomingEdges[n] = source.incomingEdges[n].slice(0); + }); + return result; + }, + /** + * 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 + * in the array. + */ + dependenciesOf:function (node, leavesOnly) { + if (this.hasNode(node)) { + var result = []; + var DFS = createDFS(this.outgoingEdges, leavesOnly, result, this.circular); + DFS(node); + var idx = result.indexOf(node); + if (idx >= 0) { + result.splice(idx, 1); + } + return result; + } + else { + throw new Error('Node does not exist: ' + node); + } + }, + /** + * 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. + */ + dependantsOf:function (node, leavesOnly) { + if (this.hasNode(node)) { + var result = []; + var DFS = createDFS(this.incomingEdges, leavesOnly, result, this.circular); + DFS(node); + var idx = result.indexOf(node); + if (idx >= 0) { + result.splice(idx, 1); + } + return result; + } else { + throw new Error('Node does not exist: ' + node); + } + }, + /** + * 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. + */ + overallOrder:function (leavesOnly) { + var self = this; + var result = []; + var keys = Object.keys(this.nodes); + if (keys.length === 0) { + return result; // Empty graph + } 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, [], this.circular); + keys.forEach(function(n) { + CycleDFS(n); + }); + + 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); + }); + + return result; + } + } +}; diff --git a/node_modules/dependency-graph/lib/index.d.ts b/node_modules/dependency-graph/lib/index.d.ts new file mode 100755 index 0000000..76aef0a --- /dev/null +++ b/node_modules/dependency-graph/lib/index.d.ts @@ -0,0 +1,89 @@ +declare module 'dependency-graph' { + export interface Options { + circular?: boolean; + } + + export class DepGraph<T> { + /** + * Creates an instance of DepGraph with optional Options. + */ + constructor(opts?: Options); + + /** + * The number of nodes in the graph. + */ + size(): number; + + /** + * Add a node in the graph with optional data. If data is not given, name will be used as data. + * @param {string} name + * @param data + */ + addNode(name: string, data?: T): void; + + /** + * Remove a node from the graph. + * @param {string} name + */ + removeNode(name: string): void; + + /** + * Check if a node exists in the graph. + * @param {string} name + */ + hasNode(name: string): boolean; + + /** + * Get the data associated with a node (will throw an Error if the node does not exist). + * @param {string} name + */ + getNodeData(name: string): T; + + /** + * Set the data for an existing node (will throw an Error if the node does not exist). + * @param {string} name + * @param data + */ + setNodeData(name: string, data?: T): void; + + /** + * Add a dependency between two nodes (will throw an Error if one of the nodes does not exist). + * @param {string} from + * @param {string} to + */ + addDependency(from: string, to: string): void; + + /** + * Remove a dependency between two nodes. + * @param {string} from + * @param {string} to + */ + removeDependency(from: string, to: string): void; + + /** + * Return a clone of the dependency graph (If any custom data is attached + * to the nodes, it will only be shallow copied). + */ + clone(): DepGraph<T>; + + /** + * Get an array containing the nodes that the specified node depends on (transitively). If leavesOnly is true, only nodes that do not depend on any other nodes will be returned in the array. + * @param {string} name + * @param {boolean} leavesOnly + */ + dependenciesOf(name: string, leavesOnly?: boolean): string[]; + + /** + * Get an array containing the nodes that depend on the specified node (transitively). If leavesOnly is true, only nodes that do not have any dependants will be returned in the array. + * @param {string} name + * @param {boolean} leavesOnly + */ + dependantsOf(name: string, leavesOnly?: boolean): string[]; + + /** + * Construct the overall processing order for the dependency graph. If leavesOnly is true, only nodes that do not depend on any other nodes will be returned. + * @param {boolean} leavesOnly + */ + overallOrder(leavesOnly?: boolean): string[]; + } +} diff --git a/node_modules/dependency-graph/package.json b/node_modules/dependency-graph/package.json new file mode 100755 index 0000000..2b94a21 --- /dev/null +++ b/node_modules/dependency-graph/package.json @@ -0,0 +1,67 @@ +{ + "_args": [ + [ + "dependency-graph@0.7.2", + "/home/dstaesse/git/website" + ] + ], + "_development": true, + "_from": "dependency-graph@0.7.2", + "_id": "dependency-graph@0.7.2", + "_inBundle": false, + "_integrity": "sha512-KqtH4/EZdtdfWX0p6MGP9jljvxSY6msy/pRUD4jgNwVpv3v1QmNLlsB3LDSSUg79BRVSn7jI1QPRtArGABovAQ==", + "_location": "/dependency-graph", + "_phantomChildren": {}, + "_requested": { + "type": "version", + "registry": true, + "raw": "dependency-graph@0.7.2", + "name": "dependency-graph", + "escapedName": "dependency-graph", + "rawSpec": "0.7.2", + "saveSpec": null, + "fetchSpec": "0.7.2" + }, + "_requiredBy": [ + "/postcss-cli" + ], + "_resolved": "https://registry.npmjs.org/dependency-graph/-/dependency-graph-0.7.2.tgz", + "_spec": "0.7.2", + "_where": "/home/dstaesse/git/website", + "author": { + "name": "Jim Riecken", + "email": "jriecken@gmail.com" + }, + "bugs": { + "url": "http://github.com/jriecken/dependency-graph/issues" + }, + "dependencies": {}, + "description": "Simple dependency graph.", + "devDependencies": { + "jasmine-node": "2.0.1" + }, + "engines": { + "node": ">= 0.6.0" + }, + "homepage": "https://github.com/jriecken/dependency-graph#readme", + "keywords": [ + "dependency", + "graph" + ], + "license": { + "type": "MIT", + "url": "http://github.com/jriecken/dependency-graph/raw/master/LICENSE" + }, + "main": "./lib/dep_graph.js", + "name": "dependency-graph", + "optionalDependencies": {}, + "repository": { + "type": "git", + "url": "git://github.com/jriecken/dependency-graph.git" + }, + "scripts": { + "test": "jasmine-node specs" + }, + "types": "./lib/index.d.ts", + "version": "0.7.2" +} diff --git a/node_modules/dependency-graph/specs/dep_graph_spec.js b/node_modules/dependency-graph/specs/dep_graph_spec.js new file mode 100755 index 0000000..46d222e --- /dev/null +++ b/node_modules/dependency-graph/specs/dep_graph_spec.js @@ -0,0 +1,389 @@ +var DepGraph = require('../lib/dep_graph').DepGraph; + +describe('DepGraph', function () { + + it('should be able to add/remove nodes', function () { + var graph = new DepGraph(); + + graph.addNode('Foo'); + graph.addNode('Bar'); + + expect(graph.hasNode('Foo')).toBe(true); + expect(graph.hasNode('Bar')).toBe(true); + expect(graph.hasNode('NotThere')).toBe(false); + + graph.removeNode('Bar'); + + expect(graph.hasNode('Bar')).toBe(false); + }); + + it('should calculate its size', function () { + var graph = new DepGraph(); + + expect(graph.size()).toEqual(0); + + graph.addNode('Foo'); + graph.addNode('Bar'); + + expect(graph.size()).toEqual(2); + + graph.removeNode('Bar'); + + expect(graph.size()).toEqual(1); + }); + + 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'); + + expect(graph.getNodeData('Foo')).toBe('Foo'); + }); + + it('should be able to associate a node name with data on node add', function () { + var graph = new DepGraph(); + + graph.addNode('Foo', 'data'); + + expect(graph.getNodeData('Foo')).toBe('data'); + }); + + it('should be able to add undefined as node data', function () { + var graph = new DepGraph(); + + graph.addNode('Foo', undefined); + + expect(graph.getNodeData('Foo')).toBe(undefined); + }); + + 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'); + + falsyData.forEach(function(data) { + graph.setNodeData('Foo', data); + + expect(graph.hasNode('Foo')).toBe(true); + + // Just an extra check to make sure that the saved data is correct + expect(graph.getNodeData('Foo')).toBe(data); + }); + }); + + 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'); + + expect(graph.getNodeData('Foo')).toBe('data2'); + }); + + 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')); + }); + + 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')); + }); + + it('should do nothing if creating a node that already exists', function () { + var graph = new DepGraph(); + + graph.addNode('a'); + graph.addNode('b'); + + graph.addDependency('a','b'); + + graph.addNode('a'); + + expect(graph.dependenciesOf('a')).toEqual(['b']); + }); + + it('should do nothing if removing a node that does not exist', function () { + var graph = new DepGraph(); + + graph.addNode('a'); + expect(graph.hasNode('a')).toBe(true); + + graph.removeNode('a'); + expect(graph.hasNode('Foo')).toBe(false); + + graph.removeNode('a'); + expect(graph.hasNode('Foo')).toBe(false); + }); + + it('should be able to add dependencies between nodes', function () { + var graph = new DepGraph(); + + graph.addNode('a'); + graph.addNode('b'); + graph.addNode('c'); + + graph.addDependency('a','b'); + graph.addDependency('a','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 () { + var graph = new DepGraph(); + + graph.addNode('a'); + + expect(function () { + graph.addDependency('a','b'); + }).toThrow(new Error('Node does not exist: b')); + }); + + it('should detect cycles', 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.dependenciesOf('b'); + }).toThrow(new Error('Dependency Cycle Found: b -> c -> a -> b')); + }); + + 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.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']); + }); + + 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: 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 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 () { + var graph = new DepGraph(); + + 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'); + + 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']); + }); + + 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.addDependency('a', 'b'); + graph.addDependency('a', 'c'); + graph.addDependency('b', 'c'); + graph.addDependency('c', 'd'); + + expect(graph.overallOrder()).toEqual(['d', 'c', 'b', 'a', 'e']); + }); + + 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.addDependency('a', 'b'); + graph.addDependency('a', 'c'); + graph.addDependency('b', 'c'); + graph.addDependency('c', 'd'); + + expect(graph.overallOrder(true)).toEqual(['d', 'e']); + }); + + 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 () { + var graph = new DepGraph(); + + expect(graph.overallOrder()).toEqual([]); + }); + + 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'); + + expect(graph.dependenciesOf('a')).toEqual(['c', 'b']); + + graph.removeNode('c'); + + expect(graph.dependenciesOf('a')).toEqual(['b']); + }); + + it('should clone an empty graph', function () { + var graph = new DepGraph(); + expect(graph.size()).toEqual(0); + var cloned = graph.clone(); + expect(cloned.size()).toEqual(0); + + expect(graph === cloned).toBe(false); + }); + + 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'); + + var cloned = graph.clone(); + + expect(graph === cloned).toBe(false); + expect(cloned.hasNode('a')).toBe(true); + expect(cloned.hasNode('b')).toBe(true); + expect(cloned.hasNode('c')).toBe(true); + 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.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 () { + var graph = new DepGraph(); + + var data = {a: 42}; + graph.addNode('a', data); + + var cloned = graph.clone(); + expect(graph === cloned).toBe(false); + expect(graph.getNodeData('a') === cloned.getNodeData('a')).toBe(true); + + graph.getNodeData('a').a = 43; + expect(cloned.getNodeData('a').a).toEqual(43); + + cloned.setNodeData('a', {a: 42}); + expect(cloned.getNodeData('a').a).toEqual(42); + expect(graph.getNodeData('a') === cloned.getNodeData('a')).toBe(false); + }); +}); |