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