Orbital Relationships In D3.js Force Graphs
Simply put, the client was publishing static, flowchart-like pdf files on their website, but was interested in making them interactive. Between Typo3 and d3, the client can now easily create interactive “maps”, where users can drag, drop and edit the individual segments of the map.
Early on, the client requested that these interactive maps support two different ways of visualizing relationships between the map nodes: linear and orbital. Implementing linear relationships was quite simple, but the latter required a bit more effort. Though the implementation of orbital relationships was but one of the many facets of this project, that is what this blog post will focus on. This blog post is code-heavy, so be ready to look at quite a bit of javascript.
Requirements
Before starting work on this, I drew up a little checklist for myself:
1) When a node is dragged, all of the node’s descendant nodes should also be dragged (this force-directed d3 graph represents the nodes in a heirarchical manner).
2) When a node is dragged, all of the node’s sibling nodes should rotate as well and keep the radial spacing between themselves even.
3) Find a way to draw and update the line that represents the orbit.
4) The map creator should be able to decide which “levels” to visualize as orbits. A node’s level/depth is how far away from the central node it is.
In thinking about how to update all these events as they happen, I turned to my “tick” function, which is called many times per second by d3 in order to create the illusion of a fluid, physics-based graph. The javascript to initialize a barebones d3 force graph looks something like the following.
1 2 3 4 5 6 |
|
Through this blog post, I’m hoping to get across just how flexible d3.js is. It’s really quite powerful, and combined with the javascript engines of modern browsers, I think that very interesting applications can be developed. From here on out, I’ll assume that you know the basics of d3 and its force graphs, including selections, their methods and the name-spaced properties d3 uses for force nodes (such as .x, .y and .fixed). Let’s dive into some code!
Setting Up A Necessary Associative Array
The functionality revolves (pun!) around creating an associative array where the key is the unique identifier of a node and the value is a d3 selection of that node’s direct descendants.
To create this object, I began with an empty array and an empty javascript object.
1 2 |
|
We also need an array of integers, which will represent all of the relationship levels that we would like to visualize as orbits. In this app, this array is received from the typo3 backend within a json object.
1 |
|
Each node’s d3 data (attached to each node as the “__data__” property) has a “depth” property, which represents how many relationships away from the central node the given node is. This custom, non-native d3 “depth” property is being declared earlier in my script using a bit of recursion, but that’s a topic for another blog entry. Each node’s d3 data also has a “parent_node” property, which was also defined in the same recursive function. It holds the value of a given node’s parent’s unique id as a string. We will be referring to each node’s “depth” and “parent_node” properties in upcoming code blocks.
Early in my script, I attached a “depth” and “parent_node” property to every node’s d3 data (which is in turn attached to each node as the “__data__” property) using a bit of recursion. A node’s “depth” property tells us how many relationships away from the central node the given node is. The “parent_node” property holds the given node’s parent node’s unique id as a string. A node’s parent node is the node that connects the given node to the rest of the graph and is always one relationship closer to the graph’s central node.
Let’s fill up orbit_level_selections.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
Okay cool. Now let’s use orbit_level_selections to define all of the previously-mentioned key/value pairs in orbit_object.
1 2 3 4 5 6 7 8 9 |
|
Sorting Child Nodes Using Quadrants
Regarding the third item from my checklist above (drawing and updating the lines representing orbits), a problem that I quickly faced was that in order to programmatically draw these orbital relationships as svg path elements, I was going to have to sort the child nodes of each parent in clockwise (or counter-clockwise) order, with the parent serving as a focal point. To help me with this, I wrote the following function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
The arguments that should be passed in quadrantize() are the offset x, y and hypotenuse of the child node relative to its parent node. In other words, the value that will eventually be passed as “your_x” is defined as (parent_node.x – child_node.x). If this is a bit unclear, you will see quadrantize in action later in this post.
You may have noticed that the quadrants are organized in a different manner than usual. The (+, +) quadrant (or quadrant I) is typically located in the upper right-hand corner of coordinate graphs. However, because our x and y values are relative to the top-left corner of the nodes’ wrapper element, our Quadrant I is in the bottom-right corner.
Inserting The Orbital Lines Into The Dom
Below, we will use quadrantize() to sort individual elements contained within the d3 selections of orbit_object in clockwise order.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
We can finally insert the svg elements that will make up the orbital visualizations into the DOM. When we call the following draw_orbits() function with orbit_object as an argument, the function will iterate over each d3.selection and create the necessary svg elements. Keep in mind that the line representing each orbital relationship is actually made up of multiple svg elements (one for every two
neighboring nodes).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
|
With the above two functions declared, draw_orbits() and sort_node_orbits(), all we have to do is call them while passing in orbit_object as an argument. Then all we will have left to do is figure out how to update these elements when the user drags a node! Woo!
1 2 |
|
The Tick() Function
This is where it starts getting hairy… I call the following within the tick function I mentioned above under “Requirements”. Most of the logic behind rotating and translating nodes lies in the rotate_siblings() and translate_all_children() functions, which I will cover soon.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 |
|
Rotating Siblings
Recall that rotate_siblings() is only called when the node that the user is dragging is the parent in an orbital relationship.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
|
Translating Every Child Node
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
20/20 Hindsight
The above code crams a lot of stuff into the tick() function, which is called many times per second. Despite my initial suspicions of the code being too “heavy” for tick(), I haven’t found the graph to be noticeably slower than it used to be. I think that this is because all of the orbital-updating code only runs while a node is being dragged. The orbital nodes are “fixed”, which means that d3’s physics simulator is processing a lot less information than if the nodes weren’t fixed.
If I were charged with developing this same functionality again, I would approach it slightly differently. All of the above code is based off of offset coordinates. I have noticed slight leaks in calculations, which I think are the result of rotating nodes based off rounded offset values. Once values are set, they are not checked to ensure that they are where they “should” be.
For example, let’s say there is a parent with three children being represented as an orbital relationship. The coordinates for each child should place them evenly around the parent. Let’s say one child’s coordinates place it 0 degrees from the parent, the second at 120 and the last at 240. The angle created by the radii extending from the parent node to any two nodes is 120 degrees. Through the code described in this post, actual values are rounded and these three angles, which are supposed to always remain at 120 degrees, might fluctuate and become 119/123/118.
The code I developed doesn’t recognize whether the angle created by two nodes and their parent is where it “should” be. It only offsets coordinates based off of the displacement of the dragged node. Even if it did, I don’t think that this would be the best way to solve the issue. I think that if the code I developed emphasized where coordinates “should” be, rather than just offset values and displacements, there would be no need for corrective action in the first place.
This is a train of thought I would like to explore, and if you have any ideas on how to implement self-correcting orbital relationships, please comment.