/**

* $Id: mxOrganicLayout.java,v 1.12 2012/12/22 22:37:52 david Exp $

* Copyright (c) 2007-2009, JGraph Ltd

*/

package com.mxgraph.layout;

import java.awt.geom.Line2D;

import java.awt.geom.Point2D;

import java.awt.geom.Rectangle2D;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashSet;

import java.util.Hashtable;

import java.util.Iterator;

import java.util.Map;

import com.mxgraph.model.mxGraphModel;

import com.mxgraph.model.mxIGraphModel;

import com.mxgraph.util.mxRectangle;

import com.mxgraph.view.mxGraph;

import com.mxgraph.view.mxGraphView;

/**

* An implementation of a simulated annealing layout, based on "Drawing Graphs

* Nicely Using Simulated Annealing" by Davidson and Harel (1996). This

* paper describes these criteria as being favourable in a graph layout: (1)

* distributing nodes evenly, (2) making edge-lengths uniform, (3)

* minimizing cross-crossings, and (4) keeping nodes from coming too close

* to edges. These criteria are translated into energy cost functions in the

* layout. Nodes or edges breaking these criteria create a larger cost function

* , the total cost they contribute related to the extent that they break it.

* The idea of the algorithm is to minimise the total system energy. Factors

* are assigned to each of the criteria describing how important that

* criteria is. Higher factors mean that those criteria are deemed to be

* relatively preferable in the final layout. Most of the criteria conflict

* with the others to some extent and so the setting of the factors determines

* the general look of the resulting graph.

* <p>

* In addition to the four aesthetic criteria the concept of a border line

* which induces an energy cost to nodes in proximity to the graph bounds is

* introduced to attempt to restrain the graph. All of the 5 factors can be

* switched on or off using the <code>isOptimize...</code> variables.

* <p>

* Simulated Annealing is a force-directed layout and is one of the more

* expensive, but generally effective layouts of this type. Layouts like

* the spring layout only really factor in edge length and inter-node

* distance being the lowest CPU intensive for the most aesthetic gain. The

* additional factors are more expensive but can have very attractive results.

* <p>

* The main loop of the algorithm consist of processing the nodes in a

* deterministic order. During the processing of each node a circle of radius

* <code>moveRadius</code> is made around the node and split into

* <code>triesPerCell</code> equal segments. Each point between neighbour

* segments is determined and the new energy of the system if the node were

* moved to that position calculated. Only the necessary nodes and edges are

* processed new energy values resulting in quadratic performance, O(VE),

* whereas calculating the total system energy would be cubic. The default

* implementation only checks 8 points around the radius of the circle, as

* opposed to the suggested 30 in the paper. Doubling the number of points

* double the CPU load and 8 works almost as well as 30.

* <p>

* The <code>moveRadius</code> replaces the temperature as the influencing

* factor in the way the graph settles in later iterations. If the user does

* not set the initial move radius it is set to half the maximum dimension

* of the graph. Thus, in 2 iterations a node may traverse the entire graph,

* and it is more sensible to find minima this way that uphill moves, which

* are little more than an expensive 'tilt' method. The factor by which

* the radius is multiplied by after each iteration is important, lowering

* it improves performance but raising it towards 1.0 can improve the

* resulting graph aesthetics. When the radius hits the minimum move radius

* defined, the layout terminates. The minimum move radius should be set

* a value where the move distance is too minor to be of interest.

* <p>

* Also, the idea of a fine tuning phase is used, as described in the paper.

* This involves only calculating the edge to node distance energy cost

* at the end of the algorithm since it is an expensive calculation and

* it really an 'optimizating' function. <code>fineTuningRadius</code>

* defines the radius value that, when reached, causes the edge to node

* distance to be calculated.

* <p>

* There are other special cases that are processed after each iteration.

* <code>unchangedEnergyRoundTermination</code> defines the number of

* iterations, after which the layout terminates. If nothing is being moved

* it is assumed a good layout has been found. In addition to this if

* no nodes are moved during an iteration the move radius is halved, presuming

* that a finer granularity is required.

*

*/

public class mxOrganicLayout extends mxGraphLayout

