How to convert a tree-like structure to a plain HTML table using rowspans?

Given a structure of nodes from different data sources where one node depends on 0 to n other nodes but a single node can only depend on nodes from one source

const nodes = [
    { dataSourceId: "a", id: "a-1", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-2", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-3", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "b", id: "b-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-2", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-3", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1", "a-2"] },
    { dataSourceId: "c", id: "c-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-1"] },
    { dataSourceId: "c", id: "c-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-3", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-4", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-5", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "c", id: "c-6", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "e", id: "e-1", dependsOnDataSourceId: "c", dependsOnNodes: ["c-1", "c-3"] },
    { dataSourceId: "e", id: "e-2", dependsOnDataSourceId: "c", dependsOnNodes: ["c-3"] },
    { dataSourceId: "self-reference", id: "a-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "d", id: "d-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "d", id: "d-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
];

nodes is not sorted, the order is random (and should not matter).

I want to represent this structure as a HTML table using rowspans. What I know is the order of columns where each data source represents a column

const dataSourceIds = ["a", "b", "c", "d", "e", "self-reference"];

The first item in dataSourceIds ( "a" ) always represents the group of root nodes.

First I tried to "draw" the expected result

table, th, td {
  border: 1px solid black;
}

<table>
  <thead>
    <tr>
      <th>a</th>
      <th>b</th>
      <th>c</th>
      <th>d</th>
      <th>e</th>
      <th>self-reference</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td rowspan="9">a-1</td>
      <td>b-1</td>
      <td>c-1</td>
      <td><!-- Empty for source d --></td>
      <td>e-1</td>
      <td>a-1</td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td rowspan="6">b-2</td>
      <td>c-2</td>
      <td>d-1</td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td rowspan="2">c-3</td>
      <td>d-2</td>
      <td>e-1</td>
      <td><!-- Empty for source a-to-a --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td style="display: none"><!-- Covered by c-3 rowspan --></td>
      <td><!-- Empty for source d --></td>
      <td>e-2</td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td>c-4</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td>c-5</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-2 rowspan --></td>
      <td>c-6</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td rowspan="2">b-3</td>
      <td>c-5</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-1 rowspan --></td>
      <td style="display: none"><!-- Covered by b-3 rowspan --></td>
      <td>c-6</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td rowspan="2">a-2</td>
      <td rowspan="2">b-3</td>
      <td>c-5</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td style="display: none"><!-- Covered by a-2 rowspan --></td>
      <td style="display: none"><!-- Covered by b-3 rowspan --></td>
      <td>c-6</td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
    <tr>
      <td>a-3</td>
      <td><!-- Empty for source b --></td>
      <td><!-- Empty for source c --></td>
      <td><!-- Empty for source d --></td>
      <td><!-- Empty for source e --></td>
      <td><!-- Empty for source self-reference --></td>
    </tr>
  </tbody>
</table>

This is what I tried so far

