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.Arrays; 036import java.util.Collections; 037import java.util.Comparator; 038import java.util.HashMap; 039import java.util.LinkedList; 040 041import org.graphstream.algorithm.Prim; 042import org.graphstream.algorithm.SpanningTree; 043import org.graphstream.algorithm.generator.BarabasiAlbertGenerator; 044import org.graphstream.algorithm.util.FibonacciHeap; 045import org.graphstream.graph.Edge; 046import org.graphstream.graph.Graph; 047import org.graphstream.graph.Node; 048import org.graphstream.graph.implementations.AdjacencyListGraph; 049import org.graphstream.stream.PipeBase; 050import org.graphstream.ui.geom.Point3; 051import org.graphstream.ui.swingViewer.Viewer; 052 053public class HierarchicalLayout extends PipeBase implements Layout { 054 055 public static enum Rendering { 056 VERTICAL, HORIZONTAL, DISK 057 } 058 059 static class Position { 060 int level; 061 int order; 062 String parent; 063 boolean changed; 064 double x, y; 065 066 Position(int level, int order) { 067 this.level = level; 068 this.order = order; 069 this.changed = true; 070 } 071 } 072 073 final HashMap<String, Position> nodesPosition; 074 final LinkedList<String> roots; 075 final Graph internalGraph; 076 077 boolean structureChanged; 078 079 Rendering renderingType; 080 081 Point3 hi, lo; 082 083 long lastStep; 084 085 int nodeMoved; 086 087 double distanceBetweenLevels = 1; 088 double levelWidth = 1, levelHeight = 1; 089 090 public HierarchicalLayout() { 091 roots = new LinkedList<String>(); 092 // listeners = new LinkedList<LayoutListener>(); 093 nodesPosition = new HashMap<String, Position>(); 094 internalGraph = new AdjacencyListGraph("hierarchical_layout-intern"); 095 hi = new Point3(); 096 lo = new Point3(); 097 renderingType = Rendering.VERTICAL; 098 } 099 100 public void setRoots(String... rootsId) { 101 roots.clear(); 102 103 if (rootsId != null) { 104 for (String id : rootsId) 105 roots.add(id); 106 } 107 } 108 109 // public void addListener(LayoutListener listener) { 110 // listeners.add(listener); 111 // } 112 113 public void clear() { 114 // TODO Auto-generated method stub 115 116 } 117 118 public void compute() { 119 nodeMoved = 0; 120 121 if (structureChanged) { 122 structureChanged = false; 123 computePositions(); 124 } 125 126 publishPositions(); 127 lastStep = System.currentTimeMillis(); 128 } 129 130 protected void computePositions() { 131 final int[] levels = new int[internalGraph.getNodeCount()]; 132 Arrays.fill(levels, -1); 133 134 final int[] columns = new int[internalGraph.getNodeCount()]; 135 136 LinkedList<Node> roots = new LinkedList<Node>(), roots2 = new LinkedList<Node>(); 137 138 if (this.roots.size() > 0) { 139 for (int i = 0; i < this.roots.size(); i++) 140 roots.add(internalGraph.getNode(this.roots.get(i))); 141 } 142 143 SpanningTree tree = new Prim("weight", "inTree"); 144 tree.init(internalGraph); 145 tree.compute(); 146 147 if (roots.size() == 0) { 148 int max = internalGraph.getNode(0).getDegree(); 149 int maxIndex = 0; 150 151 for (int i = 1; i < internalGraph.getNodeCount(); i++) 152 if (internalGraph.getNode(i).getDegree() > max) { 153 max = internalGraph.getNode(i).getDegree(); 154 maxIndex = i; 155 } 156 157 roots.add(internalGraph.getNode(maxIndex)); 158 } 159 160 Box rootBox = new Box(); 161 LevelBox rootLevelBox = new LevelBox(0); 162 LinkedList<LevelBox> levelBoxes = new LinkedList<LevelBox>(); 163 164 rootLevelBox.add(rootBox); 165 levelBoxes.add(rootLevelBox); 166 167 for (int i = 0; i < roots.size(); i++) { 168 Node n = roots.get(i); 169 levels[n.getIndex()] = 0; 170 columns[n.getIndex()] = i; 171 setBox(rootBox, n); 172 } 173 174 do { 175 while (roots.size() > 0) { 176 Node root = roots.poll(); 177 int level = levels[root.getIndex()] + 1; 178 Box box = getChildrenBox(root); 179 180 for (Edge e : root.getEdgeSet()) { 181 if (e.getAttribute(tree.getFlagAttribute()).equals( 182 tree.getFlagOn())) { 183 Node op = e.getOpposite(root); 184 185 if (levels[op.getIndex()] < 0 186 || level < levels[op.getIndex()]) { 187 levels[op.getIndex()] = level; 188 roots2.add(op); 189 op.setAttribute("parent", root); 190 setBox(box, op); 191 } 192 } 193 } 194 } 195 196 roots.addAll(roots2); 197 roots2.clear(); 198 } while (roots.size() > 0); 199 200 FibonacciHeap<Integer, Box> boxes = new FibonacciHeap<Integer, Box>(); 201 boxes.add(0, rootBox); 202 203 for (int i = 0; i < internalGraph.getNodeCount(); i++) { 204 Box box = getChildrenBox(internalGraph.getNode(i)); 205 206 if (box != null) { 207 boxes.add(box.level, box); 208 209 while (levelBoxes.size() <= box.level) 210 levelBoxes.add(new LevelBox(levelBoxes.size())); 211 212 levelBoxes.get(box.level).add(box); 213 } 214 } 215 216 for (int i = 0; i < levelBoxes.size(); i++) 217 levelBoxes.get(i).sort(); 218 219 while (boxes.size() > 0) 220 renderBox(boxes.extractMin()); 221 222 hi.x = hi.y = Double.MIN_VALUE; 223 lo.x = lo.y = Double.MAX_VALUE; 224 225 for (int idx = 0; idx < internalGraph.getNodeCount(); idx++) { 226 Node n = internalGraph.getNode(idx); 227 double y = n.getNumber("y"); 228 double x = n.getNumber("x"); 229 230 if (!n.hasNumber("oldX") || n.getNumber("oldX") != x 231 || !n.hasNumber("oldY") || n.getNumber("oldY") != y) { 232 n.setAttribute("oldX", x); 233 n.setAttribute("oldY", y); 234 n.addAttribute("changed"); 235 nodeMoved++; 236 } 237 238 hi.x = Math.max(hi.x, x); 239 hi.y = Math.max(hi.y, y); 240 lo.x = Math.min(lo.x, x); 241 lo.y = Math.min(lo.y, y); 242 } 243 } 244 245 protected void setBox(Box box, Node node) { 246 if (node.hasAttribute("box")) 247 getBox(node).remove(node); 248 249 box.add(node); 250 node.setAttribute("box", box); 251 252 if (!node.hasAttribute("children")) 253 node.addAttribute("children", new Box(node, 1)); 254 255 getChildrenBox(node).level = box.level + 1; 256 } 257 258 protected static Box getBox(Node node) { 259 Box box = node.getAttribute("box"); 260 return box; 261 } 262 263 protected static Box getChildrenBox(Node node) { 264 Box box = node.getAttribute("children"); 265 return box; 266 } 267 268 protected void renderBox(Box box) { 269 if (box.size() == 0) 270 return; 271 272 for (int i = 0; i < box.size(); i++) { 273 Node n = box.get(i); 274 275 switch (renderingType) { 276 case VERTICAL: 277 n.setAttribute("x", box.width * i / (double) box.size()); 278 n.setAttribute("y", box.height / 2); 279 break; 280 case DISK: 281 case HORIZONTAL: 282 n.setAttribute("x", box.width / 2); 283 n.setAttribute("y", box.height * i / (double) box.size()); 284 break; 285 } 286 } 287 288 double sx = 1, sy = 1; 289 double dx = 0, dy = 0; 290 291 if (box.parent != null) { 292 Box parentBox = getBox(box.parent); 293 294 switch (renderingType) { 295 case VERTICAL: 296 sx = 1 / (double) parentBox.size(); 297 sy = 1 / Math.pow(2, box.level); 298 break; 299 case DISK: 300 case HORIZONTAL: 301 sx = 1 / Math.pow(2, box.level); 302 sy = 1 / (double) parentBox.size(); 303 break; 304 } 305 } 306 307 box.scale(sx, sy); 308 309 if (box.parent != null) { 310 Box parentBox = getBox(box.parent); 311 312 dx = box.parent.getNumber("x"); 313 dy = box.parent.getNumber("y"); 314 315 switch (renderingType) { 316 case VERTICAL: 317 dx -= box.width / 2; 318 dy += parentBox.height / 2; 319 break; 320 case DISK: 321 case HORIZONTAL: 322 dx += parentBox.width / 2; 323 dy -= box.height / 2; 324 break; 325 } 326 } 327 328 box.translate(dx, dy); 329 } 330 331 protected void explore(Node parent, Node who, SpanningTree tree, 332 int[] levels) { 333 334 } 335 336 protected void publishPositions() { 337 for (Node n : internalGraph) { 338 if (n.hasAttribute("changed")) { 339 n.removeAttribute("changed"); 340 341 sendNodeAttributeChanged(sourceId, n.getId(), "xyz", null, 342 new double[] { n.getNumber("x"), n.getNumber("y"), 0 }); 343 } 344 } 345 } 346 347 /* 348 * (non-Javadoc) 349 * 350 * @see org.graphstream.ui.layout.Layout#freezeNode(java.lang.String, 351 * boolean) 352 */ 353 public void freezeNode(String id, boolean frozen) { 354 } 355 356 /* 357 * (non-Javadoc) 358 * 359 * @see org.graphstream.ui.layout.Layout#getForce() 360 */ 361 public double getForce() { 362 return 0; 363 } 364 365 /* 366 * (non-Javadoc) 367 * 368 * @see org.graphstream.ui.layout.Layout#getHiPoint() 369 */ 370 public Point3 getHiPoint() { 371 return hi; 372 } 373 374 /* 375 * (non-Javadoc) 376 * 377 * @see org.graphstream.ui.layout.Layout#getLastStepTime() 378 */ 379 public long getLastStepTime() { 380 return lastStep; 381 } 382 383 /* 384 * (non-Javadoc) 385 * 386 * @see org.graphstream.ui.layout.Layout#getLayoutAlgorithmName() 387 */ 388 public String getLayoutAlgorithmName() { 389 return "Hierarchical"; 390 } 391 392 /* 393 * (non-Javadoc) 394 * 395 * @see org.graphstream.ui.layout.Layout#getLowPoint() 396 */ 397 public Point3 getLowPoint() { 398 return lo; 399 } 400 401 /* 402 * (non-Javadoc) 403 * 404 * @see org.graphstream.ui.layout.Layout#getNodeMoved() 405 */ 406 public int getNodeMovedCount() { 407 return nodeMoved; 408 } 409 410 /* 411 * (non-Javadoc) 412 * 413 * @see org.graphstream.ui.layout.Layout#getQuality() 414 */ 415 public double getQuality() { 416 return 0; 417 } 418 419 /* 420 * (non-Javadoc) 421 * 422 * @see org.graphstream.ui.layout.Layout#getStabilization() 423 */ 424 public double getStabilization() { 425 return 1 - nodeMoved / (double) internalGraph.getNodeCount(); 426 } 427 428 /* 429 * (non-Javadoc) 430 * 431 * @see org.graphstream.ui.layout.Layout#getStabilizationLimit() 432 */ 433 public double getStabilizationLimit() { 434 return 1; 435 } 436 437 /* 438 * (non-Javadoc) 439 * 440 * @see org.graphstream.ui.layout.Layout#getSteps() 441 */ 442 public int getSteps() { 443 return 0; 444 } 445 446 /* 447 * (non-Javadoc) 448 * 449 * @see org.graphstream.ui.layout.Layout#inputPos(java.lang.String) 450 */ 451 public void inputPos(String filename) throws IOException { 452 throw new UnsupportedOperationException(); 453 } 454 455 /* 456 * (non-Javadoc) 457 * 458 * @see org.graphstream.ui.layout.Layout#moveNode(java.lang.String, double, 459 * double, double) 460 */ 461 public void moveNode(String id, double x, double y, double z) { 462 // TODO Auto-generated method stub 463 464 } 465 466 /* 467 * (non-Javadoc) 468 * 469 * @see org.graphstream.ui.layout.Layout#outputPos(java.lang.String) 470 */ 471 public void outputPos(String filename) throws IOException { 472 throw new UnsupportedOperationException(); 473 } 474 475 // /* 476 // * (non-Javadoc) 477 // * 478 // * @see 479 // * 480 // org.graphstream.ui.layout.Layout#removeListener(org.graphstream.ui.layout 481 // * .LayoutListener) 482 // */ 483 // public void removeListener(LayoutListener listener) { 484 // listeners.remove(listener); 485 // } 486 487 /* 488 * (non-Javadoc) 489 * 490 * @see org.graphstream.ui.layout.Layout#setForce(double) 491 */ 492 public void setForce(double value) { 493 } 494 495 /* 496 * (non-Javadoc) 497 * 498 * @see org.graphstream.ui.layout.Layout#setQuality(int) 499 */ 500 public void setQuality(double qualityLevel) { 501 } 502 503 /* 504 * (non-Javadoc) 505 * 506 * @see org.graphstream.ui.layout.Layout#setSendNodeInfos(boolean) 507 */ 508 public void setSendNodeInfos(boolean send) { 509 } 510 511 /* 512 * (non-Javadoc) 513 * 514 * @see org.graphstream.ui.layout.Layout#setStabilizationLimit(double) 515 */ 516 public void setStabilizationLimit(double value) { 517 } 518 519 /* 520 * (non-Javadoc) 521 * 522 * @see org.graphstream.ui.layout.Layout#shake() 523 */ 524 public void shake() { 525 // No, I will not shake my work 526 } 527 528 /* 529 * (non-Javadoc) 530 * 531 * @see org.graphstream.stream.PipeBase#nodeAdded(java.lang.String, long, 532 * java.lang.String) 533 */ 534 public void nodeAdded(String sourceId, long timeId, String nodeId) { 535 internalGraph.addNode(nodeId); 536 structureChanged = true; 537 } 538 539 /* 540 * (non-Javadoc) 541 * 542 * @see org.graphstream.stream.PipeBase#nodeRemoved(java.lang.String, long, 543 * java.lang.String) 544 */ 545 public void nodeRemoved(String sourceId, long timeId, String nodeId) { 546 internalGraph.removeNode(nodeId); 547 structureChanged = true; 548 } 549 550 /* 551 * (non-Javadoc) 552 * 553 * @see org.graphstream.stream.PipeBase#edgeAdded(java.lang.String, long, 554 * java.lang.String, java.lang.String, java.lang.String, boolean) 555 */ 556 public void edgeAdded(String sourceId, long timeId, String edgeId, 557 String fromId, String toId, boolean directed) { 558 internalGraph.addEdge(edgeId, fromId, toId, directed); 559 structureChanged = true; 560 } 561 562 /* 563 * (non-Javadoc) 564 * 565 * @see org.graphstream.stream.PipeBase#edgeRemoved(java.lang.String, long, 566 * java.lang.String) 567 */ 568 public void edgeRemoved(String sourceId, long timeId, String edgeId) { 569 internalGraph.removeEdge(edgeId); 570 structureChanged = true; 571 } 572 573 /* 574 * (non-Javadoc) 575 * 576 * @see org.graphstream.stream.PipeBase#graphCleared(java.lang.String, long) 577 */ 578 public void graphCleared(String sourceId, long timeId) { 579 internalGraph.clear(); 580 structureChanged = true; 581 } 582 583 static class Box extends LinkedList<Node> { 584 private static final long serialVersionUID = -1929536876444346726L; 585 586 Node parent; 587 int level; 588 double x, y; 589 double width, height; 590 int order; 591 592 Box() { 593 this(null, 0); 594 } 595 596 Box(Node parent, int level) { 597 this.parent = parent; 598 this.level = level; 599 this.width = 5; 600 this.height = 1; 601 this.order = 0; 602 this.x = 0; 603 this.y = 0; 604 } 605 606 void scale(double sx, double sy) { 607 width *= sx; 608 height *= sy; 609 610 for (int i = 0; i < size(); i++) { 611 get(i).setAttribute("x", sx * get(i).getNumber("x")); 612 get(i).setAttribute("y", sy * get(i).getNumber("y")); 613 } 614 } 615 616 void translate(double dx, double dy) { 617 for (int i = 0; i < size(); i++) { 618 get(i).setAttribute("x", dx + get(i).getNumber("x")); 619 get(i).setAttribute("y", dy + get(i).getNumber("y")); 620 } 621 } 622 } 623 624 static class LevelBox extends LinkedList<Box> { 625 private static final long serialVersionUID = -5818919480025868466L; 626 627 int level; 628 629 LevelBox(int level) { 630 this.level = level; 631 } 632 633 void sort() { 634 if (level > 0) { 635 Collections.sort(this, new Comparator<Box>() { 636 public int compare(Box b0, Box b1) { 637 Box pb0 = getBox(b0.parent); 638 Box pb1 = getBox(b1.parent); 639 640 if (pb0.order < pb1.order) 641 return -1; 642 else if (pb0.order > pb1.order) 643 return 1; 644 645 return 0; 646 } 647 }); 648 } 649 650 for (int i = 0; i < size(); i++) 651 get(i).order = i; 652 } 653 } 654 655 public static void main(String... args) { 656 Graph g = new AdjacencyListGraph("g"); 657 BarabasiAlbertGenerator gen = new BarabasiAlbertGenerator(); 658 HierarchicalLayout hl = new HierarchicalLayout(); 659 gen.addSink(g); 660 gen.begin(); 661 for (int i = 0; i < 200; i++) 662 gen.nextEvents(); 663 gen.end(); 664 665 Viewer v = g.display(false); 666 v.enableAutoLayout(hl); 667 } 668}