How to detect separate chains in a topological sort

74 views Asked by At

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:

enter image description here

[
    {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?

0

There are 0 answers