/ stream.nieuweinstituut.nl / node_modules / toposort /

[ICO]NameLast modifiedSizeDescription
[PARENTDIR]Parent Directory  -  
[IMG]graph.svg8 years ago5.4K 
[   ]test.js7 years ago3.5K 
[TXT]README.md7 years ago2.5Kd768d73 docs [كارل مبارك]
[   ]index.js7 years ago1.5K3e510ca test new git [كارل مبارك]
[   ]package.json2 years ago1.4K3e510ca test new git [كارل مبارك]
[   ]License9 years ago1.1K 
[   ]component.json8 years ago471  
[   ]Makefile9 years ago166  
README.md

Toposort

Sort directed acyclic graphs

Build Status

Installation

npm install toposort or component install marcelklehr/toposort

then in your code:

toposort = require('toposort')

Usage

We want to sort the following graph.

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...)

Sorting dependencies

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

API

toposort(edges)

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)

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.

MIT License

Apache/2.4.38 (Debian) Server at www.karls.computer Port 80