How To Make Tree Visualizations with JavaScript and SVG Tutorial

In this article, we’ll go step by step through the process of rendering tree structures in the browser with Scalable Vector Graphics.  By the end of this post, you will have a general framework for visualizing data-driven trees that you can apply to all kinds of domains.  We’ll be using the Reingold-Tilford algorithm to automatically produce aesthetically pleasing trees from whatever data we feed into it.

See the screenshot below of what we are going to build –

visualization tree

 

You can see the demo in action and read the final code here.  In the interest of focusing on the core algorithm, I won’t be covering the details of the final rendering operation.  The linked demo, however, contains all of the code if you’d like to see that as well.

Let’s look at an overview of the steps we’ll take to arrive at the solution before starting.

  • Create the shell of the code we’ll be working with.  This will mean an HTML template and the outline of the JavaScript that will be responsible for the rendering.
  • Write the code that will transform our input data for the tree rendering algorithm to consume.
  • Implement the first stage of the algorithm that calculates initial positions for each node in the tree.
  • Implement code that re-positions children in order to center them under their parent.
  • Finally, we’ll write code to fix any overlaps that occur within the tree.

Getting started

The project will consist of a single HTML file, a separate file for the accompanying JavaScript, and some CSS.  To begin, I’ll walk through the initial HTML and the shell of the JavaScript.

<html>
    <head>
        <link rel="stylesheet" href="/styles.css" />
        <script src="/tree.js"></script>
    </head>
    <body>
        <h1>Tree Drawing Algorithm</h1>
        <svg viewBox="0 0 1000 1000" preserveAspectRatio="xMidYMid meet">
            <g transform="translate(0, 50)"></g>
        </svg>
        <script>
            let root = {
                value: "A",
                children: [
                    {
                        value: "B",
                        children: []
                    },
                    {
                        value: "C",
                        children: []
                    }
                ]
            };

            let svgNode = document.querySelector("svg g");

            let renderer = new TreeRenderer(root, svgNode);
            renderer.draw();
        </script>
    </body>
</html>

The svg g element will be the target of our drawing operations.  An SVG g element acts as a container that will allow us to shift everything inside of it using the transform property.  This is useful when applying padding to prevent overflow.

The viewBox attribute is used to define an independent coordinate space.  As a result, this allows us to work without having to account for the different dimensions that the container may end up having.

Additionally, the preserveAspectRatio attribute controls the scaling behavior of the SVG element.  Here we are telling the browser to scale up the result as much as possible and to center everything.

The script tag is placed after the SVG container because we’ll need a reference to the container when we begin the rendering process.  The container would not exist yet if we had placed the script at the top of our HTML file.

The root variable represents the first tree that we are going to render.  Every node in the tree contains a value and references to its children.  This first tree contains only three nodes, but that will be enough to explain the fundamental concepts.  Finally, we declare an instance of the TreeRenderer class that will be responsible for turning our input data into a rendered tree.

Now let’s take a look at the shell of the JavaScript code that we’ll fill in.

There’s a lot of code here, but these are the four essential tasks that it accomplishes:

  1. Consume the input data and produce a format prepared for the algorithm to consume.
  2. Space out nodes within the same level.
  3. Adjust children so that they are centered with respect to their parent.
  4. Shift entire subtrees down that overlap with other subtrees.
class TreeNode {
    constructor(value) {
        this.x = 0;
        this.y = 0;

        this.value = value;

        this.final = 0;
        this.modifier = 0;

        this.prevSibling = null;
        this.children = [];
    }

    visit(func) {
        func(this);
        for (let i = 0; i < this.children.length; i++) {
            this.children[i].visit(func);
        }
    }
}

class TreeRenderer {
    constructor(dataRoot, svgNode, width = 1000, height = 100) {
        // The root of the JavaScript object that represents the data
        // that we'll be rendering.
        this.dataRoot = dataRoot;

        // The SVG DOM node that the renderer will insert elements into.
        this.svgNode = svgNode;

        this.width = width;
        this.height = height;

        this.nodeRoot = this.prepareData(this.dataRoot, 0, null);

        this.firstPass(this.nodeRoot);
        this.secondPass(this.nodeRoot, 0);
        this.fixNodeConflicts(this.nodeRoot);
        this.shiftTreeIntoFrame();
    }

    /*
     * Build an intermediate form of the original data tree.  The nodes of
     * this new tree will be instances of the TreeNode class.
     */
    prepareData(node, level, prevSibling) {}

    /*
     * Assign initial position values to every node based on how many
     * prior siblings the current node has.
     */
    firstPass(node) {}

    /*
     * Adjust the position of children such that they end up centered
     * under their parent.
     */
    secondPass(node, modSum) {}

    /*
     * Work from the end of the tree back toward the beginning, fixing any
     * subtree overlap as we recurse through the tree.
     */
    fixNodeConflicts(node) {}
}

We’ll go step by step and fill in each missing piece.

Preprocessing the data

The goal of the prepareData method is to take our input tree and produce an identical tree made up of TreeNode instances.  We do this because there is additional information that we need to store somewhere to be used in later stages of the algorithm.  In order to determine the tree layout, each node must remember its own x and y position.  Additionally, each node maintains modifier and final values that are used to make adjustments in the second pass of the algorithm.  We’ll go into the meaning of each value in more detail as we implement the TreeRenderer methods.

