2 * Copyright (c) 2005, the JUNG Project and the Regents of the University of
3 * California All rights reserved.
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.
8 * Created on Jul 9, 2005
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;
21 import org.apache.commons.collections15.Transformer;
22 import org.apache.commons.collections15.map.LazyMap;
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;
29 * @author Karlheinz Toni
30 * @author Tom Nelson - converted to jung2
34 public class TreeLayout<V,E> implements Layout<V,E> {
36 protected Dimension size = new Dimension(600,600);
37 protected Forest<V,E> graph;
38 protected Map<V,Integer> basePositions = new HashMap<V,Integer>();
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();
47 protected transient Set<V> alreadyDone = new HashSet<V>();
50 * The default horizontal vertex spacing. Initialized to 50.
52 public static int DEFAULT_DISTX = 50;
55 * The default vertical vertex spacing. Initialized to 50.
57 public static int DEFAULT_DISTY = 50;
60 * The horizontal vertex spacing. Defaults to {@code DEFAULT_XDIST}.
62 protected int distX = 50;
65 * The vertical vertex spacing. Defaults to {@code DEFAULT_YDIST}.
67 protected int distY = 50;
69 protected transient Point m_currentPoint = new Point();
72 * Creates an instance for the specified graph with default X and Y distances.
74 public TreeLayout(Forest<V,E> g) {
75 this(g, DEFAULT_DISTX, DEFAULT_DISTY);
79 * Creates an instance for the specified graph and X distance with
82 public TreeLayout(Forest<V,E> g, int distx) {
83 this(g, distx, DEFAULT_DISTY);
87 * Creates an instance for the specified graph, X distance, and Y distance.
89 public TreeLayout(Forest<V,E> g, int distx, int disty) {
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");
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);
106 calculateDimensionX(v);
107 m_currentPoint.x += this.basePositions.get(v)/2 + this.distX;
108 buildTree(v, this.m_currentPoint.x);
113 width += basePositions.get(v);
117 protected void buildTree(V v, int x) {
119 if (!alreadyDone.contains(v)) {
122 //go one level further down
123 this.m_currentPoint.y += this.distY;
124 this.m_currentPoint.x = x;
126 this.setCurrentPositionFor(v);
128 int sizeXofCurrent = basePositions.get(v);
130 int lastX = x - sizeXofCurrent / 2;
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;
141 this.m_currentPoint.y -= this.distY;
145 private int calculateDimensionX(V v) {
148 int childrenNum = graph.getSuccessors(v).size();
150 if (childrenNum != 0) {
151 for (V element : graph.getSuccessors(v)) {
152 size += calculateDimensionX(element) + distX;
155 size = Math.max(0, size - distX);
156 basePositions.put(v, size);
161 private int calculateDimensionX(Collection<V> roots) {
165 int childrenNum = graph.getSuccessors(v).size();
167 if (childrenNum != 0) {
168 for (V element : graph.getSuccessors(v)) {
169 size += calculateDimensionX(element) + distX;
172 size = Math.max(0, size - distX);
173 basePositions.put(v, size);
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).
184 public void setSize(Dimension size) {
185 throw new UnsupportedOperationException("Size of TreeLayout is set" +
186 " by vertex spacing in constructor");
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;
194 if(x > size.width-distX)
195 size.width = x + distX;
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);
204 public Graph<V,E> getGraph() {
208 public Dimension getSize() {
212 public void initialize() {
216 public boolean isLocked(V v) {
220 public void lock(V v, boolean state) {
223 public void reset() {
226 public void setGraph(Graph<V,E> graph) {
227 if(graph instanceof Forest) {
228 this.graph = (Forest<V,E>)graph;
231 throw new IllegalArgumentException("graph must be a Forest");
235 public void setInitializer(Transformer<V, Point2D> initializer) {
239 * Returns the center of this layout's area.
241 public Point2D getCenter() {
242 return new Point2D.Double(size.getWidth()/2,size.getHeight()/2);
245 public void setLocation(V v, Point2D location) {
246 locations.get(v).setLocation(location);
249 public Point2D transform(V v) {
250 return locations.get(v);