Topological Sort

Definition

A topological sort (sometimes abbreviated topsort or toposort) of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Source: Wikipedia

Code: https://github.com/felipernb/algorithms.js/blob/master/algorithms/graph/topological_sort.js

Test: https://github.com/felipernb/algorithms.js/blob/master/test/algorithms/graph/topological_sort.js

How to use

Import

var topsort = require('algorithms').Graph.topologicalSort;

Calling

To run the topsort, a graph should be passed, for the image above the graph would be something like:

var graph = new Graph();
graph.addVertex('shirt');
graph.addVertex('watch');
graph.addVertex('socks');
graph.addVertex('underwear');
graph.addVertex('pants');
graph.addVertex('belt');
graph.addVertex('shoes');
graph.addVertex('tie');
graph.addVertex('jacket');

// Shirt is needed in order to put belt, tie and jacket
graph.addEdge('shirt', 'belt');
graph.addEdge('shirt', 'tie');
graph.addEdge('shirt', 'jacket');

// Socks are need in order to put shoes
graph.addEdge('socks', 'shoes');

// Underwear needs to go before pants and shoes (unless you're Superman)
graph.addEdge('underwear', 'pants');
graph.addEdge('underwear', 'shoes');

// Pants go before shoes and belt
graph.addEdge('pants', 'shoes');
graph.addEdge('pants', 'belt');

// Put the belt before the jacket
graph.addEdge('belt', 'jacket');

// And the tie as well
graph.addEdge('tie', 'jacket');

And when the topsort function is called, it will return a stack contained the nodes sorted:

var stack = topsort(graph);
stack.pop(); // underwear
stack.pop(); // pants
stack.pop(); // socks
stack.pop(); // shoes
stack.pop(); // watch
stack.pop(); // shirt
stack.pop(); // tie
stack.pop(); // belt
stack.pop(); // jacket