Layered topological sort (JavaScript)

Layer-based scheduling algorithm for parallel tasks with dependencies.

Determines which tasks can be executed in parallel, by evaluating dependencies and scheduling them to start as soon as possible or as late as possible.

Acknowledgement: The code is based on quipo/dependencysolver and the introduction is taken from its README.md.

Introduction

Given a list of entries (each task with its own dependency list), it can sort them in layers of execution, where all task in the same layer can be executed in parallel, and have no other dependency than the previous layer.

For instance, given the tasks A, B, C, D, where B and C depend on A, and D depends on B and C, this function will return three layers of execution (as B and C can be executed in parallel after A completes):

Dependency tree

  A
 / \
B   C
 \ /
  D

Resulting execution layers

Layer 1	A
Layer 2	B, C
Layer 3	D

JavaScript representation and API

• A Task is represented by a string.
• Dependencies is an array of tasks.
• Entries is a map of dependencies keyed by a task.
• A Layer is an array of tasks.
• Layers is an array of layers.
• asap(entries) Returns layers, where the dependencies are ordered to run as soon as possible.
• alap(entries) Returns layers, where the dependencies are ordered to run as late as possible.

const entries = {
  A: [],
  B: ['A'],
  C: ['A'],
  D: ['B', 'C'],
}

Running either asap(entries) or alap(entries) produces an array of layers, where each layer is an array of tasks.

[ [ 'A' ], [ 'B', 'C' ], [ 'D' ] ]

As soon or as late as possible

Entries are scheduled to start either as soon as possible (asap) or as late as possible (alap). Depending on the duration and order of tasks each can produce a shorter schedule.

const entries = {
  A: [],
  B: [],
  C: ['A'],
  D: ['B', 'C'],
}

Running asap(entries) produces:

[ [ 'A', 'B' ], [ 'C' ], [ 'D' ] ]

While running alap(entries) produces:

[ [ 'A' ], [ 'B', 'C' ], [ 'D' ] ]

alap is better than asap

alap

asap

asap is better than alap

asap

alap

Examples

No dependencies

const entries = {
  A: [],
  B: [],
  C: [],
  D: [],
}

Both asap(entries) and alap(entries) produce a single layer, since all tasks are independent:

[ [ 'A', 'B', 'C', 'D' ] ]

Interdependent

const entries = {
  A: [],
  B: ['A'],
  C: ['B'],
  D: ['C'],
}

Both asap(entries) and alap(entries) produce one layer per task since they are interdependent and can’t run in parallel:

[ [ 'A' ], [ 'B' ], [ 'C' ], [ 'D' ] ]

Circular dependencies

const entries = {
  A: ['B'],
  B: ['A'],
}

Circular dependencies produce no results.
Running asap(entries) or alap(entries) produces an empty layers array.

[]

Complex

const entries = {
  A: [],
  B: ['A'],
  C: ['A', 'D'],
  D: ['E', 'B'],
  E: [],
  F: ['A', 'D', 'G'],
  G: ['H', 'I', 'J'],
  H: ['K'],
  I: ['K'],
  J: ['K'],
  K: [],
}

asap(entries) produces:

[
  [ 'A', 'E', 'K' ],
  [ 'B', 'H', 'I', 'J' ],
  [ 'D', 'G' ],
  [ 'C', 'F' ]
]

while alap(entries) produces:

[
  [ 'A', 'K' ],
  [ 'B', 'E', 'J', 'I', 'H' ],
  [ 'D', 'G' ],
  [ 'C', 'F' ]
]

JavaScript Implementation

Types

/**
 * @typedef {string} Task
 * @typedef {Task[]} Dependencies
 * @typedef {{[task: string]: Dependencies}} Entries
 * @typedef {Task[]} Layer
 * @typedef {Layer[]} Layers
 * @typedef {{[task: string]: {[task: string]: boolean}}} DGraph
 */

ALAP

/**
 * Returns a list of layers of task sorted as late as possible,
 * the tasks within each layer can be executed in parallel.
 *
 * @arg {Entries} entries
 * @return {Layers}
 */
function alap(entries) {
  const dependencies = createGraphs(entries);
  const layers = layeredTopologicalSort(dependencies[1], dependencies[0]);
  layers.reverse();
  return layers;
}

ASAP

/**
 * Returns a list of layers of task sorted as soon as possible,
 * the tasks within each layer can be executed in parallel.
 *
 * @arg {Entries} entries
 * @return {Layers}
 */
function asap(entries) {
  const dependencies = createGraphs(entries);
  return layeredTopologicalSort(dependencies[0], dependencies[1]);
}

Create graphs

/**
 * @arg {Entries} entries
 * @return {[DGraph, DGraph]}
 */
function createGraphs(entries) {
  /** @type {DGraph} */
  const toFrom = {};
  /** @type {DGraph} */
  const fromTo = {};

  // Build the dependencies graph
  for (const task in entries) {
    toFrom[task] = {};
    if (!fromTo[task]) fromTo[task] = {};
    const deps = entries[task];
    for (let n = deps.length - 1; 0 <= n; n -= 1) {
      const dep = deps[n];
      toFrom[task][dep] = true;
      if (!fromTo[dep]) fromTo[dep] = {};
      fromTo[dep][task] = true;
    }
  }
  return [toFrom, fromTo];
}

Layered topological sort

/**
 * LayeredTopologicalSort returns a list of layers of entries,
 * the entries within each layer can be executed in parallel.
 *
 * @arg {DGraph} toFrom
 * @arg {DGraph} fromTo
 * @return {Layers}
 */
function layeredTopologicalSort(toFrom, fromTo) {
  /** @type {Layers} */
  const layers = [];

  while (0 < Object.keys(toFrom).length) {
    /** @type {string[]} */
    const thisIterationIds = [];

    for (const k in toFrom) {
      const v = toFrom[k];

      // If an item has zero dependencies, remove it
      if (Object.keys(v).length === 0) thisIterationIds.push(k);
    }

    // if nothing was found to remove, there's no valid sort
    if (thisIterationIds.length === 0) return [];

    /** @type {Layer} */
    const layer = [];
    for (let i = 0, n = thisIterationIds.length; i < n; i++) {
      const id = thisIterationIds[i];
      // Add them to the overall ordering
      layer.push(id);

      // Remove the found items from the dictionary
      delete toFrom[id];

      // Remove all outbound edges
      if (fromTo[id]) {
        for (const dep in fromTo[id]) {
          delete toFrom[dep][id];
        }
      }
    }
    layers.push(layer);
  }
  return layers;
}