toposort

What is toposort?

The toposort npm package is used for sorting directed acyclic graphs (DAG) into a topological order. It is useful for tasks where dependencies need to be resolved in a specific sequence, such as task scheduling, resolving package dependencies, or processing data with dependencies.

What are toposort's main functionalities?

Topological sorting

This feature allows you to sort a list of edges representing dependencies into a topological order. The edges are pairs where the first element depends on the second one.

const toposort = require('toposort');
const edges = [
  ['task1', 'task2'],
  ['task2', 'task3'],
  ['task3', 'task4']
];
const sorted = toposort(edges);
console.log(sorted); // ['task1', 'task2', 'task3', 'task4']

Other packages similar to toposort

dagre

Dagre is a JavaScript library that lays out directed graphs on the client-side. While toposort focuses on sorting nodes in a topological order, dagre provides the additional functionality of graph layout for visualization purposes.

graphlib

Graphlib is a library that provides data structures for undirected and directed multi-graphs along with algorithms to use with them. It includes topological sorting as well as other algorithms like shortest path. It is more comprehensive than toposort, which is specialized for topological sorting.

dependency-graph

Dependency-graph is a simple dependency graph library that can be used to handle and sort dependencies. It offers a higher-level API compared to toposort, allowing for the addition of nodes and dependencies in a more object-oriented manner.

README

Sorting directed acyclic graphs

Installation

npm install toposort

Example

Let's say, you have a list of plugins or 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:

toposort = require('toposort')

var plugins =
[ ["foo", 'bar']
, ["bar", "ron"]
, ["john", "bar"]
, ["tom", "john"]
]

// this will sort our plugins by dependecy
var results = toposort(plugins)

// now, we reverse the results to get the resulting execution flow, as above
results.reverse()

console.dir(results)
/*
Output:

[ 'ron', 'bar', 'foo', 'john', 'tom' ]

*/

API

toposort(edges)

• edges {Array} An array of directed vertices like [node1, node2] (where node1 depends on node2) -- these needn't be strings but can be any of any type

Returns: {Array} a list of nodes, sorted by their dependency (following edge direction as descendancy)

Tests

Run the tests with node test.js.

Legal

MIT License