RadialTreeLayoutAlgorithm.java
| Index Score | ||
|---|---|---|
![]() |
![]() |
org.jgraph.plugins.layouts |
![]() |
![]() |
JGraph |
View: Reasons, Metrics, Source Code
These are the metrics that contribute to the Enerjy Score for this file, ranked by impact. So the metrics listed at the top influence the score to a greater extent that the metrics listed at the bottom.
/*
* @(#)RadialTreeLayoutAlgorithm.java 1.0 18-MAY-2004
*
* Copyright (c) 2004, Michael J. Lawley
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* - Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
* - Neither the name of JGraph nor the names of its contributors may be used
* to endorse or promote products derived from this software without specific
* prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
package org.jgraph.plugins.layouts;
import java.awt.Rectangle;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Properties;
import org.jgraph.JGraph;
import org.jgraph.graph.CellView;
import org.jgraph.graph.GraphConstants;
import org.jgraph.graph.GraphModel;
import org.jgraph.graph.VertexView;
/**
* Lays out the nodes in a graph as a radial tree (root at the centre, children in concentric ovals).
* <p>
* The layout algorithm is similar to that described in the paper
* <em>"Radial Tree Graph Drawing Algorithm for Representing Large Hierarchies"</em>
* by Greg Book and Neeta Keshary.
* <p>
* The algorithm is modified from that in the above paper since it
* contains bugs and the sample code contains major inefficiencies.
* <p>
* Since this algorithm needs to be applied to a tree but we have
* a directed graph, a spanning tree is first constructed then the
* algorithm is applied to it.
*
* @author <a href="mailto:lawley@dstc.edu.au">michael j lawley</a>
* @since 3.1
* @version 1.0 init
*/
public class RadialTreeLayoutAlgorithm extends JGraphLayoutAlgorithm {
/**
* Property key for specifying maximum width of layout area.
*
* If WIDTH is specified, then CENTRE_X and RADIUS_X are
* calculated from it based on the maximum depth of the
* spanning tree.
*/
public static final String KEY_WIDTH = "Width";
/**
* Property key for specifying maximum height of layout area.
*
* If HEIGHT is specified, then CENTRE_Y and RADIUS_Y are
* calculated from it based on the maximum depth of the
* spanning tree.
*/
public static final String KEY_HEIGHT = "Height";
/**
* Property key for specifying the X-axis coordinate of the centre of the layout.
*
* If WIDTH is specified, then the supplied value is ignored and
* CENTRE_X is calculated from it based on the maximum depth of the
* spanning tree.
*/
public static final String KEY_CENTRE_X = "CentreX";
/**
* Property key for specifying the Y-axis coordinate of the centre of the layout.
*
* If HEIGHT is specified, then the supplied value is ignored and
* CENTRE_Y is calculated from it based on the maximum depth of the
* spanning tree.
*/
public static final String KEY_CENTRE_Y = "CentreY";
/**
* Property key for specifying the maximum horizontal distance between a parent and child node.
*
* If WIDTH is specified, then the supplied value is ignored and
* RADIUS_X is calculated from it based on the maximum depth of the
* spanning tree.
*/
public static final String KEY_RADIUS_X = "RadiusX";
/**
* Property key for specifying the maximum vertical distance between a parent and child node.
*
* If WIDTH is specified, then the supplied value is ignored and
* RADIUS_X is calculated from it based on the maximum depth of the
* spanning tree.
*/
public static final String KEY_RADIUS_Y = "RadiusY";
// public static final String KEY_CONTINUOUS = "Continuous";
private static final String RADIAL_TREE_VISITED = "RadialTreeVisited";
private static final double TWO_PI = Math.PI * 2.0;
protected double RADIUSX;
protected double RADIUSY;
protected double ROOTX;
protected double ROOTY, WIDTH, HEIGHT;
private JGraph jgraph;
public RadialTreeLayoutAlgorithm() {
}
/**
* Returns the name of this algorithm in human
* readable form.
*/
public String toString() {
return "Radial Tree";
}
/**
* Get a human readable hint for using this layout.
*/
public String getHint() {
return "Select a tree";
}
/**
* Returns an new instance of SugiyamaLayoutSettings
*/
public JGraphLayoutSettings createSettings() {
return new RadialTreeLayoutSettings(this);
}
/**
* Applies a radial tree layout to nodes in the jgraph with respect to the supplied gpConfiguration.
*
* @param graph JGraph instance
* @param dynamic_cells List of all nodes the layout should move
* @param static_cells List of node the layout should not move but allow for
*/
public void run(JGraph graph, Object[] dynamic_cells, Object[] static_cells) {
this.jgraph = graph;
if (dynamic_cells == null || dynamic_cells.length == 0)
return;
CellView[] selectedCellViews =
graph.getGraphLayoutCache().getMapping(dynamic_cells);
// search all roots
List roots = getRoots(jgraph, selectedCellViews);
TreeNode tree = getSpanningTree(selectedCellViews, roots);
if (null == tree) {
return;
}
double depth = tree.getDepth();
Rectangle2D bounds = jgraph.getCellBounds(dynamic_cells);
double autoW = WIDTH;
if ((WIDTH == ROOTX) && (ROOTX == RADIUSX) && (ROOTX == 0)) {
autoW = bounds.getWidth();
}
if (autoW != 0) {
ROOTX = autoW / 2.0;
RADIUSX = ROOTX / depth;
}
double autoH = HEIGHT;
if ((HEIGHT == ROOTY) && (ROOTY == RADIUSY) && (ROOTY == 0)) {
autoH = bounds.getHeight();
}
if (autoH != 0) {
ROOTY = autoH / 2.0;
RADIUSY = ROOTY / depth;
}
Map viewMap = new HashMap();
layoutTree0(viewMap, tree);
jgraph.getGraphLayoutCache().edit(viewMap, null, null, null);
}
public void setConfiguration(Properties configuration) {
if (configuration.containsKey(KEY_WIDTH)) {
WIDTH = Double.parseDouble(configuration.getProperty(KEY_WIDTH));
} else {
if (configuration.containsKey(KEY_CENTRE_X)) {
ROOTX = Double.parseDouble(configuration.getProperty(KEY_CENTRE_X));
} else {
throw new IllegalArgumentException("Must specify one of KEY_WIDTH or KEY_CENTRE_X");
}
if (configuration.containsKey(KEY_RADIUS_X)) {
RADIUSX = Double.parseDouble(configuration.getProperty(KEY_RADIUS_X));
} else {
throw new IllegalArgumentException("Must specify one of KEY_WIDTH or KEY_RADIUS_X");
}
}
if (configuration.containsKey(KEY_HEIGHT)) {
HEIGHT = Double.parseDouble(configuration.getProperty(KEY_HEIGHT));
} else {
if (configuration.containsKey(KEY_CENTRE_Y)) {
ROOTY = Double.parseDouble(configuration.getProperty(KEY_CENTRE_Y));
} else {
throw new IllegalArgumentException("Must specify one of KEY_HEIGHT or KEY_CENTRE_Y");
}
if (configuration.containsKey(KEY_RADIUS_Y)) {
RADIUSY = Double.parseDouble(configuration.getProperty(KEY_RADIUS_Y));
} else {
throw new IllegalArgumentException("Must specify one of KEY_WIDTH or KEY_RADIUS_X");
}
}
}
private void layoutTree0(Map viewMap, TreeNode node) {
node.angle = 0;
node.x = ROOTX;
node.y = ROOTY;
node.rightBisector = 0;
node.rightTangent = 0;
node.leftBisector = TWO_PI;
node.leftTangent = TWO_PI;
VertexView view = node.getView();
if (null != view) {
placeView(viewMap, view, ROOTX, ROOTY);
}
List parent = new ArrayList(1);
parent.add(node);
layoutTreeN(viewMap, 1, parent);
}
private void layoutTreeN(Map viewMap, int level, List nodes) {
double i;
double prevAngle = 0.0;
TreeNode parent, node, firstParent = null, prevParent = null;
List parentNodes = new ArrayList();
Iterator nitr = nodes.iterator();
while (nitr.hasNext()) {
parent = (TreeNode) nitr.next();
List children = parent.getChildren();
double rightLimit = parent.rightLimit();
double angleSpace = (parent.leftLimit() - rightLimit) / children.size();
Iterator itr = children.iterator();
for (i = 0.5; itr.hasNext(); i++) {
node = (TreeNode) itr.next();
VertexView view = node.getView();
node.angle = rightLimit + (i * angleSpace);
node.x = ROOTX + ((level * RADIUSX) * Math.cos(node.angle));
node.y = ROOTY + ((level * RADIUSY) * Math.sin(node.angle));
placeView(viewMap, view, node.x, node.y);
// Is it a parent node?
if (node.hasChildren()) {
parentNodes.add(node);
if (null == firstParent) {
firstParent = node;
}
// right bisector limit
double prevGap = node.angle - prevAngle;
node.rightBisector = node.angle - (prevGap / 2.0);
if (null != prevParent) {
prevParent.leftBisector = node.rightBisector;
}
double arcAngle = level / (level + 1.0);
double arc = 2.0 * Math.asin(arcAngle);
node.leftTangent = node.angle + arc;
node.rightTangent = node.angle - arc;
prevAngle = node.angle;
prevParent = node;
}
}
}
if (null != firstParent) {
double remaningAngle = TWO_PI - prevParent.angle;
firstParent.rightBisector = (firstParent.angle - remaningAngle) / 2.0;
if (firstParent.rightBisector < 0) {
prevParent.leftBisector = firstParent.rightBisector + TWO_PI + TWO_PI;
} else {
prevParent.leftBisector = firstParent.rightBisector + TWO_PI;
}
}
if (parentNodes.size() > 0) {
layoutTreeN(viewMap, level + 1, parentNodes);
}
}
private void placeView(Map viewMap, VertexView view, double x, double y) {
Rectangle2D rect = view.getBounds();
Rectangle bounds = new Rectangle((int) rect.getX(),
(int) rect.getY(), (int) rect.getWidth(), (int) rect.getHeight());
//(Rectangle) view.getBounds().clone();
bounds.x = (int) Math.round(x);
bounds.y = (int) Math.round(y);
Object cell = view.getCell();
Map map = new Hashtable();
GraphConstants.setBounds(map, bounds);
viewMap.put(cell, map);
}
private List getChildren(VertexView view, List level) {
ArrayList children = new ArrayList();
Object vertex = view.getCell();
GraphModel model = jgraph.getModel();
int portCount = model.getChildCount(vertex);
// iterate any NodePort
for (int i = 0; i < portCount; i++) {
Object port = model.getChild(vertex, i);
// iterate any Edge in the port
Iterator itrEdges = model.edges(port);
while (itrEdges.hasNext()) {
Object edge = itrEdges.next();
// if the Edge is a forward edge we should follow this edge
if (port == model.getSource(edge)) {
Object targetPort = model.getTarget(edge);
Object targetVertex = model.getParent(targetPort);
VertexView targetVertexView =
(VertexView) jgraph.getGraphLayoutCache().getMapping(targetVertex, false);
if (level.contains(targetVertexView)) {
children.add(targetVertexView);
}
}
}
}
return children;
}
private List getRoots(JGraph jgraph, CellView[] cellViews) {
List roots = new ArrayList();
GraphModel model = jgraph.getModel();
for (int i = 0; i < cellViews.length; i++) {
if (cellViews[i] instanceof VertexView) {
VertexView vertexView = (VertexView) cellViews[i];
boolean isRoot = true;
Object vertex = vertexView.getCell();
int portCount = model.getChildCount(vertex);
for (int j = 0; isRoot && j < portCount; j++) {
Object port = model.getChild(vertex, j);
Iterator itrEdges = model.edges(port);
while (isRoot && itrEdges.hasNext()) {
Object edge = itrEdges.next();
if (model.getTarget(edge) == port) {
isRoot = false;
}
}
}
if (isRoot) {
roots.add(vertexView);
}
}
}
return roots;
}
/**
* Algorithm assumes a single root node so if there are multiple roots
* (nodes with no incoming edges), then we construct the spanning tree
* with an invisible root node that is the parent of the real roots.
*/
private TreeNode getSpanningTree(CellView[] cellViews, List roots) {
List vertexViews = new ArrayList(cellViews.length);
// first: mark all as not visited
for (int i = 0; i < cellViews.length; i++) {
if (cellViews[i] instanceof VertexView) {
VertexView vertexView = (VertexView) cellViews[i];
vertexView.getAttributes().remove(RADIAL_TREE_VISITED);
vertexViews.add(vertexView);
}
}
TreeNode node;
if (roots.size() == 0) {
if (vertexViews.size() == 0) {
return null;
}
// else, pick an arbitrary node
roots.add(vertexViews.get(0));
}
if (roots.size() > 1) {
node = new TreeNode(null);
buildSpanningTree(vertexViews, node, roots);
} else {
VertexView vertexView = (VertexView) roots.get(0);
node = new TreeNode(vertexView);
vertexView.getAttributes().put(RADIAL_TREE_VISITED, Boolean.TRUE);
buildSpanningTree(vertexViews, node, getChildren(vertexView, vertexViews));
}
return node;
}
/**
* Breadth-first traversal of the graph.
*/
private void buildSpanningTree(List vertexViews, TreeNode node, List children) {
Iterator itr = children.iterator();
while (itr.hasNext()) {
VertexView vertexView = (VertexView) itr.next();
if (null == vertexView.getAttributes().get(RADIAL_TREE_VISITED)) {
vertexView.getAttributes().put(RADIAL_TREE_VISITED, Boolean.TRUE);
TreeNode childNode = new TreeNode(vertexView);
node.addChild(childNode);
}
}
itr = node.getChildren().iterator();
while (itr.hasNext()) {
TreeNode childNode = (TreeNode) itr.next();
VertexView vertexView = childNode.getView();
buildSpanningTree(vertexViews, childNode, getChildren(vertexView, vertexViews));
}
}
private static class TreeNode {
private VertexView view;
private List children = new ArrayList();
public double angle, x, y, rightBisector, leftBisector, rightTangent, leftTangent;
TreeNode(VertexView view) {
this.view = view;
}
public int getDepth() {
int depth = 1;
Iterator itr = children.iterator();
while (itr.hasNext()) {
TreeNode node = (TreeNode) itr.next();
int childDepth = node.getDepth();
if (childDepth >= depth) {
depth = childDepth + 1;
}
}
return depth;
}
public VertexView getView() {
return view;
}
public void addChild(TreeNode node) {
children.add(node);
}
public List getChildren() {
return children;
}
public boolean hasChildren() {
return children.size() > 0;
}
public double leftLimit() {
return Math.min(normalize(leftBisector), (leftTangent));
}
public double rightLimit() {
return Math.max(normalize(rightBisector), (rightTangent));
}
private double normalize(double angle) {
/*
while (angle > TWO_PI) {
angle -= TWO_PI;
}
while (angle < -TWO_PI) {
angle += TWO_PI;
}
*/
return angle;
}
}
}
The table below shows all metrics for RadialTreeLayoutAlgorithm.java.




