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; 033 034import java.io.IOException; 035import java.util.HashMap; 036import java.util.Iterator; 037import java.util.Random; 038 039import org.graphstream.algorithm.generator.BarabasiAlbertGenerator; 040import org.graphstream.graph.implementations.DefaultGraph; 041import org.graphstream.stream.PipeBase; 042import org.graphstream.ui.geom.Point3; 043import org.miv.pherd.geom.Vector3; 044 045public class Eades84Layout extends PipeBase implements Layout { 046 047 boolean is3D; 048 049 double c1; 050 double c2; 051 double c3; 052 double c4; 053 054 double M; 055 056 HashMap<String, Spring> springs; 057 HashMap<String, EadesParticle> particles; 058 059 Random random; 060 061 int nodeMoved = 0; 062// LinkedList<LayoutListener> listeners; 063 double stabilization = 0; 064 065 Point3 high; 066 Point3 low; 067 068 public Eades84Layout() { 069 // 070 // Appropriate for most graphs : 071 // 072 c1 = 2; 073 c2 = 1; 074 c3 = 2; 075 c4 = 0.5; 076 M = 100; 077 // 078 079 is3D = false; 080 081 springs = new HashMap<String, Spring>(); 082 particles = new HashMap<String, EadesParticle>(); 083 random = new Random(); 084// listeners = new LinkedList<LayoutListener>(); 085 086 high = new Point3(1, 1, 1); 087 low = new Point3(-1, -1, -1); 088 } 089 090 public String getLayoutAlgorithmName() { 091 return "Eades1984"; 092 } 093 094 public int getNodeMovedCount() { 095 return nodeMoved; 096 } 097 098 public double getStabilization() { 099 return stabilization; 100 } 101 102 public double getStabilizationLimit() { 103 return M; 104 } 105 106 public void setStabilizationLimit(double l) { 107 M = l; 108 } 109 110 public Point3 getLowPoint() { 111 return low; 112 } 113 114 public Point3 getHiPoint() { 115 return high; 116 } 117 118 public int getSteps() { 119 // TODO Auto-generated method stub 120 return 0; 121 } 122 123 public long getLastStepTime() { 124 // TODO Auto-generated method stub 125 return 0; 126 } 127 128 public double getQuality() { 129 // TODO Auto-generated method stub 130 return 0; 131 } 132 133 public double getForce() { 134 // TODO Auto-generated method stub 135 return 0; 136 } 137 138 public void clear() { 139 // TODO Auto-generated method stub 140 141 } 142 143// public void addListener(LayoutListener listener) { 144// listeners.add(listener); 145// } 146// 147// public void removeListener(LayoutListener listener) { 148// listeners.remove(listener); 149// } 150 151 public void setForce(double value) { 152 // TODO Auto-generated method stub 153 154 } 155 156 public void setQuality(double qualityLevel) { 157 // TODO Auto-generated method stub 158 159 } 160 161 public void setSendNodeInfos(boolean send) { 162 // TODO Auto-generated method stub 163 164 } 165 166 public void shake() { 167 // TODO Auto-generated method stub 168 169 } 170 171 public void moveNode(String id, double x, double y, double z) { 172 // TODO Auto-generated method stub 173 174 } 175 176 public void freezeNode(String id, boolean frozen) { 177 // TODO Auto-generated method stub 178 179 } 180 181 public void compute() { 182 nodeMoved = 0; 183 184 for (Spring s : springs.values()) 185 s.computeForce(); 186 187 for (EadesParticle p : particles.values()) 188 p.step(); 189 190 double minx, miny, minz, maxx, maxy, maxz; 191 192 minx = miny = minz = Double.MAX_VALUE; 193 maxx = maxy = maxz = Double.MIN_VALUE; 194 195 for (EadesParticle p : particles.values()) { 196 p.commit(); 197 198 if (p.getEnergy() > 0) 199 particleMoved(p.id, p.pos.x, p.pos.y, p.pos.z); 200 201 minx = Math.min(minx, p.pos.x); 202 miny = Math.min(miny, p.pos.y); 203 minz = Math.min(minz, p.pos.z); 204 maxx = Math.max(minx, p.pos.x); 205 maxy = Math.max(miny, p.pos.y); 206 maxz = Math.max(minz, p.pos.z); 207 } 208 209 high.x = maxx; 210 high.y = maxy; 211 high.z = maxz; 212 213 low.x = minx; 214 low.y = miny; 215 low.z = minz; 216 217 stabilization += 1; 218 219// for (LayoutListener listener : listeners) 220// listener.stepCompletion(getStabilization()); 221 } 222 223 public void nodeAdded(String sourceId, long timeId, String nodeId) { 224 particles.put(nodeId, getNewParticle(nodeId)); 225 stabilization = 0; 226 } 227 228 public void nodeRemoved(String sourceId, long timeId, String nodeId) { 229 particles.remove(nodeId); 230 stabilization = 0; 231 } 232 233 public void edgeAdded(String sourceId, long timeId, String edgeId, 234 String fromNodeId, String toNodeId, boolean directed) { 235 EadesParticle p1, p2; 236 Spring spring; 237 238 p1 = (EadesParticle) particles.get(fromNodeId); 239 p2 = (EadesParticle) particles.get(toNodeId); 240 241 spring = getNewSpring(p1, p2); 242 springs.put(edgeId, spring); 243 244 p1.springs.put(p2, spring); 245 p2.springs.put(p1, spring); 246 247 stabilization = 0; 248 } 249 250 public void edgeRemoved(String sourceId, long timeId, String edgeId) { 251 Spring s = springs.remove(edgeId); 252 253 if (s != null) { 254 s.p1.springs.remove(s.p2); 255 s.p2.springs.remove(s.p1); 256 257 stabilization = 0; 258 } 259 } 260 261 public void inputPos(String filename) throws IOException { 262 throw new RuntimeException("unhandle feature"); 263 } 264 265 public void outputPos(String filename) throws IOException { 266 throw new RuntimeException("unhandle feature"); 267 } 268 269 public void particleMoved(Object id, double x, double y, double z) { 270 //for (LayoutListener listener : listeners) 271 // listener.nodeMoved((String) id, x, y, z); 272 273 Object xyz[] = new Object[3]; 274 xyz[0] = x; 275 xyz[1] = y; 276 xyz[2] = z; 277 278 sendNodeAttributeChanged(getLayoutAlgorithmName(), (String) id, "xyz", 279 xyz, xyz); 280 281 // System.out.printf("particle %s moved : %f;%f;%f\n", id, x, y, z); 282 } 283 284 protected EadesParticle getNewParticle(String id) { 285 return new EadesParticle(id); 286 } 287 288 protected Spring getNewSpring(EadesParticle p1, EadesParticle p2) { 289 return new Spring(p1, p2); 290 } 291 292 protected class Spring { 293 EadesParticle p1; 294 EadesParticle p2; 295 296 double force; 297 298 Spring(EadesParticle p1, EadesParticle p2) { 299 this.p1 = p1; 300 this.p2 = p2; 301 } 302 303 /** 304 * Force of a spring is : c1 * log(d/c2) 305 */ 306 void computeForce() { 307 double d = p1.d(p2); 308 force = c1 * Math.log(d / c2); 309 } 310 311 void set(EadesParticle p, Vector3 v) { 312 v.set(Math.signum(p2.getPosition().x - p1.getPosition().x), 313 Math.signum(p2.getPosition().y - p1.getPosition().y), 314 Math.signum(p2.getPosition().z - p1.getPosition().z)); 315 316 if (p == p2) 317 v.scalarMult(-1); 318 319 v.scalarMult(force); 320 } 321 } 322 323 protected class EadesParticle { 324 HashMap<EadesParticle, Spring> springs; 325 Vector3 dir; 326 Vector3 sum; 327 Point3 pos; 328 String id; 329 330 public EadesParticle(String id) { 331 this.id = id; 332 springs = new HashMap<EadesParticle, Spring>(); 333 dir = new Vector3(); 334 sum = new Vector3(); 335 pos = new Point3(); 336 337 pos.x = random.nextDouble() * (high.x - low.x) + low.x; 338 pos.y = random.nextDouble() * (high.y - low.y) + low.y; 339 340 if (is3D) 341 pos.z = random.nextDouble() * (high.z - low.z) + low.z; 342 } 343 344 public void step() { 345 Vector3 v = new Vector3(); 346 347 dir.fill(0); 348 sum.fill(0); 349 350 for (Spring s : springs.values()) { 351 s.set(this, v); 352 sum.add(v); 353 } 354 355 // if (springs.size() > 0) 356 // sum.scalarDiv(springs.size()); 357 // dir.add(sum); 358 359 // sum.fill(0); 360 361 Iterator<EadesParticle> it = particles.values().iterator(); 362 //double i = 0; 363 364 while (it.hasNext()) { 365 EadesParticle p = it.next(); 366 367 if (!springs.containsKey(p) && p != this) { 368 double d = d(p); 369 /* 370 * Force of a non-spring particle : c3 / sqrt(d) 371 */ 372 double f = Double.isNaN(d) ? c3 : c3 / Math.sqrt(d); 373 374 v.set(Math.signum(getPosition().x - p.getPosition().x), 375 Math.signum(getPosition().y - p.getPosition().y), 376 Math.signum(getPosition().z - p.getPosition().z)); 377 378 v.scalarMult(f); 379 380 sum.add(v); 381 //i++; 382 } 383 } 384 385 //if (i + springs.size() > 0) 386 // sum.scalarDiv(i + springs.size()); 387 388 dir.add(sum); 389 dir.scalarMult(c4); 390 391 assert (!Double.isNaN(dir.data[0]) && !Double.isNaN(dir.data[1])); 392 } 393 394 public double getEnergy() { 395 return dir.length(); 396 } 397 398 public void commit() { 399 pos.x = pos.x + dir.data[0]; 400 pos.y = pos.y + dir.data[1]; 401 402 assert (!Double.isNaN(pos.x) && !Double.isNaN(pos.y)); 403 404 if (is3D) 405 pos.z = pos.z + dir.data[2]; 406 407 nodeMoved++; 408 } 409 410 protected double d(EadesParticle p) { 411 return getPosition().distance(p.getPosition()); 412 } 413 414 public Point3 getPosition() { 415 return pos; 416 } 417 } 418 419 public static void main(String... args) { 420 DefaultGraph g = new DefaultGraph("g"); 421 BarabasiAlbertGenerator gen = new BarabasiAlbertGenerator(); 422 Eades84Layout layout = new Eades84Layout(); 423 424 int size = 30; 425 426 gen.addSink(g); 427 g.addSink(layout); 428 layout.addAttributeSink(g); 429 430 g.display(false); 431 432 gen.begin(); 433 while (size-- > 0) 434 gen.nextEvents(); 435 gen.end(); 436 437 while (true) { 438 layout.compute(); 439 try { 440 Thread.sleep(50); 441 } catch (Exception e) { 442 } 443 } 444 } 445}