Toposort
Sorting directed acyclic graphs
This was originally done by Marcel Klehr. Why not checkout his original repo?
Installation
npm install toposort-class
Example
Let's say you have the following dependency graph:
- Plugin depends on Backbone and jQuery UI Button;
- Backbone depends on jQuery and Underscore;
- jQuery UI Button depends on jQuery UI Core and jQuery UI Widget;
- jQuery UI Widget and jQuery UI Core depend on jQuery;
- jQuery and Underscore don't depend on anyone.
Now, how would you sort this in a way that each asset will be correctly placed? You'll probably need the following sorting:
jQuery
, jQuery UI Core
, jQuery UI Widget
, jQuery UI Button
, Underscore
, Backbone
, Plugin
You can achieve it with the following code, using toposort-class
:
var Toposort = require('toposort-class'),
t = new Toposort();
t.add("jquery-ui-core", "jquery")
.add("jquery-ui-widget", "jquery")
.add("jquery-ui-button", ["jquery-ui-core", "jquery-ui-widget"])
.add("plugin", ["backbone", "jquery-ui-button"])
.add("backbone", ["underscore", "jquery"]);
console.log(t.sort().reverse());
API
First of all:
var Toposort = require('toposort-class'),
t = new Toposort();
t = new require('toposort-class').Toposort();
.add(item, deps)
- {String}
item
- The name of the dependent item that is being added - {Array|String}
deps
- A dependency or list of dependencies of item
Returns: {Toposort} The Toposort instance, for chaining.
.sort()
Returns: {Array} The list of dependencies topologically sorted.
This method will check for cyclic dependencies, like "A is dependent of A".
Legal
MIT License