toposort-class

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.

README

Toposort

Sorting directed acyclic graphs, for Node.js and the browser This was originally done by Marcel Klehr. Why not checkout his original repo?

Installation

npm install toposort-class

Or download toposort.js file 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());

/* Will output:
 * ['jquery', 'jquery-ui-core', 'jquery-ui-widget', 'jquery-ui-button', 'underscore', 'backbone', 'plugin']
 *
 * And you're done.
 */

API

First of all:

var Toposort = require('toposort-class'),
	t = new Toposort();

// If you prefer, you can do this way also:
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