toposort

Topological sort of directed ascyclic graphs (like dependecy lists)

Toposort

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' ] 
  • 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"

  • 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"

Run the tests with node test.js.

MIT License