001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.ui.layout.springbox; 033 034import java.io.FileOutputStream; 035import java.io.PrintStream; 036import java.util.ArrayList; 037import java.util.Collection; 038import java.util.Locale; 039 040import org.graphstream.ui.geom.Vector3; 041import org.miv.pherd.Particle; 042 043/** 044 * Base implementation of a node particle to be used in the {@link BarnesHutLayout} 045 * to represent nodes and choose their positions. 046 * 047 * <p> 048 * Several abstract methods have to be overrided to provide a computation of the 049 * layout (all the attraction/repulsion computation is done in this class): 050 * <ul> 051 * <li>{@link #attraction(Vector3)}</li> 052 * <li>{@link #repulsionN2(Vector3)}</li> 053 * <li>{@link #repulsionNLogN(Vector3)}</li> 054 * </ul> 055 * </p> 056 */ 057public abstract class NodeParticle extends Particle { 058 /** 059 * Set of edge connected to this node. 060 */ 061 public ArrayList<EdgeSpring> neighbours = new ArrayList<EdgeSpring>(); 062 063 /** 064 * Should the node move?. 065 */ 066 public boolean frozen = false; 067 068 /** 069 * Displacement vector. 070 */ 071 public Vector3 disp; 072 073 /** 074 * Last computed displacement vector length. 075 */ 076 public double len; 077 078 /** 079 * Attraction energy for this node only. 080 */ 081 public double attE; 082 083 /** 084 * Repulsion energy for this node only. 085 */ 086 public double repE; 087 088 /** 089 * If non null, all this node statistics will be output to this stream. 090 */ 091 public PrintStream out; 092 093 /** 094 * The box. 095 */ 096 protected BarnesHutLayout box; 097 098 // Constructors 099 100 /** 101 * New node. 102 * 103 * The node is placed at random in the space of the simulation. 104 * 105 * @param box 106 * The spring box. 107 * @param id 108 * The node identifier. 109 */ 110 public NodeParticle(BarnesHutLayout box, String id) { 111// this(box, id, box.getCenterPoint().x, box.getCenterPoint().y, box.is3D() ? box.getCenterPoint().z : 0); 112 this(box, id, box.randomXInsideBounds(), box.randomYInsideBounds(), box.is3D ? box.randomZInsideBounds() : 0); 113// this(box, id, (box.random.nextDouble() * 2) - 1, (box.random 114// .nextDouble() * 2) - 1, 115// box.is3D ? (box.random.nextDouble() * 2) - 1 : 0); 116 117 this.box = box; 118 } 119 120 /** 121 * New node at a given position. 122 * 123 * @param box 124 * The spring box. 125 * @param id 126 * The node identifier. 127 * @param x 128 * The abscissa. 129 * @param y 130 * The ordinate. 131 * @param z 132 * The depth. 133 */ 134 public NodeParticle(BarnesHutLayout box, String id, double x, double y, 135 double z) { 136 super(id, x, y, box.is3D ? z : 0); 137 this.box = box; 138 disp = new Vector3(); 139 createDebug(); 140 } 141 142 /** 143 * Create a file for statistics about this node. 144 */ 145 protected void createDebug() { 146 if (box.outputNodeStats) { 147 try { 148 out = new PrintStream(new FileOutputStream("out" + getId() 149 + ".data")); 150 } catch (Exception e) { 151 e.printStackTrace(); 152 System.exit(1); 153 } 154 } 155 } 156 157 /** 158 * All the edges connected to this node. 159 * 160 * @return A set of edges. 161 */ 162 public Collection<EdgeSpring> getEdges() { 163 return neighbours; 164 } 165 166 @Override 167 public void move(int time) { 168 if (!frozen) { 169 disp.fill(0); 170 171 Vector3 delta = new Vector3(); 172 173 repE = 0; 174 attE = 0; 175 176 if (box.viewZone < 0) 177 repulsionN2(delta); 178 else 179 repulsionNLogN(delta); 180 181 attraction(delta); 182 183 if(box.gravity != 0) 184 gravity(delta); 185 186 disp.scalarMult(box.force); 187 188 len = disp.length(); 189 190 if (len > (box.area / 2)) { 191 disp.scalarMult((box.area / 2) / len); 192 len = box.area / 2; 193 } 194 195 box.avgLength += len; 196 197 if (len > box.maxMoveLength) 198 box.maxMoveLength = len; 199 } 200 } 201 202 @Override 203 public void nextStep(int time) { 204 if (!frozen) { 205 nextPos.x = pos.x + disp.data[0]; 206 nextPos.y = pos.y + disp.data[1]; 207 208 if (box.is3D) 209 nextPos.z = pos.z + disp.data[2]; 210 211 box.nodeMoveCount++; 212 moved = true; 213 } else { 214 nextPos.x = pos.x; 215 nextPos.y = pos.y; 216 if (box.is3D) 217 nextPos.z = pos.z; 218 } 219 220 if (out != null) { 221 out.printf(Locale.US, "%s %f %f %f%n", getId(), len, attE, repE); 222 out.flush(); 223 } 224 225 super.nextStep(time); 226 } 227 228 /** 229 * Force a node to move from a given vector. 230 * 231 * @param dx 232 * The x component. 233 * @param dy 234 * The y component. 235 * @param dz 236 * The z component. 237 */ 238 public void moveOf(double dx, double dy, double dz) { 239 pos.set(pos.x + dx, pos.y + dy, pos.z + dz); 240 } 241 242 /** 243 * Force a node to move at a given position. 244 * 245 * @param x 246 * The new x. 247 * @param y 248 * The new y. 249 * @param z 250 * The new z. 251 */ 252 public void moveTo(double x, double y, double z) { 253 pos.set(x, y, z); 254 moved = true; 255 } 256 257 /** 258 * Compute the repulsion for each other node. This is the most precise way, 259 * but the algorithm is a time hog : complexity is O(n^2). 260 * 261 * @param delta 262 * The computed displacement vector. 263 */ 264 protected abstract void repulsionN2(Vector3 delta); 265 266 /** 267 * Compute the repulsion for each node in the viewing distance, and use the 268 * n-tree to find them. For a certain distance the node repulsion is 269 * computed one by one. At a larger distance the repulsion is computed using 270 * nodes barycenters. 271 * 272 * @param delta 273 * The computed displacement vector. 274 */ 275 protected abstract void repulsionNLogN(Vector3 delta); 276 277 /** 278 * Compute the global attraction toward each connected node. 279 * @param delta 280 * The computed displacement vector. 281 */ 282 protected abstract void attraction(Vector3 delta); 283 284 /** 285 * Compute the global attraction toward the layout center (if enabled). 286 * @param delta 287 * The computed displacement vector. 288 * @see BarnesHutLayout#useGravity 289 */ 290 protected abstract void gravity(Vector3 delta); 291 292 /** 293 * The given edge is connected to this node. 294 * 295 * @param e 296 * The edge to connect. 297 */ 298 public void registerEdge(EdgeSpring e) { 299 neighbours.add(e); 300 } 301 302 /** 303 * The given edge is no more connected to this node. 304 * 305 * @param e 306 * THe edge to disconnect. 307 */ 308 public void unregisterEdge(EdgeSpring e) { 309 int i = neighbours.indexOf(e); 310 311 if (i >= 0) { 312 neighbours.remove(i); 313 } 314 } 315 316 /** 317 * Remove all edges connected to this node. 318 */ 319 public void removeNeighborEdges() { 320 ArrayList<EdgeSpring> edges = new ArrayList<EdgeSpring>(neighbours); 321 322 for (EdgeSpring edge : edges) 323 box.removeEdge(box.getLayoutAlgorithmName(), edge.id); 324 325 neighbours.clear(); 326 } 327 328 @Override 329 public void inserted() { 330 } 331 332 @Override 333 public void removed() { 334 } 335}