Visualize a tree from list of arrays

Cumulo Nimbus 0
Viewed 49

Given the following input of arrays:

[a, b, d]
[a, b, e]
[a, c, f]
[a, c, g]
[a, c, h]

I'd like an output that builds a tree looking like:

      a
    /    \
   b      c
  / \   / | \
 d  e  f  g  h

This solution should apply to any number or arrays.

I've looked for a good tool to achieve this but have not found anything as of yet. I have looked at https://pypi.org/project/treebuilder/ and https://www.jstree.com/ but neither meet these requirements. Thinking I'll just write my own, but wanted to see if anyone had any clever solutions, suggestions or input on how to do this. I'm guessing the best solution for this type of thing will be something written in Python or JavaScript, so tagging these languages, but am open to a solution in any language

language-agnostic tree javascript python
1 Answers

The input/output suggests that the tree is a bit like a trie, i.e., parent nodes have children that are uniquely identified by their labels, and there could be multiple top-level nodes, held together by an unrendered (super)root node.

So we could first build such a tree data structure, using object properties (dict keys in Python) much like is done in tries, but without the "word-end" notion.

Then from that data structure we could produce the text output. Here we would perform a depth-first iteration (post-order), where the string representation for sibling trees is "merged" line by line.

Here is an implementation in JavaScript:

class TrieNode {
    static PADDING = 2 // Space between horiztonally adjacent node labels
    addPath([key, ...path]) {
        if (key === undefined) return;
        if (!Object.hasOwn(this, key)) this[key] = new TrieNode;
        this[key].addPath(path);
    }
    toString() {
        const prefixAll = (lines, count) => lines.forEach((line, i) => lines[i] = " ".repeat(count) + line);

        function buildLines(node) {
            let lines = [];
            for (const [key, child] of Object.entries(node)) {
                let childLines = buildLines(child);
                let width = childLines.reduce((acc, {length}) => Math.max(acc, length), 0);
                // Ensure there is enough width to fit the key
                if (key.length > width) {
                    prefixAll(childLines, (key.length - width) >> 1)
                    width = key.length;
                }
                // Determine position for key
                const i = (1 + childLines[0]?.search(/[┤├┼│┴]/)) || (key.length + 1) >> 1;
                // Add line with the key and a line with a temporary edge on top of this key
                childLines.unshift("┬".padStart(i), key.padStart(i + (key.length >> 1)));
                // Accumuate this subtree with previous sibling subtrees:
                // Calcuate horizontal offset of this subtree
                let x = Math.max(...childLines.slice(0, lines.length).map((line, i) =>                 
                    lines[i].length + TrieNode.PADDING - (line + ".").search(/\S/)
                ));
                if (x < 0) { // Make room at left side of partial tree if needed
                    prefixAll(lines, -x);
                    x = 0;
                }
                // Merge next subtree at the right side of the partial tree
                childLines.forEach((line, i) =>
                    lines[i] = line.replace(/^\s*/, m => (lines[i] ?? "").padEnd(x + m.length))
                );
            }
            // Connect the subtrees with a horizontal branch, towards a single upward branch
            if (!lines.length) return lines;
            let top = lines[0];
            const i = (top.length - 1 + top.indexOf("┬")) >> 1;
            top = top.replace(/(?<=┬)\s+(?=┬)/g, m => "─".repeat(m.length))
                      .replace("┬", "┌")
                      .replace(/┌$/, "│")
                      .replace(/┬$/, "┐");
            lines[0] = top.slice(0, i) + "┤├┼│┴"["┐┌┬│─".indexOf(top[i])] + top.slice(i + 1);
            return lines;
        }
        
        const lines = buildLines(this);
        if (lines[0].includes("│")) lines.shift(); // If top-level has just one node
        return lines.join("\n");
    }
}

let trie = new TrieNode();
let paths = [
    ["aaa", "cccccc", "ffff","ooooo"],
    ["aaa", "cccccc", "ffff","ppppp", "qqqqq"],
    ["aaa", "cccccc", "ffff","ppppp", "rrrrrr"],
    ["aaa", "cccccc", "ffff","ppppp", "ssssss"],
    ["aaa", "cccccc", "gggggg"],
    ["aaa", "cccccc", "hhh"],
    ["aaa", "bbbb", "ddd"],
    ["aaa", "bbbb", "eeeee", "iiiiiii"],
    ["aaa", "bbbb", "eeeee", "jjj", "s", "tttttttttttttttttttttttttttttttttttttttttttttttttttttttttt"],
    ["aaa", "bbbb", "eeeee", "kkk"],
    ["aaa", "bbbb", "eeeee", "lll"],
    ["aaa", "bbbb", "eeeee", "mmm"],
    ["other_root"]
];
// Load the paths into the trie:
for (const path of paths) trie.addPath(path);
console.log(trie.toString());

The fiddling with strings is a bit cumbersome. I hope the comments clarify a bit what is happening.

trincot0
Related