@n1ru4l/toposort

Why?

All toposort libraries I found where either JavaScript only, had a lot of dependencies, were cumbersome to deal with or did not produce dependency list that allowed detecting which tasks could be executed in parallel.

This library is basically a port of batching-toposort to TypeScript that uses modern ECMA structures such as Map and Set, as well as providing a utility toposortReverse function that I needed most of the time, when dealing with dependency lists.

This library also provides CommonJS and ES Module builds.

Install

yarn install -E @n1ru4l/toposort

Usage

toposort

Sort list of tasks.

import { toposort } from "@n1ru4l/toposort";

const tasks = new Map([
  // after wakeUp is done we can do drinkCoffee and eatBreakfast
  ["wakeUp", ["drinkCoffee", "eatBreakfast"]],
  ["drinkCoffee", ["brushTeeth"]],
  ["eatBreakfast", ["brushTeeth"]],
  ["brushTeeth", ["floss"]],
  // after flossing is done no further task must be done
  ["floss", []],
]);

const sorted = toposort(tasks);
console.log(sorted);
// [
//   Set(1) { 'wakeUp' },
//   Set(2) { 'drinkCoffee', 'eatBreakfast' },
//   Set(1) { 'brushTeeth' },
//   Set(1) { 'floss' }
// ]

toposortReverse

Most of the time I needed this instead of toposort. It is easier to grasp for my mind that task a depends on task b and c instead of declaring it the other way around. I am not sure about the naming. If you think a better naming is possible please send a pull request.

import { toposortReverse } from "@n1ru4l/toposort";

const graph = new Map([
  // before we can drinkCoffee, we need to wakeUp
  ["drinkCoffee", ["wakeUp"]],
  // before we can eatBreakfast, we need to wakeUp
  ["eatBreakfast", ["wakeUp"]],
  // before we can brushTeeth, we need to drinkCoffee and eatBreakfast
  ["brushTeeth", ["drinkCoffee", "eatBreakfast"]],
  // before we can floss, we need to brushTeeth
  ["floss", ["brushTeeth"]],
  // wakeUp can be done without any dependencies
  ["wakeUp", []],
]);

const sorted = toposortReverse(graph);
// [
//   Set(1) { 'wakeUp' },
//   Set(2) { 'drinkCoffee', 'eatBreakfast' },
//   Set(1) { 'brushTeeth' },
//   Set(1) { 'floss' }
// ]