1 // A rudimentary force layout using Gauss-Seidel.

     2 d3.layout.force = function() {

     3   var force = {},

     4       event = d3.dispatch("tick"),

     5       size = [1, 1],

     6       drag,

     7       alpha,

     8       friction = .9,

     9       linkDistance = d3_layout_forceLinkDistance,

    10       linkStrength = d3_layout_forceLinkStrength,

    11       charge = -30,

    12       gravity = .1,

    13       theta = .8,

    14       interval,

    15       nodes = [],

    16       links = [],

    17       distances,

    18       strengths,

    19       charges;

    20 

    21   function repulse(node) {

    22     return function(quad, x1, y1, x2, y2) {

    23       if (quad.point !== node) {

    24         var dx = quad.cx - node.x,

    25             dy = quad.cy - node.y,

    26             dn = 1 / Math.sqrt(dx * dx + dy * dy);

    27 

    28         /* Barnes-Hut criterion. */

    29         if ((x2 - x1) * dn < theta) {

    30           var k = quad.charge * dn * dn;

    31           node.px -= dx * k;

    32           node.py -= dy * k;

    33           return true;

    34         }

    35 

    36         if (quad.point && isFinite(dn)) {

    37           var k = quad.pointCharge * dn * dn;

    38           node.px -= dx * k;

    39           node.py -= dy * k;

    40         }

    41       }

    42       return !quad.charge;

    43     };

    44   }

    45 

    46   function tick() {

    47     var n = nodes.length,

    48         m = links.length,

    49         q,

    50         i, // current index

    51         o, // current object

    52         s, // current source

    53         t, // current target

    54         l, // current distance

    55         k, // current force

    56         x, // x-distance

    57         y; // y-distance

    58 

    59     // gauss-seidel relaxation for links

    60     for (i = 0; i < m; ++i) {

    61       o = links[i];

    62       s = o.source;

    63       t = o.target;

    64       x = t.x - s.x;

    65       y = t.y - s.y;

    66       if (l = (x * x + y * y)) {

    67         l = alpha * strengths[i] * ((l = Math.sqrt(l)) - distances[i]) / l;

    68         x *= l;

    69         y *= l;

    70         t.x -= x * (k = s.weight / (t.weight + s.weight));

    71         t.y -= y * k;

    72         s.x += x * (k = 1 - k);

    73         s.y += y * k;

    74       }

    75     }

    76 

    77     // apply gravity forces

    78     if (k = alpha * gravity) {

    79       x = size[0] / 2;

    80       y = size[1] / 2;

    81       i = -1; if (k) while (++i < n) {

    82         o = nodes[i];

    83         o.x += (x - o.x) * k;

    84         o.y += (y - o.y) * k;

    85       }

    86     }

    87 

    88     // compute quadtree center of mass and apply charge forces

    89     if (charge) {

    90       d3_layout_forceAccumulate(q = d3.geom.quadtree(nodes), alpha, charges);

    91       i = -1; while (++i < n) {

    92         if (!(o = nodes[i]).fixed) {

    93           q.visit(repulse(o));

    94         }

    95       }

    96     }

    97 

    98     // position verlet integration

    99     i = -1; while (++i < n) {

   100       o = nodes[i];

   101       if (o.fixed) {

   102         o.x = o.px;

   103         o.y = o.py;

   104       } else {

   105         o.x -= (o.px - (o.px = o.x)) * friction;

   106         o.y -= (o.py - (o.py = o.y)) * friction;

   107       }

   108     }

   109 

   110     event.tick({type: "tick", alpha: alpha});

   111 

   112     // simulated annealing, basically

   113     return (alpha *= .99) < .005;

   114   }

   115 

   116   force.on = function(type, listener) {

   117     event.on(type, listener);

   118     return force;

   119   };

   120 

   121   force.nodes = function(x) {

   122     if (!arguments.length) return nodes;

   123     nodes = x;

   124     return force;

   125   };

   126 

   127   force.links = function(x) {

   128     if (!arguments.length) return links;

   129     links = x;

   130     return force;

   131   };

   132 

   133   force.size = function(x) {

   134     if (!arguments.length) return size;

   135     size = x;

   136     return force;

   137   };

   138 

   139   force.linkDistance = function(x) {

   140     if (!arguments.length) return linkDistance;

   141     linkDistance = d3.functor(x);

   142     return force;

   143   };

   144 

   145   // For backwards-compatibility.

   146   force.distance = force.linkDistance;

   147 

   148   force.linkStrength = function(x) {

   149     if (!arguments.length) return linkStrength;

   150     linkStrength = d3.functor(x);

   151     return force;

   152   };

   153 

   154   force.friction = function(x) {

   155     if (!arguments.length) return friction;

   156     friction = x;

   157     return force;

   158   };

   159 

   160   force.charge = function(x) {

   161     if (!arguments.length) return charge;

   162     charge = typeof x === "function" ? x : +x;

   163     return force;

   164   };

   165 

   166   force.gravity = function(x) {

   167     if (!arguments.length) return gravity;

   168     gravity = x;

   169     return force;

   170   };

   171 

   172   force.theta = function(x) {

   173     if (!arguments.length) return theta;

   174     theta = x;

   175     return force;

   176   };

   177 

   178   force.start = function() {

   179     var i,

   180         j,

   181         n = nodes.length,

   182         m = links.length,

   183         w = size[0],

   184         h = size[1],

   185         neighbors,

   186         o;

   187 

   188     for (i = 0; i < n; ++i) {

   189       (o = nodes[i]).index = i;

   190       o.weight = 0;

   191     }

   192 

   193     distances = [];

   194     strengths = [];

   195     for (i = 0; i < m; ++i) {

   196       o = links[i];

   197       if (typeof o.source == "number") o.source = nodes[o.source];

   198       if (typeof o.target == "number") o.target = nodes[o.target];

   199       distances[i] = linkDistance.call(this, o, i);

   200       strengths[i] = linkStrength.call(this, o, i);

   201       ++o.source.weight;

   202       ++o.target.weight;

   203     }

   204 

   205     for (i = 0; i < n; ++i) {

   206       o = nodes[i];

   207       if (isNaN(o.x)) o.x = position("x", w);

   208       if (isNaN(o.y)) o.y = position("y", h);

   209       if (isNaN(o.px)) o.px = o.x;

   210       if (isNaN(o.py)) o.py = o.y;

   211     }

   212 

   213     charges = [];

   214     if (typeof charge === "function") {

   215       for (i = 0; i < n; ++i) {

   216         charges[i] = +charge.call(this, nodes[i], i);

   217       }

   218     } else {

   219       for (i = 0; i < n; ++i) {

   220         charges[i] = charge;

   221       }

   222     }

   223 

   224     // initialize node position based on first neighbor

   225     function position(dimension, size) {

   226       var neighbors = neighbor(i),

   227           j = -1,

   228           m = neighbors.length,

   229           x;

   230       while (++j < m) if (!isNaN(x = neighbors[j][dimension])) return x;

   231       return Math.random() * size;

   232     }

   233 

   234     // initialize neighbors lazily

   235     function neighbor() {

   236       if (!neighbors) {

   237         neighbors = [];

   238         for (j = 0; j < n; ++j) {

   239           neighbors[j] = [];

   240         }

   241         for (j = 0; j < m; ++j) {

   242           var o = links[j];

   243           neighbors[o.source.index].push(o.target);

   244           neighbors[o.target.index].push(o.source);

   245         }

   246       }

   247       return neighbors[i];

   248     }

   249 

   250     return force.resume();

   251   };

   252 

   253   force.resume = function() {

   254     alpha = .1;

   255     d3.timer(tick);

   256     return force;

   257   };

   258 

   259   force.stop = function() {

   260     alpha = 0;

   261     return force;

   262   };

   263 

   264   // use `node.call(force.drag)` to make nodes draggable

   265   force.drag = function() {

   266     if (!drag) drag = d3.behavior.drag()

   267         .on("dragstart", dragstart)

   268         .on("drag", d3_layout_forceDrag)

   269         .on("dragend", d3_layout_forceDragEnd);

   270 

   271     this.on("mouseover.force", d3_layout_forceDragOver)

   272         .on("mouseout.force", d3_layout_forceDragOut)

   273         .call(drag);

   274   };

   275 

   276   function dragstart(d) {

   277     d3_layout_forceDragOver(d3_layout_forceDragNode = d);

   278     d3_layout_forceDragForce = force;

   279   }

   280 

   281   return force;

   282 };

   283 

   284 var d3_layout_forceDragForce,

   285     d3_layout_forceDragNode;

   286 

   287 function d3_layout_forceDragOver(d) {

   288   d.fixed |= 2;

   289 }

   290 

   291 function d3_layout_forceDragOut(d) {

   292   if (d !== d3_layout_forceDragNode) d.fixed &= 1;

   293 }

   294 

   295 function d3_layout_forceDragEnd() {

   296   d3_layout_forceDrag();

   297   d3_layout_forceDragNode.fixed &= 1;

   298   d3_layout_forceDragForce = d3_layout_forceDragNode = null;

   299 }

   300 

   301 function d3_layout_forceDrag() {

   302   d3_layout_forceDragNode.px += d3.event.dx;

   303   d3_layout_forceDragNode.py += d3.event.dy;

   304   d3_layout_forceDragForce.resume(); // restart annealing

   305 }

   306 

   307 function d3_layout_forceAccumulate(quad, alpha, charges) {

   308   var cx = 0,

   309       cy = 0;

   310   quad.charge = 0;

   311   if (!quad.leaf) {

   312     var nodes = quad.nodes,

   313         n = nodes.length,

   314         i = -1,

   315         c;

   316     while (++i < n) {

   317       c = nodes[i];

   318       if (c == null) continue;

   319       d3_layout_forceAccumulate(c, alpha, charges);

   320       quad.charge += c.charge;

   321       cx += c.charge * c.cx;

   322       cy += c.charge * c.cy;

   323     }

   324   }

   325   if (quad.point) {

   326     // jitter internal nodes that are coincident

   327     if (!quad.leaf) {

   328       quad.point.x += Math.random() - .5;

   329       quad.point.y += Math.random() - .5;

   330     }

   331     var k = alpha * charges[quad.point.index];

   332     quad.charge += quad.pointCharge = k;

   333     cx += k * quad.point.x;

   334     cy += k * quad.point.y;

   335   }

   336   quad.cx = cx / quad.charge;

   337   quad.cy = cy / quad.charge;

   338 }

   339 

   340 function d3_layout_forceLinkDistance(link) {

   341   return 20;

   342 }

   343 

   344 function d3_layout_forceLinkStrength(link) {

   345   return 1;

   346 }