{"size": 2552, "ext": "js", "max_stars_repo_path": "lib/dag/toposort.js", "max_stars_repo_name": "CartoDB/camshaft", "max_stars_repo_stars_event_min_datetime": "2016-02-11T11:57:15.000Z", "max_stars_repo_stars_event_max_datetime": "2021-01-01T03:29:55.000Z", "max_issues_repo_path": "lib/dag/toposort.js", "max_issues_repo_name": "CartoDB/camshaft", "max_issues_repo_issues_event_min_datetime": "2016-03-15T14:49:35.000Z", "max_issues_repo_issues_event_max_datetime": "2021-12-27T14:49:36.000Z", "max_forks_repo_path": "lib/dag/toposort.js", "max_forks_repo_name": "CartoDB/camshaft", "max_forks_repo_forks_event_min_datetime": "2016-09-09T16:43:11.000Z", "max_forks_repo_forks_event_max_datetime": "2020-01-05T21:37:06.000Z"}
{"max_stars_count": 20, "max_issues_count": 240, "max_forks_count": 7, "avg_line_length": 25.52, "max_line_length": 100, "alphanum_fraction": 0.5975705329}
'use strict';

var debug = require('../util/debug')('toposort');

function toposort (rootNode) {
    var edges = buildEdges(rootNode);
    edges = Object.keys(edges).reduce(function (acc, nodeId) {
        acc.push(edges[nodeId]);
        return acc;
    }, []);

    debug('Found %d edges: %j', edges.length, edges.map(function (edge) {
        return [edge[0].id(), edge[1].id()];
    }));
    if (edges.length === 0) {
        return [rootNode];
    }
    return sort(edges);
}

module.exports = toposort;

function sort (edges) {
    return depthFirst(uniqueNodes(edges), edges);
}

function buildEdges (node, edges) {
    edges = edges || {};

    node.getInputNodes().forEach(function (inputNode) {
        edges[inputNode.id()] = [inputNode, node];
        debug('%s (%s) => %s (%s)', inputNode.id(), inputNode.getType(), node.id(), node.getType());

        buildEdges(inputNode, edges);
    });

    return edges;
}

function uniqueNodes (edges) {
    return edges.reduce(function (uniq, edge) {
        uniq[edge[0].id()] = edge[0];
        uniq[edge[1].id()] = edge[1];
        return uniq;
    }, {});
}

// See https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
function depthFirst (uniqNodes, edges) {
    var nodeIds = Object.keys(uniqNodes);
    var totalNodes = nodeIds.length;
    debug('Found %d unique nodes: %j', totalNodes, nodeIds);

    var sortedNodes = [];
    var markedNodes = {};

    var nodeIndex = 0;
    do {
        var currentNode = uniqNodes[nodeIds[nodeIndex]];

        if (!markedNodes[currentNode.id()]) {
            visit(currentNode, edges, markedNodes, sortedNodes);
        }
    } while (++nodeIndex < totalNodes);

    return sortedNodes;
}

function visit (node, allEdges, markedNodes, sortedNodes, parents) {
    parents = parents || {};

    debug('Visiting node=%s', node.id());

    if (Object.prototype.hasOwnProperty.call(parents, node.id())) {
        var err = new Error('Cycle at node: ' + JSON.stringify(node.toJSON()));
        err.node_id = node.params ? node.params.id : undefined;
        throw err;
    }

    if (markedNodes[node.id()]) {
        return true;
    }

    markedNodes[node.id()] = true;

    var outgoingEdges = allEdges.filter(function (edge) {
        return edge[0].id() === node.id();
    });

    if (outgoingEdges.length) {
        parents[node.id()] = true;

        outgoingEdges.forEach(function (outgoingEdge) {
            visit(outgoingEdge[1], allEdges, markedNodes, sortedNodes, parents);
        });
    }

    sortedNodes.unshift(node);
}
