From 26105034da4fcce7ac883c899d781f016559310d Mon Sep 17 00:00:00 2001 From: ruki Date: Thu, 8 Nov 2018 00:38:48 +0800 Subject: switch to vuepress --- node_modules/toposort/.npmignore | 1 + node_modules/toposort/.travis.yml | 8 ++ node_modules/toposort/License | 21 +++++ node_modules/toposort/Makefile | 11 +++ node_modules/toposort/README.md | 98 ++++++++++++++++++++++ node_modules/toposort/component.json | 24 ++++++ node_modules/toposort/graph.svg | 1 + node_modules/toposort/index.js | 69 +++++++++++++++ node_modules/toposort/package.json | 29 +++++++ node_modules/toposort/test.js | 157 +++++++++++++++++++++++++++++++++++ 10 files changed, 419 insertions(+) create mode 100644 node_modules/toposort/.npmignore create mode 100644 node_modules/toposort/.travis.yml create mode 100644 node_modules/toposort/License create mode 100644 node_modules/toposort/Makefile create mode 100644 node_modules/toposort/README.md create mode 100644 node_modules/toposort/component.json create mode 100644 node_modules/toposort/graph.svg create mode 100644 node_modules/toposort/index.js create mode 100644 node_modules/toposort/package.json create mode 100644 node_modules/toposort/test.js (limited to 'node_modules/toposort') diff --git a/node_modules/toposort/.npmignore b/node_modules/toposort/.npmignore new file mode 100644 index 00000000..3c3629e6 --- /dev/null +++ b/node_modules/toposort/.npmignore @@ -0,0 +1 @@ +node_modules diff --git a/node_modules/toposort/.travis.yml b/node_modules/toposort/.travis.yml new file mode 100644 index 00000000..de1d11e4 --- /dev/null +++ b/node_modules/toposort/.travis.yml @@ -0,0 +1,8 @@ +language: node_js +node_js: + - 0.8 + - 0.6 + - 0.10 + - 0.12 + - 4 + - 6 diff --git a/node_modules/toposort/License b/node_modules/toposort/License new file mode 100644 index 00000000..7975a823 --- /dev/null +++ b/node_modules/toposort/License @@ -0,0 +1,21 @@ + +Toposort - Topological sorting for node.js +Copyright (c) 2012 by Marcel Klehr +MIT LICENSE +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. diff --git a/node_modules/toposort/Makefile b/node_modules/toposort/Makefile new file mode 100644 index 00000000..0f14dac3 --- /dev/null +++ b/node_modules/toposort/Makefile @@ -0,0 +1,11 @@ + +build: components index.js + @component build --dev + +components: component.json + @component install --dev + +clean: + rm -fr build components template.js + +.PHONY: clean diff --git a/node_modules/toposort/README.md b/node_modules/toposort/README.md new file mode 100644 index 00000000..58d4ab3e --- /dev/null +++ b/node_modules/toposort/README.md @@ -0,0 +1,98 @@ +# Toposort + +Sort directed acyclic graphs + +[![Build Status](https://travis-ci.org/marcelklehr/toposort.png)](https://travis-ci.org/marcelklehr/toposort) + +## Installation + +`npm install toposort` or `component install marcelklehr/toposort` + +then in your code: + +```js +toposort = require('toposort') +``` + +## Usage +We want to sort the following graph. + +![graph](https://cdn.rawgit.com/marcelklehr/toposort/8b14e9fd/graph.svg) + +```js +// First, we define our edges. +var graph = [ + ['put on your shoes', 'tie your shoes'] +, ['put on your shirt', 'put on your jacket'] +, ['put on your shorts', 'put on your jacket'] +, ['put on your shorts', 'put on your shoes'] +] + + +// Now, sort the vertices topologically, to reveal a legal execution order. +toposort(graph) +// [ 'put on your shirt' +// , 'put on your shorts' +// , 'put on your jacket' +// , 'put on your shoes' +// , 'tie your shoes' ] +``` + +(Note that there is no defined order for graph parts that are not connected + -- you could also put on your jacket after having tied your shoes...) + +### Sorting dependencies +It is usually more convenient to specify *dependencies* instead of "sequences". +```js +// This time, edges represent dependencies. +var graph = [ + ['tie your shoes', 'put on your shoes'] +, ['put on your jacket', 'put on your shirt'] +, ['put on your shoes', 'put on your shorts'] +, ['put on your jacket', 'put on your shorts'] +] + +toposort(graph) +// [ 'tie your shoes' +// , 'put on your shoes' +// , 'put on your jacket' +// , 'put on your shirt' +// , 'put on your shorts' ] + +// Now, reversing the list will reveal a legal execution order. +toposort(graph).reverse() +// [ 'put on your shorts' +// , 'put on your shirt' +// , 'put on your jacket' +// , 'put on your shoes' +// , 'tie your shoes' ] +``` + +## API + +### toposort(edges) + ++ edges {Array} An array of directed edges describing a graph. An edge looks like this: `[node1, node2]` (vertices needn't be strings but can be of any type). + +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 ++ edges {Array} An array of directed edges. You don't need to mention all `nodes` here. + +This is a convenience method that allows you to define nodes that may or may not be connected to any other nodes. The ordering of unconnected nodes is not defined. + +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`. + +## Legal + +MIT License diff --git a/node_modules/toposort/component.json b/node_modules/toposort/component.json new file mode 100644 index 00000000..fe12ae20 --- /dev/null +++ b/node_modules/toposort/component.json @@ -0,0 +1,24 @@ +{ + "name": "toposort", + "author": "Marcel Klehr ", + "repo": "marcelklehr/toposort", + "description": "Topological sort of directed acyclic graphs (like dependency lists)", + "version": "0.2.10", + "keywords": [ + "topological", + "sort", + "sorting", + "graphs", + "graph", + "dependency", + "list", + "dependencies", + "acyclic" + ], + "dependencies": {}, + "development": {}, + "license": "MIT", + "scripts": [ + "index.js" + ] +} diff --git a/node_modules/toposort/graph.svg b/node_modules/toposort/graph.svg new file mode 100644 index 00000000..e14b0d93 --- /dev/null +++ b/node_modules/toposort/graph.svg @@ -0,0 +1 @@ +image/svg+xmlput on your shortsput on your shirtput on your shoesput on your jackettie your shoes diff --git a/node_modules/toposort/index.js b/node_modules/toposort/index.js new file mode 100644 index 00000000..c9897e71 --- /dev/null +++ b/node_modules/toposort/index.js @@ -0,0 +1,69 @@ + +/** + * Topological sorting function + * + * @param {Array} edges + * @returns {Array} + */ + +module.exports = function(edges){ + return toposort(uniqueNodes(edges), edges) +} + +module.exports.array = toposort + +function toposort(nodes, edges) { + var cursor = nodes.length + , sorted = new Array(cursor) + , visited = {} + , i = cursor + + while (i--) { + if (!visited[i]) visit(nodes[i], i, []) + } + + return sorted + + function visit(node, i, predecessors) { + if(predecessors.indexOf(node) >= 0) { + var nodeRep + try { + nodeRep = ", node was:" + JSON.stringify(node) + } catch(e) { + nodeRep = "" + } + throw new Error('Cyclic dependency' + nodeRep) + } + + if (!~nodes.indexOf(node)) { + throw new Error('Found unknown node. Make sure to provided all involved nodes. Unknown node: '+JSON.stringify(node)) + } + + if (visited[i]) return; + visited[i] = true + + // outgoing edges + var outgoing = edges.filter(function(edge){ + return edge[0] === node + }) + if (i = outgoing.length) { + var preds = predecessors.concat(node) + do { + var child = outgoing[--i][1] + visit(child, nodes.indexOf(child), preds) + } while (i) + } + + sorted[--cursor] = node + } +} + +function uniqueNodes(arr){ + var res = [] + for (var i = 0, len = arr.length; i < len; i++) { + var edge = arr[i] + if (res.indexOf(edge[0]) < 0) res.push(edge[0]) + if (res.indexOf(edge[1]) < 0) res.push(edge[1]) + } + return res +} diff --git a/node_modules/toposort/package.json b/node_modules/toposort/package.json new file mode 100644 index 00000000..26b7febe --- /dev/null +++ b/node_modules/toposort/package.json @@ -0,0 +1,29 @@ +{ + "name": "toposort", + "version": "1.0.7", + "description": "Topological sort of directed ascyclic graphs (like dependecy lists)", + "main": "index.js", + "scripts": { + "test": "node test.js" + }, + "repository": { + "type": "git", + "url": "https://github.com/marcelklehr/toposort.git" + }, + "devDependencies": { + "vows": "0.7.x" + }, + "keywords": [ + "topological", + "sort", + "sorting", + "graphs", + "graph", + "dependency", + "list", + "dependencies", + "acyclic" + ], + "author": "Marcel Klehr ", + "license": "MIT" +} diff --git a/node_modules/toposort/test.js b/node_modules/toposort/test.js new file mode 100644 index 00000000..4f095c4e --- /dev/null +++ b/node_modules/toposort/test.js @@ -0,0 +1,157 @@ +var vows = require('vows') + , toposort = require('./index') + , assert = require('assert') + +var suite = vows.describe('toposort') +suite.addBatch( +{ 'acyclic graphs': + { topic: function() { + /*(read downwards) + 6 3 + | | + 5->2 + | | + 4 1 + */ + return toposort( + [ ["3", '2'] + , ["2", "1"] + , ["6", "5"] + , ["5", "2"] + , ["5", "4"] + ]) + } + , 'should be sorted correctly': function(er, result) { + assert.instanceOf(result, Array) + var failed = [], passed + // valid permutations + ;[ [ '3','6','5','2','1','4' ] + , [ '3','6','5','2','4','1' ] + , [ '6','3','5','2','1','4' ] + , [ '6','5','3','2','1','4' ] + , [ '6','5','3','2','4','1' ] + , [ '6','5', '4','3','2','1' ] + ].forEach(function(solution) { + try { + assert.deepEqual(result, solution) + passed = true + }catch (e) { + failed.push(e) + } + }) + if (!passed) { + console.log(failed) + throw failed[0]; + } + } + } +, 'simple cyclic graphs': + { topic: function() { + /* + foo<->bar + */ + return toposort( + [ ["foo", 'bar'] + , ["bar", "foo"]// cyclic dependecy + ]) + } + , 'should throw an exception': function(_, val) { + assert.instanceOf(val, Error) + } + } +, 'complex cyclic graphs': + { topic: function() { + /* + foo + | + bar<-john + | ^ + ron->tom + */ + return toposort( + [ ["foo", 'bar'] + , ["bar", "ron"] + , ["john", "bar"] + , ["tom", "john"] + , ["ron", "tom"]// cyclic dependecy + ]) + } + , 'should throw an exception': function(_, val) { + assert.instanceOf(val, Error) + } + } +, 'unknown nodes in edges': + { topic: function() { + return toposort.array(['bla'] + [ ["foo", 'bar'] + , ["bar", "ron"] + , ["john", "bar"] + , ["tom", "john"] + , ["ron", "tom"] + ]) + } + , 'should throw an exception': function(_, val) { + assert.instanceOf(val, Error) + } + } +, 'triangular dependency': + { topic: function() { + /* + a-> b + | / + c<- + */ + return toposort([ + ['a', 'b'] + , ['a', 'c'] + , ['b', 'c'] + ]); + } + , 'shouldn\'t throw an error': function(er, result) { + assert.deepEqual(result, ['a', 'b', 'c']) + } + } +, 'toposort.array': + { topic: function() { + return toposort.array(['d', 'c', 'a', 'b'], [['a','b'],['b','c']]) + } + , 'should include unconnected nodes': function(er, result){ + var i = result.indexOf('d') + assert(i >= 0) + result.splice(i, 1) + assert.deepEqual(result, ['a', 'b', 'c']) + } + } +, 'toposort.array mutation': + { topic: function() { + var array = ['d', 'c', 'a', 'b'] + toposort.array(array, [['a','b'],['b','c']]) + return array + } + , 'should not mutate its arguments': function(er, result){ + 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) +}) -- cgit v1.2.3