d3 force directed graph downward force simulation

Question

Maybe this isn't the best way to do this, but now that I've gone down the rabbit hole, I want to know how it works. I'm trying to use d3 to create a tree where the nodes will settle downwards, much like there is gravity. I'm hoping that this, along with the charge that each node has and the tension in the rope will make it so that it will end up looking as I imagine, with it balancing itself out. I'm trying to simulate this constant downward acceleration in d3, but I'm a beginner at d3, and don't know exactly how. I'm also running into the problem that the simulation stops running, and d3.timer(force.resume) doesn't help.

So essentially, I want to have a root node fixed at a certain position like a pivot, with child nodes coming off of it and gravity, charges, and tension being present so that the children settle automatically and balance themselves into a tree structure.

Answer 1

Force directed simulations are a great way to layout a tree, a diagram, or a graph. This method is used in many open source and commercial libraries and applications, so D3 is just one of many. Also, this topic constantly attracts attention of applied mathematicians.

I just want to tell you this is a huge topic. If one limits oneself just to D3, there are still a number of ways to do what you described in your question. Since this answer has to have a reasonable length, I'll try to show only some highlights to you, by walking you through 3 D3 examples. I'll start with a simple example of force directed tree layout (that is not really what you want, bit it is simple), and each example will build on previous, and will be closer to what you want to achieve.

Example 1

link to jsfiddle

This is a basic example of a tree laid out in radial way by D3 force layout. You really need to understand ALL code that is used. I'll just mention here some highlights:

• function getData() returns a test tree (which is a convenient subset of so called "flare" test tree);
• function flatten() converts tree object to an array, this is format needed to initialize D3 force layout;
• positions of all nodes are initialized (otherwise D3 force layout will behave a little strange and unpredictable);
• root node position is initialized to the center of the diagram, and root node is declared fixed;
• function "ontick" is provided, and it just draws links and nodes exactly as they behave during the simulation;
• D3 force layout algorithm is initialized with D3 gravity 0.2 and D3 charge -200;
• D3 force layout algorithm is started by calling its method start().

Let me know if you have additional question related to this example. I know the code looks a little weird for people without D3 experience - but, in reality, its very simple, and easy to understand, once you get D3 force layout to know. You can play with different D3 gravity and D3 charge, to understand better why specific values 0.2 and -200 are chosen.

This, of course, is not what you want, but it can serve as a "canonical example" for us.

Example 2

link to jsfiddle

Codewise, this example differs from previus just in two things:

• Root node position is initialized at (width/2, 100) instead of (width/2, height/2) - this is natural position of the root for "hanging" layout"
• A custom force is defined in "ontick" function in following lines:

var ky = e.alpha;

links.forEach(function(d, i) {

d.target.y += (d.target.depth * 100 - d.target.y) * 5 * ky;

});

This custom force will attract the nodes of the same depth to the same horizontal line. This is enough to produce the diagram in the picture.

However, you can notice somwhat unnatural arangements of certain nodes in the diagram - generally, they don't look like precisely as if they are "hanging" off of parent. Next example will be an attempt to fix that.

Example 3

link to jsfiddle

This looks more natural than previous example.

New in this example is just one more custom force: one that "centers" all parents to the middle of horizontal positions of their children. You can easily find the code responsible for that in the "ontick()" function.

This looks much closer to what what you want. I am not claiming this is an ideal layout for your needs. However, it can serve you as a good starting point. Once you understand all these examples, you will be able to modify them, and, if you want, to create different simulations, based on different custom forces.

So, the last example is not simulation based on physical gravity, but it has effects similar to physical gravity. If you want to simulate physical gravity, this will require a little bit more of code - but do you really need it, if the effect is almost the same?

Hope this helps. Let me know if you have a question, need a clarification, etc.

Answer 2

The easiest way to do this would be to simply tweak the "size" if the layout so that the center for the existing "gravity" force is at the bottom of the display, while the root node is fixed at the top of the display. However, you will probably have to do a lot of tweaking of parameters to get things looking nicely.

Example here: http://jsfiddle.net/cSn6w/13/

var force = d3.layout.force()
    .on("tick", tick)
    .charge(-30)
    .linkDistance(10)
    .gravity(0.005)
    .size([w, 2*h]);

Another option would be to add a "custom force", similar to what is used in the Multi-foci force layout example. The specifics of the calculation used in that demo aren't relevant, but the idea is simply that, at the beginning of each tick() function, every data point is adjusted slightly in a certain direction. If that direction throws off any of the other constraints, it will be counter-acted in the next tick by the internal calculations of the layout.

Example here: http://jsfiddle.net/cSn6w/14/

var g = 0.0005;
function gravityFunction(d,i) {
    if (d.fixed) return;
   //used to modify each data object's position
   //at the start of every tick
   var distToGround = h-d.y;
   if (distToGround <= 0) d.y = h; //make "ground" solid
   else d.y += g * (Math.min(distToGround, h/4) ); 
}
function tick() {
    nodeCircles.each(gravityFunction) 
       //adjust each node according to the custom force
        .attr("cx", function (d) {
            return d.x;
        })
        /* etc. */

Getting the gravity function optimized for a nice layout will be the tricky part. Based on my experiments, you will probably want to keep track of the depth of each node in the tree, and have either the gravity function or the link strength correlate with depth, so that you don't end up stretching out the "trunk" of your tree too much.