Orbital Relationships In D3.js Force Graphs

Tags:

October 18, 2013

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.

INFIELD DIGITAL TECHNOLOGY

With the implementation described in this post, it is possible to display orbital and linear relationships simultaneously.

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

var force = d3.layout.force()

    .nodes(array_of_nodes)

    .links(array_of_links)

    .size([canvas_width, canvas_height])

    .on("tick", tick)

    .start();

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

var orbit_level_selections = [],

    orbit_object = {};

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

var levels_which_orbit = json.orbits;

INFIELD DIGITAL TECHNOLOGY

                                               The parent-child relationship

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

if (levels_which_orbit.length !=  0) {

    for ( var a = 0; a < levels_which_orbit.length; a++ ) {

        var this_level = d3.selectAll("g.node")

            .filter(function(d) {

            // We want to filter out nodes whose depth property is not found in levels_which_orbit.

                return d.depth == levels_which_orbit[a] ? true : false;

            .each(function(d) {

                var par = d3.select("g#" + d.parentNode + ".node").datum();

                par.fixed = true;

                d.fixed = true;

            // We don't want nodes in orbits to be affected by d3's physics simulator, so we must 

            //      set their d3 data property "fixed" to "true". d3 will know not to affect them.

            })

            .classed("orbit", true)

            // Down the line, we will want to be able to tell if a node being dragged is involved 

            //      in an orbit, regardless of whether is a parent or child.

        orbit_level_selections.push(this_level);

        // Above, this_level holds a filtered d3 selection that contains every node in the level 

        //  contained by "levels_which_orbit[a]"

    };

};

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

for ( var i = 0; i < levels_which_orbit.length; i++ ) {

    orbit_level_selections[i].each(function(d) {

        if ( !orbit_object[d.parent_node] ) {

            orbit_object[d.parent_node] = orbit_level_selections[i].filter( function( that_data ) {

                return d.parent_node == that_data.parent_node ? true : false;

            });

        };

    });

};

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

function quadrantize (your_x, your_y, your_hypotenuse) {

    if ( your_x >= 0 && your_y > 0 ) {

    // (+,+) Traditionally Quadrant IV

        return Math.asin( your_y / your_hypotenuse );

    } else if ( your_x < 0 && your_y >= 0 ) {

    // (-,+) Traditionally Quadrant III

        return Math.acos( your_x / your_hypotenuse ) ; 

    } else if ( your_x <= 0 && your_y < 0 ) {

    // (-,-) Traditionally Quadrant II

        return Math.PI - Math.asin( your_y / your_hypotenuse );  

    } else if ( your_x > 0 && your_y <= 0 ) {

    // (+,-) Traditionally Quadrant I

        return Math.PI * 2 - Math.acos( your_x / your_hypotenuse );  

    }

}

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.

INFIELD DIGITAL TECHNOLOGY

                       Here, the force graph’s relationships are visualized as lines

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

var sort_node_orbits = function(to_sort) {

    for (i=0; i < to_sort.length; i++) {

        this_parent = d3.select("g#" + to_sort[i].datum().parentNode).datum();

        var counter = 0;

        to_sort[i] = to_sort[i].sort(function (a, b) {

            var offset_x_a = this_parent.x - a.x,

                offset_y_a = this_parent.y - a.y,

                offset_x_b = this_parent.x - b.x,

                offset_y_b = this_parent.y - b.y,

                offset_hyp_a = Math.sqrt(offset_x_a * offset_x_a + offset_y_a * offset_y_a),

                offset_hyp_b = Math.sqrt(offset_x_b * offset_x_b + offset_y_b * offset_y_b),

                radian_a = quadrantize(offset_x_a, offset_y_a, offset_hyp_a),

                radian_b = quadrantize(offset_x_b, offset_y_b, offset_hyp_b);

            return radian_a < radian_b ? -1 : 1;

        });

    }

}

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

var draw_orbits = function(to_draw) {

    for ( i = 0; i < to_draw.length; i++ ) {

        this_level = to_draw[i];

        for ( b in this_level[0]) {

            b  = parseFloat(b)

            // We're calling setting b to a parsed version of itself because we only 

            //      want to iterate over keys that hold elements, not keys like "parentNode"

            if ( b >= 0 ) {

                var first_arc = this_level[0][b],

                // first_arc is the element from which we want our curved line to start.

                    second_arc,

                // Below, we'll define second_arc as the element at which we want our curved line to end.

                    parent_data = d3.select("g.node." + first_arc.__data__.parentNode)[0][0].__data__,

                    rgbFromHex = hexToRGBConverter(parent_data.properties.color);

                if (this_level[0][b + 1]) {

                    second_arc = this_level[0][b + 1]

                } else {

                    second_arc = this_level[0][0]

                }

                // Above, we declare second_arc as the element that immediately follows first_arc, which 

                //      we know is the next clockwise element because we sorted all of the current d3 

                //      selection's elements in sort_node_orbits().

                // The above "else" case handles the final element in the selection. The final element's 

                //      successive clockwise element is the first element in the selection.

                d3.select("g#paths")

                // #paths is the svg element that will be holding all of the svg <path>s that will

                //      soon be rendered.

                .append("svg:path")

                    .attr("class", function(d) {

                        return "curvedpath " + parent_data.name;

                        // The class "curvedpath" is what we'll use down the line to update the orbital 

                        //      lines when nodes are dragged (using d3.selectAll(".curvedpath")).

                        // Adding the parent node's name as a class helped me with development and

                        //      debugging, but serves no other purpose.

                    })

                    .property("parent", parentData )

                    .property("source", first_arc.__data__)

                    .property("target", second_arc.__data__);

                        // We need to attach the d3 data of all three nodes that are involved in the 

                        //      rendering of this arc: the parent and two neighboring children. 

                        //  When we want to update this <path>, we will use the coordinates of these 

                        //      three nodes to figure out the starting and ending coordinates of the 

                        //      <path>, as well as the values needed to render a perfect curvature.

                    .style("stroke", parent_data.properties.color)

                    .style("stroke-width", (nodeTreeDepth - parent_data.depth) * 30 + "px")

                d3.select('g#' + parent_data.name + '.node')

                    .classed("orbParent", true);

                // Later on we'll want to check whether a node that is being dragged is a parent in an 

                //      orbit, which we'll do by checking if the dragged node has the "orbParent" class.

            }

        }

    }

}

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

sort_node_orbits(orbit_object);

draw_orbits(orbit_object);

 INFIELD DIGITAL TECHNOLOGY

                        A screenshot of the finalized, locally-developed prototype

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

if (levels_which_orbit != []) {

    d3.selectAll(".curvedpath")

    // "curvedpath" is a class given to all of the svg <path> elements that make up the orbital

    //      relationships. The number of path elements used per orbit is the same as the amount

    //      of nodes in the orbit.

        .attr('d', function(d) {

            var d_source = this.source,

                d_target = this.target,

                d_parent = this.parent,

            // "this" is referring to each individual svg .curvedpath element, to which I had given 

            //      the "source", "target" and "parent" properties. Each of these properties holds a 

            //      copy of the respective node's d3 data (reachable by d3.select("css selector").datum() 

            //      or the node's "__data__" property)

                ax = ( d_source.x - d_parent.x),

                ay = ( d_source.y - d_parent.y),

                bx = ( d_target.x - d_parent.x + ax ) / 2,

                by = ( d_target.y - d_parent.y + ay ) / 2,

                cr = Math.sqrt( bx * bx + by * by ),

            // "cr" is necessary in defining the curvature of the current svg element

                numOrbs = d_parent.numOfLinks + d_parent.numOfSignals;

            // numOrbs is the total amount of nodes in a given orbit, including the parent. Having to 

            //      gather this value by adding two properties is a result of a different feature 

            //      requested by the client.

                if (d_parent.depth != 0) {

                    numOrbs -= 1;

            // The -1 is to account for the node around which the child nodes orbit. We only want the 

            //      number of orbiting nodes in the current relationship. The map's central node has no 

            //      parent, so we should not account for its parent.

                };

                if (numOrbs == 1) {

            // The following renders a special path in the event that an orbit only contains a single node.

            //      The returned value draws a full circle around the parent node.

                    return "M" + d_source.x + "," + d_source.y + 

                    "A" + cr + "," + cr + " 0 0,1 " + 

                    (2 * d_parent.x - d_target.x) + "," + (2 * d_parent.y - d_target.y) + 

                    "A" + cr + "," + cr + " 0 0,1 " + 

                    d_source.x + "," + d_source.y;

                } else if (numOrbs == 2) {

                    cr = 12.5;

                } else {

                    cr *= Math.pow(numOrbs / 6, -1)

                }

            // I derived the above equation, ( A / 6 ) ^ -1 = B, from a combination of trial and error 

            //      and a pair of basic algebraic functions that I developed earlier this year, which 

            //      I'm about to pimp. The goal of this self-imposed project was, given two pairs of 

            //      integers, [A, B] and [C, D], to find a single equation that represents the 

            //      relationship between both numbers in each pair. 

            // Below is what I found during the trial and error phase, where I quickly recognized a 

            //      pattern, but couldn't figure out how to put them into an equation for the sake of 

            //      scaling past six nodes. That's when I bust out my secret weapon, which is beyond 

            //      the scope of this post.

                // } else if (numOrbs == 3) {

                //     cr *= 2;

                // } else if (numOrbs == 4) {

                //     cr *= 1.5;

                // } else if (numOrbs == 5) {

                //     cr *= 1.25;

                // } else if (numOrbs >= 6) {

                //     cr *= 1.125;

                // };

                return "M" + d_source.x + "," + d_source.y + 

                "A" + cr + "," + cr + " 0 0,1 " + 

                d_target.x + "," + d_target.y;

        });

    var dragged_node = d3.select(".dragging");

    if (dragged_node[0][0] != null) {

    // One of the changes I made to the default d3 dragging functionality was to add a class of "dragging"

    //      to the node that is being dragged. Because this code is running inside of tick(), there will 

    //      not always be a node that is being dragged, making the above check imperative.

    // Side note: d3.select(".example")[0][0] is the same as d3.select(".example").node(). 

    //      Syntactic sugar be damned!

        if (dragged_node[0][0].className.baseVal.indexOf("orb") > -1) {

        // There are certainly better ways to check if a node is involved in an orbit than this. I gave 

        //      both the parents and the children involved in an orbital visualization a class name that 

        //      starts with "orb", so I took a shortcut by performing the above check.

            if ( draggedNode.classed("orbParent") && typeof(old_x) != "undefined") {

            //  The first boolean above returns true if the dragged node is a parent in an orbit.

            //  The second boolean is in place because all of this code relating to orbits is 

            //      dependant on offset values, or values that are derived from comparing older 

            //      coordinates to new ones. 

            //  In our case, these offset values compare the dragged node's new coordinates to its

            //      coordinates from the ones from the last time tick() was called, which was maybe 100

            //      milliseconds ago. Every time a dragged node is released/dropped, old_x and y are set 

            //      back to undefined, which prevents the following code from running.

            //  We'll record the old coordinates further down the line.

                var this_data = dragged_node.datum();

                offset_x = this_data.x - old_x,

                offset_y = this_data.y - old_y;

                // offset_x and y are used within translate_all_children(), though take note that 

                //      they are not being passed as arguments.

                translate_all_children(this_data);

            };

            if ( draggedNode.classed("orbit") && typeof(old_x) != "undefined") {

            //  The first boolean above returns true if the dragged node is a parent OR a child node.

            //  The second boolean is in place for the same reasons as mentioned earlier.

                var this_data = dragged_node.datum();

                offX = this_data.x - old_x;

                offY = this_data.y - old_y;

                rotate_siblings(this_data);

            };

            old_x = dragged_node.datum().x;

            old_y = dragged_node.datum().y;

        }

    } else {

    //  If a node is not being dragged, old_x and y are emptied. They will be defined as 

    //      integers the next time that a node is dragged.

        old_x = undefined;

        old_y = undefined;

    } 

}

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

var rotate_siblings = function (k_data) {

    // Through the k_data parameter, I pass the bound data of the node being dragged.

    var rotate_parent = d3.select("g#" + k_data.parent_node + ".node").datum(),

        this_x = rotate_parent.x - k_data.x,

        this_y = rotate_parent.y - k_data.y,

        this_hypotenuse = Math.sqrt(this_x * this_x + this_y * this_y),

        this_angle = quadrantize(this_x, this_y, this_hypotenuse),

        this_old_x = rotate_parent.x - oldX,

        this_old_y = rotate_parent.y - oldY,

        this_old_hyp = Math.sqrt(this_old_x * this_old_x + this_old_y * this_old_y),

        old_angle = quadrantize(this_old_x, this_old_y, this_old_hyp),

        offset_angle = this_angle - old_angle;

    orbit_object[k_data.parent_node].each(function(sib) {

    //  Let's iterate through each of the dragged node's siblings using the orbit_object object, 

    //      which we created earlier.

    //  Above, we use the dragged node's d3 data's (k_data) parent_node property as a key to a d3 

    //      selection of all of that parent's children.

        if (k_data.name != sib.name) {

        // The above check is in place so that we don't run the following code for the node that is 

        //      being dragged. We only want to rotate its siblings.

            var current_sibling_x = rotate_parent.x - sib.x,

                current_sibling_y = rotate_parent.y - sib.y,

                current_sibling_hyp = Math.sqrt( current_sibling_x * current_sibling_x + 

                    current_sibling_y * current_sibling_y),

                current_sibling_angle = quadrantize( 

                    current_sibling_x, current_sibling_y, current_sibling_hyp

                ),

            // Above, the quadrantize() function that we declared earlier makes an appearance. Recall 

            //      that the values that should be passed as arguments are not coordinates relative 

            //      to the upper-left corner of the wrapping element, but relative to the parent node.

                current_rotate_angle = current_sibling_angle + offset_angle,

                sib_new_x = (current_sibling_hyp * Math.cos(current_rotate_angle)),

                sib_new_y = (current_sibling_hyp * Math.sin(current_rotate_angle));

                offset_x = rotate_parent.x - sib_new_x - sib.x;

                offset_y = rotate_parent.y - sib_new_y - sib.y;

            // offset_x and y are defined here only to be used in translate_all_children(). Notice 

            //      that they aren't being passed as arguments when we call translate_all_children()

            //      a few lines below, which means that using the correct variable name is imperative.

                sib.x = rotate_parent.x - sib_new_x;

                sib.y = rotate_parent.y - sib_new_y;

                sib.px = rotate_parent.x - sib_new_x;

                sib.py = rotate_parent.y - sib_new_y;

                

            // Above, we give the dragged node's currently-selected sibling (sib) its new coordinates.

                translate_all_children(sib);

            // The desired functionality is not to also rotate all of the descendants of the nodes that 

            //      we are rotating. Rather, it is to translate them relative to the coordinates of 

            //      the newly-rotated node, hence, our call to translate_all_children() above.

    })

}

 INFIELD DIGITAL TYPO3 TECHNOLOGY

                  The children of rotated siblings are translated along with their parent.

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

var translate_all_children = function (j_data) {

    if (orbit_object[j_data.name]) {

        orbit_object[j_data.name]

            .attr("transform", function(d) {

                new_x = (d.x + offset_x);

                new_y = (d.y + offset_y);

                // Above, we're using the offset_x and y variables that are declared before

                //      translate_all_children is called. They hold the currently-selected 

                //      node's displacement between its old coordinates and its new ones.

                d.x = new_x;

                d.y = new_y;

                d.px = new_x;

                d.py = new_y;

                return "translate(" + new_x + "," + new_y + ")";

            })

        orbit_object[j_data.name].each( function (e) {

            translate_all_children(e)

        //  Here, recursion is used to translate all descendants of the node that is being 

        //      dragged. 

        //  When translate_all_children() is called within rotate_siblings(), 

        //      this will also recurse and translate all descendants of the rotated siblings. 

        //  Because translate_all_children() is only reached if the d3 selection returned 

        //      by orbit_object[j_data.name] holds at least one element, we won't create an 

        //      infinite loop by running this.

        })

    }

}

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.