caoge c760052ff9 机车状态修改 | 8 månader sedan | |
---|---|---|
.. | ||
.npmignore | 8 månader sedan | |
.travis.yml | 8 månader sedan | |
License | 8 månader sedan | |
Makefile | 8 månader sedan | |
README.md | 8 månader sedan | |
component.json | 8 månader sedan | |
graph.svg | 8 månader sedan | |
index.js | 8 månader sedan | |
package.json | 8 månader sedan | |
test.js | 8 månader sedan |
Sort directed acyclic graphs
npm install toposort
or component install marcelklehr/toposort
then in your code:
toposort = require('toposort')
We want to sort the following graph.
// 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...)
It is usually more convenient to specify dependencies instead of "sequences".
// 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' ]
[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.
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.
Run the tests with node test.js
.
MIT License