--- /dev/null
+/*
+ * Copyright (c) 2005, the JUNG Project and the Regents of the University of
+ * California All rights reserved.
+ *
+ * This software is open-source under the BSD license; see either "license.txt"
+ * or http://jung.sourceforge.net/license.txt for a description.
+ *
+ * Created on Jul 9, 2005
+ */
+
+package edu.uci.ics.jung.algorithms.layout;
+import java.awt.Dimension;
+import java.awt.Point;
+import java.awt.geom.Point2D;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.commons.collections15.Transformer;
+import org.apache.commons.collections15.map.LazyMap;
+
+import edu.uci.ics.jung.graph.Forest;
+import edu.uci.ics.jung.graph.Graph;
+import edu.uci.ics.jung.graph.util.TreeUtils;
+
+/**
+ * @author Karlheinz Toni
+ * @author Tom Nelson - converted to jung2
+ *
+ */
+
+public class TreeLayout<V,E> implements Layout<V,E> {
+
+ protected Dimension size = new Dimension(600,600);
+ protected Forest<V,E> graph;
+ protected Map<V,Integer> basePositions = new HashMap<V,Integer>();
+
+ protected Map<V, Point2D> locations =
+ LazyMap.decorate(new HashMap<V, Point2D>(),
+ new Transformer<V,Point2D>() {
+ public Point2D transform(V arg0) {
+ return new Point2D.Double();
+ }});
+
+ protected transient Set<V> alreadyDone = new HashSet<V>();
+
+ /**
+ * The default horizontal vertex spacing. Initialized to 50.
+ */
+ public static int DEFAULT_DISTX = 50;
+
+ /**
+ * The default vertical vertex spacing. Initialized to 50.
+ */
+ public static int DEFAULT_DISTY = 50;
+
+ /**
+ * The horizontal vertex spacing. Defaults to {@code DEFAULT_XDIST}.
+ */
+ protected int distX = 50;
+
+ /**
+ * The vertical vertex spacing. Defaults to {@code DEFAULT_YDIST}.
+ */
+ protected int distY = 50;
+
+ protected transient Point m_currentPoint = new Point();
+
+ /**
+ * Creates an instance for the specified graph with default X and Y distances.
+ */
+ public TreeLayout(Forest<V,E> g) {
+ this(g, DEFAULT_DISTX, DEFAULT_DISTY);
+ }
+
+ /**
+ * Creates an instance for the specified graph and X distance with
+ * default Y distance.
+ */
+ public TreeLayout(Forest<V,E> g, int distx) {
+ this(g, distx, DEFAULT_DISTY);
+ }
+
+ /**
+ * Creates an instance for the specified graph, X distance, and Y distance.
+ */
+ public TreeLayout(Forest<V,E> g, int distx, int disty) {
+ if (g == null)
+ throw new IllegalArgumentException("Graph must be non-null");
+ if (distx < 1 || disty < 1)
+ throw new IllegalArgumentException("X and Y distances must each be positive");
+ this.graph = g;
+ this.distX = distx;
+ this.distY = disty;
+ buildTree();
+ }
+
+ protected void buildTree() {
+ this.m_currentPoint = new Point(0, 20);
+ Collection<V> roots = TreeUtils.getRoots(graph);
+ if (roots.size() > 0 && graph != null) {
+ calculateDimensionX(roots);
+ for(V v : roots) {
+ calculateDimensionX(v);
+ m_currentPoint.x += this.basePositions.get(v)/2 + this.distX;
+ buildTree(v, this.m_currentPoint.x);
+ }
+ }
+ int width = 0;
+ for(V v : roots) {
+ width += basePositions.get(v);
+ }
+ }
+
+ protected void buildTree(V v, int x) {
+
+ if (!alreadyDone.contains(v)) {
+ alreadyDone.add(v);
+
+ //go one level further down
+ this.m_currentPoint.y += this.distY;
+ this.m_currentPoint.x = x;
+
+ this.setCurrentPositionFor(v);
+
+ int sizeXofCurrent = basePositions.get(v);
+
+ int lastX = x - sizeXofCurrent / 2;
+
+ int sizeXofChild;
+ int startXofChild;
+
+ for (V element : graph.getSuccessors(v)) {
+ sizeXofChild = this.basePositions.get(element);
+ startXofChild = lastX + sizeXofChild / 2;
+ buildTree(element, startXofChild);
+ lastX = lastX + sizeXofChild + distX;
+ }
+ this.m_currentPoint.y -= this.distY;
+ }
+ }
+
+ private int calculateDimensionX(V v) {
+
+ int size = 0;
+ int childrenNum = graph.getSuccessors(v).size();
+
+ if (childrenNum != 0) {
+ for (V element : graph.getSuccessors(v)) {
+ size += calculateDimensionX(element) + distX;
+ }
+ }
+ size = Math.max(0, size - distX);
+ basePositions.put(v, size);
+
+ return size;
+ }
+
+ private int calculateDimensionX(Collection<V> roots) {
+
+ int size = 0;
+ for(V v : roots) {
+ int childrenNum = graph.getSuccessors(v).size();
+
+ if (childrenNum != 0) {
+ for (V element : graph.getSuccessors(v)) {
+ size += calculateDimensionX(element) + distX;
+ }
+ }
+ size = Math.max(0, size - distX);
+ basePositions.put(v, size);
+ }
+
+ return size;
+ }
+
+ /**
+ * This method is not supported by this class. The size of the layout
+ * is determined by the topology of the tree, and by the horizontal
+ * and vertical spacing (optionally set by the constructor).
+ */
+ public void setSize(Dimension size) {
+ throw new UnsupportedOperationException("Size of TreeLayout is set" +
+ " by vertex spacing in constructor");
+ }
+
+ protected void setCurrentPositionFor(V vertex) {
+ int x = m_currentPoint.x;
+ int y = m_currentPoint.y;
+ if(x < 0) size.width -= x;
+
+ if(x > size.width-distX)
+ size.width = x + distX;
+
+ if(y < 0) size.height -= y;
+ if(y > size.height-distY)
+ size.height = y + distY;
+ locations.get(vertex).setLocation(m_currentPoint);
+
+ }
+
+ public Graph<V,E> getGraph() {
+ return graph;
+ }
+
+ public Dimension getSize() {
+ return size;
+ }
+
+ public void initialize() {
+
+ }
+
+ public boolean isLocked(V v) {
+ return false;
+ }
+
+ public void lock(V v, boolean state) {
+ }
+
+ public void reset() {
+ }
+
+ public void setGraph(Graph<V,E> graph) {
+ if(graph instanceof Forest) {
+ this.graph = (Forest<V,E>)graph;
+ buildTree();
+ } else {
+ throw new IllegalArgumentException("graph must be a Forest");
+ }
+ }
+
+ public void setInitializer(Transformer<V, Point2D> initializer) {
+ }
+
+ /**
+ * Returns the center of this layout's area.
+ */
+ public Point2D getCenter() {
+ return new Point2D.Double(size.getWidth()/2,size.getHeight()/2);
+ }
+
+ public void setLocation(V v, Point2D location) {
+ locations.get(v).setLocation(location);
+ }
+
+ public Point2D transform(V v) {
+ return locations.get(v);
+ }
+}