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

Sorting directed acyclic graphs

Installation

npm install toposort-class

Example

Let's say, you have a list of pluginsor tasks, which depend on each other (depends defines plugins or tasks that should be executed before the plugin that declares the directive):

var plugins =
[ {name: "foo", depends: ['bar']}
, {name: "bar", depends: ["ron"]}
, {name: "john", depends: ["bar"]}
, {name: "tom", depends: ["john"]}
, {name: "ron", depends: []}
]

A quick analysis, will result in the following dependency tree:

tom
 |
john  foo
 |     |
 - - - - 
    |
   bar
    |
   ron

and thus the following execution flow:

   ron
    |
   bar
 - - - - 
 |     |
john  foo
 |
tom

Let's try this with toposort:

var toposort = require('toposort-class');

// this will sort our plugins by dependecy
var toposort = new Toposort();
toposort.add("foo", "bar");
toposort.add("bar", "ron");
toposort.add("john", "bar");
toposort.add("tom", "john");

// now, we reverse the results to get the resulting execution flow, as above
var results = toposort.sort();

console.log(results)
/*
Output:
[ 'ron', 'bar', 'foo', 'john', 'tom' ]
*/

Legal

MIT License