2020-04-19 17:10:25 +02:00
|
|
|
|
2021-10-11 12:29:03 +02:00
|
|
|
export function TopologicalSorter () {
|
2021-05-21 11:16:11 +05:30
|
|
|
const graph = {}
|
|
|
|
|
let isVisitedNode
|
|
|
|
|
let finishTimeCount
|
|
|
|
|
let finishingTimeList
|
|
|
|
|
let nextNode
|
2020-05-04 11:58:44 +05:30
|
|
|
|
|
|
|
|
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 = []
|
|
|
|
|
|
2021-05-21 11:16:11 +05:30
|
|
|
for (const node in graph) {
|
2020-05-04 11:58:44 +05:30
|
|
|
if (Object.prototype.hasOwnProperty.call(graph, node) && !isVisitedNode[node]) {
|
|
|
|
|
dfsTraverse(node)
|
|
|
|
|
}
|
2020-04-19 17:10:25 +02:00
|
|
|
}
|
|
|
|
|
|
2020-05-04 11:58:44 +05:30
|
|
|
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]) {
|
2021-05-21 11:16:11 +05:30
|
|
|
for (let i = 0; i < graph[node].length; i++) {
|
2020-05-04 11:58:44 +05:30
|
|
|
nextNode = graph[node][i]
|
|
|
|
|
if (isVisitedNode[nextNode]) continue
|
|
|
|
|
dfsTraverse(nextNode)
|
|
|
|
|
}
|
2020-05-03 01:03:10 +05:30
|
|
|
}
|
2020-04-19 17:10:25 +02:00
|
|
|
|
2020-05-04 11:58:44 +05:30
|
|
|
finishingTimeList.push({
|
2022-04-21 03:08:38 -03:00
|
|
|
node,
|
2020-05-04 11:58:44 +05:30
|
|
|
finishTime: ++finishTimeCount
|
|
|
|
|
})
|
|
|
|
|
}
|
|
|
|
|
}
|
2020-05-03 01:03:10 +05:30
|
|
|
|
2020-04-19 17:10:25 +02:00
|
|
|
/* TEST */
|
2021-10-11 12:29:03 +02:00
|
|
|
// 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()
|
