Kahn's algorithm for topological sort

topologicalSortFinal.js

// Kahn's topological sort

// row number -> references
const input = [
    {id: "A", refs: []},
    {id: "B", refs: []},
    {id: "C", refs: ["D"]},
    {id: "D", refs: ["B"]},
    {id: "E", refs: ["A", "B"]},
    {id: "F", refs: ["A", "C"]}
]

function topologicalSort(referenceArray) {

    const numRows = referenceArray.length

    // This is a hashmap that holds that allows you to look up the index
    // of every Reference object in the referenceArray based on its ID
    // Result: { A: 0, B: 1, C: 2, D: 3, E: 4, F: 5 }
    // and you can access the index by doing indexMap["C"] (== 2)
    const indexMap = {}
    for (let i = 0; i < numRows; i++) {
        indexMap[referenceArray[i].id] = i
    }

    console.log(indexMap)

    // This is a hashmap containing the indegrees for every ID.
    // calculate the indegrees of each row
    const indegrees = {}

    // initialize all IDs with 0
    for (let i = 0; i < numRows; i++) {
        let row = referenceArray[i]
        indegrees[row.id] = 0
    }

    // and every time an ID is contained in a "refs" array, add 1 to the
    // count in the indegrees object
    // Result: { A: 2, B: 2, C: 1, D: 1, E: 0, F: 0 }
    for (let i = 0; i < numRows; i++) {
        let row = referenceArray[i]
        for (let j = 0; j < row.refs.length; j++) {
            let ref = row.refs[j]
            indegrees[ref] += 1
        }
    }
    
    console.log(indegrees)
    
    // Queue all IDs with indegree of 0
    //  Initally, that is only [ 'E', 'F' ]
    const queue = []

    for (let i = 0; i < numRows; i++) {
        let row = referenceArray[i]
        if (indegrees[row.id] === 0) {
            queue.push(row.id)
        }
    }
    
    console.log(queue)

    // store the IDs in the final order
    const finalOrder = []

    // continue until no more elements in queue
    while (queue.length > 0) {

        // remove and return the first ID from queue
        const next = queue.shift()
        finalOrder.push(next)

        // use the index map to get the index of the Reference of the ID
        // in the referenceArray
        const nextIndex = indexMap[next]

        // Get the Reference from the referenceArray based on this index
        const nextReference = referenceArray[nextIndex]


        // Iterate over References of the current row and reduce indegree by 1
        for (let i = 0; i < nextReference.refs.length; i++) {

            // ID of the reference
            let ref = nextReference.refs[i]
            indegrees[ref] -= 1

            // Queue the ID of the reference if it now has indegree 0
            if (indegrees[ref] === 0) {
                queue.push(ref)
            }
        }
    }

    if (finalOrder.length != numRows) {
        console.log("error")
        return []
    } else {
        return finalOrder
    }
}

console.log(input)
const finalOrder = topologicalSort(input)
console.log(finalOrder)  // Expected output: [ 'E', 'F', 'A', 'C', 'D', 'B' ]

https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/