third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/TreeLayout.java

   1 /*
   2  * Copyright (c) 2005, the JUNG Project and the Regents of the University of
   3  * California All rights reserved.
   4  *
   5  * This software is open-source under the BSD license; see either "license.txt"
   6  * or http://jung.sourceforge.net/license.txt for a description.
   7  *
   8  * Created on Jul 9, 2005
   9  */
  10
  11 package edu.uci.ics.jung.algorithms.layout;
  12 import java.awt.Dimension;
  13 import java.awt.Point;
  14 import java.awt.geom.Point2D;
  15 import java.util.Collection;
  16 import java.util.HashMap;
  17 import java.util.HashSet;
  18 import java.util.Map;
  19 import java.util.Set;
  20
  21 import org.apache.commons.collections15.Transformer;
  22 import org.apache.commons.collections15.map.LazyMap;
  23
  24 import edu.uci.ics.jung.graph.Forest;
  25 import edu.uci.ics.jung.graph.Graph;
  26 import edu.uci.ics.jung.graph.util.TreeUtils;
  27
  28 /**
  29  * @author Karlheinz Toni
  30  * @author Tom Nelson - converted to jung2
  31  *
  32  */
  33
  34 public class TreeLayout<V,E> implements Layout<V,E> {
  35
  36         protected Dimension size = new Dimension(600,600);
  37         protected Forest<V,E> graph;
  38         protected Map<V,Integer> basePositions = new HashMap<V,Integer>();
  39
  40     protected Map<V, Point2D> locations =
  41         LazyMap.decorate(new HashMap<V, Point2D>(),
  42                         new Transformer<V,Point2D>() {
  43                                         public Point2D transform(V arg0) {
  44                                                 return new Point2D.Double();
  45                                         }});
  46
  47     protected transient Set<V> alreadyDone = new HashSet<V>();
  48
  49     /**
  50      * The default horizontal vertex spacing.  Initialized to 50.
  51      */
  52     public static int DEFAULT_DISTX = 50;
  53
  54     /**
  55      * The default vertical vertex spacing.  Initialized to 50.
  56      */
  57     public static int DEFAULT_DISTY = 50;
  58
  59     /**
  60      * The horizontal vertex spacing.  Defaults to {@code DEFAULT_XDIST}.
  61      */
  62     protected int distX = 50;
  63
  64     /**
  65      * The vertical vertex spacing.  Defaults to {@code DEFAULT_YDIST}.
  66      */
  67     protected int distY = 50;
  68
  69     protected transient Point m_currentPoint = new Point();
  70
  71     /**
  72      * Creates an instance for the specified graph with default X and Y distances.
  73      */
  74     public TreeLayout(Forest<V,E> g) {
  75         this(g, DEFAULT_DISTX, DEFAULT_DISTY);
  76     }
  77
  78     /**
  79      * Creates an instance for the specified graph and X distance with
  80      * default Y distance.
  81      */
  82     public TreeLayout(Forest<V,E> g, int distx) {
  83         this(g, distx, DEFAULT_DISTY);
  84     }
  85
  86     /**
  87      * Creates an instance for the specified graph, X distance, and Y distance.
  88      */
  89     public TreeLayout(Forest<V,E> g, int distx, int disty) {
  90         if (g == null)
  91             throw new IllegalArgumentException("Graph must be non-null");
  92         if (distx < 1 || disty < 1)
  93             throw new IllegalArgumentException("X and Y distances must each be positive");
  94         this.graph = g;
  95         this.distX = distx;
  96         this.distY = disty;
  97         buildTree();
  98     }
  99
 100         protected void buildTree() {
 101         this.m_currentPoint = new Point(0, 20);
 102         Collection<V> roots = TreeUtils.getRoots(graph);
 103         if (roots.size() > 0 && graph != null) {
 104                 calculateDimensionX(roots);
 105                 for(V v : roots) {
 106                         calculateDimensionX(v);
 107                         m_currentPoint.x += this.basePositions.get(v)/2 + this.distX;
 108                         buildTree(v, this.m_currentPoint.x);
 109                 }
 110         }
 111         int width = 0;
 112         for(V v : roots) {
 113                 width += basePositions.get(v);
 114         }
 115     }
 116
 117     protected void buildTree(V v, int x) {
 118
 119         if (!alreadyDone.contains(v)) {
 120             alreadyDone.add(v);
 121
 122             //go one level further down
 123             this.m_currentPoint.y += this.distY;
 124             this.m_currentPoint.x = x;
 125
 126             this.setCurrentPositionFor(v);
 127
 128             int sizeXofCurrent = basePositions.get(v);
 129
 130             int lastX = x - sizeXofCurrent / 2;
 131
 132             int sizeXofChild;
 133             int startXofChild;
 134
 135             for (V element : graph.getSuccessors(v)) {
 136                 sizeXofChild = this.basePositions.get(element);
 137                 startXofChild = lastX + sizeXofChild / 2;
 138                 buildTree(element, startXofChild);
 139                 lastX = lastX + sizeXofChild + distX;
 140             }
 141             this.m_currentPoint.y -= this.distY;
 142         }
 143     }
 144
 145     private int calculateDimensionX(V v) {
 146
 147         int size = 0;
 148         int childrenNum = graph.getSuccessors(v).size();
 149
 150         if (childrenNum != 0) {
 151             for (V element : graph.getSuccessors(v)) {
 152                 size += calculateDimensionX(element) + distX;
 153             }
 154         }
 155         size = Math.max(0, size - distX);
 156         basePositions.put(v, size);
 157
 158         return size;
 159     }
 160
 161     private int calculateDimensionX(Collection<V> roots) {
 162
 163         int size = 0;
 164         for(V v : roots) {
 165                 int childrenNum = graph.getSuccessors(v).size();
 166
 167                 if (childrenNum != 0) {
 168                         for (V element : graph.getSuccessors(v)) {
 169                                 size += calculateDimensionX(element) + distX;
 170                         }
 171                 }
 172                 size = Math.max(0, size - distX);
 173                 basePositions.put(v, size);
 174         }
 175
 176         return size;
 177     }
 178
 179     /**
 180      * This method is not supported by this class.  The size of the layout
 181      * is determined by the topology of the tree, and by the horizontal
 182      * and vertical spacing (optionally set by the constructor).
 183      */
 184     public void setSize(Dimension size) {
 185         throw new UnsupportedOperationException("Size of TreeLayout is set" +
 186                 " by vertex spacing in constructor");
 187     }
 188
 189     protected void setCurrentPositionFor(V vertex) {
 190         int x = m_currentPoint.x;
 191         int y = m_currentPoint.y;
 192         if(x < 0) size.width -= x;
 193
 194         if(x > size.width-distX)
 195                 size.width = x + distX;
 196
 197         if(y < 0) size.height -= y;
 198         if(y > size.height-distY)
 199                 size.height = y + distY;
 200         locations.get(vertex).setLocation(m_currentPoint);
 201
 202     }
 203
 204         public Graph<V,E> getGraph() {
 205                 return graph;
 206         }
 207
 208         public Dimension getSize() {
 209                 return size;
 210         }
 211
 212         public void initialize() {
 213
 214         }
 215
 216         public boolean isLocked(V v) {
 217                 return false;
 218         }
 219
 220         public void lock(V v, boolean state) {
 221         }
 222
 223         public void reset() {
 224         }
 225
 226         public void setGraph(Graph<V,E> graph) {
 227                 if(graph instanceof Forest) {
 228                         this.graph = (Forest<V,E>)graph;
 229                         buildTree();
 230                 } else {
 231                         throw new IllegalArgumentException("graph must be a Forest");
 232                 }
 233         }
 234
 235         public void setInitializer(Transformer<V, Point2D> initializer) {
 236         }
 237
 238     /**
 239      * Returns the center of this layout's area.
 240      */
 241         public Point2D getCenter() {
 242                 return new Point2D.Double(size.getWidth()/2,size.getHeight()/2);
 243         }
 244
 245         public void setLocation(V v, Point2D location) {
 246                 locations.get(v).setLocation(location);
 247         }
 248
 249         public Point2D transform(V v) {
 250                 return locations.get(v);
 251         }
 252 }