EDIT: My question was originally about how to sort the following data. I was pointed in the direction of topological sort which got me started, but I am editing the question now to my new issue.
Given the following data structure:
[
{name: 'B', input: []},
{name: 'C', input: ['B']},
{name: 'D', input: ['C']},
{name: 'E', input: ['C']},
{name: 'H', input: ['E']},
{name: 'I', input: ['D', 'H']},
{name: 'J', input: []},
{name: 'L', input: ['J']},
]
I have used a topological sort to get these items in order.
However, elements J and L are a separate chain and it is important that the result distinguishes them.
This is the function I am using:
orderModelNodesTopologically(nodes: ExternalInputGraphNode[]): string[] {
const adjacencyList = this.createAdjacencyList(nodes);
const vertices = Object.keys(adjacencyList);
const visited = {};
const topNums = {};
let n = vertices.length - 1;
for (const v of vertices) {
if (!visited[v]) {
n = this.depthFirstSearch(v, n, visited, topNums, adjacencyList);
}
}
return Object.keys(topNums).sort((a, b) => topNums[a] - topNums[b]);
}
createAdjacencyList(nodes: ExternalInputGraphNode[]) {
const list = {};
nodes.forEach(node => list[node.name] = []);
nodes.forEach(node => {
node.input.forEach(inp => {
if (list[inp] !== undefined) {
list[inp].push(node.name);
}
});
});
return list;
}
depthFirstSearch(nodeName: string, n: number, visited: {[key: string]: boolean}, topNums: {[key: string]: number}, adjacencyList: {[key: string]: string[]}) {
visited[nodeName] = true;
const neighbors = adjacencyList[nodeName];
for (const neighbor of neighbors) {
if (!visited[neighbor]) {
n = this.depthFirstSearch(neighbor, n, visited, topNums, adjacencyList);
}
}
topNums[nodeName] = n;
return n - 1;
}
This returns the steps topologically sorted, but does not indicate that steps J and L are not connected to the other chain. Is there a way to adapt my sort to achieve this?
