com.jgraph.layout.organic
public class JGraphOrganicLayout extends Object implements JGraphLayout, JGraphLayout.Stoppable
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 isOptimize...
variables.
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.
The main loop of the algorithm consist of processing the nodes in a random
order. During the processing of each node a circle of radius
moveRadius
is made around the node and split into
triesPerCell
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.
The moveRadius
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 but 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.
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. fineTuningRadius
defines the radius value that, when reached, causes the edge to node
distance to be calculated.
There are other special cases that are processed after each iteration.
unchangedEnergyRoundTermination
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.
Nested Class Summary | |
---|---|
class | JGraphOrganicLayout.CellWrapper
Internal representation of a node or edge that holds cached information
to enable the layout to perform more quickly and to simplify the code |
Field Summary | |
---|---|
protected boolean | approxNodeDimensions
Whether or not to use approximate node dimensions or not. |
protected double | averageNodeArea
The average amount of area allocated per node. |
protected double | borderLineCostFactor
Cost factor applied to energy calculations for node promixity to the
notional border of the graph. |
protected double | boundsHeight
The height coordinate of the final graph |
protected double | boundsWidth
The width coordinate of the final graph |
protected double | boundsX
The x coordinate of the final graph |
protected double | boundsY
The y coordinate of the final graph |
protected JGraphOrganicLayout.CellWrapper[] | e
Internal models collection of edges to be laid out |
protected double | edgeCrossingCostFactor
Cost factor applied to energy calculations involving edges that cross
over one another. |
protected double | edgeDistanceCostFactor
Cost factor applied to energy calculations involving the distance
nodes and edges. |
protected double | edgeLengthCostFactor
Cost factor applied to energy calculations for the edge lengths.
|
protected JGraphFacade | facade
The facade describing the graph to be laid out |
protected double | fineTuningRadius
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. |
protected double | initialMoveRadius
The initial value of moveRadius . |
protected boolean | isDeterministic
Whether or not nodes should be processed in the same order every time.
|
protected boolean | isFineTuning
Whether or not fine tuning is on. |
protected boolean | isOptimizeBorderLine
Whether or not nodes will contribute an energy cost as they approach
the bound of the graph. |
protected boolean | isOptimizeEdgeCrossing
Whether or not edges crosses will be calculated as an energy cost
function. |
protected boolean | isOptimizeEdgeDistance
Whether or not the distance between edge and nodes will be calculated
as an energy cost function. |
protected boolean | isOptimizeEdgeLength
Whether or not edge lengths will be calculated as an energy cost
function. |
protected boolean | isOptimizeNodeDistribution
Whether or not node distribute will contribute an energy cost where
nodes are close together. |
protected int | iteration
current iteration number of the layout |
protected double | maxDistanceLimit
distance limit beyond which energy costs due to object repulsive is
not calculated as it would be too insignificant |
protected double | maxDistanceLimitSquared
cached version of maxDistanceLimit squared |
protected int | maxIterations
Limit to the number of iterations that may take place. |
protected double | minDistanceLimit
prevents from dividing with zero and from creating excessive energy
values |
protected double | minDistanceLimitSquared
cached version of minDistanceLimit squared |
protected double | minMoveRadius
when moveRadiusreaches this value, the algorithm is terminated |
protected double | moveRadius
The current radius around each node where the next position energy
values will be calculated for a possible move |
protected double | nodeDistributionCostFactor
Cost factor applied to energy calculations involving the general node
distribution of the graph. |
protected JGraphLayoutProgress | progress
The layout progress bar |
protected double | radiusScaleFactor
The factor by which the moveRadius is multiplied by after
every iteration. |
protected int | triesPerCell
determines, in how many segments the circle around cells is divided, to
find a new position for the cell. |
protected int | unchangedEnergyRoundCount
Keeps track of how many consecutive round have passed without any energy
changes |
protected int | unchangedEnergyRoundTermination
The number of round of no node moves taking placed that the layout
terminates |
protected JGraphOrganicLayout.CellWrapper[] | v
Internal models collection of nodes ( vertices ) to be laid out |
Constructor Summary | |
---|---|
JGraphOrganicLayout()
Constructor for JGraphOrganicLayout. | |
JGraphOrganicLayout(Rectangle2D bounds)
Constructor for JGraphOrganicLayout. |
Method Summary | |
---|---|
protected double | calcEnergyDelta(int index, double oldNodeDistribution, double oldEdgeDistance, double oldEdgeCrossing, double oldBorderLine, double oldEdgeLength, double oldAdditionalFactorsEnergy)
Calculates the change in energy for the specified node. |
protected int[] | createPermutation(int length)
Creates a random permutation of the numbers from 0 to
length
|
protected double | getAdditionFactorsEnergy(int i)
Hook method to adding additional energy factors into the layout.
|
double | getAverageNodeArea() |
protected double | getBorderline(int i)
This method calculates the energy of the distance of the specified
node to the notional border of the graph. |
double | getBorderLineCostFactor() |
protected int[] | getConnectedEdges(int cellIndex)
Returns all Edges that are connected with the specified cell
|
protected double | getEdgeCrossing(int i)
This method calculates the energy of the distance from the specified
edge crossing any other edges. |
protected double | getEdgeCrossingAffectedEdges(int node)
Obtains the energy cost function for the specified node being moved.
|
double | getEdgeCrossingCostFactor() |
protected double | getEdgeDistanceAffectedNodes(int node)
Obtains the energy cost function for the specified node being moved.
|
double | getEdgeDistanceCostFactor() |
protected double | getEdgeDistanceFromEdge(int i)
This method calculates the energy of the distance between Cells and
Edges. |
protected double | getEdgeDistanceFromNode(int i)
This method calculates the energy of the distance between Cells and
Edges. |
protected double | getEdgeLength(int i)
This method calculates the energy due to the length of the specified
edge. |
protected double | getEdgeLengthAffectedEdges(int node)
Obtains the energy cost function for the specified node being moved.
|
double | getEdgeLengthCostFactor() |
double | getFineTuningRadius() |
double | getInitialMoveRadius() |
double | getMaxDistanceLimit() |
int | getMaxIterations() |
double | getMinDistanceLimit() |
double | getMinMoveRadius() |
protected double | getNodeDistribution(int i)
Calculates the energy cost of the specified node relative to all other
nodes. |
double | getNodeDistributionCostFactor() |
JGraphLayoutProgress | getProgress() |
double | getRadiusScaleFactor() |
protected int[] | getRelevantEdges(int cellIndex)
Returns all Edges that are not connected to the specifed cell
|
int | getTriesPerCell() |
int | getUnchangedEnergyRoundTermination() |
boolean | isApproxNodeDimensions() |
boolean | isDeterministic() |
boolean | isFineTuning() |
boolean | isOptimizeBorderLine() |
boolean | isOptimizeEdgeCrossing() |
boolean | isOptimizeEdgeDistance() |
boolean | isOptimizeEdgeLength() |
boolean | isOptimizeNodeDistribution() |
protected void | performRound()
The main round of the algorithm. |
void | run(JGraphFacade graph)
Initializes and runs the layout |
void | setApproxNodeDimensions(boolean approxNodeDimensions) |
void | setAverageNodeArea(double averageNodeArea) |
void | setBorderLineCostFactor(double borderLineCostFactor) |
void | setDeterministic(boolean isDeterministic) |
void | setEdgeCrossingCostFactor(double edgeCrossingCostFactor) |
void | setEdgeDistanceCostFactor(double edgeDistanceCostFactor) |
void | setEdgeLengthCostFactor(double edgeLengthCostFactor) |
void | setFineTuning(boolean isFineTuning) |
void | setFineTuningRadius(double fineTuningRadius) |
void | setInitialMoveRadius(double initialMoveRadius) |
void | setLoggerLevel(Level level)
Sets the logging level of this class |
void | setMaxDistanceLimit(double maxDistanceLimit) |
void | setMaxIterations(int maxIterations) |
void | setMinDistanceLimit(double minDistanceLimit) |
void | setMinMoveRadius(double minMoveRadius) |
void | setNodeDistributionCostFactor(double nodeDistributionCostFactor) |
void | setOptimizeBorderLine(boolean isOptimizeBorderLine) |
void | setOptimizeEdgeCrossing(boolean isOptimizeEdgeCrossing) |
void | setOptimizeEdgeDistance(boolean isOptimizeEdgeDistance) |
void | setOptimizeEdgeLength(boolean isOptimizeEdgeLength) |
void | setOptimizeNodeDistribution(boolean isOptimizeNodeDistribution) |
void | setRadiusScaleFactor(double radiusScaleFactor) |
void | setTriesPerCell(int triesPerCell) |
void | setUnchangedEnergyRoundTermination(int unchangedEnergyRoundTermination) |
String | toString()
Returns Annealing , the name of this algorithm. |
bounds
is not set this value mutiplied by the number of nodes to find
the total graph area. The graph is assumed square.isOptimizeBorderLine
must be true for border
repulsion to be applied.isOptimizeEdgeCrossing
must be true for edge crossings
to be taken into account.isOptimizeEdgeDistance
must be true for edge to nodes
distances to be taken into account.isOptimizeEdgeLength
must be true for edge length
shortening to be applied.moveRadius
. If this is set to zero
the layout will automatically determine a suitable value.true
the outcome for a given graph will always be the
same for a constant set of conditions. Random processing of nodes might
produce a slightly better looking results, but the difference is
marginal.isFineTuning
is switched to
true
if and when the fineTuningRadius
radius is reached. Switching this variable to true
before the algorithm runs mean the node to edge cost function
is always calculated.maxDistanceLimit
squaredminDistanceLimit
squaredisOptimizeNodeDistribution
must be true for this general
distribution to be applied.moveRadius
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.performRound
method might further improve accuracy for a
small performance hit. The change is described in the method comment.Parameters: index
The index of the node in the vertices
array oldNodeDistribution
The previous node distribution energy cost of this node oldEdgeDistance
The previous edge distance energy cost of this node oldEdgeCrossing
The previous edge crossing energy cost for edges connected to
this node oldBorderLine
The previous border line energy cost for this node oldEdgeLength
The previous edge length energy cost for edges connected to
this node oldAdditionalFactorsEnergy
The previous energy cost for additional factors from
sub-classes
Returns: the delta of the new energy cost to the old energy cost
length
Parameters: length number of different numbers to be generated
Returns: Permutation of the Numbers between 0 and length
Parameters: i the nodes whose energy is being calculated
Returns: the energy of this node caused by the additional factors
Returns: Returns the averageNodeArea.
Parameters: i the index of the node in the array v
Returns: the total border line energy of the specified node
Returns: Returns the borderLineCostFactor.
Parameters: cellIndex the cell index to which the edges are connected
Returns: Array of all connected Edges
Parameters: i the index of the edge in the array e
Returns: the total edge crossing energy of the specified edge
getEdgeCrossing
for all
edges connected to the specified nodeParameters: node the node whose connected edges cost functions are to be calculated
Returns: the total edge crossing energy of the connected edges
Returns: Returns the edgeCrossingCostFactor.
getEdgeDistanceFromEdge
for all
edges connected to the specified nodeParameters: node the node whose connected edges cost functions are to be calculated
Returns: the total edge distance energy of the connected edges
Returns: Returns the edgeDistanceCostFactor.
Parameters: i the index of the edge in the array e
Returns: the total edge distance energy of the edge
Parameters: i the index of the node in the array v
Returns: the total edge distance energy of the node
Parameters: i the index of the edge in the array e
Returns: the total edge length energy of the specified edge
getEdgeLength
for all
edges connected to the specified nodeParameters: node the node whose connected edges cost functions are to be calculated
Returns: the total edge length energy of the connected edges
Returns: Returns the edgeLengthCostFactor.
Returns: Returns the fineTuningRadius.
Returns: Returns the initialMoveRadius.
Returns: Returns the maxDistanceLimit.
Returns: Returns the maxIterations.
Returns: Returns the minDistanceLimit.
Returns: Returns the minMoveRadius.
Parameters: i the index of the node in the array v
Returns: the total node distribution energy of the specified node
Returns: Returns the nodeDistributionCostFactor.
Returns: Returns the progress.
Returns: Returns the radiusScaleFactor.
Parameters: cellIndex the cell index to which the edges are not connected
Returns: Array of all interesting Edges
Returns: Returns the triesPerCell.
Returns: Returns the unchangedEnergyRoundTermination.
Returns: the approxNodeDimensions
Returns: Returns the isDeterministic.
Returns: Returns the isFineTuning.
Returns: Returns the isOptimizeBorderLine.
Returns: Returns the isOptimizeEdgeCrossing.
Returns: Returns the isOptimizeEdgeDistance.
Returns: Returns the isOptimizeEdgeLength.
Returns: Returns the isOptimizeNodeDistribution.
moveRadius
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.Parameters: approxNodeDimensions the approxNodeDimensions to set
Parameters: averageNodeArea The averageNodeArea to set.
Parameters: borderLineCostFactor The borderLineCostFactor to set.
Parameters: isDeterministic The isDeterministic to set.
Parameters: edgeCrossingCostFactor The edgeCrossingCostFactor to set.
Parameters: edgeDistanceCostFactor The edgeDistanceCostFactor to set.
Parameters: edgeLengthCostFactor The edgeLengthCostFactor to set.
Parameters: isFineTuning The isFineTuning to set.
Parameters: fineTuningRadius The fineTuningRadius to set.
Parameters: initialMoveRadius The initialMoveRadius to set.
Parameters: level the logging level to set
Parameters: maxDistanceLimit The maxDistanceLimit to set.
Parameters: maxIterations The maxIterations to set.
Parameters: minDistanceLimit The minDistanceLimit to set.
Parameters: minMoveRadius The minMoveRadius to set.
Parameters: nodeDistributionCostFactor The nodeDistributionCostFactor to set.
Parameters: isOptimizeBorderLine The isOptimizeBorderLine to set.
Parameters: isOptimizeEdgeCrossing The isOptimizeEdgeCrossing to set.
Parameters: isOptimizeEdgeDistance The isOptimizeEdgeDistance to set.
Parameters: isOptimizeEdgeLength The isOptimizeEdgeLength to set.
Parameters: isOptimizeNodeDistribution The isOptimizeNodeDistribution to set.
Parameters: radiusScaleFactor The radiusScaleFactor to set.
Parameters: triesPerCell The triesPerCell to set.
Parameters: unchangedEnergyRoundTermination The unchangedEnergyRoundTermination to set.
Annealing
, the name of this algorithm.