const nodes = [
    { dataSourceId: "a", id: "a-1", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-2", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "a", id: "a-3", dependsOnDataSourceId: undefined, dependsOnNodes: [] },
    { dataSourceId: "b", id: "b-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-2", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "b", id: "b-3", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1", "a-2"] },
    { dataSourceId: "c", id: "c-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-1"] },
    { dataSourceId: "c", id: "c-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-3", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-4", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "c", id: "c-5", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "c", id: "c-6", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2", "b-3"] },
    { dataSourceId: "e", id: "e-1", dependsOnDataSourceId: "c", dependsOnNodes: ["c-1", "c-3"] },
    { dataSourceId: "e", id: "e-2", dependsOnDataSourceId: "c", dependsOnNodes: ["c-3"] },
    { dataSourceId: "self-reference", id: "a-1", dependsOnDataSourceId: "a", dependsOnNodes: ["a-1"] },
    { dataSourceId: "d", id: "d-1", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
    { dataSourceId: "d", id: "d-2", dependsOnDataSourceId: "b", dependsOnNodes: ["b-2"] },
];

const dataSourceIds = ["a", "b", "c", "d", "e", "self-reference"];

// group the nodes by source so it's easier to inspect them
const groupedNodes = {};

for (const dataSourceId of dataSourceIds) {
    groupedNodes[dataSourceId] = nodes.filter(node => node.dataSourceId === dataSourceId);
}

// extract the root node id so dataSourceIds only contains child sources
const rootNodeId = dataSourceIds.shift();

const rootNodes = groupedNodes[rootNodeId];

let rows = [];

// setup the initial rows with root nodes
for (const rootNode of rootNodes) {
    const row = {
        [rootNodeId]: rootNode
    };

    for (const dataSourceId of dataSourceIds) {
        row[dataSourceId] = "empty";
    }

    rows.push(row);
}

// fill the rows with child nodes
for (let dataSourceIdIndex = 0; dataSourceIdIndex < dataSourceIds.length; dataSourceIdIndex++) {
    const dataSourceId = dataSourceIds[dataSourceIdIndex];
    const childNodes = groupedNodes[dataSourceId];

    for (const childNode of childNodes) {
        const { dependsOnDataSourceId, dependsOnNodes } = childNode;

        for (const parentNodeId of dependsOnNodes) {
            for (let rowIndex = 0; rowIndex < rows.length; rowIndex++) {
                const row = rows[rowIndex];
                const parentNode = row[dependsOnDataSourceId];

                // parent node must exist in this row
                if (parentNode === "empty") {
                    continue;
                }

                const isParentNodeCovered = parentNode.coveredByRowIndex !== undefined;

                // parent node might be covered so we have to check the original node
                if (isParentNodeCovered) {
                    const originalParentNode = rows[parentNode.coveredByRowIndex][dependsOnDataSourceId];

                    if (originalParentNode.id !== parentNodeId) {
                        continue;
                    }
                }

                // parent node is not covered
                if (!isParentNodeCovered && parentNode.id !== parentNodeId) {
                    continue;
                }

                // simply add it if there is no value yet
                if (row[dataSourceId] === "empty") {
                    row[dataSourceId] = childNode;
                    continue;
                }

                // it should not matter if the previous child node is covered since we duplicate the row and replace its value

                // this row already has a value for this data source so we have to duplicate it
                const additionalRow = structuredClone(row);

                // replace the parent node with a rowspan
                additionalRow[dependsOnDataSourceId] = { coveredByRowIndex: rowIndex };

                // set all data source values between dependsOnDataSourceId ( exclusive ) and dataSourceIdIndex ( exclusive ) to empty
                const dependsOnDataSourceIdIndex = dataSourceIds.findIndex(previousDataSourceId => previousDataSourceId === dependsOnDataSourceId);

                for (let dataSourceIdToEmptyIndex = dependsOnDataSourceIdIndex + 1; dataSourceIdToEmptyIndex < dataSourceIdIndex; dataSourceIdToEmptyIndex++) {
                    const dataSourceIdToEmpty = dataSourceIds[dataSourceIdToEmptyIndex];
                    additionalRow[dataSourceIdToEmpty] = "empty";
                }

                // insert the new row right after the original one
                const previousRows = rows.slice(0, rowIndex);
                const nextRows = rows.slice(rowIndex, rows.length);

                rows = [
                    ...previousRows,
                    additionalRow,
                    ...nextRows
                ];

                // but don't inspect this one in the next run
                rowIndex++;
            }
        }
    }
}

console.log(rows);

where

• "empty" means that the <td> element is empty
• coveredByRowIndex means that it should use style="display: none"

The code is inefficient but this shouldn't matter for now, I want to optimize it later.

As you can see rows does not contain the expected result. It seems my algorithm is not correct yet. My thoughts on how I do it manually

• group nodes by dataSourceId
• for each a, create a new row with empty values ( except for a )
• fill b
• if there already is a b, duplicate the row and replace the a with a "covered" index
• repeat for c
• repeat for d
• repeat for e-1
• repeat for e-2 but you must replace d-2 with an "empty" value ( set all sources between parent key and own key to "empty" )
• repeat for self-reference

Do you guys have any ideas how to solve this problem? I don't think that I need the final code, I just don't have any idea how to setup the algorithm... so any pseudo code / algorithm suggestions are highly appreciated!

from How to convert a tree-like structure to a plain HTML table using rowspans?