1 /**
  2  * Constructs a new, empty force-directed layout. Layouts are not typically
  3  * constructed directly; instead, they are added to an existing panel via
  4  * {@link pv.Mark#add}.
  5  *
  6  * @class Implements force-directed network layout as a node-link diagram. This
  7  * layout uses the Fruchterman-Reingold algorithm, which applies an attractive
  8  * spring force between neighboring nodes, and a repulsive electrical charge
  9  * force between all nodes. An additional drag force improves stability of the
 10  * simulation. See {@link pv.Force.spring}, {@link pv.Force.drag} and {@link
 11  * pv.Force.charge} for more details; note that the n-body charge force is
 12  * approximated using the Barnes-Hut algorithm.
 13  *
 14  * <p>This layout is implemented on top of {@link pv.Simulation}, which can be
 15  * used directly for more control over simulation parameters. The simulation
 16  * uses Position Verlet integration, which does not compute velocities
 17  * explicitly, but allows for easy geometric constraints, such as bounding the
 18  * nodes within the layout panel. Many of the configuration properties supported
 19  * by this layout are simply passed through to the underlying forces and
 20  * constraints of the simulation.
 21  *
 22  * <p>Force layouts are typically interactive. The gradual movement of the nodes
 23  * as they stabilize to a local stress minimum can help reveal the structure of
 24  * the network, as can {@link pv.Behavior.drag}, which allows the user to pick
 25  * up nodes and reposition them while the physics simulation continues. This
 26  * layout can also be used with pan & zoom behaviors for interaction.
 27  *
 28  * <p>To facilitate interaction, this layout by default automatically re-renders
 29  * using a <tt>setInterval</tt> every 42 milliseconds. This can be disabled via
 30  * the <tt>iterations</tt> property, which if non-null specifies the number of
 31  * simulation iterations to run before the force-directed layout is finalized.
 32  * Be careful not to use too high an iteration count, as this can lead to an
 33  * annoying delay on page load.
 34  *
 35  * <p>As with other network layouts, the network data can be updated
 36  * dynamically, provided the property cache is reset. See
 37  * {@link pv.Layout.Network} for details. New nodes are initialized with random
 38  * positions near the center. Alternatively, positions can be specified manually
 39  * by setting the <tt>x</tt> and <tt>y</tt> attributes on nodes.
 40  *
 41  * @extends pv.Layout.Network
 42  * @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.8444&rep=rep1&type=pdf"
 43  * >"Graph Drawing by Force-directed Placement"</a> by T. Fruchterman &
 44  * E. Reingold, Software--Practice & Experience, November 1991.
 45  */
 46 pv.Layout.Force = function() {
 47   pv.Layout.Network.call(this);
 48 
 49   /* Force-directed graphs can be messy, so reduce the link width. */
 50   this.link.lineWidth(function(d, p) { return Math.sqrt(p.linkValue) * 1.5; });
 51   this.label.textAlign("center");
 52 };
 53 
 54 pv.Layout.Force.prototype = pv.extend(pv.Layout.Network)
 55     .property("bound", Boolean)
 56     .property("iterations", Number)
 57     .property("dragConstant", Number)
 58     .property("chargeConstant", Number)
 59     .property("chargeMinDistance", Number)
 60     .property("chargeMaxDistance", Number)
 61     .property("chargeTheta", Number)
 62     .property("springConstant", Number)
 63     .property("springDamping", Number)
 64     .property("springLength", Number);
 65 
 66 /**
 67  * The bound parameter; true if nodes should be constrained within the layout
 68  * panel. Bounding is disabled by default. Currently the layout does not observe
 69  * the radius of the nodes; strictly speaking, only the center of the node is
 70  * constrained to be within the panel, with an additional 6-pixel offset for
 71  * padding. A future enhancement could extend the bound constraint to observe
 72  * the node's radius, which would also support bounding for variable-size nodes.
 73  *
 74  * <p>Note that if this layout is used in conjunction with pan & zoom
 75  * behaviors, those behaviors should have their bound parameter set to the same
 76  * value.
 77  *
 78  * @type boolean
 79  * @name pv.Layout.Force.prototype.bound
 80  */
 81 
 82 /**
 83  * The number of simulation iterations to run, or null if this layout is
 84  * interactive. Force-directed layouts are interactive by default, using a
 85  * <tt>setInterval</tt> to advance the physics simulation and re-render
 86  * automatically.
 87  *
 88  * @type number
 89  * @name pv.Layout.Force.prototype.iterations
 90  */
 91 
 92 /**
 93  * The drag constant, in the range [0,1]. A value of 0 means no drag (a
 94  * perfectly frictionless environment), while a value of 1 means friction
 95  * immediately cancels all momentum. The default value is 0.1, which provides a
 96  * minimum amount of drag that helps stabilize bouncy springs; lower values may
 97  * result in excessive bounciness, while higher values cause the simulation to
 98  * take longer to converge.
 99  *
100  * @type number
101  * @name pv.Layout.Force.prototype.dragConstant
102  * @see pv.Force.drag#constant
103  */
104 
105 /**
106  * The charge constant, which should be a negative number. The default value is
107  * -40; more negative values will result in a stronger repulsive force, which
108  * may lead to faster convergence at the risk of instability. Too strong
109  * repulsive charge forces can cause comparatively weak springs to be stretched
110  * well beyond their rest length, emphasizing global structure over local
111  * structure. A nonnegative value will break the Fruchterman-Reingold algorithm,
112  * and is for entertainment purposes only.
113  *
114  * @type number
115  * @name pv.Layout.Force.prototype.chargeConstant
116  * @see pv.Force.charge#constant
117  */
118 
119 /**
120  * The minimum distance at which charge forces are applied. The default minimum
121  * distance of 2 avoids applying forces that are two strong; because the physics
122  * simulation is run at discrete time intervals, it is possible for two same-
123  * charged particles to become very close or even a singularity! Since the
124  * charge force is inversely proportional to the square of the distance, very
125  * small distances can break the simulation.
126  *
127  * <p>In rare cases, two particles can become stuck on top of each other, as a
128  * minimum distance threshold will prevent the charge force from repelling them.
129  * However, this occurs very rarely because other forces and momentum typically
130  * cause the particles to become separated again, at which point the repulsive
131  * charge force kicks in.
132  *
133  * @type number
134  * @name pv.Layout.Force.prototype.chargeMinDistance
135  * @see pv.Force.charge#domain
136  */
137 
138 /**
139  * The maximum distance at which charge forces are applied. This improves
140  * performance by ignoring weak charge forces at great distances. Note that this
141  * parameter is partly redundant, as the Barnes-Hut algorithm for n-body forces
142  * already improves performance for far-away particles through approximation.
143  *
144  * @type number
145  * @name pv.Layout.Force.prototype.chargeMaxDistance
146  * @see pv.Force.charge#domain
147  */
148 
149 /**
150  * The Barnes-Hut approximation factor. The Barnes-Hut approximation criterion
151  * is the ratio of the size of the quadtree node to the distance from the point
152  * to the node's center of mass is beneath some threshold. The default value is
153  * 0.9.
154  *
155  * @type number
156  * @name pv.Layout.Force.prototype.chargeTheta
157  * @see pv.Force.charge#theta
158  */
159 
160 /**
161  * The spring constant, which should be a positive number. The default value is
162  * 0.1; greater values will result in a stronger attractive force, which may
163  * lead to faster convergence at the risk of instability. Too strong spring
164  * forces can cause comparatively weak charge forces to be ignored, emphasizing
165  * local structure over global structure. A nonpositive value will break the
166  * Fruchterman-Reingold algorithm, and is for entertainment purposes only.
167  *
168  * <p>The spring tension is automatically normalized using the inverse square
169  * root of the maximum link degree of attached nodes.
170  *
171  * @type number
172  * @name pv.Layout.Force.prototype.springConstant
173  * @see pv.Force.spring#constant
174  */
175 
176 /**
177  * The spring damping factor, in the range [0,1]. Damping functions identically
178  * to drag forces, damping spring bounciness by applying a force in the opposite
179  * direction of attached nodes' velocities. The default value is 0.3.
180  *
181  * <p>The spring damping is automatically normalized using the inverse square
182  * root of the maximum link degree of attached nodes.
183  *
184  * @type number
185  * @name pv.Layout.Force.prototype.springDamping
186  * @see pv.Force.spring#damping
187  */
188 
189 /**
190  * The spring rest length. The default value is 20 pixels. Larger values may be
191  * appropriate if the layout panel is larger, or if the nodes are rendered
192  * larger than the default dot size of 20.
193  *
194  * @type number
195  * @name pv.Layout.Force.prototype.springLength
196  * @see pv.Force.spring#length
197  */
198 
199 /**
200  * Default properties for force-directed layouts. The default drag constant is
201  * 0.1, the default charge constant is -40 (with a domain of [2, 500] and theta
202  * of 0.9), and the default spring constant is 0.1 (with a damping of 0.3 and a
203  * rest length of 20).
204  *
205  * @type pv.Layout.Force
206  */
207 pv.Layout.Force.prototype.defaults = new pv.Layout.Force()
208     .extend(pv.Layout.Network.prototype.defaults)
209     .dragConstant(.1)
210     .chargeConstant(-40)
211     .chargeMinDistance(2)
212     .chargeMaxDistance(500)
213     .chargeTheta(.9)
214     .springConstant(.1)
215     .springDamping(.3)
216     .springLength(20);
217 
218 /** @private Initialize the physics simulation. */
219 pv.Layout.Force.prototype.buildImplied = function(s) {
220 
221   /* Any cached interactive layouts need to be rebound for the timer. */
222   if (pv.Layout.Network.prototype.buildImplied.call(this, s)) {
223     var f = s.$force;
224     if (f) {
225       f.next = this.binds.$force;
226       this.binds.$force = f;
227     }
228     return;
229   }
230 
231   var that = this,
232       nodes = s.nodes,
233       links = s.links,
234       k = s.iterations,
235       w = s.width,
236       h = s.height;
237 
238   /* Initialize positions randomly near the center. */
239   for (var i = 0, n; i < nodes.length; i++) {
240     n = nodes[i];
241     if (isNaN(n.x)) n.x = w / 2 + 40 * Math.random() - 20;
242     if (isNaN(n.y)) n.y = h / 2 + 40 * Math.random() - 20;
243   }
244 
245   /* Initialize the simulation. */
246   var sim = pv.simulation(nodes);
247 
248   /* Drag force. */
249   sim.force(pv.Force.drag(s.dragConstant));
250 
251   /* Charge (repelling) force. */
252   sim.force(pv.Force.charge(s.chargeConstant)
253       .domain(s.chargeMinDistance, s.chargeMaxDistance)
254       .theta(s.chargeTheta));
255 
256   /* Spring (attracting) force. */
257   sim.force(pv.Force.spring(s.springConstant)
258       .damping(s.springDamping)
259       .length(s.springLength)
260       .links(links));
261 
262   /* Position constraint (for interactive dragging). */
263   sim.constraint(pv.Constraint.position());
264 
265   /* Optionally add bound constraint. TODO: better padding. */
266   if (s.bound) {
267     sim.constraint(pv.Constraint.bound().x(6, w - 6).y(6, h - 6));
268   }
269 
270   /** @private Returns the speed of the given node, to determine cooling. */
271   function speed(n) {
272     return n.fix ? 1 : n.vx * n.vx + n.vy * n.vy;
273   }
274 
275   /*
276    * If the iterations property is null (the default), the layout is
277    * interactive. The simulation is run until the fastest particle drops below
278    * an arbitrary minimum speed. Although the timer keeps firing, this speed
279    * calculation is fast so there is minimal CPU overhead. Note: if a particle
280    * is fixed for interactivity, treat this as a high speed and resume
281    * simulation.
282    */
283   if (k == null) {
284     sim.step(); // compute initial previous velocities
285     sim.step(); // compute initial velocities
286 
287     /* Add the simulation state to the bound list. */
288     var force = s.$force = this.binds.$force = {
289       next: this.binds.$force,
290       nodes: nodes,
291       min: 1e-4 * (links.length + 1),
292       sim: sim
293     };
294 
295     /* Start the timer, if not already started. */
296     if (!this.$timer) this.$timer = setInterval(function() {
297       var render = false;
298       for (var f = that.binds.$force; f; f = f.next) {
299         if (pv.max(f.nodes, speed) > f.min) {
300           f.sim.step();
301           render = true;
302         }
303       }
304       if (render) that.render();
305     }, 42);
306   } else for (var i = 0; i < k; i++) {
307     sim.step();
308   }
309 };
310