TopologicalSort.js

export function TopologicalSorter() {
 const graph = {}
 let isVisitedNode
 let finishTimeCount
 let finishingTimeList
 let 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 (const 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 (let i = 0; i < graph[node].length; i++) {
 nextNode = graph[node][i]
 if (isVisitedNode[nextNode]) continue
 dfsTraverse(nextNode)
 }
 }

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

/* TEST */
// const 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)
// topoSorter.sortAndGetOrderedItems()