{

/**

* Whether or not the distance between edge and nodes will be calculated

* as an energy cost function. This function is CPU intensive and is best

* only used in the fine tuning phase.

*/

protected boolean isOptimizeEdgeDistance = true;

/**

* Whether or not edges crosses will be calculated as an energy cost

* function. This function is CPU intensive, though if some iterations

* without it are required, it is best to have a few cycles at the start

* of the algorithm using it, then use it intermittantly through the rest

* of the layout.

*/

protected boolean isOptimizeEdgeCrossing = true;

/**

* Whether or not edge lengths will be calculated as an energy cost

* function. This function not CPU intensive.

*/

protected boolean isOptimizeEdgeLength = true;

/**

* Whether or not nodes will contribute an energy cost as they approach

* the bound of the graph. The cost increases to a limit close to the

* border and stays constant outside the bounds of the graph. This function

* is not CPU intensive

*/

protected boolean isOptimizeBorderLine = true;

/**

* Whether or not node distribute will contribute an energy cost where

* nodes are close together. The function is moderately CPU intensive.

*/

protected boolean isOptimizeNodeDistribution = true;

/**

* when {@link #moveRadius}reaches this value, the algorithm is terminated

*/

protected double minMoveRadius = 2.0;

/**

* The current radius around each node where the next position energy

* values will be calculated for a possible move

*/

protected double moveRadius;

/**

* The initial value of <code>moveRadius</code>. If this is set to zero

* the layout will automatically determine a suitable value.

*/

protected double initialMoveRadius = 0.0;

/**

* The factor by which the <code>moveRadius</code> is multiplied by after

* every iteration. A value of 0.75 is a good balance between performance

* and aesthetics. Increasing the value provides more chances to find

* minimum energy positions and decreasing it causes the minimum radius

* termination condition to occur more quickly.

*/

protected double radiusScaleFactor = 0.75;

/**

* The average amount of area allocated per node. If <code> bounds</code>

* is not set this value mutiplied by the number of nodes to find

* the total graph area. The graph is assumed square.

*/

protected double averageNodeArea = 160000;

/**

* The radius below which fine tuning of the layout should start

* This involves allowing the distance between nodes and edges to be

* taken into account in the total energy calculation. If this is set to

* zero, the layout will automatically determine a suitable value

*/

protected double fineTuningRadius = 40.0;

/**

* Limit to the number of iterations that may take place. This is only

* reached if one of the termination conditions does not occur first.

*/

protected int maxIterations = 1000;

/**

* Cost factor applied to energy calculations involving the distance

* nodes and edges. Increasing this value tends to cause nodes to move away

* from edges, at the partial cost of other graph aesthetics.

* <code>isOptimizeEdgeDistance</code> must be true for edge to nodes

* distances to be taken into account.

*/

protected double edgeDistanceCostFactor = 3000;

/**

* Cost factor applied to energy calculations involving edges that cross

* over one another. Increasing this value tends to result in fewer edge

* crossings, at the partial cost of other graph aesthetics.

* <code>isOptimizeEdgeCrossing</code> must be true for edge crossings

* to be taken into account.

*/

protected double edgeCrossingCostFactor = 6000;

/**

* Cost factor applied to energy calculations involving the general node

* distribution of the graph. Increasing this value tends to result in

* a better distribution of nodes across the available space, at the

* partial cost of other graph aesthetics.

* <code>isOptimizeNodeDistribution</code> must be true for this general

* distribution to be applied.

*/

protected double nodeDistributionCostFactor = 30000;

/**

* Cost factor applied to energy calculations for node promixity to the

* notional border of the graph. Increasing this value results in

* nodes tending towards the centre of the drawing space, at the

* partial cost of other graph aesthetics.

* <code>isOptimizeBorderLine</code> must be true for border

* repulsion to be applied.

*/

protected double borderLineCostFactor = 5;

/**

* Cost factor applied to energy calculations for the edge lengths.

* Increasing this value results in the layout attempting to shorten all

* edges to the minimum edge length, at the partial cost of other graph

* aesthetics.

* <code>isOptimizeEdgeLength</code> must be true for edge length

* shortening to be applied.

*/

protected double edgeLengthCostFactor = 0.02;

/**

* The x coordinate of the final graph

*/

protected double boundsX = 0.0;

/**

* The y coordinate of the final graph

*/

protected double boundsY = 0.0;

/**

* The width coordinate of the final graph

*/

protected double boundsWidth = 0.0;

/**

* The height coordinate of the final graph

*/

protected double boundsHeight = 0.0;

/**

* current iteration number of the layout

*/

protected int iteration;

/**

* determines, in how many segments the circle around cells is divided, to

* find a new position for the cell. Doubling this value doubles the CPU

* load. Increasing it beyond 16 might mean a change to the

* <code>performRound</code> method might further improve accuracy for a

* small performance hit. The change is described in the method comment.

*/

protected int triesPerCell = 8;

/**

* prevents from dividing with zero and from creating excessive energy

* values

*/

protected double minDistanceLimit = 2;

/**

* cached version of <code>minDistanceLimit</code> squared

*/

protected double minDistanceLimitSquared;

/**

* distance limit beyond which energy costs due to object repulsive is

* not calculated as it would be too insignificant

*/

protected double maxDistanceLimit = 100;

/**

* cached version of <code>maxDistanceLimit</code> squared

*/

protected double maxDistanceLimitSquared;

/**

* Keeps track of how many consecutive round have passed without any energy

* changes

*/

protected int unchangedEnergyRoundCount;

/**

* The number of round of no node moves taking placed that the layout

* terminates

*/

protected int unchangedEnergyRoundTermination = 5;

/**

* Whether or not to use approximate node dimensions or not. Set to true

* the radius squared of the smaller dimension is used. Set to false the

* radiusSquared variable of the CellWrapper contains the width squared

* and heightSquared is used in the obvious manner.

*/

protected boolean approxNodeDimensions = true;

/**

* Internal models collection of nodes ( vertices ) to be laid out

*/

protected CellWrapper[] v;

/**

* Internal models collection of edges to be laid out

*/

protected CellWrapper[] e;

/**

* Array of the x portion of the normalised test vectors that

* are tested for a lower energy around each vertex. The vector

* of the combined x and y normals are multipled by the current

* radius to obtain test points for each vector in the array.

*/

protected double[] xNormTry;

/**

* Array of the y portion of the normalised test vectors that

* are tested for a lower energy around each vertex. The vector

* of the combined x and y normals are multipled by the current

* radius to obtain test points for each vector in the array.

*/

protected double[] yNormTry;

/**

* Whether or not fine tuning is on. The determines whether or not

* node to edge distances are calculated in the total system energy.

* This cost function , besides detecting line intersection, is a

* performance intensive component of this algorithm and best left

* to optimization phase. <code>isFineTuning</code> is switched to

* <code>true</code> if and when the <code>fineTuningRadius</code>

* radius is reached. Switching this variable to <code>true</code>

* before the algorithm runs mean the node to edge cost function

* is always calculated.

*/

protected boolean isFineTuning = true;

/**

* Specifies if the STYLE_NOEDGESTYLE flag should be set on edges that are

* modified by the result. Default is true.

*/

protected boolean disableEdgeStyle = true;

/**

* Specifies if all edge points of traversed edges should be removed.

* Default is true.

*/

protected boolean resetEdges = false;

/**

* Constructor for mxOrganicLayout.

*/

public mxOrganicLayout(mxGraph graph)

{

super(graph);

}

/**

* Constructor for mxOrganicLayout.

*/

public mxOrganicLayout(mxGraph graph, Rectangle2D bounds)

{

super(graph);

boundsX = bounds.getX();

boundsY = bounds.getY();

boundsWidth = bounds.getWidth();

boundsHeight = bounds.getHeight();

}

/**

* Returns true if the given vertex has no connected edges.

*

* @param vertex Object that represents the vertex to be tested.

* @return Returns true if the vertex should be ignored.

*/

public boolean isVertexIgnored(Object vertex)

{

return false;

}

/**

* Implements <mxGraphLayout.execute>.

*/

public void execute(Object parent)

{

mxIGraphModel model = graph.getModel();

mxGraphView view = graph.getView();

Object[] vertices = graph.getChildVertices(parent);

HashSet<Object> vertexSet = new HashSet<Object>(Arrays.asList(vertices));

HashSet<Object> validEdges = new HashSet<Object>();

// Remove edges that do not have both source and target terminals visible

for (int i = 0; i < vertices.length; i++)

{

Object[] edges = mxGraphModel.getEdges(model, vertices[i], false, true, false);

for (int j = 0; j < edges.length; j++)

{

// Only deal with sources. To be valid in the layout, each edge must be attached

// at both source and target to a vertex in the layout. Doing this avoids processing

// each edge twice.

if (view.getVisibleTerminal(edges[j], true) == vertices[i] && vertexSet.contains(view.getVisibleTerminal(edges[j], false)))

{

validEdges.add(edges[j]);

}

}

}

Object[] edges = validEdges.toArray();

// If the bounds dimensions have not been set see if the average area

// per node has been

mxRectangle totalBounds = null;

mxRectangle bounds = null;

// Form internal model of nodes

Map<Object, Integer> vertexMap = new Hashtable<Object, Integer>();

v = new CellWrapper[vertices.length];

for (int i = 0; i < vertices.length; i++)

{

v[i] = new CellWrapper(vertices[i]);

vertexMap.put(vertices[i], new Integer(i));

bounds = getVertexBounds(vertices[i]);

if (totalBounds == null)

{

totalBounds = (mxRectangle) bounds.clone();

}

else

{

totalBounds.add(bounds);

}

// Set the X,Y value of the internal version of the cell to

// the center point of the vertex for better positioning

double width = bounds.getWidth();

double height = bounds.getHeight();

v[i].x = bounds.getX() + width / 2.0;

v[i].y = bounds.getY() + height / 2.0;

if (approxNodeDimensions)

{

v[i].radiusSquared = Math.min(width, height);

v[i].radiusSquared *= v[i].radiusSquared;

}

else

{

v[i].radiusSquared = width * width;

v[i].heightSquared = height * height;

}

}

if (averageNodeArea == 0.0)

{

if (boundsWidth == 0.0 && totalBounds != null)

{

// Just use current bounds of graph

boundsX = totalBounds.getX();

boundsY = totalBounds.getY();

boundsWidth = totalBounds.getWidth();

boundsHeight = totalBounds.getHeight();

}

}

else

{

// find the center point of the current graph

// based the new graph bounds on the average node area set

double newArea = averageNodeArea * vertices.length;

double squareLength = Math.sqrt(newArea);

if (bounds != null)

{

double centreX = totalBounds.getX() + totalBounds.getWidth() / 2.0;

double centreY = totalBounds.getY() + totalBounds.getHeight() / 2.0;

boundsX = centreX - squareLength / 2.0;

boundsY = centreY - squareLength / 2.0;

}

else

{

boundsX = 0;

boundsY = 0;

}

boundsWidth = squareLength;

boundsHeight = squareLength;

// Ensure x and y are 0 or positive

if (boundsX < 0.0 || boundsY < 0.0)

{

double maxNegativeAxis = Math.min(boundsX, boundsY);

double axisOffset = -maxNegativeAxis;

boundsX += axisOffset;

boundsY += axisOffset;

}

}

// If the initial move radius has not been set find a suitable value.

// A good value is half the maximum dimension of the final graph area

if (initialMoveRadius == 0.0)

{

initialMoveRadius = Math.max(boundsWidth, boundsHeight) / 2.0;

}

moveRadius = initialMoveRadius;

minDistanceLimitSquared = minDistanceLimit * minDistanceLimit;

maxDistanceLimitSquared = maxDistanceLimit * maxDistanceLimit;

unchangedEnergyRoundCount = 0;

// Form internal model of edges

e = new CellWrapper[edges.length];

for (int i = 0; i < e.length; i++)

{

e[i] = new CellWrapper(edges[i]);

Object sourceCell = model.getTerminal(edges[i], true);

Object targetCell = model.getTerminal(edges[i], false);

Integer source = null;

Integer target = null;

// Check if either end of the edge is not connected

if (sourceCell != null)

{

source = vertexMap.get(sourceCell);

}

if (targetCell != null)

{

target = vertexMap.get(targetCell);

}

if (source != null)

{

e[i].source = source.intValue();

}

else

{

// source end is not connected

e[i].source = -1;

}

if (target != null)

{

e[i].target = target.intValue();

}

else

{

// target end is not connected

e[i].target = -1;

}

}

// Set up internal nodes with information about whether edges

// are connected to them or not

for (int i = 0; i < v.length; i++)

{

v[i].relevantEdges = getRelevantEdges(i);

v[i].connectedEdges = getConnectedEdges(i);

}

// Setup the normal vectors for the test points to move each vertex to

xNormTry = new double[triesPerCell];

yNormTry = new double[triesPerCell];

for (int i = 0; i < triesPerCell; i++)

{

double angle = i

* ((2.0 * Math.PI) / triesPerCell);

xNormTry[i] = Math.cos(angle);

yNormTry[i] = Math.sin(angle);

}

int childCount = model.getChildCount(parent);

for (int i = 0; i < childCount; i++)

{

Object cell = model.getChildAt(parent, i);

if (!isEdgeIgnored(cell))

{

if (isResetEdges())

{

graph.resetEdge(cell);

}

if (isDisableEdgeStyle())

{

setEdgeStyleEnabled(cell, false);

}

}

}

// The main layout loop

for (iteration = 0; iteration < maxIterations; iteration++)

{

performRound();

}

// Obtain the final positions

double[][] result = new double[v.length][2];

for (int i = 0; i < v.length; i++)

{

vertices[i] = v[i].cell;

bounds = getVertexBounds(vertices[i]);

result[i][0] = v[i].x - bounds.getWidth() / 2;

result[i][1] = v[i].y - bounds.getHeight() / 2;

}

model.beginUpdate();

try

{

for (int i = 0; i < vertices.length; i++)

{

setVertexLocation(vertices[i], result[i][0], result[i][1]);

}

}

finally

{

model.endUpdate();

}

}

/**

* The main round of the algorithm. Firstly, a permutation of nodes

* is created and worked through in that random order. Then, for each node

* a number of point of a circle of radius <code>moveRadius</code> are

* selected and the total energy of the system calculated if that node

* were moved to that new position. If a lower energy position is found

* this is accepted and the algorithm moves onto the next node. There

* may be a slightly lower energy value yet to be found, but forcing

* the loop to check all possible positions adds nearly the current

* processing time again, and for little benefit. Another possible

* strategy would be to take account of the fact that the energy values

* around the circle decrease for half the loop and increase for the

* other, as a general rule. If part of the decrease were seen, then

* when the energy of a node increased, the previous node position was

* almost always the lowest energy position. This adds about two loop

* iterations to the inner loop and only makes sense with 16 tries or more.

*/

protected void performRound()

{

// sequential order cells are computed (every round the same order)

// boolean to keep track of whether any moves were made in this round

boolean energyHasChanged = false;

for (int i = 0; i < v.length; i++)

{

int index = i;

// Obtain the energies for the node is its current position

// TODO The energy could be stored from the last iteration

// and used again, rather than re-calculate

double oldNodeDistribution = getNodeDistribution(index);

double oldEdgeDistance = getEdgeDistanceFromNode(index);

oldEdgeDistance += getEdgeDistanceAffectedNodes(index);

double oldEdgeCrossing = getEdgeCrossingAffectedEdges(index);

double oldBorderLine = getBorderline(index);

double oldEdgeLength = getEdgeLengthAffectedEdges(index);

double oldAdditionFactors = getAdditionFactorsEnergy(index);

for (int j = 0; j < triesPerCell; j++)

{

double movex = moveRadius * xNormTry[j];

double movey = moveRadius * yNormTry[j];

// applying new move

double oldx = v[index].x;

double oldy = v[index].y;

v[index].x = v[index].x + movex;

v[index].y = v[index].y + movey;

// calculate the energy delta from this move

double energyDelta = calcEnergyDelta(index,

oldNodeDistribution, oldEdgeDistance, oldEdgeCrossing,

oldBorderLine, oldEdgeLength, oldAdditionFactors);

if (energyDelta < 0)

{

// energy of moved node is lower, finish tries for this

// node

energyHasChanged = true;

break; // exits loop

}

else

{

// Revert node coordinates

v[index].x = oldx;

v[index].y = oldy;

}

}

}

// Check if we've hit the limit number of unchanged rounds that cause

// a termination condition

if (energyHasChanged)

{

unchangedEnergyRoundCount = 0;

}

else

{

unchangedEnergyRoundCount++;

// Half the move radius in case assuming it's set too high for

// what might be an optimisation case

moveRadius /= 2.0;

}

if (unchangedEnergyRoundCount >= unchangedEnergyRoundTermination)

{

iteration = maxIterations;

}

// decrement radius in controlled manner

double newMoveRadius = moveRadius * radiusScaleFactor;

// Don't waste time on tiny decrements, if the final pixel resolution

// is 50 then there's no point doing 55,54.1, 53.2 etc

if (moveRadius - newMoveRadius < minMoveRadius)

{

newMoveRadius = moveRadius - minMoveRadius;

}

// If the temperature reaches its minimum temperature then finish

if (newMoveRadius <= minMoveRadius)

{

iteration = maxIterations;

}

// Switch on fine tuning below the specified temperature

if (newMoveRadius < fineTuningRadius)

{

isFineTuning = true;

}

moveRadius = newMoveRadius;

}

/**

* Calculates the change in energy for the specified node. The new energy is

* calculated from the cost function methods and the old energy values for

* each cost function are passed in as parameters

*

* @param index

* The index of the node in the <code>vertices</code> array

* @param oldNodeDistribution

* The previous node distribution energy cost of this node

* @param oldEdgeDistance

* The previous edge distance energy cost of this node

* @param oldEdgeCrossing

* The previous edge crossing energy cost for edges connected to

* this node

* @param oldBorderLine

* The previous border line energy cost for this node

* @param oldEdgeLength

* The previous edge length energy cost for edges connected to

* this node

* @param oldAdditionalFactorsEnergy

* The previous energy cost for additional factors from

* sub-classes

*

* @return the delta of the new energy cost to the old energy cost

*

*/

protected double calcEnergyDelta(int index, double oldNodeDistribution,

double oldEdgeDistance, double oldEdgeCrossing,

double oldBorderLine, double oldEdgeLength,

double oldAdditionalFactorsEnergy)

{

double energyDelta = 0.0;

energyDelta += getNodeDistribution(index) * 2.0;

energyDelta -= oldNodeDistribution * 2.0;

energyDelta += getBorderline(index);

energyDelta -= oldBorderLine;

energyDelta += getEdgeDistanceFromNode(index);

energyDelta += getEdgeDistanceAffectedNodes(index);

energyDelta -= oldEdgeDistance;

energyDelta -= oldEdgeLength;

energyDelta += getEdgeLengthAffectedEdges(index);

energyDelta -= oldEdgeCrossing;

energyDelta += getEdgeCrossingAffectedEdges(index);

energyDelta -= oldAdditionalFactorsEnergy;

energyDelta += getAdditionFactorsEnergy(index);

return energyDelta;

}

/**

* Calculates the energy cost of the specified node relative to all other

* nodes. Basically produces a higher energy the closer nodes are together.

*

* @param i the index of the node in the array <code>v</code>

* @return the total node distribution energy of the specified node

*/

protected double getNodeDistribution(int i)

{

double energy = 0.0;

// This check is placed outside of the inner loop for speed, even

// though the code then has to be duplicated

if (isOptimizeNodeDistribution == true)

{

if (approxNodeDimensions)

{

for (int j = 0; j < v.length; j++)

{

if (i != j)

{

double vx = v[i].x - v[j].x;

double vy = v[i].y - v[j].y;

double distanceSquared = vx * vx + vy * vy;

distanceSquared -= v[i].radiusSquared;

distanceSquared -= v[j].radiusSquared;

// prevents from dividing with Zero.

if (distanceSquared < minDistanceLimitSquared)

{

distanceSquared = minDistanceLimitSquared;

}

energy += nodeDistributionCostFactor / distanceSquared;

}

}

}

else

{

for (int j = 0; j < v.length; j++)

{

if (i != j)

{

double vx = v[i].x - v[j].x;

double vy = v[i].y - v[j].y;

double distanceSquared = vx * vx + vy * vy;

distanceSquared -= v[i].radiusSquared;

distanceSquared -= v[j].radiusSquared;

// If the height separation indicates overlap, subtract

// the widths from the distance. Same for width overlap

// TODO if ()

// prevents from dividing with Zero.

if (distanceSquared < minDistanceLimitSquared)

{

distanceSquared = minDistanceLimitSquared;

}

energy += nodeDistributionCostFactor / distanceSquared;

}

}

}

}

return energy;

}

/**

* This method calculates the energy of the distance of the specified

* node to the notional border of the graph. The energy increases up to

* a limited maximum close to the border and stays at that maximum

* up to and over the border.

*

* @param i the index of the node in the array <code>v</code>

* @return the total border line energy of the specified node

*/

protected double getBorderline(int i)

{

double energy = 0.0;

if (isOptimizeBorderLine)

{

// Avoid very small distances and convert negative distance (i.e

// outside the border to small positive ones )

double l = v[i].x - boundsX;

if (l < minDistanceLimit)

l = minDistanceLimit;

double t = v[i].y - boundsY;

if (t < minDistanceLimit)

t = minDistanceLimit;

double r = boundsX + boundsWidth - v[i].x;

if (r < minDistanceLimit)

r = minDistanceLimit;

double b = boundsY + boundsHeight - v[i].y;

if (b < minDistanceLimit)

b = minDistanceLimit;

energy += borderLineCostFactor

* ((1000000.0 / (t * t)) + (1000000.0 / (l * l))

+ (1000000.0 / (b * b)) + (1000000.0 / (r * r)));

}

return energy;

}

/**

* Obtains the energy cost function for the specified node being moved.

* This involves calling <code>getEdgeLength</code> for all

* edges connected to the specified node

* @param node

* the node whose connected edges cost functions are to be

* calculated

* @return the total edge length energy of the connected edges

*/

protected double getEdgeLengthAffectedEdges(int node)

{

double energy = 0.0;

for (int i = 0; i < v[node].connectedEdges.length; i++)

{

energy += getEdgeLength(v[node].connectedEdges[i]);

}

return energy;

}

/**

* This method calculates the energy due to the length of the specified

* edge. The energy is proportional to the length of the edge, making

* shorter edges preferable in the layout.

*

* @param i the index of the edge in the array <code>e</code>

* @return the total edge length energy of the specified edge

*/

protected double getEdgeLength(int i)

{

if (isOptimizeEdgeLength)

{

double edgeLength = Point2D.distance(v[e[i].source].x,

v[e[i].source].y, v[e[i].target].x, v[e[i].target].y);

return (edgeLengthCostFactor * edgeLength * edgeLength);

}

else

{

return 0.0;

}

}

/**

* Obtains the energy cost function for the specified node being moved.

* This involves calling <code>getEdgeCrossing</code> for all

* edges connected to the specified node

* @param node

* the node whose connected edges cost functions are to be

* calculated

* @return the total edge crossing energy of the connected edges

*/

protected double getEdgeCrossingAffectedEdges(int node)

{

double energy = 0.0;

for (int i = 0; i < v[node].connectedEdges.length; i++)

{

energy += getEdgeCrossing(v[node].connectedEdges[i]);

}

return energy;

}

/**

* This method calculates the energy of the distance from the specified

* edge crossing any other edges. Each crossing add a constant factor

* to the total energy

*

* @param i the index of the edge in the array <code>e</code>

* @return the total edge crossing energy of the specified edge

*/

protected double getEdgeCrossing(int i)

{

// TODO Could have a cost function per edge

int n = 0; // counts energy of edgecrossings through edge i

// max and min variable for minimum bounding rectangles overlapping

// checks

double minjX, minjY, miniX, miniY, maxjX, maxjY, maxiX, maxiY;

if (isOptimizeEdgeCrossing)

{

double iP1X = v[e[i].source].x;

double iP1Y = v[e[i].source].y;

double iP2X = v[e[i].target].x;

double iP2Y = v[e[i].target].y;

for (int j = 0; j < e.length; j++)

{

double jP1X = v[e[j].source].x;

double jP1Y = v[e[j].source].y;

double jP2X = v[e[j].target].x;

double jP2Y = v[e[j].target].y;

if (j != i)

{

// First check is to see if the minimum bounding rectangles

// of the edges overlap at all. Since the layout tries

// to separate nodes and shorten edges, the majority do not

// overlap and this is a cheap way to avoid most of the

// processing

// Some long code to avoid a Math.max call...

if (iP1X < iP2X)

{

miniX = iP1X;

maxiX = iP2X;

}

else

{

miniX = iP2X;

maxiX = iP1X;

}

if (jP1X < jP2X)

{

minjX = jP1X;

maxjX = jP2X;