index.js

/**
 * Topological sorting function
 *
 * @param {Array} edges
 * @returns {Array}
 */

module.exports = function (edges) {
  return toposort(uniqueNodes(edges), edges);
};

module.exports.array = toposort;
module.exports.parallel = parallel_toposort;

function toposort(nodes, edges) {
  var cursor = nodes.length,
    sorted = new Array(cursor),
    visited = {},
    i = cursor,
    // Better data structures make algorithm much faster.
    outgoingEdges = makeOutgoingEdges(edges),
    nodesHash = makeNodesHash(nodes);

  // check for unknown nodes
  edges.forEach(function (edge) {
    if (!nodesHash.has(edge[0]) || !nodesHash.has(edge[1])) {
      const missing = new Set(!nodesHash.has(edge[0]) ? edge[0] : edge[1]);

      throw new Error(
        `Unknown node. There is an unknown node in the supplied edges (${
          Array.from(missing).join(", ") || "unknown"
        }).`
      );
    }
  });

  while (i--) {
    if (!visited[i]) visit(nodes[i], i, new Set());
  }

  return sorted;

  function visit(node, i, predecessors) {
    if (predecessors.has(node)) {
      var nodeRep;
      try {
        nodeRep = ", node was:" + JSON.stringify(node);
      } catch (e) {
        nodeRep = "";
      }
      throw new Error("Cyclic dependency" + nodeRep);
    }

    if (!nodesHash.has(node)) {
      throw new Error(
        "Found unknown node. Make sure to provided all involved nodes. Unknown node: " +
          JSON.stringify(node)
      );
    }

    if (visited[i]) return;
    visited[i] = true;

    var outgoing = outgoingEdges.get(node) || new Set();
    outgoing = Array.from(outgoing);

    if ((i = outgoing.length)) {
      predecessors.add(node);
      do {
        var child = outgoing[--i];
        visit(child, nodesHash.get(child), predecessors);
      } while (i);
      predecessors.delete(node);
    }

    sorted[--cursor] = node;
  }
}

// a, b, c, d, e, f
// d -> b, e -> b, f -> d
// parallel_toposort: [a, c, b], [d, e], [f]
function parallel_toposort(nodes, edges) {
  const nodesHash = makeNodesHash(nodes);
  edges.forEach((edge) => {
    if (!nodesHash.has(edge[0]) || !nodesHash.has(edge[1])) {
      const missing = new Set(!nodesHash.has(edge[0]) ? edge[0] : edge[1]);

      throw new Error(
        `Unknown node. There is an unknown node in the supplied edges (${
          Array.from(missing).join(", ") || "unknown"
        }).`
      );
    }
  });

  const visited = new Set();
  const sorted = [];

  while (visited.size < nodes.length) {
    // visit nodes with no dependencies or nodes with all dependencies visited
    const next = nodes.filter((node) => {
      if (visited.has(node)) return false;

      const dependencies = edges
        .filter(([_, to]) => to === node)
        .map(([from, _]) => from);

      return dependencies.every((dependency) => visited.has(dependency));
    });

    if (next.length === 0) throw new Error("Circular dependency detected");

    next.forEach((node) => visited.add(node));
    sorted.push(next);
  }

  return sorted;
}

function uniqueNodes(arr) {
  var res = new Set();
  for (var i = 0, len = arr.length; i < len; i++) {
    var edge = arr[i];
    res.add(edge[0]);
    res.add(edge[1]);
  }
  return Array.from(res);
}

function makeOutgoingEdges(arr) {
  var edges = new Map();
  for (var i = 0, len = arr.length; i < len; i++) {
    var edge = arr[i];
    if (!edges.has(edge[0])) edges.set(edge[0], new Set());
    if (!edges.has(edge[1])) edges.set(edge[1], new Set());
    edges.get(edge[0]).add(edge[1]);
  }
  return edges;
}

function makeNodesHash(arr) {
  var res = new Map();
  for (var i = 0, len = arr.length; i < len; i++) {
    res.set(arr[i], i);
  }
  return res;
}