In the world of software today, you can usually find a 3rd party library or existing code for anything you need to do, whether that’s using Moment.js to handle everything that is time related or using react-dnd for drag and drop functionality. A good engineer should be willing to first evaluate that no one has already solved their problem before starting a custom solution -- especially these days when there are so many excellent libraries out there. If you were tasked with using a library or tool to render a tree of nodes and lines, what would you use? In our case, the task was to create a method of rendering lines and node components that represents a hierarchical tree structure. Our problem was slightly complicated by the fact that we needed to be able to support different configurations and designs for our nodes and lines as well as allow for individualized interactions with each line and node.
Open Source Libraries
When evaluating the current open source offerings, we considered a multitude of options including:
- Countless tree rendering libraries (including D3 and various forks of the D3 tree implementation as well as some React specific tree libraries)
- Sankey Diagrams
Over a period of a week and a half, we evaluated the alternatives and at the end of that time, we were left with the realization that the best we could do using these libraries wasn’t good enough for what we needed:
- D3 didn’t work for us because while it gave us the flexibility over the lines that we needed, the actual nodes themselves weren’t customizable enough as is and would have required a greater amount of effort to work around.
- A lot of the tree rendering libraries required us to pre-define the configurations of the trees and then they would simply inject the variables and values where needed. That was a problem because the whole point of this feature is to support almost any configuration of lines and nodes.
- Sankey diagrams led us down a whole rabbit hole of other options and trade-offs, but ultimately we were left with the realization that we would just need to come up with our own solution.
Some of the custom options we considered but ended up discarding were:
- Using HTML elements and just using styling to control the look and positioning of the lines
- Using the HTML Canvas methods and drawing the lines by moving to each point separately
We discarded Option 1 because it would have forced us to spend a lot of time on styling the elements and we would have had to make too many compromises on design. Meanwhile, Option 2 would have involved some heavy calculations each time the components needed to be updated and would have made the code more unreadable and harder to maintain in the future.
Having exhausted those choices, we spent two days prototyping a few options and there was one that was clearly superior. The final design we landed on to render the structures we needed was a mix of Scalable Vector Graphics (SVG) paths and React components.
React trees with Bézier Curves
Once we had a plan in place, the question then became: Where do we even start with this? One of the things that was clear from the beginning was that we needed to keep track of the parent-child relationships of our nodes since all of the positioning of the elements relied on the positioning of the parent nodes. For example, if we have a node `Foo` that has two children: `Bar` and `Baz`, where we render Bar and Baz directly relies on where `Foo` is positioned. Furthermore, the shapes of the lines connecting the children to the parent node needed to be smooth curves that we could easily define. So for each line we needed to be able to connect two nodes: the parent and the child. To do so, we needed at least:
- Location of the parent = starting point of the line
- Location of the child node = ending point of the line
- Intermediate point(s) defining the smoothness and definition of the curve itself
These requirements led us to cubic Bézier curves because they are widely used in vector graphics to model smooth curves and they require only three defining sets of coordinates: Two control points that specify where the curve begins and ends and the actual point (x,y) where you want the line to end (the starting point of the line is handled separately). This is exactly what we wanted!
But before we get into the actual calculations of our starting and ending points, let’s talk about SVG paths. SVGs themselves are defined in XML format within HTML <svg /> tags. The path element is used to create lines, curves, arcs and other 2d shapes. The shape of the path element is defined by the d attribute which contains a series of commands and parameters that the commands use. In the example below, the M command is the “move to” command so it specifies that the path will move to and in this case start at the coordinate (10,55). Using SVG paths was a clear choice then because two of the three curve commands for SVG paths (denoted by the C in the example below) use Bézier curves! For more about reading and understanding SVG paths, check out this handy tutorial.
Using all this information about Bézier curves and SVG paths, we came up with a few formulas to generate the Bézier curves, which use the position of the parent node as well as the number of sibling nodes the child node has in order to calculate the starting and ending points for the curves. Once the starting and ending points of the lines have been calculated, we pass the coordinates into React components to be rendered into SVG paths.
One of the other main reasons for going with SVG paths was the ability to render the nodes themselves as separate HTML components from the lines. Since the lines and the nodes are independently created, the positioning of the nodes simply relies on using the already calculated coordinates of the lines. The ending coordinate of a line is also the starting coordinate of the child node. Since the structure of our entire tree is stored as a hierarchical representation of the nodes, by recursively iterating through the tree and drawing each node as it is processed along with the lines that connect it to its children, we are able to parallelize the rendering of the lines and the nodes. This is a modified preorder traversal of the tree which uses a visitor design pattern to actually process and render each node appropriately. Thus, each node is actually a React component that is added to the results of the recursive call which are eventually rendered. Since each node is represented as an HTML component, it is extremely easy to customize and control the elements.
The basic implementation of the lines and nodes can be boiled down to the following:
- Calculate the starting and ending points for the Bézier curve control points
- Render the lines and nodes
- Configure time optimizations, style tweaks, etc.
Once we had the rendering of the lines and nodes figured out, all that was left was to tweak the formulas used to calculate the starting and ending points. At one point, we even had the length of the lines as a customizable option that resulted in lines of time-proportionate length. Since the rendering of the lines and nodes has been separated, making changes like that are relatively simple and do not require large re-writes of the code, which is obviously optimal. There are also some optimizations to reduce the amount of times the whole tree structure needs to be iterated over as well as how often each element renders due to changes in other elements. However, since it all depends on the positioning of the other elements, we needed a solution that would allow for quick and lightweight re-renders and updates as needed.
We could have probably spent time cobbling together bits and pieces of various open source solutions for tree and line graphs to come up with something that fit our needs, but we found that it made more sense to implement a custom solution given the parameters of the problem we needed to solve. In our case, configurability and customizability were two things we simply couldn’t give up, and that meant we couldn’t use an existing solution easily. In general, we say evaluate the current offerings out there, and if none quite fit what you need, figure out the best approach that gives you the things that are missing. If you need a highly customizable and configurable network of curves and nodes, we are planning on open sourcing our approach in the future, but in the meantime we recommend you look into Bézier curves and SVG paths.