JSFiddle - React, Tailwind, and code Playground

by Tim Ko

JavaScript

ABCDE is A correct ordering
but we're ok with ANY correct ordering

E -> D
D -> C
C -> A
D -> A
C -> B
F -> C

->  reads as "Depends on"


// Build nodes: children
E: [D]
D: [C, A]
C: [A, B]
A: []
B: []
F: [C]

// Perform DFS / Topological Sort

E: 1
D: 2
C: 3
A: 4
B: 5


ABCDE


// [E, D];

{
    E: {visited: false, children: [D]}
}

node {
    parents: false,
    visited,
    children: [];
}

function correctOrdering(transitions) {
    var nodes = {};
    
    // TEMP
    var currentNode = transitions[0][0];
    
    // map nodes to children
    for (var i = 0, ln = transitions.length; i < ln; i++) {
        var n = transitions[i];

        if (nodes.hasOwnProperty(n[0]) {
            nodes[n[0]].children.push(n[1]);
        } else {
            nodes[n[0]] = { parents: false, visited: false, children: [n[1]] };
        }
        
        if (!nodes.hasOwnProperty(n[1]) {
            nodes[n[1]] = { parents: true, visited: false, children: [] };
        }
    }
    
    var depth = 1;
    var results = [];

    // dfs
    function dfs(node) {
        if (node.visited != false) {
            return; // CHECK FOR CYCLE HERE
        }
        
        node.visited = depth;
        depth++;
        results.push(node);
        
        for (var child = 0, ln < node.children.length; child < ln; child++) {
            dfs(nodes[node.children[child]]);
        }
    }
    
    // [E, D, C, A, B, F]
    // F B A C D E
    
    var keys = Object.keys(nodes);
    for (var k = 0, ln = keys.length; k < ln; k++) {
        if (nodes[keys[k]].parents == false) {
            dfs(nodes[keys[k]]);
        }
    }
    
    // [E, D, C, A, B]
    // print out B A C D E
    console.log(results.reverse().join(" "));
}