diff options
Diffstat (limited to 'node_modules/toposort')
| -rw-r--r-- | node_modules/toposort/.travis.yml | 5 | ||||
| -rw-r--r-- | node_modules/toposort/README.md | 6 | ||||
| -rw-r--r-- | node_modules/toposort/index.js | 12 | ||||
| -rw-r--r-- | node_modules/toposort/package.json | 2 | ||||
| -rw-r--r-- | node_modules/toposort/test.js | 19 |
5 files changed, 38 insertions, 6 deletions
diff --git a/node_modules/toposort/.travis.yml b/node_modules/toposort/.travis.yml index cba9d4a7a..de1d11e49 100644 --- a/node_modules/toposort/.travis.yml +++ b/node_modules/toposort/.travis.yml @@ -2,4 +2,7 @@ language: node_js node_js: - 0.8 - 0.6 - - 0.10
\ No newline at end of file + - 0.10 + - 0.12 + - 4 + - 6 diff --git a/node_modules/toposort/README.md b/node_modules/toposort/README.md index c5d46ce84..58d4ab3e8 100644 --- a/node_modules/toposort/README.md +++ b/node_modules/toposort/README.md @@ -17,7 +17,7 @@ toposort = require('toposort') ## Usage We want to sort the following graph. - + ```js // First, we define our edges. @@ -76,6 +76,8 @@ toposort(graph).reverse() Returns: {Array} a list of vertices, sorted from "start" to "end" +Throws an error if there are any cycles in the graph. + ### toposort.array(nodes, edges) + nodes {Array} An array of nodes @@ -85,6 +87,8 @@ This is a convenience method that allows you to define nodes that may or may not Returns: {Array} a list of vertices, sorted from "start" to "end" +Throws an error if there are any cycles in the graph. + ## Tests Run the tests with `node test.js`. diff --git a/node_modules/toposort/index.js b/node_modules/toposort/index.js index 67f131f67..c9897e718 100644 --- a/node_modules/toposort/index.js +++ b/node_modules/toposort/index.js @@ -6,11 +6,11 @@ * @returns {Array} */ -module.exports = exports = function(edges){ +module.exports = function(edges){ return toposort(uniqueNodes(edges), edges) } -exports.array = toposort +module.exports.array = toposort function toposort(nodes, edges) { var cursor = nodes.length @@ -26,7 +26,13 @@ function toposort(nodes, edges) { function visit(node, i, predecessors) { if(predecessors.indexOf(node) >= 0) { - throw new Error('Cyclic dependency: '+JSON.stringify(node)) + var nodeRep + try { + nodeRep = ", node was:" + JSON.stringify(node) + } catch(e) { + nodeRep = "" + } + throw new Error('Cyclic dependency' + nodeRep) } if (!~nodes.indexOf(node)) { diff --git a/node_modules/toposort/package.json b/node_modules/toposort/package.json index ad388f98e..26b7febe4 100644 --- a/node_modules/toposort/package.json +++ b/node_modules/toposort/package.json @@ -1,6 +1,6 @@ { "name": "toposort", - "version": "1.0.3", + "version": "1.0.7", "description": "Topological sort of directed ascyclic graphs (like dependecy lists)", "main": "index.js", "scripts": { diff --git a/node_modules/toposort/test.js b/node_modules/toposort/test.js index 10a58afe6..4f095c4eb 100644 --- a/node_modules/toposort/test.js +++ b/node_modules/toposort/test.js @@ -132,7 +132,26 @@ suite.addBatch( assert.deepEqual(result, ['d', 'c', 'a', 'b']) } } +, 'giant graphs': + { + topic: function() { + var graph = [] + , nodeCount = 10000 + for (var i = 0; i < nodeCount; i++) { + graph.push([i, i + 1]) + } + return graph + } + , 'should sort quickly': function(er, result){ + var start = (new Date).getTime() + var sorted = toposort(result) + var end = (new Date).getTime() + var elapsedSeconds = (end - start) / 1000 + assert(elapsedSeconds < 1) + } + } }) .run(null, function() { (suite.results.broken+suite.results.errored) > 0 && process.exit(1) + process.exit(0) }) |