--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/toolkit/javascript/d3/src/layout/force.js Thu Apr 10 14:20:23 2014 +0200
@@ -0,0 +1,346 @@
+// A rudimentary force layout using Gauss-Seidel.
+d3.layout.force = function() {
+ var force = {},
+ event = d3.dispatch("tick"),
+ size = [1, 1],
+ drag,
+ alpha,
+ friction = .9,
+ linkDistance = d3_layout_forceLinkDistance,
+ linkStrength = d3_layout_forceLinkStrength,
+ charge = -30,
+ gravity = .1,
+ theta = .8,
+ interval,
+ nodes = [],
+ links = [],
+ distances,
+ strengths,
+ charges;
+
+ function repulse(node) {
+ return function(quad, x1, y1, x2, y2) {
+ if (quad.point !== node) {
+ var dx = quad.cx - node.x,
+ dy = quad.cy - node.y,
+ dn = 1 / Math.sqrt(dx * dx + dy * dy);
+
+ /* Barnes-Hut criterion. */
+ if ((x2 - x1) * dn < theta) {
+ var k = quad.charge * dn * dn;
+ node.px -= dx * k;
+ node.py -= dy * k;
+ return true;
+ }
+
+ if (quad.point && isFinite(dn)) {
+ var k = quad.pointCharge * dn * dn;
+ node.px -= dx * k;
+ node.py -= dy * k;
+ }
+ }
+ return !quad.charge;
+ };
+ }
+
+ function tick() {
+ var n = nodes.length,
+ m = links.length,
+ q,
+ i, // current index
+ o, // current object
+ s, // current source
+ t, // current target
+ l, // current distance
+ k, // current force
+ x, // x-distance
+ y; // y-distance
+
+ // gauss-seidel relaxation for links
+ for (i = 0; i < m; ++i) {
+ o = links[i];
+ s = o.source;
+ t = o.target;
+ x = t.x - s.x;
+ y = t.y - s.y;
+ if (l = (x * x + y * y)) {
+ l = alpha * strengths[i] * ((l = Math.sqrt(l)) - distances[i]) / l;
+ x *= l;
+ y *= l;
+ t.x -= x * (k = s.weight / (t.weight + s.weight));
+ t.y -= y * k;
+ s.x += x * (k = 1 - k);
+ s.y += y * k;
+ }
+ }
+
+ // apply gravity forces
+ if (k = alpha * gravity) {
+ x = size[0] / 2;
+ y = size[1] / 2;
+ i = -1; if (k) while (++i < n) {
+ o = nodes[i];
+ o.x += (x - o.x) * k;
+ o.y += (y - o.y) * k;
+ }
+ }
+
+ // compute quadtree center of mass and apply charge forces
+ if (charge) {
+ d3_layout_forceAccumulate(q = d3.geom.quadtree(nodes), alpha, charges);
+ i = -1; while (++i < n) {
+ if (!(o = nodes[i]).fixed) {
+ q.visit(repulse(o));
+ }
+ }
+ }
+
+ // position verlet integration
+ i = -1; while (++i < n) {
+ o = nodes[i];
+ if (o.fixed) {
+ o.x = o.px;
+ o.y = o.py;
+ } else {
+ o.x -= (o.px - (o.px = o.x)) * friction;
+ o.y -= (o.py - (o.py = o.y)) * friction;
+ }
+ }
+
+ event.tick({type: "tick", alpha: alpha});
+
+ // simulated annealing, basically
+ return (alpha *= .99) < .005;
+ }
+
+ force.on = function(type, listener) {
+ event.on(type, listener);
+ return force;
+ };
+
+ force.nodes = function(x) {
+ if (!arguments.length) return nodes;
+ nodes = x;
+ return force;
+ };
+
+ force.links = function(x) {
+ if (!arguments.length) return links;
+ links = x;
+ return force;
+ };
+
+ force.size = function(x) {
+ if (!arguments.length) return size;
+ size = x;
+ return force;
+ };
+
+ force.linkDistance = function(x) {
+ if (!arguments.length) return linkDistance;
+ linkDistance = d3.functor(x);
+ return force;
+ };
+
+ // For backwards-compatibility.
+ force.distance = force.linkDistance;
+
+ force.linkStrength = function(x) {
+ if (!arguments.length) return linkStrength;
+ linkStrength = d3.functor(x);
+ return force;
+ };
+
+ force.friction = function(x) {
+ if (!arguments.length) return friction;
+ friction = x;
+ return force;
+ };
+
+ force.charge = function(x) {
+ if (!arguments.length) return charge;
+ charge = typeof x === "function" ? x : +x;
+ return force;
+ };
+
+ force.gravity = function(x) {
+ if (!arguments.length) return gravity;
+ gravity = x;
+ return force;
+ };
+
+ force.theta = function(x) {
+ if (!arguments.length) return theta;
+ theta = x;
+ return force;
+ };
+
+ force.start = function() {
+ var i,
+ j,
+ n = nodes.length,
+ m = links.length,
+ w = size[0],
+ h = size[1],
+ neighbors,
+ o;
+
+ for (i = 0; i < n; ++i) {
+ (o = nodes[i]).index = i;
+ o.weight = 0;
+ }
+
+ distances = [];
+ strengths = [];
+ for (i = 0; i < m; ++i) {
+ o = links[i];
+ if (typeof o.source == "number") o.source = nodes[o.source];
+ if (typeof o.target == "number") o.target = nodes[o.target];
+ distances[i] = linkDistance.call(this, o, i);
+ strengths[i] = linkStrength.call(this, o, i);
+ ++o.source.weight;
+ ++o.target.weight;
+ }
+
+ for (i = 0; i < n; ++i) {
+ o = nodes[i];
+ if (isNaN(o.x)) o.x = position("x", w);
+ if (isNaN(o.y)) o.y = position("y", h);
+ if (isNaN(o.px)) o.px = o.x;
+ if (isNaN(o.py)) o.py = o.y;
+ }
+
+ charges = [];
+ if (typeof charge === "function") {
+ for (i = 0; i < n; ++i) {
+ charges[i] = +charge.call(this, nodes[i], i);
+ }
+ } else {
+ for (i = 0; i < n; ++i) {
+ charges[i] = charge;
+ }
+ }
+
+ // initialize node position based on first neighbor
+ function position(dimension, size) {
+ var neighbors = neighbor(i),
+ j = -1,
+ m = neighbors.length,
+ x;
+ while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x;
+ return Math.random() * size;
+ }
+
+ // initialize neighbors lazily
+ function neighbor() {
+ if (!neighbors) {
+ neighbors = [];
+ for (j = 0; j < n; ++j) {
+ neighbors[j] = [];
+ }
+ for (j = 0; j < m; ++j) {
+ var o = links[j];
+ neighbors[o.source.index].push(o.target);
+ neighbors[o.target.index].push(o.source);
+ }
+ }
+ return neighbors[i];
+ }
+
+ return force.resume();
+ };
+
+ force.resume = function() {
+ alpha = .1;
+ d3.timer(tick);
+ return force;
+ };
+
+ force.stop = function() {
+ alpha = 0;
+ return force;
+ };
+
+ // use `node.call(force.drag)` to make nodes draggable
+ force.drag = function() {
+ if (!drag) drag = d3.behavior.drag()
+ .on("dragstart", dragstart)
+ .on("drag", d3_layout_forceDrag)
+ .on("dragend", d3_layout_forceDragEnd);
+
+ this.on("mouseover.force", d3_layout_forceDragOver)
+ .on("mouseout.force", d3_layout_forceDragOut)
+ .call(drag);
+ };
+
+ function dragstart(d) {
+ d3_layout_forceDragOver(d3_layout_forceDragNode = d);
+ d3_layout_forceDragForce = force;
+ }
+
+ return force;
+};
+
+var d3_layout_forceDragForce,
+ d3_layout_forceDragNode;
+
+function d3_layout_forceDragOver(d) {
+ d.fixed |= 2;
+}
+
+function d3_layout_forceDragOut(d) {
+ if (d !== d3_layout_forceDragNode) d.fixed &= 1;
+}
+
+function d3_layout_forceDragEnd() {
+ d3_layout_forceDrag();
+ d3_layout_forceDragNode.fixed &= 1;
+ d3_layout_forceDragForce = d3_layout_forceDragNode = null;
+}
+
+function d3_layout_forceDrag() {
+ d3_layout_forceDragNode.px += d3.event.dx;
+ d3_layout_forceDragNode.py += d3.event.dy;
+ d3_layout_forceDragForce.resume(); // restart annealing
+}
+
+function d3_layout_forceAccumulate(quad, alpha, charges) {
+ var cx = 0,
+ cy = 0;
+ quad.charge = 0;
+ if (!quad.leaf) {
+ var nodes = quad.nodes,
+ n = nodes.length,
+ i = -1,
+ c;
+ while (++i < n) {
+ c = nodes[i];
+ if (c == null) continue;
+ d3_layout_forceAccumulate(c, alpha, charges);
+ quad.charge += c.charge;
+ cx += c.charge * c.cx;
+ cy += c.charge * c.cy;
+ }
+ }
+ if (quad.point) {
+ // jitter internal nodes that are coincident
+ if (!quad.leaf) {
+ quad.point.x += Math.random() - .5;
+ quad.point.y += Math.random() - .5;
+ }
+ var k = alpha * charges[quad.point.index];
+ quad.charge += quad.pointCharge = k;
+ cx += k * quad.point.x;
+ cy += k * quad.point.y;
+ }
+ quad.cx = cx / quad.charge;
+ quad.cy = cy / quad.charge;
+}
+
+function d3_layout_forceLinkDistance(link) {
+ return 20;
+}
+
+function d3_layout_forceLinkStrength(link) {
+ return 1;
+}