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

Sort directed graphs

Example

Let's say, you have a list of plugins, which depend on each other:

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

depends defines plugins that should be executed before the plugin that declares the directive.

A quick analysis, will result in the following dependency (and thus execution) flow:

ron
 - bar
   - john
     - tom
   - foo

Let's try this with toposort:

toposort = require('toposort')

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

var result = toposort('name', 'depends', plugins)

// we reverse the resulting list, because
// toposort assumes ancestry, but we want descendancy
console.dir(result.reverse())

Output:

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

API

toposort(idProperty, ancestryProperty, list)

• idProperty {String} The property of the objects in the list, which should be used as the identifier
• ancestryProperty {String} The property of the objects in list, which should be used as the ancestry list
• list {Array} A list of objects that have both properties.

Returns a list of identifiers, sorted by their ancestry.

Legal

MIT License