AnnealingLayoutAlgorithm.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.
| Metric | Description | |
|---|---|---|
| LOOPS | Number of loops |  |
| DECL_COMMENTS | Comments in declarations | |
| SIZE | Size of the file in bytes | |
| DOC_COMMENT | Number of javadoc comment lines | |
| EXEC_COMMENTS | Comments in executable code | |
| COMPARISONS | Number of comparison operators | |
| COMMENTS | Comment lines | |
| JAVA0034 | JAVA0034 Missing braces in if statement | |
| PROGRAM_LENGTH | Halstead program length | |
| OPERATORS | Number of operators | |
| OPERANDS | Number of operands | |
| LINES | Number of lines in the source file | |
| CYCLOMATIC | Cyclomatic complexity | |
| LOGICAL_LINES | Number of statements | |
| LINE_COMMENT | Number of line comments | |
| ELOC | Effective lines of code | |
| LOC | Lines of code | |
| JAVA0035 | JAVA0035 Missing braces in for statement | |
| BLOCKS | Number of blocks | |
| UNIQUE_OPERANDS | Number of unique operands | |
| PROGRAM_VOCAB | Halstead program vocabulary | |
| EXITS | Procedure exits | |
| WHITESPACE | Number of whitespace lines | |
| INTERFACE_COMPLEXITY | Interface complexity | |
| RETURNS | Number of return points from functions | |
| JAVA0068 | JAVA0068 Modifiers not declared in recommended order | |
| JAVA0144 | JAVA0144 Line exceeds maximum M characters | |
| JAVA0270 | JAVA0270 Use Java 5.0 enhanced for loop construct to iterate over all elements in an array | |
| PARAMS | Number of formal parameter declarations | |
| FUNCTIONS | Number of function declarations | |
| JAVA0110 | JAVA0110 Incorrect javadoc: no @return tag | |
| JAVA0078 | JAVA0078 Floating point values compared with == | |
| JAVA0116 | JAVA0116 Missing javadoc: field 'field' | |
| JAVA0108 | JAVA0108 Incorrect javadoc: no @param tag for 'parameter' | |
| JAVA0076 | JAVA0076 Use of magic number | |
| JAVA0119 | JAVA0119 Control variable changed within body of for loop | |
| JAVA0130 | JAVA0130 Non-static method does not use instance fields | |
| JAVA0254 | JAVA0254 Use enhanced for loop construct instead of Iterator | |
| JAVA0049 | JAVA0049 Nested block at depth N (maximum: M) | |
| UNIQUE_OPERATORS | Number of unique operators | |
| JAVA0036 | JAVA0036 Missing braces in while statement | |
| JAVA0267 | JAVA0267 Use of System.err | |
| JAVA0117 | JAVA0117 Missing javadoc: method 'method' | |
| NEST_DEPTH | Maximum nesting depth | |
| PROGRAM_VOLUME | Halstead program volume | |
| JAVA0136 | JAVA0136 N methods defined in class (maximum: M) | |
| JAVA0266 | JAVA0266 Use of System.out | |
| JAVA0174 | JAVA0174 Assigned local variable never used | |
| JAVA0256 | JAVA0256 Assignment of external collection/array to field | |
| JAVA0126 | JAVA0126 Method declares unchecked exception in throws | |
| JAVA0179 | JAVA0179 Local variable hides visible field | |
| JAVA0100 | JAVA0100 Class contains N non-final fields (maximum: M) | |
| JAVA0075 | JAVA0075 Method parameter hides field | |
| BLOCK_COMMENT | Number of block comment lines | |
| JAVA0145 | JAVA0145 Tab character used in source file | |
/*
* @(#)AnnealingLayoutAlgorithm.java 1.0 18-MAY-2004
*
* Copyright (c) 2004, Winkler
* All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
package org.jgraph.plugins.layouts;
import java.awt.Rectangle;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Properties;
import org.jgraph.JGraph;
import org.jgraph.event.GraphModelEvent;
import org.jgraph.event.GraphModelListener;
import org.jgraph.graph.AttributeMap;
import org.jgraph.graph.CellMapper;
import org.jgraph.graph.CellView;
import org.jgraph.graph.EdgeView;
import org.jgraph.graph.GraphConstants;
import org.jgraph.graph.GraphModel;
import org.jgraph.graph.VertexView;
/**
* <h1>Simulated Annealing Layout Algorithm</h1><p>
* Implemented from the paper: "Drawing Graphs Nicely Using Simulated Annealing"
* from Ron Davidson and David Harel. ACM Transactions on Graphics, Vol. 15,
* No. 4, October 1996, Pages 301-331.
* @author winkler
* @version 1.0
* Date of creation: 11.04.2003 - 12:39:58
*/
public class AnnealingLayoutAlgorithm extends JGraphLayoutAlgorithm implements GraphModelListener {
public final static int COUT_COSTFUNCTION = 6;
public final static int COSTFUNCTION_EDGE_DISTANCE = 1;
public final static int COSTFUNCTION_EDGE_CROSSING = 2;
public final static int COSTFUNCTION_EDGE_LENGTH = 4;
public final static int COSTFUNCTION_BORDERLINE = 8;
public final static int COSTFUNCTION_NODE_DISTRIBUTION = 16;
public final static int COSTFUNCTION_NODE_DISTANCE = 32;
public final static String KEY_CAPTION = "Annealing Layoutalgorithm Attributes";
public final static String KEY_POSITION = "Position";
public final static String KEY_RELATIVES = "Relatives";
public final static String CF_KEY_EDGE_DISTANCE_RELEVANT_EDGES = "costfunction edge distance key for relevant edges";
/**
* Key used only with clusters. Under this key a cluster has an ArrayList.
* This list is filled with the clustered vertices.
* @see #clusterGraph()
*/
public final static String KEY_CLUSTERED_VERTICES = "Clustered Vertices";
/**
* Key used only with clusters. Under this key vertices have the cluster
* they belong to.
* @see #clusterGraph()
*/
public final static String KEY_CLUSTER = "Cluster";
/**
* Key used only with clusters. Under this key a cluster has a boolean value
* indicating that this vertice is a cluster (clusters are
* VertexView-instances like every other cell).
* @see #clusterGraph()
*/
public final static String KEY_IS_CLUSTER = "is Cluster";
/**
* Key used only with clusters. Under this key every cluster has a position,
* which represents the position of the cluster, right after the clustering
* process. After the layout update process is finished, the move, resulting
* of subtracting the position under {@link #KEY_POSITION} from the
* position under this value, will be performed to all vertices in the
* cluster. By holding the initial position here clustering becomes
* possible.
*
* @see #clusterGraph()
* @see #declusterGraph()
*/
public final static String KEY_CLUSTER_INIT_POSITION = "initial Position of the Cluster";
/**
* Key for loading gpConfiguration values. Indicates to load values for a
* normal run.
*/
protected final static int CONFIG_KEY_RUN = 0;
/**
* Key for loading gpConfiguration values. Indicates to load values for a
* layout update.
*/
protected final static int CONFIG_KEY_LAYOUT_UPDATE = 1;
/**
* actual temperature
*/
private double temperature;
/**
* starting temperature
*/
private double initTemperature = 40;
/**
* when {@link #temperature} reaches this value, the algorithm finishes its
* calculation.
*/
private double minTemperature = 2;
/**
* value for costfunctions and getEdgeDistribution.
* Determines, how long the edges have to
* be.
*/
private double minDistance = 50;
/**
* {@link #temperature} will be multiplied with this value every round
*/
private double tempScaleFactor = 0.95;
/**
* maximum number of rounds, if algorithm doesn't stop earlier, by
* temperature decreasement.
*/
private int maxRounds = 10000;
/**
* normalizing and priority factors for the costfunctions
*/
protected double[] lambdaList = new double[]{
1000, 100000, 0.02, 2000, 150, 1000000};
/**
* the drawing area, the graph should be layouted in.
*/
private Rectangle bounds = new Rectangle(0, 0, 1000, 700);
/**
* determines, if the cells of the graph are computed every time in the
* same order or a random order, calculated every round.
*/
private boolean computePermutation = true;
/**
* determines, if the only allowed moves for cells of the graph are moves,
* that cost less.
*/
private boolean uphillMovesAllowed = true;
/**
* Indicates, if the algorithm should also run on Updates in the graph.
*/
private boolean isLayoutUpdateEnabled = true;
/**
* Indicates what costfunctions to use for calculating the costs of the
* graph. The bits of this Integer switches the functions. Possible Values
* are <br>
* <blockquote><blockquote>
* {@link AnnealingLayoutAlgorithm#COSTFUNCTION_NODE_DISTRIBUTION
* COSTFUNCTION_NODE_DISTRIBUTION}<br>
* {@link AnnealingLayoutAlgorithm#COSTFUNCTION_NODE_DISTANCE
* COSTFUNCTION_NODE_DISTANCE}<br>
* {@link AnnealingLayoutAlgorithm#COSTFUNCTION_BORDERLINE
* COSTFUNCTION_BORDERLINE}<br>
* {@link AnnealingLayoutAlgorithm#COSTFUNCTION_EDGE_DISTANCE
* COSTFUNCTION_EDGE_DISTANCE}<br>
* {@link AnnealingLayoutAlgorithm#COSTFUNCTION_EDGE_CROSSING
* COSTFUNCTION_EDGE_CROSSING}<br>
* </blockquote></blockquote>
*/
private int costFunctionConfig = Integer.parseInt("111110", 2);
/**
* counts the rounds
*/
private int round;
/**
* determines, in how many segments the circle around cells is divided,
* to find a new position for the cell.
*/
private int triesPerCell = 8;
/**
* the list of all cells of the graph
*/
protected ArrayList cellList;
/**
* the list of all edges of the graph
*/
protected ArrayList edgeList;
/**
* the list of all cells, a new layout should be calculated for
*/
protected ArrayList applyCellList;
/**
* the JGraph
*/
private JGraph jgraph;
/**
* holds the gpConfiguration of the algorithm, gained by the controller
*/
protected Properties presetConfig;
/**
* for debugging purpose.
*/
// private long time = 0;
/**
* for debugging purpose
*/
// private boolean isDebugging = false;
/**
* indicates if the algorihm is performing a calculation. this prevents from
* entering the method {@link #graphChanged(GraphModelEvent)
* graphChanged(...)} more than once at a time.
*/
private boolean isRunning = false;
/**
* the number of edges, neighbors of inserted cells are away,
* to be also layouted again.
*/
private int luRecursionDepth = 1;
/**
* if a cell has a lower distance to a inserted cell, after the cell gained
* its initial position, it will be layouted too
*/
private double luPerimeterRadius = 100;
/**
* if more than one cell is inserted and the initial position of other
* inserted cells is inside {@link #luPerimeterRadius} around a initial
* position of a inserted cell, than {@link #luPerimeterRadius} will be
* increased by this value.
*/
private double luPerimeterRadiusInc = 20;
/**
* determines how the neighborhood is handled, when a layout update
* should be performed. Possible values are:<p>
* <blockquote><blockquote>
* </blockquote></blockquote>
*/
private String luMethod = AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_METHOD_PERIMETER;
/**
* prevents from dividing with zero and from creating to high costs
*/
private double equalsNull = 0.05;
/**
* Switches clustering for the layout update process on/off
*/
private boolean isClusteringEnabled = true;
/**
* Scales movement of clusters. It is recommendet to take
* a value between 1.0 and 0.0. This garanties, that clusters move slower
* than other cells. That rises the chance of getting a good looking layout
* after the calculation.
*/
private double clusterMoveScaleFactor = 0.1;
/**
* Effects, how many clusters are created, when the layout update process
* starts. This affects the initial number of clusters, which is the number
* of cells available minus the number of cells to layout. The result of
* that term is divided by this factor, to get the maximum number of
* clusters. After this calculation, the clustering algorithm tries to
* minimize the number of clusters, so there might be less clusters than
* the maximum number.
*/
private double clusteringFactor = 8.0;
protected boolean isOptimizer = false;
/******************************************************************************/
/**
* Constructor for SimulatedAnnealingAlgorithm.
*/
public AnnealingLayoutAlgorithm() {
this(false);
setMaximumProgress(100);
}
/**
* Constructor for SimulatedAnnealingAlgorithm.
*/
public AnnealingLayoutAlgorithm(boolean isOptimizer) {
this.isOptimizer = isOptimizer;
}
/**
* Returns the name of this algorithm in human
* readable form.
*/
public String toString() {
return "Annealing";
}
/**
* Get a human readable hint for using this layout.
*/
public String getHint() {
return "Ignores selection";
}
/**
* Returns an new instance of SugiyamaLayoutSettings
*/
public JGraphLayoutSettings createSettings() {
return new AnnealingLayoutSettings(this, false);
}
/******************************************************************************/
/**
* Runs the Algorithm
*/
public void run(JGraph graph, Object[] dynamic_cells, Object[] static_cells) {
isRunning = true;
setAllowedToRun(true);
setProgress(1);
// System.out.println("now running Simulated Annealing");
/*----------------AQUIRATION OF RUNTIME CONSTANTS----------------*/
jgraph = graph;
//presetConfig = gpConfiguration;
cellList = new ArrayList();
edgeList = new ArrayList();
applyCellList = new ArrayList();
getNodes(jgraph, dynamic_cells);
if( applyCellList.size() == 0 )
return;
if( isLayoutUpdateEnabled )
jgraph.getModel().addGraphModelListener(this);
/*------------------------AQUIRATION DONE------------------------*/
/*------------------------ALGORITHM START------------------------*/
init(true);
run();
/*-------------------------ALGORITHM END-------------------------*/
if (isAllowedToRun()) {
//if this algorithm isn't a optimization add-on of another algorithm
moveGraphToNW();//moves the graph to the upper left corner
applyChanges(); // making temporary positions to real positions
removeTemporaryData(); // remove temporary positions
}
isRunning = false;
}
/******************************************************************************/
/**
* Runs the Algorithm as a optimization Algorithm of another Algorithm
* @param applyList List of all Cells, a new Layout should be found for.
* @param allCellList List of all Cells of the Graph
* @param allEdgeList List of all Edges of the Graph
*/
public void performOptimization(ArrayList applyList, ArrayList allCellList, ArrayList allEdgeList, Properties config) {
cellList = allCellList;
applyCellList = applyList;
edgeList = allEdgeList;
presetConfig = config;
loadConfiguration(CONFIG_KEY_RUN);
init(false);
run();
}
/******************************************************************************/
/**
* Loads the initial Values from the gpConfiguration.
*
* @param configSwitch Determines which configurationvalues have to be loaded
* Possible values are {@link #CONFIG_KEY_RUN} and
* {@link #CONFIG_KEY_LAYOUT_UPDATE}
*/
private void loadConfiguration(int configSwitch) {
//load config for normal runs
if( configSwitch == CONFIG_KEY_RUN ){
initTemperature = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_INIT_TEMPERATURE));
minTemperature = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_MIN_TEMPERATURE));
minDistance = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_MIN_DISTANCE));
tempScaleFactor = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_TEMP_SCALE_FACTOR));
maxRounds = Integer.parseInt((String)presetConfig.get(AnnealingLayoutSettings.KEY_MAX_ROUNDS));
triesPerCell = Integer.parseInt((String)presetConfig.get(AnnealingLayoutSettings.KEY_TRIES_PER_CELL));
ArrayList lambda = (ArrayList) presetConfig.get(AnnealingLayoutSettings.KEY_LAMBDA);
lambdaList = new double[COUT_COSTFUNCTION];
for( int i = 0; i < lambdaList.length; i++ )
lambdaList[i] = ((Double)lambda.get(i)).doubleValue();
bounds = (Rectangle) presetConfig.get(AnnealingLayoutSettings.KEY_BOUNDS);
costFunctionConfig = Integer.parseInt((String)presetConfig.get(AnnealingLayoutSettings.KEY_COST_FUNCTION_CONFIG),2);
computePermutation = isTrue((String)presetConfig.get(AnnealingLayoutSettings.KEY_COMPUTE_PERMUTATION));
uphillMovesAllowed = isTrue((String)presetConfig.get(AnnealingLayoutSettings.KEY_IS_UPHILL_MOVE_ALLOWED));
}
//load config for layout updates
else if( configSwitch == CONFIG_KEY_LAYOUT_UPDATE ){
initTemperature = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_INIT_TEMPERATURE));
minTemperature = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_MIN_TEMPERATURE));
minDistance = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_MIN_DISTANCE));
tempScaleFactor = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_TEMP_SCALE_FACTOR));
maxRounds = Integer.parseInt((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_MAX_ROUNDS));
triesPerCell = Integer.parseInt((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_TRIES_PER_CELL));
ArrayList lambda = (ArrayList) presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_LAMBDA);
lambdaList = new double[COUT_COSTFUNCTION];
for( int i = 0; i < lambdaList.length; i++ )
lambdaList[i] = ((Double)lambda.get(i)).doubleValue();
bounds = (Rectangle) presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_BOUNDS);
costFunctionConfig = Integer.parseInt((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_COST_FUNCTION_CONFIG),2);
computePermutation = isTrue((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_COMPUTE_PERMUTATION));
uphillMovesAllowed = isTrue((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_IS_UPHILL_MOVE_ALLOWED));
luRecursionDepth = Integer.parseInt((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_METHOD_NEIGHBORS_DEPTH));
luPerimeterRadius = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_METHOD_PERIMETER_RADIUS));
luPerimeterRadiusInc = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_METHOD_PERIMETER_RADIUS_INCREASE));
luMethod = (String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_METHOD);
isClusteringEnabled = isTrue((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_CLUSTERING_ENABLED));
clusteringFactor = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_CLUSTERING_FACTOR));
clusterMoveScaleFactor = Double.parseDouble((String)presetConfig.get(AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_CLUSTERING_MOVE_SCALE));
}
}
/******************************************************************************/
/**
* Helper-method. Transforms a String into a Boolean Value. The String
* has to contain the characters "true" or "false". upper case writings
* of some letters doesn't matter. if the String doesn't contain "true"
* or "false" the method returns false (easier to handle than throwing
* an exception).
*/
private boolean isTrue(String boolValue) {
if( boolValue != null ){
if( "TRUE".equals(boolValue.toUpperCase()) ) {
return true;
}
else if( "FALSE".equals(boolValue.toUpperCase()) ) {
return false;
}
}
return false;
}
/******************************************************************************/
/**
* Extracts all cells, all edges and all cells, the algorithm should run for,
* from JGraph. After calling this Method {@link #cellList},
* {@link #applyCellList} and {@link #edgeList} is filled.
*
* @param jgraph A instanz from JGraph, the Cells will be extract from.
*/
private void getNodes(JGraph jgraph, Object[] cells){
Object[] all = jgraph.getRoots();
CellView[] view = jgraph.getGraphLayoutCache().getMapping(all,false);
CellView[] selectedView = jgraph.getGraphLayoutCache().getMapping(
cells,false);
for (int i = 0; i < view.length; i++)
if (view[i] instanceof VertexView){
cellList.add(view[i]);
applyCellList.add(view[i]);
}
else if( view[i] instanceof EdgeView ){
edgeList.add(view[i]);
}
for( int i = 0; i < selectedView.length; i++ )
if( selectedView[i] instanceof VertexView )
applyCellList.add(selectedView[i]);
}
/******************************************************************************/
/**
* Makes the changed Positions of the Cells of the graph visible. This is like
* a "commit". Before this Method runs, nothing has change is the visible
* representation of the graph. After this method, the Layout for the Cells
* of the graph is applied.
*/
private void applyChanges(){
Map viewMap = new Hashtable();
for( int i = 0; i < applyCellList.size(); i++ ){
CellView view = (CellView)applyCellList.get(i);
Point2D.Double pos = getPosition(view);
Rectangle2D r = view.getBounds();
r.setFrame(pos.getX() - (r.getWidth() /2.0),
pos.getY() - (r.getHeight()/2.0),
r.getWidth(), r.getHeight());
Object cell = ((CellView) applyCellList.get(i)).getCell();
Map attributes = new Hashtable();
GraphConstants.setBounds(attributes, r);
viewMap.put(cell, attributes);
}
jgraph.getGraphLayoutCache().edit(viewMap,null,null,null);
}
/******************************************************************************/
/**
* Removes the temporary Data from the Cells of the graph. During the run of the
* Algorithm there has been plenty of Data stored in the Cells. These are
* removed here, if the Algorithm is canceled or finished.
*/
private void removeTemporaryData(){
for( int i = 0; i < applyCellList.size(); i++ )
((CellView)applyCellList.get(i)).getAttributes().clear();
}
/******************************************************************************/
/**
* Initialises the Algorithm. This is the step right before running the
* Algorithm. Letting this method set the initial Positions for all cells is
* only necessary when the Algorithm makes a normal run. Otherwise the initial
* Positions are allready set, by
* {@link #arrangeLayoutUpdateInsertPlacement(CellView[])
* arrangeLayoutUpdateInsertPlacement(...)}.
* @param setInitPositions Determines, if the initial Positions of the cells
* should be set or not. Initial Positions are calculated by random.
*/
private void init(boolean setInitPositions){
if( setInitPositions ){
for( int i = 0; i < applyCellList.size(); i++ )
if( !((CellView)applyCellList.get(i)).getAttributes().containsKey(KEY_POSITION) )
setPosition(i,
(Math.random()*bounds.getWidth()) +bounds.getX(),
(Math.random()*bounds.getHeight())+bounds.getY());
for( int i = 0; i < cellList.size(); i++ )
if( !((CellView)cellList.get(i)).getAttributes().containsKey(KEY_POSITION) )
setPosition((CellView)cellList.get(i),
(Math.random()*bounds.getWidth()) +bounds.getX(),
(Math.random()*bounds.getHeight())+bounds.getY());
}
temperature = initTemperature;
maxRounds = Math.min(100 * applyCellList.size(),
getMaxRoundsByTemperature(temperature));
round = 0;
}
/******************************************************************************/
/**
* Runs the Algorithm until {@link #temperature} is lower than
* {@link #minTemperature}.
*/
private void run(){
while( round <= maxRounds && isAllowedToRun())
performRound();
}
/******************************************************************************/
/**
* Performs one round, so thats the main part of the Algorithm.
* Different to the original Implementation of the Algorithm, this Algorithm
* doesn't work with aproximativ 30 random Placements per Cell to find the best
* Position. This Algorithm works with a user defined number of segments. The
* Circle, the Cells will be placed on, is calculated like the original
* Implementation tells. But it is splited into a user defined number of
* segments. Then per cell a random offset is calculated and starting from
* that offset every segment is checked out, whether there is a better position
* for the cell. This can be done in a random order of the cells or always in
* the same order. Temperature is decreased after all cells are checked out
* for a new position, like in the original. While the original Implementation
* allows always uphill moves, this Algorithm allows the user to decide to work
* with or without them.
*/
private void performRound(){
Point2D.Double[] config = getConfig();
double startEnergy = getGlobalCosts(lambdaList);
double globalEnergy = startEnergy;
double newGlobalEnergy = globalEnergy * 1.1; //somewhat higher than globalEnergy
//sequencial order cells are computed (every round the same order)
int[] sequence = new int[applyCellList.size()];
if( !computePermutation )
for( int i = 0; i < applyCellList.size(); i++ )
sequence[i] = i;
for( int i = 0; i < applyCellList.size(); i++ ){
if( computePermutation )//random order
sequence = createPermutation(applyCellList.size());
//random offset
double offset = Math.random() * 2.0 * Math.PI;
for( int j = 0; j < triesPerCell; j++ ){
double angle = j * ((2.0 * Math.PI)/triesPerCell);
angle += offset;
Point2D.Double move = null;
//calculating new move
if( isCluster((CellView)applyCellList.get(i)) ){
move = new Point2D.Double(
clusterMoveScaleFactor * temperature * Math.cos(angle),
clusterMoveScaleFactor * temperature * Math.sin(angle));
}
else {
move = new Point2D.Double( temperature * Math.cos(angle),
temperature * Math.sin(angle));
}
// Point2D.Double randomMove = getRandomVector(temperature);
//applying new move
setPosition(sequence[i],config[sequence[i]].x + move.x,
config[sequence[i]].y + move.y);
//calculating the costs for the actual layout
newGlobalEnergy = getGlobalCosts(lambdaList);
//taking move if costs < previos cost or uphill move possible
if( newGlobalEnergy < globalEnergy ||
(getBolzmanBreak(globalEnergy,newGlobalEnergy) &&
uphillMovesAllowed) ){
// if( isDebugging )
// System.out.println("taking new energy : "+globalEnergy+" -> "+newGlobalEnergy+" <<<<<<<<<<<<<<<<<<<<<<<<<");
globalEnergy = newGlobalEnergy;
config[sequence[i]] = new Point2D.Double(
config[sequence[i]].x + move.x,
config[sequence[i]].y + move.y);
// if( isDebugging )
// showApplyCellList();
break;
}
else {
// if( isDebugging )
// System.out.println("energy = "+globalEnergy+" new Global Energy = "+newGlobalEnergy+" temperature = "+temperature);
setPosition(sequence[i],
config[sequence[i]].x,
config[sequence[i]].y);
}
setProgress((int)(((double)((round*applyCellList.size()*triesPerCell)+(i*triesPerCell)+j)/(double)(maxRounds*applyCellList.size()*triesPerCell))*(100.0)));
if (!isAllowedToRun())
break;
}
//if this rounds runs very good and energy is 5% of starting value
//then break this round and start next round
if( globalEnergy == startEnergy * 0.05 )
break;
if (!isAllowedToRun())
break;
}
//temperature will be decreased
temperature *= tempScaleFactor;
round++;//rounds are counted
}
/******************************************************************************/
/**
* Extracts the Positions of all cells into a array of Positions.
* @return Array that represents the Positions of the Cells in
* {@link #applyCellList}.
*/
private Point2D.Double[] getConfig(){
Point2D.Double[] config = new Point2D.Double[applyCellList.size()];
for( int i = 0; i < applyCellList.size(); i++ ){
Point2D.Double pos = getPosition((CellView)applyCellList.get(i));
config[i] = new Point2D.Double(pos.x,pos.y);
}
return config;
}
/******************************************************************************/
/**
* Calculates the costs of the actual graph by using costfunctions.
* @param lambda Normalizing and priority values for the costfunctions
* @return costs for the actual graph
* @see #costFunctionConfig
* @see #getBorderline(double)
* @see #getEdgeDistance(double)
* @see #getEdgeLength(double)
* @see #getNodeDistance(double)
* @see #getNodeDistribution(double)
*/
private double getGlobalCosts(double[] lambda){
//assert lambda.length != COUT_COSTFUNCTION;
// long startTime = System.currentTimeMillis();
double energy = 0.0;
if( (costFunctionConfig & COSTFUNCTION_NODE_DISTANCE) != 0 ){
energy += getNodeDistance(lambda[5]);
}
if( (costFunctionConfig & COSTFUNCTION_NODE_DISTRIBUTION) != 0 ){
energy += getNodeDistribution(lambda[0]);
}
if( (costFunctionConfig & COSTFUNCTION_BORDERLINE) != 0 ){
energy += getBorderline(lambda[1]);
}
if( (costFunctionConfig & COSTFUNCTION_EDGE_LENGTH) != 0 ){
energy += getEdgeLength(lambda[2]);
}
if( (costFunctionConfig & COSTFUNCTION_EDGE_CROSSING) != 0 ){
energy += getEdgeCrossing(1.0,lambda[3]);
}
if( (costFunctionConfig & COSTFUNCTION_EDGE_DISTANCE) != 0 ){
energy += getEdgeDistance(lambda[4]);
}
return energy;
}
/******************************************************************************/
/**
* Creates a permutation of the Numbers from 0 to a determined value.
* @param length Number of Numbers and maximal distance to 0 for the Numbers
* filling the permutation
* @return Permutation of the Numbers between 0 and <code>length</code>
*/
public int[] createPermutation(int length){
int[] permutation = new int[length];
for( int i = 0; i < permutation.length; i++ ){
int newValue = (int)(Math.random()*length);
for( int j = 0; j < i; j++ )
if( newValue == permutation[j] ){
newValue = (int)(Math.random()*length);
j = -1; // wird auf 0 zurÔøΩckgesetzt
}
permutation[i] = newValue;
}
return permutation;
}
/******************************************************************************/
/**
* Calculates a break condition for {@link #performRound()} if uphill moves
* are allowed. This is computed by a formular from Bolzman:<p>
* <blockquote><blockquote><code>
* random < e^(oldEnergy-newEnergy)
* </code></blockquote></blockquote>
* @param oldEnergy The Energy before the Energy has increased, so it's the
* lower one, of the two values.
* @param newEnergy The Energy after the Energy has increased, so it's the
* higher one, of the two values
* @return sometimes <code><b>true</b></code> when the random number is
* smaler than <code>e^(oldEnergy-newEnergy)</code>
*/
private boolean getBolzmanBreak(double oldEnergy, double newEnergy){
return Math.random() < Math.pow(Math.E,(oldEnergy-newEnergy)/temperature);
}
/******************************************************************************/
/**
* Calculates the maximal number of rounds, by flattening the actual
* {@link #temperature} with the temperature scaling factor
* {@link #tempScaleFactor}
*
* @param actualTemperature The Temperature of the actual Graph
* @return The number of Rounds that have to be performed until
* {@link #temperature} falls under {@link #minTemperature}.
*/
private int getMaxRoundsByTemperature(double actualTemperature){
return (int)Math.ceil( Math.log(minTemperature/actualTemperature) /
Math.log(tempScaleFactor));
}
/******************************************************************************/
/**
* Costfunction. One criterion for drawing a "nice" graph is to spread the cells
* out evenly on the drawing space. The distances between the cells need not to
* be perfectly uniform, but the graph sould be occupy a reasonable part of
* the drawing space, and, if possible, the cells shouldn't be overcrowded.
* This function calculates the sum, over all pairs of cells, of a function
* that is inverse-proportional to the distance between the cells.
*
* @param lambda A normalizing factor that defines the relativ importance of
* this criterion compared to others. Increasing lambda relative to the other
* normalizing factors causes the Algorithm to prefer pictures with smaller
* distances between cells.
* @return costs of this criterion
*/
private double getNodeDistribution(double lambda){
double energy = 0.0;
for( int i = 0 ; i < applyCellList.size(); i++ )
for( int j = 0; j < cellList.size(); j++ ){
if( applyCellList.get(i) != cellList.get(j) ){
double distance = MathExtensions.getEuclideanDistance(
getPosition((CellView)applyCellList.get(i)),
getPosition((CellView)cellList.get(j)));
//prevents from dividing with Zero
if( Math.abs(distance) < equalsNull )
distance = equalsNull;
energy += lambda/(distance*distance);
}
}
// System.out.println("NodeDistribution : "+energy);
return energy;
}
/******************************************************************************/
/**
* Costfunction. As in physics, truly minimizing the potential energy might
* result in spreading out the elements indefinitely. To avoid this, and to
* reflect the physical limitations of the output device, add this costfunction
* to the energy function to deal with the borderlines of the drawing space.
*
* @param lambda Value relative to the other lamdas pushes the cells
* towards the center, while decreasing it results in using more of the
* drawing space near the borderlines.
* @return costs of this criterion
*/
private double getBorderline(double lambda){
double energy = 0.0;
for( int i = 0; i < applyCellList.size(); i++ ){
Point2D.Double pos = getPosition((CellView)applyCellList.get(i));
double t = pos.y-bounds.y;
double l = pos.x-bounds.x;
double b = bounds.y+bounds.height-pos.y;
double r = bounds.x+bounds.width -pos.x;
energy += lambda * ( (1.0/(t*t)) + (1.0/(l*l)) + (1.0/(b*b)) + (1.0/(r*r)) );
}
// System.out.println("Borderline : "+energy);
return energy;
}
/******************************************************************************/
/**
* Costfunction. This criterion tries to shorten the edges to a necessary
* minimum without causing the entire graph to become to tightly packed.
* This function penalizes long edges.
*
* @param lambda An appropriate normalizing factor. Increasing lamda relative
* to the lambdas of other costfunctions will result in shorter Edges.
* Decreasing brings up very different length of the edges.
* @return costs of this criterion
*/
private double getEdgeLength(double lambda ){
double energy = 0.0;
Line2D.Double[] lineList = getEdgeLines(edgeList);
for( int i = 0; i < lineList.length; i++ ){
Point2D p1 = lineList[i].getP1();
Point2D p2 = lineList[i].getP2();
double edgeLength = p1.distance(p2);
energy += lambda * edgeLength * edgeLength;
}
// System.out.println("EdgeLength : "+energy);
return energy;
}
/******************************************************************************/
/**
* Costfunction. A constant penalty value is added for every two edges that
* cross.
* @param lambda Normalizing factor. Increasing lambda means attributing more
* importance to the elimination of edge crossings, and results in pictures
* with fewer crossings on average. However, this may be at the expense of other
* aesthetics.
* @return costs of this criterion.
*/
private double getEdgeCrossing(double f, double lambda){
int n = 0; // counts edgecrossings around vertex[i]
Line2D.Double[] lineList = getEdgeLines(edgeList);
for( int i = 0; i < lineList.length; i++ )
for( int j = i; j < lineList.length; j++ )
if( j != i )
if( lineList[i].intersectsLine(lineList[j]) ){
if( ((lineList[i].getP1().getX() != lineList[j].getP1().getX()) && (lineList[i].getP1().getY() != lineList[j].getP1().getY())) &&
((lineList[i].getP1().getX() != lineList[j].getP2().getX()) && (lineList[i].getP1().getY() != lineList[j].getP2().getY())) &&
((lineList[i].getP2().getX() != lineList[j].getP1().getX()) && (lineList[i].getP2().getY() != lineList[j].getP1().getY())) &&
((lineList[i].getP2().getX() != lineList[j].getP2().getX()) && (lineList[i].getP2().getY() != lineList[j].getP2().getY())) ){
n++;
}
}
// System.out.println("EdgeCrossings : "+n);
return lambda * f * n;
}
/******************************************************************************/
/**
* Costfunction. This method calculates the distance between Cells and Edges.
* A small distance brings up higher costs while great distances generates lower
* costs. Costs for the distance between Cells and Edges are always computed
* by the method. If the distance is smaller than {@link #minDistance}
* additional costs are added. This method is suggested for finetuning and other
* short running calculations. Its the slowest of all costfunctions implemented
* here.
*
* @param lambda A normalizing factor for this function. Drawings with a
* relativ increase lambda will have greater distances between nodes and
* edges, by the expense of other aesthetics.
*/
private double getEdgeDistance(double lambda){
double energy = 0.0;
for( int i = 0; i < applyCellList.size(); i++ ){
double h = 0.0;
CellView view = (CellView) applyCellList.get(i);
ArrayList relevantEdges = null;
if( view.getAttributes().containsKey(CF_KEY_EDGE_DISTANCE_RELEVANT_EDGES) ){
relevantEdges = (ArrayList) view.getAttributes().get(CF_KEY_EDGE_DISTANCE_RELEVANT_EDGES);
}
else {
relevantEdges = getRelevantEdges(view);
view.getAttributes().put(CF_KEY_EDGE_DISTANCE_RELEVANT_EDGES,relevantEdges);
}
Line2D.Double[] lineList = getEdgeLines(getRelevantEdges(view));
for( int j = 0; j < lineList.length; j++ ){
double distance = lineList[j].ptSegDist(getPosition(view));
//prevents from dividing with Zero
if( Math.abs(distance) < equalsNull )
distance = equalsNull;
if( distance != 0.0 )
h += lambda / ( distance * distance );
if( distance < minDistance )
h += lambda / ( minDistance * minDistance );
}
energy += h;
}
// System.out.println("EdgeDistance : "+energy);
return energy;
}
/******************************************************************************/
/**
* Costfunction. This is a extension to the original Algorithm. This method
* evaluates the distances between cells. When the distance is lower than
* {@link #minDistance} or the cells are overlapping the costs from this
* function increase.
*
* @param lambda Normalizing value for this function. Increasing this value
* brings up less overlapping pairs of cells, by the expense of other
* aesthetics.
* @return costs of this criterion.
*/
private double getNodeDistance(double lambda){
double energy = 0.0;
double radiusInc = 30.0;
int overlapCount = 0;
for( int i = 0; i < applyCellList.size(); i++ ){
Point2D.Double pos = (Point2D.Double)((CellView)applyCellList.get(i)).getAttributes().get(KEY_POSITION);
Rectangle2D vertex = ((CellView)applyCellList.get(i)).getBounds();
for( int j = 0; j < cellList.size(); j++ ){
if( applyCellList.get(i) != cellList.get(j) ){
Point2D.Double uPos = (Point2D.Double)((CellView)cellList.get(j)).getAttributes().get(KEY_POSITION);
Rectangle2D uVertex = ((CellView)cellList.get(j)).getBounds();
double minDist = Math.max((2.0 * radiusInc) +
(Math.max(vertex.getWidth(),vertex.getHeight())/2.0) +
(Math.max(uVertex.getWidth(),uVertex.getHeight())/2.0),
minDistance);
double distance = Math.abs(pos.distance(uPos));
//prevents from dividing with Zero
if( Math.abs(distance) < equalsNull )
distance = equalsNull;
if( distance < minDist ){
energy += lambda / (distance * distance);
overlapCount++;
}
}
}
}
return energy;
}
/******************************************************************************/
/**
* Transforms the Edges stored in a given List of edges into an array of lines.
* This is usefull, to get the Positions of the Edges.
* @param edges List containing only EdgeViews
* @return Array of Lines representing the edges of the graph.
*/
private Line2D.Double[] getEdgeLines(ArrayList edges){
Line2D.Double[] lines = new Line2D.Double[edges.size()];
for( int i = 0; i < edges.size(); i++ ){
EdgeView edge = (EdgeView) edges.get(i);
CellView source = edge.getSource().getParentView();
CellView target = edge.getTarget().getParentView();
lines[i] = new Line2D.Double(getPosition(source),
getPosition(target));
}
return lines;
}
/******************************************************************************/
/**
* Returns all Edges that are connected with cells, member of
* {@link #applyCellList}, except the edges connected the the given cell.
* @param except Edges connected to this cell are not of interest
* @return List of all interesting Edges
*/
private ArrayList getRelevantEdges(CellView except){
ArrayList relevantEdgeList = new ArrayList();
for( int i = 0; i < edgeList.size(); i++ ){
CellView view = ((EdgeView)edgeList.get(i)).getSource().getParentView();
if( view != except &&
applyCellList.contains(view) ){
relevantEdgeList.add(edgeList.get(i));
}
else {
view = ((EdgeView)edgeList.get(i)).getTarget().getParentView();
if( view != except &&
applyCellList.contains(view) ){
relevantEdgeList.add(edgeList.get(i));
}
}
}
return relevantEdgeList;
}
/******************************************************************************/
/**
* Computes a random Vector with a random direction and a given length.
*/
public Point2D.Double getRandomVector(double maxLength){
double alpha = Math.random()*Math.PI*2;
double length = Math.random()*maxLength;
return new Point2D.Double(length*Math.cos(alpha),
length*Math.sin(alpha));
}
/******************************************************************************/
/**
* Sets the position of a CellView to the given Position
*
* @param view The CellView, the position should be set
* @param pos New Position
* @see #setAttribute(CellView,String,Object)
*/
private void setPosition(CellView view, Point2D.Double pos){
setAttribute(view,KEY_POSITION,pos);
}
/******************************************************************************/
/**
* Sets the position of a CellView member of {@link #applyCellList} to the given
* position.
*
* @param index ID of the CellView in {@link #applyCellList}
* @param x X-Coordinate of the new position
* @param y Y-Coordinate of the new position
* @see #setPosition(CellView,double,double)
*/
private void setPosition(int index, double x, double y){
setPosition((CellView)applyCellList.get(index),x,y);
}
/******************************************************************************/
/**
* Sets the position of a CellView to the given Position
*
* @param view The CellView, the position should be set
* @param x X-Coordinate of the new position
* @param y Y-Coordinate of the new position
* @see #setPosition(CellView,Point2D.Double)
*/
private void setPosition(CellView view, double x, double y){
setPosition(view,new Point2D.Double(x,y));
}
/******************************************************************************/
/**
* Returns the Position of a CellView
*
* @param view CellView, the position is requested
* @return Position of the CellView
* @see #getAttribute(CellView,String)
*/
private Point2D.Double getPosition(CellView view){
return (Point2D.Double) getAttribute(view,KEY_POSITION);
}
/******************************************************************************/
/**
* Sets an attribute in a CellView
*
* @param view CellView, the attribute should be set
* @param key The attribute will be stored in the CellView under that key.
* @param obj Object representing the attribute, that should be stored.
*/
private void setAttribute(CellView view,String key, Object obj){
if( view.getAttributes() == null )
view.changeAttributes(new AttributeMap());
Map attributes = view.getAttributes();
attributes.put(key,obj);
}
/******************************************************************************/
/**
* Returns an attribute from a CellView
*
* @param view CellView, that stores the attribute
* @param key The attribute is stored in the CellView with this key
* @return Object stored with the given key in the given CellView
*/
private Object getAttribute(CellView view, String key){
return view.getAttributes().get(key);
}
/******************************************************************************/
/**
* After the calculation of the new Layout for a graph, the cells of the graph
* are positioned somewhere on the drawing space. They even might have negative
* coordinates. To prevent from this, this method is called, everytime before
* {@link #applyChanges()} is called. This method moves the whole graph to the
* upper left corner. No cell will have negative x- or y-coordinates.
*/
private void moveGraphToNW(){
Point2D.Double firstPos = getPosition((CellView)cellList.get(0));
double minX = firstPos.x;
double minY = firstPos.y;
double maxX = minX;
double maxY = minY;
for( int i = 0; i < cellList.size(); i++ ){
CellView view = (CellView) cellList.get(i);
Point2D.Double viewPos = getPosition((CellView)cellList.get(i));
Rectangle2D viewBounds = view.getAttributes().createRect(view.getBounds());
if( viewPos.getX() < minX ){
minX = viewPos.getX();
}
else if( viewPos.getX()+viewBounds.getWidth() > maxX ){
maxX = viewPos.getX()+viewBounds.getWidth();
}
if( viewPos.getY() < minY ){
minY = viewPos.getY();
}
else if( viewPos.getY()+viewBounds.getHeight() > maxY ){
maxY = viewPos.getY()+viewBounds.getHeight();
}
}
minX -= 50;
minY -= 50;
for( int i = 0; i < cellList.size(); i++ ){
CellView view = (CellView) cellList.get(i);
Point2D.Double pos = getPosition(view);
setPosition(view,new Point2D.Double(pos.x-minX,
pos.y-minY));
}
}
/******************************************************************************/
/**
* Retrieves the Cells that are directly connected to the given Cell and
* member of the given list.
* @param list Only relatives from this List are allowed
* @param view Relatives from this view are requested
* @return Relatives from view that are in the list
* @see #getRelatives(CellView)
*/
protected ArrayList getRelativesFrom(ArrayList list, CellView view){
ArrayList relatives = getRelatives(view);
ArrayList result = new ArrayList();
for( int i = 0; i < relatives.size(); i++ )
if( list.contains(relatives.get(i)) )
result.add(relatives.get(i));
return result;
}
/******************************************************************************/
/**
* Retrieves all Cells that have an edge with the given Cell.
* @param view Cell, the relatives are requested from
* @return Relatives of view
*/
protected ArrayList getRelatives(CellView view){
if( view.getAttributes().containsKey(KEY_RELATIVES) )
return (ArrayList) view.getAttributes().get(KEY_RELATIVES);
ArrayList relatives = new ArrayList();
ArrayList portsCells = new ArrayList();
VertexView vertexView = (VertexView)view;
if( isCluster(view) ){
ArrayList clusteredVertices = (ArrayList) vertexView.getAttributes().get(KEY_CLUSTERED_VERTICES);
for( int i = 0; i < clusteredVertices.size(); i++ ){
ArrayList clusterRelatives = getRelatives((CellView)clusteredVertices.get(i));
for( int j = 0; j < clusterRelatives.size(); j++ )
if( !relatives.contains(clusterRelatives.get(j)) &&
!clusteredVertices.contains(clusterRelatives.get(j)) ){
relatives.add(clusterRelatives.get(j));
}
}
}
else {
GraphModel model = jgraph.getModel();
CellMapper mapper = jgraph.getGraphLayoutCache() ;
Object vertexCell = vertexView.getCell() ;
for (int i = 0; i < model.getChildCount(vertexCell); i++){
Object portCell = model.getChild(vertexCell, i);
portsCells.add(portCell);
}
for( int i = 0; i < portsCells.size() ; i++ ){
Object portCell = portsCells.get(i);
Iterator edges = model.edges(portCell);
while (edges.hasNext() ){
Object edge = edges.next() ;
Object nextPort = null;
if( model.getSource(edge) != portCell ){
nextPort = model.getSource(edge);
}
else {
nextPort = model.getTarget(edge);
}
CellView nextVertex = mapper.getMapping(
model.getParent(nextPort), false);
relatives.add(nextVertex);
}
}
}
view.getAttributes().put(KEY_RELATIVES,relatives);
return relatives;
}
/******************************************************************************/
/**
* When Cells are inserted and a update of the layout is desired, this method
* defines the initial positions for all cells, the already layouted cells and
* the inserted. The already layouted cells get their previos calculated
* position, gained from their bounds. The inserted Cells are positioned
* recursivly. The inserted Cells, that have at least one relative in
* {@link #cellList} are placed in the barycenter of the relatives. After this,
* the inserted Cells, with a new position are added to {@link #cellList}.
* This is done, until all inserted Cells are in {@link #cellList}.
*
* @param viewList List of the inserted Cells
* @see #arrangeLayoutUpdateInsertedCellsPlacement(ArrayList)
*/
private void arrangeLayoutUpdateInsertPlacement(CellView[] viewList){
//preinitialisation - init positions for all known vertexViews
for( int i = 0; i < cellList.size(); i++ ){
CellView view = (CellView) cellList.get(i);
if( !view.getAttributes().containsKey(KEY_POSITION) ){
Point2D.Double pos = new Point2D.Double(
view.getBounds().getCenterX(),
view.getBounds().getCenterY());
view.getAttributes().put(KEY_POSITION,pos);
}
}
ArrayList placableCells = new ArrayList();
for( int i = 0; i < viewList.length; i++ )
placableCells.add(viewList[i]);
arrangeLayoutUpdateInsertedCellsPlacement(placableCells);
/*
//puts the view in the barycenter of the relatives, if there are any
for( int i = 0; i < viewList.length; i++ )
if( viewList[i] instanceof VertexView ){
ArrayList relatives = getRelativesFrom(cellList,viewList[i]);
if( relatives.size() != 0 ){
double sumX = 0.0;
double sumY = 0.0;
for( int j = 0; j < relatives.size(); j++ ){
Point2D.Double pos = (Point2D.Double)
((CellView)relatives.get(j)).
getAttributes().
get(KEY_POSITION);
sumX += pos.x;
sumY += pos.y;
}
Point2D.Double randomVector = new Point2D.Double(Math.cos(Math.random()*2.0*Math.PI)*10.0,
Math.sin(Math.random()*2.0*Math.PI)*10.0);
viewList[i].getAttributes().put(KEY_POSITION,
new Point2D.Double(
(sumX/(double)relatives.size())+randomVector.x,
(sumY/(double)relatives.size())+randomVector.y));
}
else {
viewList[i].getAttributes().put(KEY_POSITION,
new Point2D.Double(
0.0,
0.0));
}
}*/
}
/******************************************************************************/
/**
* Recursive method for finding the initial position for inserted cells. The
* inserted cells are checked, whether there is at leased one of the relatives
* in {@link #cellList}. If there is any, the cells are positioned in the
* barycenter of the relatives. If there is only one relative, this means, the
* inserted CellViews are positioned exactly on the position of the relative.
* Cells with no relative in {@link #cellList} are stored in a list. After all
* Cells are visited and checked, all positioned cells are added to
* {@link #cellList}. Then, while the list with the non positioned Cells is
* not empty, the method is called recursivly again. This is done, until all
* inserted cells are positioned or no relatives could be found for all left
* Cells (that causes that the left cells are positioned in the upper left
* corner).
*
* @param placableCells A List of CellViews, that have to be placed in the
* barycenter of their relatives
* @see #arrangeLayoutUpdateInsertPlacement(CellView[])
* @see #graphChanged(GraphModelEvent)
*/
private void arrangeLayoutUpdateInsertedCellsPlacement(ArrayList placableCells){
ArrayList notPlacedCells = new ArrayList();
for( int i = 0; i < placableCells.size(); i++ ){
CellView view = (CellView) placableCells.get(i);
if( view instanceof VertexView ){
ArrayList relatives = getRelativesFrom(cellList,view);
if( relatives.size() != 0 ){
double sumX = 0.0;
double sumY = 0.0;
for( int j = 0; j < relatives.size(); j++ ){
Point2D.Double pos = (Point2D.Double)
((CellView)relatives.get(j)).
getAttributes().
get(KEY_POSITION);
sumX += pos.x;
sumY += pos.y;
}
Point2D.Double randomVector = new Point2D.Double(Math.cos(Math.random()*2.0*Math.PI)*10.0,
Math.sin(Math.random()*2.0*Math.PI)*10.0);
view.getAttributes().put(KEY_POSITION,
new Point2D.Double(
(sumX/relatives.size())+randomVector.x,
(sumY/relatives.size())+randomVector.y));
}
else {
notPlacedCells.add(view);
}
}
}
for( int i = 0; i < placableCells.size(); i++ ){
if( placableCells.get(i) != null )
if( ((CellView) placableCells.get(i)).getAttributes() != null )
if( ((CellView) placableCells.get(i)).getAttributes().containsKey(KEY_POSITION) )
cellList.add(placableCells.get(i));
}
if( notPlacedCells.size() != placableCells.size() ){
arrangeLayoutUpdateInsertedCellsPlacement(notPlacedCells);
}
else {
for( int i = 0; i < notPlacedCells.size(); i++ ){
CellView view = (CellView) notPlacedCells.get(i);
if( !view.getAttributes().containsKey(KEY_POSITION) )
view.getAttributes().put(KEY_POSITION,
new Point2D.Double(0.0,0.0));
}
}
for( int i = 0; i < cellList.size(); i++ )
if( ((CellView)cellList.get(i)).getAttributes().get(KEY_POSITION) == null )
System.err.println("WHATCH OUT!!! NODE "+i+" == NULL");
}
/******************************************************************************/
/**
* Decides in a layout update process, what cells are member of
* {@link #applyCellList}. This depends on the gpConfiguration of the layout
* update method. First, regardless which layout update method was chosen, all
* inserted cells, gained as parameter, are added. Then, when the perimeter
* method is chosen, the cells are counted, which position is in the basic
* perimeter radius around an inserted cell. That number multiplied with the
* perimeter radius increase are added to the basic perimeter radius. Every
* Cell, that was not inserted but is positioned in that radius, is added to
* {@link #applyCellList}. After that, if perimeter method or neighbor method
* is choosen, the relatives up to {@link #luRecursionDepth} away of the
* inserted cells are added to {@link #applyCellList}.
*
* @param viewList Array of the inserted CellView's (includes EdgeView)
* @see #graphChanged(GraphModelEvent)
*/
private void getLayoutUpdateCells(CellView[] viewList){
//adds all inserted views
for( int i = 0; i < viewList.length; i++ ){
if( viewList[i] instanceof VertexView ){
if( !applyCellList.contains(viewList[i]) )
applyCellList.add(viewList[i]);
if( !cellList.contains(viewList[i]) )
cellList.add(viewList[i]);
}
else if( viewList[i] instanceof EdgeView &&
viewList[i] != null ){
if( !edgeList.contains(viewList[i]) ){
edgeList.add(viewList[i]);
System.out.println("edge added");
}
}
}
//now all vertices (old and new) are in cellList & all edges in edgeList
//adds all known cells in a perimeter
if( AnnealingLayoutSettings.KEY_LAYOUT_UPDATE_METHOD_PERIMETER.
equals(luMethod)){
//precalculation of perimeters
ArrayList perimeterList = new ArrayList();
for( int i = 0; i < applyCellList.size(); i++ ){
VertexView vertex = (VertexView) applyCellList.get(i);
Point2D.Double pos = (Point2D.Double) vertex.
getAttributes().get(KEY_POSITION);
int intersectionCount = 0;
for( int j = 0; j < applyCellList.size(); j++ ){
if( i != j ){
VertexView uVertex = (VertexView) applyCellList.get(j);
Point2D.Double uPos = (Point2D.Double) uVertex.
getAttributes().get(KEY_POSITION);
if( pos.distance(uPos) < luPerimeterRadius )
intersectionCount++;//counting inserted cells in perimeter
}
}
perimeterList.add(new Ellipse2D.Double(
pos.x - (luPerimeterRadius + (intersectionCount * luPerimeterRadiusInc)),
pos.y - (luPerimeterRadius + (intersectionCount * luPerimeterRadiusInc)),
2.0 * (luPerimeterRadius + (intersectionCount * luPerimeterRadiusInc)),
2.0 * (luPerimeterRadius + (intersectionCount * luPerimeterRadiusInc))));
}
//adding all members of cellList within a perimeter to applyCellList
for( int i = 0; i < cellList.size(); i++ ){
VertexView vertex = (VertexView) cellList.get(i);
Point2D.Double pos = (Point2D.Double) vertex.getAttributes().get(KEY_POSITION);
for( int j = 0; j < perimeterList.size(); j++ ){
Ellipse2D.Double perimeter = (Ellipse2D.Double)
perimeterList.get(j);
Point2D.Double center = new Point2D.Double(
perimeter.getCenterX(),
perimeter.getCenterY());
double radius = perimeter.getCenterX() - perimeter.getX();
if( center.distance(pos) < radius )
if( !applyCellList.contains(vertex) )
applyCellList.add(vertex);
}
}
}
if( luRecursionDepth > 0 ){
int vertexCount = 0;
for( int i = 0; i < viewList.length; i++ )
if( viewList[i] instanceof VertexView )
vertexCount++;
VertexView[] vertexList = new VertexView[vertexCount];
vertexCount = 0;
for( int i = 0; i < viewList.length; i++ )
if( viewList[i] instanceof VertexView )
vertexList[vertexCount++] = (VertexView) viewList[i];
addRelativesToList(vertexList,luRecursionDepth);
}
}
/******************************************************************************/
/**
* Recursive method, to add relatives to {@link #applyCellList}, that are
* maximal a given pathlength away of the views in the given Array.
*
* @param vertexList Array of the VertexView's, which relatives should be
* added to {@link #applyCellList}, if they are whithin a given pathlength
* away of the VertexViews
* @param depth Pathlength, relatives could be away of the VertexViews
* @see #graphChanged(GraphModelEvent)
*/
private void addRelativesToList(VertexView[] vertexList, int depth){
if( vertexList == null ) return;
if( vertexList.length == 0 ) return;
if( depth == 0 ) return;
for( int i = 0; i < vertexList.length; i++ ){
ArrayList relatives = getRelatives(vertexList[i]);
VertexView[] relativeList = new VertexView[relatives.size()];
for( int j = 0; j < relatives.size(); j++ ){
if( !applyCellList.contains(relatives.get(j)) ){
applyCellList.add(relatives.get(j));
// showCell((CellView)relatives.get(j),new Color(0,180,180));
}
if( !cellList.contains(relatives.get(j)) )
cellList.add(relatives.get(j));
relativeList[j] = (VertexView) relatives.get(j);
}
addRelativesToList(relativeList,depth-1);
}
}
/******************************************************************************/
/**
* When a event reaches this method, it will be scanned, if there are
* Cells removed or Cells inserted. When there are Cells removed from the graph,
* they have to be removed from {@link #cellList}, {@link #edgeList} and from
* {@link #applyCellList}. If there are Cells added, the layout update process
* starts. This triggers the algorithm to try to find a suitable layout for
* the inserted cells, by layouting them and some of the cells, available in
* {@link #cellList}. The algorithm tries to stimulate the cells from
* {@link #cellList} to make place for the layout of the inserted Cells.
*/
public void graphChanged(GraphModelEvent e){
if( !isRunning ){
isRunning = true;
Object[] vertexIns = e.getChange().getInserted();
Object[] vertexRem = e.getChange().getRemoved();
//Insert - Action
if( vertexIns != null && vertexRem == null ){
if( vertexIns.length == 0 ){
isRunning = false;
return;
}
CellView[] viewList = jgraph.getGraphLayoutCache().getMapping(
vertexIns,false);
if( viewList.length == 0 ){
isRunning = false;
return;
}
applyCellList.clear();
loadConfiguration(CONFIG_KEY_LAYOUT_UPDATE);
//enables a workaround if a known bug is still present
boolean bugPresent = false;
for( int i = 0; i < viewList.length; i++ )
if( viewList[i] == null ){
bugPresent = true;
break;
}
if( bugPresent )
getAllEdges();
arrangeLayoutUpdateInsertPlacement(viewList);
getLayoutUpdateCells(viewList);
if( applyCellList.size() == 0 ){
isRunning = false;
return;
}
round = 0;
if( isClusteringEnabled )
clusterGraph();
//algorithm start
init(false);
run();
//algorithm end
if( isClusteringEnabled )
declusterGraph();
applyChanges();
removeTemporaryData();
}
//Remove - Action
else if( vertexIns == null && vertexRem != null ){
isRunning = true;
CellView[] viewList = jgraph.getGraphLayoutCache().getMapping(
vertexRem,false);
for( int i = 0; i < viewList.length; i++ )
if( viewList[i] instanceof VertexView ){
if( applyCellList.contains(viewList[i]) )
applyCellList.remove(viewList[i]);
if( cellList.contains(viewList[i]) )
cellList.remove(viewList[i]);
}
else if( viewList[i] instanceof EdgeView ){
// as long as graphChanged get no inserted Edges, this lines should stay
// commented out.
// if( edgeList.contains(viewList[i]) )
// edgeList.remove(viewList[i]);
}
}
isRunning = false;
}
}
/******************************************************************************/
/**
* Workaround for a BUG. When
* {@link #graphChanged(GraphModelEvent) graphChanged(...)} is called, the
* method gets via myGraphModelEvent.getChanged().getInserted() an array of
* objects. This array consists of the key's to the views inserted into the
* graph. When this views are gained, the BUG appears. The array gained from
* the GraphLayoutCache contains only VertexView's. Instead of the EdgeViews
* there is NULL in the array. This method is callen if this BUG appears, in the
* hope, to get the inserted edges.
*/
private void getAllEdges(){
Object[] cells = jgraph.getRoots();
CellView[] views = jgraph.getGraphLayoutCache().getMapping(cells,false);
for( int i = 0; i < views.length; i++ ){
if( views[i] instanceof VertexView ){
VertexView vertexView = (VertexView) views[i];
GraphModel model = jgraph.getModel();
CellMapper mapper = jgraph.getGraphLayoutCache() ;
Object vertexCell = vertexView.getCell() ;
ArrayList portsCells = new ArrayList();
for (int j = 0; j < model.getChildCount(vertexCell); j++){
Object portCell = model.getChild(vertexCell, j);
portsCells.add(portCell);
}
for( int j = 0; j < portsCells.size(); j++ ){
Object portCell = portsCells.get(j);
Iterator edges = model.edges(portCell);
while (edges.hasNext() ){
Object edge = edges.next() ;
Object e = mapper.getMapping(edge,false);
if( !edgeList.contains(e) &&
e != null){
edgeList.add(e);
}
}
}
}
else if( views[i] instanceof EdgeView ){
if( !edgeList.contains(views[i]) &&
views[i] != null ){
edgeList.add(views[i]);
}
}
}
}
/******************************************************************************/
/******************** CLUSTERING METHODS **************************************/
/******************************************************************************/
/**
* Clusters a graph. Cells, contained in {@link #cellList} and not contained
* in {@link #applyCellList} are clustered by this short algorithm. The
* algorithm first tries to identify how many cells it should cluster. This
* is calculated by subtracting the size of {@link #applyCellList} from
* the size of {@link #cellList} and dividing the result by the
* {@link #clusteringFactor}. In the next step, the identified number of
* clusters are created, and their position is initialised by random. Then
* every clusterable cell is added to the cluster where the distance of the
* vertex and the cluster is minimal. After adding a cell, the clusters position
* is recalculated. Finishing this step, the algorithm tries to minimize the
* number of clusters, by sorting the clustered vertices, if there is another
* cluster, that distance is shorter than the distance to the cluster, the
* vertice is actually in. This can happen, because by moving vertices into the
* clusters, the position of the clusters are changed. The minimization runs
* until no vertice can be moved anymore. empty clusters are removed and finaly
* the clusters are added to {@link #applyCellList}, because they should move
* while the upcoming next calculations. That move can later be retrieved by
* subtracting the attributes {@link #KEY_POSITION} and
* {@link #KEY_CLUSTER_INIT_POSITION}.
*
* @see #declusterGraph()
*/
protected void clusterGraph(){
//initialisation
int maxClusters = Math.max((int)((cellList.size() - applyCellList.size()) / clusteringFactor ),2);
if( cellList.size() <= 1 ){
System.out.println("cellList.size() <= 1");
return;
}
ArrayList clusterList = new ArrayList();
ArrayList cellsToCluster = new ArrayList();
//identifying all cells, that are clusterable
for( int i = 0; i < cellList.size(); i++ )
if( !applyCellList.contains(cellList.get(i)) )
cellsToCluster.add(cellList.get(i));
//initialize clusters
VertexView[] clusters = new VertexView[maxClusters];
Rectangle boundingBox = getBoundingBox();
for( int i = 0; i < clusters.length; i++ ){
clusters[i] = new VertexView(null);
Map attributes = clusters[i].getAttributes();
attributes.put(KEY_IS_CLUSTER,"true");
attributes.put(KEY_POSITION,new Point2D.Double(
Math.random()*boundingBox.width,
Math.random()*boundingBox.height));
clusterList.add(clusters[i]);
}
//cluster all available cells
for( int i = 0; i < cellsToCluster.size(); i++ ){
VertexView cell = (VertexView) cellsToCluster.get(i);
Point2D.Double cellPos = getPosition(cell);
int clusterID = 0;
Point2D.Double clusterPos = getPosition((CellView)clusterList.get(0));
double minDistance = MathExtensions.getEuclideanDistance(cellPos,clusterPos);
//search for nearest cluster
for( int j = 1; j < clusterList.size(); j++ ){
clusterPos = getPosition((VertexView)clusterList.get(j));
double distance = MathExtensions.getEuclideanDistance(cellPos,clusterPos);
if( minDistance > distance ){
minDistance = distance;
clusterID = j;
}
}
VertexView cluster = (VertexView) clusterList.get(clusterID);
moveVerticeToCluster(cell,cluster);
}
//initialization done
//sorting the clustered vertices. if a vertice is nearer to a clusters
//barycenter then to it's own clusters barycenter the vertice is moved
//to that cluster. The coordinates of both clusters are recalculated.
//this is done, until nothing could be done better.
boolean couldMakeItBetter = false;
do {
couldMakeItBetter = false;
for( int i = 0; i < cellsToCluster.size(); i++ ){
VertexView cell = (VertexView) cellsToCluster.get(i);
VertexView oldCluster = (VertexView) cell.getAttributes().get(KEY_CLUSTER);
Point2D.Double cellPos = getPosition(cell);
Point2D.Double clusterPos = getPosition(oldCluster);
double distance = MathExtensions.getEuclideanDistance(cellPos,clusterPos);
for( int j = 0; j < clusterList.size(); j++ ){
VertexView cluster = (VertexView) clusterList.get(j);
if( cluster != oldCluster ){
clusterPos = getPosition(cluster);
double newDistance = MathExtensions.getEuclideanDistance(cellPos,clusterPos);
if( newDistance < distance ){
moveVerticeToCluster(cell,cluster);
couldMakeItBetter = true;
break;
}
}
}
}
}
while( couldMakeItBetter );
//empty clusters are removed
for( int i = 0; i < clusterList.size(); i++ ){
if( !((VertexView)clusterList.get(i)).getAttributes().containsKey(KEY_CLUSTERED_VERTICES)){
clusterList.remove(i--);
}
else if( ((ArrayList)((VertexView)clusterList.get(i)).getAttributes().get(KEY_CLUSTERED_VERTICES)).size() == 0 ){
clusterList.remove(i--);
}
}
//remove clustered vertices from cellList
for( int i = 0; i < cellsToCluster.size(); i++ )
cellList.remove(cellsToCluster.get(i));
//adding clusters to applyCellList and cellList
for( int i = 0; i < clusterList.size(); i++ ){
applyCellList.add(clusterList.get(i));
cellList.add(clusterList.get(i));
}
//storing a copy of position, to move vertices while declustering
for( int i = 0; i < clusterList.size(); i++ ){
VertexView cluster = (VertexView) clusterList.get(i);
Map attribs = cluster.getAttributes();
Point2D.Double clusterPos = (Point2D.Double) attribs.get(KEY_POSITION);
attribs.put(KEY_CLUSTER_INIT_POSITION,
new Point2D.Double( clusterPos.x,
clusterPos.y));
}
for( int i = 0; i < clusterList.size(); i++ ){
VertexView cluster = (VertexView)clusterList.get(i);
cluster.setCachedBounds(getBoundingBox((ArrayList)cluster.getAttributes().get(KEY_CLUSTERED_VERTICES)));
}
/* colorizeClusters(clusterList);
stop(20000);*/
}
/******************************************************************************/
/**
* Moves a vertice from the cluster, it is holded, to another cluster. This
* implies that the vertice is removed from the old cluster and added to the
* new. After this, the positions of the old and the new cluster are
* recalculated.
*
* @param vertice Vertex that should be moved
* @param cluster Cluster the vertex should be moved
*/
protected void moveVerticeToCluster(VertexView vertice, VertexView cluster){
//adding vertice to new cluster
if( !cluster.getAttributes().containsKey(KEY_CLUSTERED_VERTICES) )
cluster.getAttributes().put(KEY_CLUSTERED_VERTICES,new ArrayList());
ArrayList clusteredVertices = (ArrayList) cluster.getAttributes().get(KEY_CLUSTERED_VERTICES);
clusteredVertices.add(vertice);
//removing vertice from old cluster
if( vertice.getAttributes().containsKey(KEY_CLUSTER) ){
VertexView oldCluster = (VertexView) vertice.getAttributes().get(KEY_CLUSTER);
ArrayList list = (ArrayList)oldCluster.getAttributes().get(KEY_CLUSTERED_VERTICES);
list.remove(vertice);
computeClusterPosition(oldCluster);
}
//register cluster in vertice
vertice.getAttributes().put(KEY_CLUSTER,cluster);
//reposition cluster
computeClusterPosition(cluster);
}
/******************************************************************************/
/**
* Recalculates the position of a cluster. The position of a cluster is defined
* by the barycenter of the clustered vertices.
*
* @param cluster Cell, that has to be a cluster, should be repositioned.
*/
protected void computeClusterPosition(VertexView cluster){
ArrayList clusteredVertices = (ArrayList)cluster.getAttributes().get(KEY_CLUSTERED_VERTICES);
Point2D.Double clusterPos = computeBarycenter(clusteredVertices);
cluster.getAttributes().put(KEY_POSITION,clusterPos);
}
/******************************************************************************/
/**
* Moves all clusters from {@link #cellList} and {@link #applyCellList},
* extracts their clustered vertices and adds them to {@link #cellList}. While
* doing this, it repositions the clustered vertices with the move, the cluster
* has made during the calculation.
*
* @see #clusterGraph()
*/
protected void declusterGraph(){
if( cellList.size() <= 1 )
return;
//first collecting all clusters from applyCellList
ArrayList clusterList = new ArrayList();
for( int i = 0; i < cellList.size(); i++ ){
VertexView cell = ((VertexView)cellList.get(i));
if( isCluster(cell) )
clusterList.add(cell);
}
if( clusterList.size() == 0 )
return;
//cleaning up the cell lists
for( int i = 0; i < clusterList.size(); i++ ){
cellList.remove(clusterList.get(i));
applyCellList.remove(clusterList.get(i));
}
//repositioning and extracting vertices to cellList
for( int i = 0; i < clusterList.size(); i++ ){
VertexView cluster = (VertexView)clusterList.get(i);
Map attribs = cluster.getAttributes();
Point2D.Double newClusterPos = getPosition(cluster);
Point2D.Double oldClusterPos = (Point2D.Double) attribs.get(KEY_CLUSTER_INIT_POSITION);
//calculating move, cluster has made during his existance
Point2D.Double move = new Point2D.Double(newClusterPos.x - oldClusterPos.x,
newClusterPos.y - oldClusterPos.y);
ArrayList vertexList = (ArrayList)attribs.get(KEY_CLUSTERED_VERTICES);
//applying move to clustered vertices
for( int j = 0; j < vertexList.size(); j++ ){
VertexView cell = (VertexView) vertexList.get(j);
Point2D.Double cellPos = getPosition(cell);
Point2D.Double newCellPos = new Point2D.Double(cellPos.x + move.x,
cellPos.y + move.y);
cell.getAttributes().put(KEY_POSITION,newCellPos);
//refilling clustered vertices in cellList
cellList.add(cell);
}
}
}
/******************************************************************************/
/**
* Returns <code><b>true</b></code> when a cell is a cluster, else
* <code<b>false</b></code>. A cell is a cluster when it has under it's
* attributes a attribute with the boolean value <code><b>true</b></code> under
* the key {@link #KEY_IS_CLUSTER}.
*
* @param cell cell, that should be researched wheather it is a cluster or not.
* @return <code><b>true</b></code> if cell is a cluster, else
* <code><b>false</b></code>.
*/
protected boolean isCluster(CellView cell){
if( cell.getAttributes().containsKey(KEY_IS_CLUSTER)){
if( isTrue((String)cell.getAttributes().get(KEY_IS_CLUSTER))){
return true;
}
else {
System.err.println("FATAL ERROR: CELL CANNOT CLEARLY BE IDENTIFIED AS A CLUSTER!!!");
return false;
}
}
else return false;
}
/******************************************************************************/
/**
* Calculates the barycenter of a graph, given by a list. This calculation is
* done by summing the coordinates and dividing them with the number of
* coordinates.
*
* @param list List of CellView's
* @return Position of the barycenter
*/
private Point2D.Double computeBarycenter(ArrayList list){
double sumX = 0.0;
double sumY = 0.0;
for( int i = 0; i < list.size(); i++ ){
CellView view = (CellView) list.get(i);
Point2D.Double pos = getPosition(view);
sumX += pos.x;
sumY += pos.y;
}
return new Point2D.Double(sumX/(list.size()),
sumY/(list.size()));
}
/******************************************************************************/
/**
* Computes the bounding box of the graph in the given list of CellViews.
* The result is a Rectangle, parallel to the X- and Y-axises of the drawing
* system, closing about the graph in the given list.
*
* @param verticeList List containing the CellViews, the bounding box is of
* interest.
* @return Rectangle, that contains the whole graph, linked in the given list.
*/
private Rectangle getBoundingBox(ArrayList verticeList){
if( verticeList.size() > 0 ){
Point2D.Double vertexPos = getPosition((VertexView)verticeList.get(0));
Rectangle2D vertexSize = ((CellView)verticeList.get(0)).getBounds();
double minX = vertexPos.getX();
double minY = vertexPos.getX();
double maxX = vertexPos.getX()+vertexSize.getWidth();
double maxY = vertexPos.getX()+vertexSize.getHeight();
for( int i = 1; i < verticeList.size(); i++ ){
vertexPos = getPosition((VertexView)verticeList.get(i));
vertexSize =((CellView)verticeList.get(i)).getBounds();
if( minX > vertexPos.getX() )
minX = vertexPos.getX();
if( minY > vertexPos.getY() )
minY = vertexPos.getY();
if( maxX < vertexPos.getX()+vertexSize.getWidth() )
maxX = vertexPos.getX()+vertexSize.getWidth();
if( maxY < vertexPos.getY()+vertexSize.getHeight() )
maxY = vertexPos.getY()+vertexSize.getHeight();
}
Rectangle boundingBox = new Rectangle((int)minX,
(int)minY,
(int)(maxX-minX),
(int)(maxY-minY));
return boundingBox;
}
return null;
}
/******************************************************************************/
private Rectangle getBoundingBox(){
return getBoundingBox(cellList);
}
/******************************************************************************/
public static abstract class MathExtensions {
/**************************************************************************/
/**
* Extracts the leading sign of x.
*
* @param x Any double value.
* @return If x has a positive value <code>-1.0</code>, for <code>x = 0.0</code>
* here comes <code>0.0</code> and if x has a negative the method returns
* <code>-1.0</code>.
*/
public static double sgn(double x){
if( x < 0.0 ) {
return -1.0;
}
else if( x > 0.0 ){
return 1.0;
}
else {
return 0.0;
}
}
/**************************************************************************/
/**
* Computes the absolute value of <code>v</code>. Assuming <code>v</code>
* is a mathematical Vector, pointing from Point Zero to the Point, represented
* by <code>x</code> and <code>y</code> in v, then this method returns the
* length of v.
* <p><blockquote><blockquote><code>
* return sqrt( v.xÔøΩ + v.yÔøΩ )
* </code></blockquote></blockquote>
* @param v Point the Vector is pointing at, coming from the point
* <code>(0;0)</code>.
* @return Length of the mathematical Vector v, computed by Pytagoras's
* theorem.
*/
public static double abs(Point2D.Double v){
return Math.sqrt(getTransposed(v,v));
}
/**************************************************************************/
/**
* Computes the absolute value of a Vector, running from the
* Point <code>(0;0)</code> to the Point <code>(x;y)</code>. This is the length
* of that Vector.
* <p><blockquote><blockquote><code>
* return sqrt( v.xÔøΩ + v.yÔøΩ )
* </code></blockquote></blockquote>
* @param x Length of one Karthese. Between x and y is an Angle of 90ÔøΩ
* @param y Length of the other Karthese. Between x and y is an Angle of 90ÔøΩ
* @return Length of the Hypothenuse.
*/
public static double abs(double x, double y){
return Math.sqrt( (x*x) + (y*y) );
}
/**************************************************************************/
/**
* Calculates the angle between v1 and v2. Assuming that v1 and v2 are
* mathematical Vectors, leading from the Point <code>(0;0)</code> to
* their coordinates, the angle in <code>(0;0)</code> is calculated.
* <p><blockquote><blockquote><code>
* return arccos( ( v1.x*v2.x + v1.y*v2.y ) / ( sqrt( v1.xÔøΩ + v1.yÔøΩ ) *
* sqrt( v2.xÔøΩ + v2.yÔøΩ ) ) )
* </code></blockquote></blockquote>
* @param v1 One of two Vectors leading from <code>(0;0)</code> to
* <code>(v1.x;v1.y)</code>
* @param v2 One of two Vectors leading from <code>(0;0)</code> to
* <code>(v2.x;v2.y)</code>
* @return The Angle between the two vectors
*/
public static double angleBetween(Point2D.Double v1, Point2D.Double v2){
double xty = getTransposed(v1,v2);
double lx = Math.sqrt(getTransposed(v1,v1));
double ly = Math.sqrt(getTransposed(v2,v2));
double result = xty/(lx*ly);
if( result > 1.0 ) result = 1.0; //gleicht rundungsfehler aus
if( result < -1.0 ) result = -1.0; //gleicht rundungsfehler aus
return Math.acos(result);
}
/**************************************************************************/
/**
* Calculates the Transposed of v1 and v2. It is assumed, that v1 and v2 are
* mathematical Vectors, leading from the Point <code>(0;0)</code> to
* their coordinates.
* <p><blockquote><blockquote><code>
* return v1.x * v2.x + v1.y * v2.y
* </code></blockquote></blockquote>
* @param v1 Vector, leading from <code>(0;0)</code> to the coordinates of
* the point.
* @param v2 Vector, leading from <code>(0;0)</code> to the coordinates of
* the point.
* @return Transposed from v1 and v2.
*/
public static double getTransposed(Point2D.Double v1, Point2D.Double v2){
return v1.getX() * v2.getX() + v1.getY() * v2.getY();
}
/**************************************************************************/
/**
* Returns the euclidean Distance between two Points in a 2D cartesian
* coordinate system. The euclidean Distance is calculated in the following way:
* <p>
* <blockquote><blockquote><code>
* sqrt( (p1.x - p2.x)ÔøΩ + (p1.y - p2.y)ÔøΩ )
* </code></blockquote></blockquote>
* @param p1 First of two Points, the Distance should be calculated between.
* @param p2 Second of two Points, the Distance should be calculated between.
* @return Distance between p1 and p2, calculated in the euclidean way.
*/
public static double getEuclideanDistance(Point2D.Double p1,
Point2D.Double p2){
return Math.sqrt(((p1.x-p2.x)*(p1.x-p2.x))+((p1.y-p2.y)*(p1.y-p2.y)));
}
/**************************************************************************/
public static Point2D.Double getNormalizedVector(Point2D.Double v){
double length = abs(v);
return new Point2D.Double(v.x / length, v.y / length );
}
/**************************************************************************/
}
/**
* @return Returns the isOptimizer.
*/
public boolean isOptimizer() {
return isOptimizer;
}
/**
* @return Returns the presetConfig.
*/
public Properties getPresetConfig() {
return presetConfig;
}
/**
* @param presetConfig The presetConfig to set.
*/
public void setPresetConfig(Properties presetConfig) {
this.presetConfig = presetConfig;
loadConfiguration(CONFIG_KEY_RUN);
}
}
The table below shows all metrics for AnnealingLayoutAlgorithm.java.
| Metric | Value | Description | |
|---|---|---|---|
| BLOCKS | 193.00 | Number of blocks | |
| BLOCK_COMMENT | 61.00 | Number of block comment lines | |
| COMMENTS | 876.00 | Comment lines | |
| COMMENT_DENSITY | 1.00 | Comment density | |
| COMPARISONS | 264.00 | Number of comparison operators | |
| CYCLOMATIC | 272.00 | Cyclomatic complexity | |
| DECL_COMMENTS | 159.00 | Comments in declarations | |
| DOC_COMMENT | 742.00 | Number of javadoc comment lines | |
| ELOC | 879.00 | Effective lines of code | |
| EXEC_COMMENTS | 73.00 | Comments in executable code | |
| EXITS | 132.00 | Procedure exits | |
| FUNCTIONS | 62.00 | Number of function declarations | |
| HALSTEAD_DIFFICULTY | 145.61 | Halstead difficulty | |
| HALSTEAD_EFFORT | 0.00 | Halstead effort | |
| INTERFACE_COMPLEXITY | 169.00 | Interface complexity | |
| JAVA0001 | 0.00 | JAVA0001 Package name does not contain only lower case letters | |
| JAVA0002 | 0.00 | JAVA0002 Package name does not begin with a top level domain name or country code | |
| JAVA0003 | 0.00 | JAVA0003 Minimize use of on-demand (.*) imports | |
| JAVA0004 | 0.00 | JAVA0004 Unnecessary import from java.lang | |
| JAVA0005 | 0.00 | JAVA0005 Imports not in specified order | |
| JAVA0006 | 0.00 | JAVA0006 Empty finally block | |
| JAVA0007 | 0.00 | JAVA0007 Should not declare public field | |
| JAVA0008 | 0.00 | JAVA0008 Empty catch block | |
| JAVA0009 | 0.00 | JAVA0009 Protected member in final class | |
| JAVA0010 | 0.00 | JAVA0010 Non-instantiable class does not contain a non-private static member | |
| JAVA0011 | 1.00 | JAVA0011 Abstract class does not contain an abstract method | |
| JAVA0012 | 0.00 | JAVA0012 Non-constructor method with same name as declaring class | |
| JAVA0013 | 0.00 | JAVA0013 Non-blank final field is not static | |
| JAVA0014 | 1.00 | JAVA0014 Class with only static members has non-private constructor | |
| JAVA0015 | 0.00 | JAVA0015 Package class contains public nested type | |
| JAVA0016 | 0.00 | JAVA0016 Abstract class contains public constructor | |
| JAVA0017 | 0.00 | JAVA0017 Class name does not have required form | |
| JAVA0018 | 0.00 | JAVA0018 Method name does not have required form | |
| JAVA0019 | 0.00 | JAVA0019 Interface name does not have required form | |
| JAVA0020 | 0.00 | JAVA0020 Field name does not have required form | |
| JAVA0021 | 0.00 | JAVA0021 Interface method name does not have required form | |
| JAVA0022 | 0.00 | JAVA0022 Static final field name does not have required form | |
| JAVA0023 | 0.00 | JAVA0023 Empty finalize method | |
| JAVA0024 | 0.00 | JAVA0024 Empty class | |
| JAVA0025 | 0.00 | JAVA0025 Method override is empty | |
| JAVA0026 | 0.00 | JAVA0026 Finalize method with parameters | |
| JAVA0029 | 0.00 | JAVA0029 Private method not used | |
| JAVA0030 | 0.00 | JAVA0030 Private field not used | |
| JAVA0031 | 0.00 | JAVA0031 Case statement not properly closed | |
| JAVA0032 | 0.00 | JAVA0032 Switch statement missing default | |
| JAVA0033 | 0.00 | JAVA0033 default: not last case in switch statement | |
| JAVA0034 | 52.00 | JAVA0034 Missing braces in if statement | |
| JAVA0035 | 22.00 | JAVA0035 Missing braces in for statement | |
| JAVA0036 | 1.00 | JAVA0036 Missing braces in while statement | |
| JAVA0038 | 0.00 | JAVA0038 Non-case label in switch statement | |
| JAVA0039 | 0.00 | JAVA0039 Break statement with label | |
| JAVA0040 | 0.00 | JAVA0040 Switch statement contains N cases (maximum: M) | |
| JAVA0041 | 0.00 | JAVA0041 Nested synchronized block | |
| JAVA0042 | 0.00 | JAVA0042 Empty synchronized statement | |
| JAVA0043 | 0.00 | JAVA0043 Inner class does not use outer class | |
| JAVA0044 | 0.00 | JAVA0044 Serializable class with no instance variables | |
| JAVA0045 | 0.00 | JAVA0045 Serializable cl | |