CODEWITHSUNDEEP
javascriptgraphd3.jsforce-layout
DaViS
DaViS

Reputation: 613

Optimize d3 force directed layout, via charge/gravity properties, based on number of nodes

I've been working on a network topology visualization using the force-directed algorithm built into D3. Everything is working well but having troubles with one important detail... I can't seem to get the graph to layout in an ideal way for graphs with a varying number of nodes. By ideal, i mean the nodes are nicely spaced out from each (no overlap) and nodes cluster wherever it makes sense. I've been trying to do this by adjusting the 'charge' and 'gravity' properties of the force layout, but no matter what i try, it seems to always work for one scenario (ie. large number of nodes), but not for another scenario (ie. small number of nodes). For example, if i have the layout working for a large graph, then when i look at small graph using the same formula for charge/gravity, ill have a few nodes that are way way out of site from the rest of the nodes. Here's an example of a formula i was using based on another SO question post:

var k = Math.sqrt(json.nodes.length / (dim.w * dim.h));
var charge = -10 / k;
var gravity = 100 * k;

This works for a graph with 14 nodes, but if i try the same with a graph of 5 nodes, some of those nodes are completely off the screen. Note that the width/height used in the calculation of 'k' is not changing between these two scenarios. Now maybe i shouldn't have these properties based on the width/height of visible area of graph. To be honest, this is not a requirement. I don't need the graph to render and fit within the viewport of graph. I just need the graph to lay itself out sensibly, so it's fine if some of it may be outside of visible area, especially in a large graph. I've also tried the following with some success, but i still find nodes are being rendered too far away from the rest of the graph for small graphs:

var charge = -1 * Math.pow(json.nodes.length, 3);
var gravity = 1 / json.nodes.length;

Can anyone out there help me out with this ? Would be greatly appreciated as i feel kind of stuck on this atm.

Upvotes: 3

Views: 2684

Answers (2)

DaViS
DaViS

Reputation: 613

I actually figured this out on my own...

So the values i was using for charge/gravity/etc were not so much the problem. The issue was related to how many times the tick function was being called to adjust the graph. For my larger graphs, the nodes were always laid out fairly well. The main problem i was having was with smaller graphs. I was finding that nodes would frequently be placed outside of the viewport when the graph only had around 5-10 nodes in it.

In my code, im calling the tick function manually, like so:

force.start();

for (var i = tickLimit; i > 0; --i)
    force.tick();

force.stop();

Previously, tickLimit was being set as follows:

var tickLimit = Math.pow(json.nodes.length, 2);

After messing around with charge/gravity values etc, I eventually realized that this is not sufficient for small graphs. If i have a graph with 4 nodes, then that means only 16 tick() calls will be made. This is not enough for the graph to adjust itself fully (ie. stabilize). Therefore i just needed to add a check to ensure the graph ticks a minimum number of times (ex. at least 300), and a maximum (ex. no more than 10000).

This may not work for everyone but it solves the issue for me.

Upvotes: 3

pkuderov
pkuderov

Reputation: 3551

In this force based algorithm case I would say that it's almost impossible to set all-cases-fit settings. This layout'd hardly depend on graph density and inner graph semantic.
What is the range of possible number of nodes? What about density? Is it randomly generated graph with predefined density coefficient or it has some semantic behind and has possibility to look good based on this semantic.
You said that nodes flows far away from each other. What higher gravity gives you?
Also the suggestion about linkDistance may help you too. E.g. I'm using d3.forceLayout also for drawing network graphs (but they're mostly small handmade graphs with nodes < 50). And I just copied stats from one of Mike Bostock's force layout example. Here they're:

// graph force layout defaults
var linkDistance = 50,
    charge = -200;
// chart properties
var height = 720,
    width = 720;
    radius = 10;

I don't expect that it'll help you but maybe it'll stimulate the others to discuss.

UPD. All I can suggest you is to experiment. Choose a small set of test graphs and find optimal init settings for every one, then interpolate given numbers. Also if you deal with very big graphs (very big for "nice" visualization I mean) maybe you'll find grouping (colapsing) some parts of it helpfull - it reduces the number of nodes (and maybe the graph complexity).
Also keep in mind you don't need to set constant force layout settings (charge, gravity, linkDistance and etc. are all maintain functions). And you can set radius of nodes a little bit more than visible radius so they won't overlapping each other. Or set non constant function for charge, e.g. smth like this. Or use Mike Bostock advice to spread nodes on each tick manually.

Upvotes: 2

Related Questions