prepareData(node, level, prevSibling) {
        let treeNode = new TreeNode(node.value);
        treeNode.x = level;
        treeNode.prevSibling = prevSibling;

        for (let i = 0; i < node.children.length; i++) {
            treeNode.children.push(
                this.prepareData(
                    node.children[i],
                    level + 1,
                    i >= 1 ? treeNode.children[i - 1] : null
                )
            );
        }
        return treeNode;
    }

After preprocessing the data we have a set of TreeNode instances that hold references to their parent and sibling.  Each node also knows the tree level in which they reside.

Calculating initial positions

We have created our TreeNode instances, but all of their layout values have defaulted to zero.  Our tree, if we rendered it now, would collapse into a single point.

Although I’ll show you how to render the tree in any orientation, for this article we’ll think of the tree as rendered from left to right. Because of that default orientation, calculating the x value of each node will be very simple.  The total available width (in the independent SVG coordinate space) divided by the number of tree levels will determine the space between levels.  Therefore, the x value of a node is its tree-level multiplied by the space per level.

In fact, the prepareData method has already assigned a level to each node, so this calculation should be straightforward.

The y value, however, is where most of the complexity comes from.  Finding the correct y values is a three-step process.

In the first step, we’ll derive initial values based on how many siblings a node has.  Let’s take a look at that code and walk through it.

firstPass(node) {
        for (let i = 0; i < node.children.length; i++) {
            this.firstPass(node.children[i]);
        }

        if (node.prevSibling) {
            node.y = node.prevSibling.y + NODE_SEP;
        } else {
            node.y = 0;
        }

        if (node.children.length == 1) {
            node.modifier = node.y;
        } else if (node.children.length >= 2) {
            let minY = Infinity;
            let maxY = -minY;
            for (let i = 0; i < node.children.length; i++) {
                minY = Math.min(minY, node.children[i].y);
                maxY = Math.max(maxY, node.children[i].y);
            }
            node.modifier = node.y - (maxY - minY) / 2;
        }
    }

The method is a post-order traversal of the tree, meaning that we start assigning values from bottom to top and right to left. This is important because the y value of each node depends on the y value of its previous sibling.  The modifier value of the current node comes from finding the midpoint of the children.  This will be used later, in the second pass, to shift children so that they end up centered relative to their parent.

This is what our tree would look like if we rendered it after this first step:

tree-drawing-parents-unaligned

Each node is populated with its final position value.  After this first step, each level of the tree would have a correct layout, but parents are not centered over their children.  To fix this, the second pass will use modifier values to pull the children in the right direction.

Centering nodes using position modifiers

In this next step, we’ll utilize the modifier values to offset the children of each node so that they are centered.

secondPass(node, modSum) {
        node.final = node.y + modSum;
        for (let i = 0; i < node.children.length; i++) {
            this.secondPass(node.children[i], node.modifier + modSum);
        }
    }

Unlike the first pass, here we’re using a pre-order traversal because we want the effect of the modifier to be compounding. While recursing through the tree and shifting nodes, we will carry the effect of each shift through the rest of that subtree via the modSum value.

We will use the final value to determine y-axis position when rendering the tree.  This is how the previous example tree will appear after executing the second pass:

tree-drawing-parents-aligned

Our trees are looking pretty good at this point, but there is still another important issue that our algorithm needs to contend with.

Fixing node conflicts

Neighboring nodes are going to overlap when they have too many children.  This happens because the first and second passes of the algorithm don’t take into account the subtrees of their neighbors.  After two neighboring nodes have spaced out their children and centered them, it’s fairly easy for their respective subtrees to end up overlapping.

Let’s take a look at this issue in action.

tree-drawing-with-overlaps

Here we have nodes A-G, where C is a child of B.  E, F, and G are children of D.  Unfortunately, E has completely covered up C.  Fixing this issue involves tracing the subtree contour of each node and essentially pushing one of the subtrees down and out of the way.  In this example, C defines the bottom contour of B, while E defines the top contour of D.

The following code finds the contours and pushes the bottom subtree down according to how much overlap was discovered.

fixNodeConflicts(node) {
        for (let i = 0; i < node.children.length; i++) {
            this.fixNodeConflicts(node.children[i]);
        }

        for (let i = 0; i < node.children.length - 1; i++) {
            // Get the bottom-most contour position of the current node
            let botContour = -Infinity;
            node.children[i].visit(
                node => (botContour = Math.max(botContour, node.final))
            );

            // Get the topmost contour position of the node underneath the current one
            let topContour = Infinity;
            node.children[i + 1].visit(
                node => (topContour = Math.min(topContour, node.final))
            );

            if (botContour >= topContour) {
                node.children[i + 1].visit(
                    node => (node.final += botContour - topContour + NODE_SEP)
                );
            }
        }
    }

We’ll have a much better-looking tree once we adjust the final values to account for overlaps.

tree-drawing-with-overlaps-fixed

Changing orientation

Luckily, changing the orientation of the output is fairly easy, thanks to SVG.  Instead of having to make alterations to the code we’ve already written, we can use SVG transforms to rotate the original output.

After updating the HTML to add a rotation to the g container element:

<svg viewBox="0 0 1000 1000" preserveAspectRatio="xMidYMid meet">
    <g transform="translate(550, 50) rotate(90)"></g>
</svg>

The output will be rotated:

In conclusion

I hope this post will give you a template that you can customize for your own applications. Although we covered the core of the algorithm, not every line of code is included in this post, so please refer to this link if you’d like to dive into the details.

 

SHARE ON

The Author: Zach Todd

How To Make Tree Visualizations with JavaScript and SVG Tutorial

You May Also Like

Leave a Reply

Your email address will not be published.