What is toposort-class?
The toposort-class npm package is a JavaScript library that provides functionality for topological sorting. Topological sorting is a linear ordering of vertices in a directed graph such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. This is particularly useful in scenarios like resolving dependencies, scheduling tasks, and organizing data with precedence constraints.
What are toposort-class's main functionalities?
Add Edges
This feature allows you to add directed edges to the graph. In the example, 'a' depends on 'b' and 'b' depends on 'c'. The sort method then returns the topologically sorted order.
const Toposort = require('toposort-class');
const ts = new Toposort();
ts.add('a', 'b');
ts.add('b', 'c');
console.log(ts.sort()); // Output: ['a', 'b', 'c']
Add Multiple Edges
This feature allows you to add multiple edges at once. In the example, 'a' depends on both 'b' and 'c', and both 'b' and 'c' depend on 'd'. The sort method returns the topologically sorted order.
const Toposort = require('toposort-class');
const ts = new Toposort();
ts.add('a', ['b', 'c']);
ts.add('b', 'd');
ts.add('c', 'd');
console.log(ts.sort()); // Output: ['a', 'b', 'c', 'd']
Cycle Detection
This feature detects cycles in the graph. In the example, adding edges 'a' -> 'b', 'b' -> 'c', and 'c' -> 'a' creates a cycle. The sort method throws an error indicating the presence of a cycle.
const Toposort = require('toposort-class');
const ts = new Toposort();
ts.add('a', 'b');
ts.add('b', 'c');
ts.add('c', 'a');
try {
console.log(ts.sort());
} catch (e) {
console.log(e.message); // Output: 'There is a cycle in the graph. It is not possible to sort.'
}
Other packages similar to toposort-class
graphlib
Graphlib is a library for creating and manipulating directed graphs in JavaScript. It provides more comprehensive graph manipulation capabilities compared to toposort-class, including algorithms for finding shortest paths, detecting cycles, and more.
toposort
Toposort is a simpler library focused solely on topological sorting. It provides similar functionality to toposort-class but is more lightweight and has fewer features related to graph manipulation.
dagre
Dagre is a library for laying out directed graphs on the web. It includes functionality for topological sorting but is primarily focused on graph visualization and layout, making it more feature-rich in terms of visual representation compared to toposort-class.
Toposort
Sorting directed acyclic graphs, for Node.js, io.js and the browser
This was originally done by Marcel Klehr. Why not checkout his original repo?
Installation
There are a few ways for installing Toposort. Here are them:
- Via NPM:
npm install toposort-class
- Via Bower:
bower install toposort
- Via Git:
git clone git://github.com/gustavohenke/toposort.git
- Direct download (Minified) for use in the browser
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());
Usage
CommonJS (Node.js and io.js):
var Toposort = require('toposort-class'),
t = new Toposort();
Browser with AMD:
define("myModule", ["Toposort"], function(Toposort) {
var t = new Toposort();
});
Browser without AMD:
var t = new window.Toposort();
or whatever global object there is instead of window
.
API
.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".
.clear()
Returns: {Toposort} The Toposort instance, for chaining.
Clears all edges, effectively resetting the instance.
.Toposort
Reference to the Toposort constructor.
Legal
MIT License