Skip to content

Commit fd804ce

Browse files
mbostockmbostock
committed
Better force layout.
Use Barnes-Hut criterion (a fast multipole method) for approximating repulsive charge forces between nodes. This replaces the previous approach using Floyd- Warshall to compute the graph theoretic distance between all nodes, eliminating O(n^3) initialization time. Additionally, the charge force is now O(n lg n) per iteration rather than O(n^2). Using the center of mass of the graph, apply gravitional attraction towards the graph center (based on the layout size). This encourages the graph to stay near the center rather than drifting away.
1 parent 587b1bb commit fd804ce

4 files changed

Lines changed: 220 additions & 113 deletions

File tree

‎d3.layout.js‎

Lines changed: 109 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -155,42 +155,127 @@ d3.layout.force = function() {
155155
var force = {},
156156
event = d3.dispatch("tick"),
157157
size = [1, 1],
158-
alpha = .5,
158+
alpha = .1,
159+
drag = .9,
159160
distance = 30,
161+
charge = -60,
162+
gravity = 180,
163+
theta = .8,
160164
interval,
161165
nodes,
162166
links,
163167
distances;
164168

169+
function accumulate(n) {
170+
var cx = 0,
171+
cy = 0;
172+
n.count = 0;
173+
if (!n.leaf) {
174+
n.nodes.forEach(function(c) {
175+
accumulate(c);
176+
n.count += c.count;
177+
cx += c.count * c.cx;
178+
cy += c.count * c.cy;
179+
});
180+
}
181+
if (n.point) {
182+
n.count++;
183+
cx += n.point.x;
184+
cy += n.point.y;
185+
}
186+
n.cx = cx / n.count;
187+
n.cy = cy / n.count;
188+
}
189+
190+
function repulse(p) {
191+
return function(n, x1, y1, x2, y2) {
192+
var dx = n.cx - p.x,
193+
dy = n.cy - p.y,
194+
dn = 1 / Math.sqrt(dx * dx + dy * dy);
195+
196+
/* Barnes-Hut criterion. */
197+
if ((x2 - x1) * dn < theta) {
198+
var k = alpha * charge * n.count * dn * dn;
199+
p.fx += dx * k;
200+
p.fy += dy * k;
201+
return true;
202+
}
203+
204+
if (n.point && (n.point != p)) {
205+
var k = alpha * charge * dn * dn;
206+
p.fx += dx * k;
207+
p.fy += dy * k;
208+
}
209+
};
210+
}
211+
165212
function tick() {
166-
var n = distances.length,
213+
var n = nodes.length,
214+
m = links.length,
215+
q = d3.geom.quadtree(nodes),
167216
i, // current index
168-
o, // current link
217+
o, // current object
169218
s, // current source
170219
t, // current target
171220
l, // current distance
172221
x, // x-distance
173222
y; // y-distance
174223

175-
// gauss-seidel relaxation
176-
for (i = 0; i < n; ++i) {
177-
o = distances[i];
224+
// reset forces
225+
i = -1; while (++i < n) {
226+
(o = nodes[i]).fx = o.fy = 0;
227+
}
228+
229+
// gauss-seidel relaxation for links
230+
for (i = 0; i < m; ++i) {
231+
o = links[i];
178232
s = o.source;
179233
t = o.target;
180234
x = t.x - s.x;
181235
y = t.y - s.y;
182236
if (l = Math.sqrt(x * x + y * y)) {
183-
l = alpha / (o.distance * o.distance) * (l - distance * o.distance) / l;
237+
l = alpha * (l - distance) / l;
184238
x *= l;
185239
y *= l;
186-
if (!t.fixed) {
187-
t.x -= x;
188-
t.y -= y;
189-
}
190-
if (!s.fixed) {
191-
s.x += x;
192-
s.y += y;
193-
}
240+
t.x -= x;
241+
t.y -= y;
242+
s.x += x;
243+
s.y += y;
244+
}
245+
}
246+
247+
// compute quadtree center of mass
248+
accumulate(q);
249+
250+
// apply gravity forces
251+
x = size[0] / 2 - q.cx;
252+
y = size[1] / 2 - q.cy;
253+
l = Math.min(.02, 1 / Math.sqrt(x * x + y * y));
254+
l = alpha * gravity * l * l;
255+
x *= l;
256+
y *= l;
257+
i = -1; while (++i < n) {
258+
o = nodes[i];
259+
o.fx += x;
260+
o.fy += y;
261+
}
262+
263+
// apply charge forces
264+
i = -1; while (++i < n) {
265+
q.visit(repulse(nodes[i]));
266+
}
267+
268+
// position verlet integration
269+
i = -1; while (++i < n) {
270+
o = nodes[i];
271+
if (o.fixed) {
272+
o.x = o.px;
273+
o.y = o.py;
274+
} else {
275+
x = o.px - (o.px = o.x);
276+
y = o.py - (o.py = o.y);
277+
o.x += o.fx - x * drag;
278+
o.y += o.fy - y * drag;
194279
}
195280
}
196281

@@ -231,59 +316,27 @@ d3.layout.force = function() {
231316

232317
force.start = function() {
233318
var i,
234-
j,
235-
k,
236319
n = nodes.length,
237320
m = links.length,
238321
w = size[0],
239322
h = size[1],
240323
o;
241324

242-
var paths = [];
325+
// TODO initialize positions of new nodes using constraints (links)
243326
for (i = 0; i < n; ++i) {
244327
o = nodes[i];
245-
o.x = o.x || Math.random() * w;
246-
o.y = o.y || Math.random() * h;
247-
o.fixed = 0;
248-
paths[i] = [];
249-
for (j = 0; j < n; ++j) {
250-
paths[i][j] = Infinity;
251-
}
252-
paths[i][i] = 0;
328+
if (isNaN(o.x)) o.x = Math.random() * w;
329+
if (isNaN(o.y)) o.y = Math.random() * h;
330+
if (isNaN(o.px)) o.px = o.x;
331+
if (isNaN(o.py)) o.py = o.y;
253332
}
254333

255334
for (i = 0; i < m; ++i) {
256335
o = links[i];
257-
paths[o.source][o.target] = 1;
258-
paths[o.target][o.source] = 1;
259-
o.source = nodes[o.source];
260-
o.target = nodes[o.target];
336+
if (typeof o.source == "number") o.source = nodes[o.source];
337+
if (typeof o.target == "number") o.target = nodes[o.target];
261338
}
262339

263-
// Floyd-Warshall
264-
for (k = 0; k < n; ++k) {
265-
for (i = 0; i < n; ++i) {
266-
for (j = 0; j < n; ++j) {
267-
paths[i][j] = Math.min(paths[i][j], paths[i][k] + paths[k][j]);
268-
}
269-
}
270-
}
271-
272-
distances = [];
273-
for (i = 0; i < n; ++i) {
274-
for (j = i + 1; j < n; ++j) {
275-
distances.push({
276-
source: nodes[i],
277-
target: nodes[j],
278-
distance: paths[i][j] * paths[i][j]
279-
});
280-
}
281-
}
282-
283-
distances.sort(function(a, b) {
284-
return a.distance - b.distance;
285-
});
286-
287340
d3.timer(tick);
288341
return force;
289342
};
@@ -321,8 +374,8 @@ d3.layout.force = function() {
321374
function mousemove() {
322375
if (!node) return;
323376
var m = d3.svg.mouse(element);
324-
node.x = m[0];
325-
node.y = m[1];
377+
node.px = m[0];
378+
node.py = m[1];
326379
force.resume(); // restart annealing
327380
}
328381

0 commit comments

Comments
 (0)