Topological Sort Algorithm

The Topological Sort Algorithm is a graph-based algorithm used to linearly order the vertices of a directed acyclic graph (DAG) such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. This algorithm is particularly useful in determining the sequence of tasks with dependencies, scheduling, and determining the order of compilation for a given set of files. The main idea behind this algorithm is to visit all vertices in the graph in the topological order, starting from the vertices with no incoming edges, and then removing the visited vertices along with their edges. There are two common approaches to implementing the Topological Sort Algorithm: Depth-First Search (DFS) based algorithm and Kahn's algorithm. The DFS-based algorithm involves traversing the graph in a depth-first manner while maintaining a visited set and a stack to store the topological order. Once a node is visited and all its children are processed, it is pushed onto the stack. At the end of the traversal, the stack contains the vertices in the topological order. On the other hand, Kahn's algorithm starts by identifying nodes with no incoming edges, adding them to a queue. Then, it iteratively removes nodes from the queue, processes them, and removes their outgoing edges. As a result, new nodes with no incoming edges are discovered and added to the queue. The algorithm continues until the queue is empty or a cycle is detected, in which case topological sorting is not possible.

function TopologicalSorter () {
  var graph = {}
  var isVisitedNode
  var finishTimeCount
  var finishingTimeList
  var nextNode

  this.addOrder = function (nodeA, nodeB) {
    nodeA = String(nodeA)
    nodeB = String(nodeB)
    graph[nodeA] = graph[nodeA] || []
    graph[nodeA].push(nodeB)
  }

  this.sortAndGetOrderedItems = function () {
    isVisitedNode = Object.create(null)
    finishTimeCount = 0
    finishingTimeList = []

    for (var node in graph) {
      if (Object.prototype.hasOwnProperty.call(graph, node) && !isVisitedNode[node]) {
        dfsTraverse(node)
      }
    }

    finishingTimeList.sort(function (item1, item2) {
      return item1.finishTime > item2.finishTime ? -1 : 1
    })

    return finishingTimeList.map(function (value) { return value.node })
  }

  function dfsTraverse (node) {
    isVisitedNode[node] = true
    if (graph[node]) {
      for (var i = 0; i < graph[node].length; i++) {
        nextNode = graph[node][i]
        if (isVisitedNode[nextNode]) continue
        dfsTraverse(nextNode)
      }
    }

    finishingTimeList.push({
      node: node,
      finishTime: ++finishTimeCount
    })
  }
}

/* TEST */
var topoSorter = new TopologicalSorter()
topoSorter.addOrder(5, 2)
topoSorter.addOrder(5, 0)
topoSorter.addOrder(4, 0)
topoSorter.addOrder(4, 1)
topoSorter.addOrder(2, 3)
topoSorter.addOrder(3, 1)
console.log(topoSorter.sortAndGetOrderedItems())

LANGUAGE:

DARK MODE: