toposort-parallel.js

function flatMap(xs, f) {
    return xs.reduce(function(ys, x) {
        return ys.concat(f(x));
    }, []);
}

var vertices = Object.keys;

function edges(graph) {
    return flatMap(vertices(graph), function(vertex) {
        return graph[vertex].map(function(dep) {
            return [vertex, dep];
        });
    });
}

function edgesToGraph(edges) {
    return edges.reduce(function(graph, edge) {
        if(graph[edge[0]]) graph[edge[0]].push(edge[1]);
        else graph[edge[0]] = [edge[1]];
        return graph;
    }, {});
}

function invertEdges(edges) {
    return edges.map(function(edge) {
        return edge.reverse();
    });
}

function invertGraph(graph) {
    return edgesToGraph(invertEdges(edges(graph)));
}

var t = require('@quarterto/toposort');
function toposort(graph) {
    return t(vertices(graph), edges(graph));
}

function depths(graph) {
    var d = {};
    var t = toposort(graph);
    var inv = invertGraph(graph);
    t.forEach(function(v) {
        d[v] = 0;
        (inv[v] || []).forEach(function(c) {
            d[v] = Math.max(d[v], (d[c] || 0) + 1);
        });
    });
    
    return d;
}

var invert = require('lodash.invertby');
var values = require('lodash.values');

function toposortParallel(graph) {
    return values(invert(depths(graph)));
}

module.exports = toposortParallel;