You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
// First, we define our edges.vargraph=[['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 specifydependencies instead of "sequences".
// This time, edges represent dependencies.vargraph=[['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 allnodes 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 withnode test.js.
Legal
MIT License
About
Topologically sort directed acyclic graphs (such as dependency lists) in javascript
