graph-toposort

node-graph-toposort

An implementation of Kahn's Algorithm for topologically sorting a graph.js instance.

Install

$ npm install graph-toposort

Example

var toposort = require('graph-toposort');
var Graph = require('graph.js');

// a -> b -> c
var graph = new Graph(
  [ 'a', 'b' ],
  [ 'b', 'c' ]
);

var list = toposort(graph);
// [ 'a', 'b', 'c' ]

Usage

This algorithm is useful when determining what order to go in when dealing with a tree of dependencies. The graph must be acyclic, in other words it cannot have circular dependencies. (you must remove these yourself)

toposort(graph)

Given the input graph, it will return an Array of the vertex keys sorted topologically.