const nodeCount = 5;
/**@type {number[]} */
let graphNodes = Array(nodeCount)
.fill(0)
.map((item, index) => index);
/**@type {number[][]} */
const graphEdges = {
0: [1],
1: [3],
2: [3, 4],
3: [4],
};
/**
*
* @param {number[]} graphNodes
* @param {number[][]} graphEdges
* @returns {nodeType[]}
*/
const generateGraph = (graphNodes, graphEdges) => {
graphNodes = graphNodes.map((item, index) => {
const tempNode = { value: index, next: null };
return tempNode;
});
Object.entries(graphEdges).map(([value, edges]) => {
graphNodes[value].next = edges.reduce((res, toNode) => {
let tempRes = res;
while (tempRes.next) tempRes = tempRes.next;
tempRes.next = { value: toNode - 0, next: null };
return res;
}, {}).next;
});
return graphNodes;
};
const graph = generateGraph(graphNodes, graphEdges);
const getDegree = (graph) => {
const degree = Array(nodeCount).fill(0);
for (let i = 0; i < graph.length; i++) {
let node = graph[i].next;
while (node) {
degree[node.value]++;
node = node.next;
}
}
return degree;
};
const topoLogicSort = (graph) => {
const sortArray = [];
const stack = [];
const degree = getDegree(graph);
for (let i = 0; i < degree.length; i++) {
if (degree[i] == 0) stack.push(i);
}
while (stack.length !== 0) {
const currentNode = stack.pop();
sortArray.push(currentNode);
for (let node = graph[currentNode].next; node; node = node.next) {
if (--degree[node.value] == 0) stack.push(node.value);
}
}
if (sortArray.length < nodeCount) {
console.log("there is a loop");
return;
}
return sortArray;
};
const sortArray = topoLogicSort(graph);
console.log(sortArray);
// [ 2, 0, 1, 3, 4 ]
