tsort.js

// TSORT: my half-assed topological sort program
// it is ugly, but it works (I think?)
//
// tsort expects an array 2 element arrays, where the first item is an
// identifier of the node, and the second is an array of identifiers
// for nodes that are dependencies.
// 
// example:
//
// [
//     ["a", ["b", "c", "d"]],
//     ["b", ["c", "d"]],
//     ["c", []],
//     ["d", ["c"]]
// ]
// => [ 'c', 'd', 'b', 'a' ]
//
// There is probably a better way to do this ;P
export default (graph) => {
    let output = [];
    // start: the names of nodes in the graph without dependencies
    let start = graph.filter(([_, deps]) => deps.length === 0)
        .map(([name, _]) => name);
    // if there are no starting nodes there is a cycle
    if (start.length === 0) {
        throw Error(`Cyclical dependency detected in ${JSON.stringify(graph)}!`);
    };
    let g;			// container to build modified graph 
    while (start.length > 0) {
        let node = start[0];	// pull off first node in start
        start = start.slice(1);	// remove node from start
        g = [];			// clear g to rebuild graph
        output = [...output, node]; // add the node to output
        graph.forEach(
            ([visiting, deps]) => {
                if (deps.includes(node)) {
                    // if node found in deps, remove it
                    deps.splice(deps.indexOf(node), 1);
                    if (deps.length === 0) {
                        // if visiting has no more deps, add to start
                        start.push(visiting);
                    }
                }
                // otherwise add visiting and deps to rebuilt graph
                g.push([visiting, deps]);
            }
        );
        graph = g;		// assign back for next loop
    }
    if (g.find(([_, deps]) => deps.length > 0)) {
        // if graph has any edges there is a cycle
        throw Error(`Cyclical dependency in ${JSON.stringify(g)}!`);
    } else {
        // all sorted!
        return output;
    }
};