Class JGraphOrganicLayout

java.lang.Object
com.jgraph.layout.organic.JGraphOrganicLayout
All Implemented Interfaces:
JGraphLayout, JGraphLayout.Stoppable
Direct Known Subclasses:
JGraphAnnealingLayout
public class JGraphOrganicLayout extends Object implements JGraphLayout, JGraphLayout.Stoppable
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.

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.

  • Field Details

    • isOptimizeEdgeDistance

      protected boolean isOptimizeEdgeDistance
      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.

    • isOptimizeEdgeCrossing

      protected boolean isOptimizeEdgeCrossing
      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.

    • isOptimizeEdgeLength

      protected boolean isOptimizeEdgeLength
      Whether or not edge lengths will be calculated as an energy cost function. This function not CPU intensive.

    • isOptimizeBorderLine

      protected boolean isOptimizeBorderLine
      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

    • isOptimizeNodeDistribution

      protected boolean isOptimizeNodeDistribution
      Whether or not node distribute will contribute an energy cost where nodes are close together. The function is moderately CPU intensive.

    • minMoveRadius

      protected double minMoveRadius
      when moveRadiusreaches this value, the algorithm is terminated

    • moveRadius

      protected double moveRadius
      The current radius around each node where the next position energy values will be calculated for a possible move

    • initialMoveRadius

      protected double initialMoveRadius
      The initial value of moveRadius. If this is set to zero the layout will automatically determine a suitable value.

    • radiusScaleFactor

      protected double radiusScaleFactor
      The factor by which the 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.

    • averageNodeArea

      protected double averageNodeArea
      The average amount of area allocated per node. If bounds is not set this value mutiplied by the number of nodes to find the total graph area. The graph is assumed square.

    • fineTuningRadius

      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. If this is set to zero, the layout will automatically determine a suitable value

    • maxIterations

      protected int maxIterations
      Limit to the number of iterations that may take place. This is only reached if one of the termination conditions does not occur first.

    • edgeDistanceCostFactor

      protected double edgeDistanceCostFactor
      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. isOptimizeEdgeDistance must be true for edge to nodes distances to be taken into account.

    • edgeCrossingCostFactor

      protected double edgeCrossingCostFactor
      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. isOptimizeEdgeCrossing must be true for edge crossings to be taken into account.

    • nodeDistributionCostFactor

      protected double nodeDistributionCostFactor
      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. isOptimizeNodeDistribution must be true for this general distribution to be applied.

    • borderLineCostFactor

      protected double borderLineCostFactor
      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. isOptimizeBorderLine must be true for border repulsion to be applied.

    • edgeLengthCostFactor

      protected double edgeLengthCostFactor
      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. isOptimizeEdgeLength must be true for edge length shortening to be applied.

    • boundsX

      protected double boundsX
      The x coordinate of the final graph

    • boundsY

      protected double boundsY
      The y coordinate of the final graph

    • boundsWidth

      protected double boundsWidth
      The width coordinate of the final graph

    • boundsHeight

      protected double boundsHeight
      The height coordinate of the final graph

    • iteration

      protected int iteration
      current iteration number of the layout

    • triesPerCell

      protected int triesPerCell
      determines, in how many segments the circle around cells is divided, to find a new position for the cell. Doubling this value double the CPU load. Increasing it beyond 16 might mean a change to the performRound method might further improve accuracy for a small performance hit. The change is described in the method comment.

    • minDistanceLimit

      protected double minDistanceLimit
      prevents from dividing with zero and from creating excessive energy values

    • minDistanceLimitSquared

      protected double minDistanceLimitSquared
      cached version of minDistanceLimit squared

    • maxDistanceLimit

      protected double maxDistanceLimit
      distance limit beyond which energy costs due to object repulsive is not calculated as it would be too insignificant

    • maxDistanceLimitSquared

      protected double maxDistanceLimitSquared
      cached version of maxDistanceLimit squared

    • unchangedEnergyRoundCount

      protected int unchangedEnergyRoundCount
      Keeps track of how many consecutive round have passed without any energy changes

    • unchangedEnergyRoundTermination

      protected int unchangedEnergyRoundTermination
      The number of round of no node moves taking placed that the layout terminates

    • isDeterministic

      protected boolean isDeterministic
      Whether or not nodes should be processed in the same order every time. If 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.

    • approxNodeDimensions

      protected boolean approxNodeDimensions
      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.

    • v

      protected JGraphOrganicLayout.CellWrapper[] v
      Internal models collection of nodes ( vertices ) to be laid out

    • e

      protected JGraphOrganicLayout.CellWrapper[] e
      Internal models collection of edges to be laid out

    • isFineTuning

      protected boolean isFineTuning
      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. 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.

    • facade

      protected JGraphFacade facade
      The facade describing the graph to be laid out

    • progress

      protected JGraphLayoutProgress progress
      The layout progress bar

  • Constructor Details

    • JGraphOrganicLayout

      public JGraphOrganicLayout()
      Constructor for JGraphOrganicLayout.

    • JGraphOrganicLayout

      public JGraphOrganicLayout(Rectangle2D bounds)
      Constructor for JGraphOrganicLayout.

  • Method Details

    • getProgress

      public JGraphLayoutProgress getProgress()
      Description copied from interface: JGraphLayout.Stoppable
      Returns the progress object that represents the progress of the current layout run. Once created, this instance should not be replaced during a layout run. For new runs you should use the reset method on the progress. Consequently, the max progress is only valid after the run method has been invoked, which means you should use a listener if you spawn a new thread.

      By convention, the layout must check the isStopped method in its inner-most loops and return immediately if the method returns true.

      Specified by:
      getProgress in interface JGraphLayout.Stoppable
      Returns:
      Returns the progress.

    • run

      public void run(JGraphFacade graph)
      Initializes and runs the layout
      Specified by:
      run in interface JGraphLayout
      Parameters:
      graph - The layout facade that the layout will use as input

    • performRound

      protected void performRound()
      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 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.

    • calcEnergyDelta

      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. The new energy is calculated from the cost function methods and the old energy values for each cost function are passed in as parameters
      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

    • createPermutation

      protected int[] createPermutation(int length)
      Creates a random permutation of the numbers from 0 to length
      Parameters:
      length - number of different numbers to be generated
      Returns:
      Permutation of the Numbers between 0 and length

    • getNodeDistribution

      protected double getNodeDistribution(int i)
      Calculates the energy cost of the specified node relative to all other nodes. Basically produces a higher energy the closer nodes are together.
      Parameters:
      i - the index of the node in the array v
      Returns:
      the total node distribution energy of the specified node

    • getBorderline

      protected double getBorderline(int i)
      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.
      Parameters:
      i - the index of the node in the array v
      Returns:
      the total border line energy of the specified node

    • getEdgeLengthAffectedEdges

      protected double getEdgeLengthAffectedEdges(int node)
      Obtains the energy cost function for the specified node being moved. This involves calling getEdgeLength for all edges connected to the specified node
      Parameters:
      node - the node whose connected edges cost functions are to be calculated
      Returns:
      the total edge length energy of the connected edges

    • getEdgeLength

      protected double getEdgeLength(int i)
      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.
      Parameters:
      i - the index of the edge in the array e
      Returns:
      the total edge length energy of the specified edge

    • getEdgeCrossingAffectedEdges

      protected double getEdgeCrossingAffectedEdges(int node)
      Obtains the energy cost function for the specified node being moved. This involves calling getEdgeCrossing for all edges connected to the specified node
      Parameters:
      node - the node whose connected edges cost functions are to be calculated
      Returns:
      the total edge crossing energy of the connected edges

    • getEdgeCrossing

      protected double getEdgeCrossing(int i)
      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
      Parameters:
      i - the index of the edge in the array e
      Returns:
      the total edge crossing energy of the specified edge

    • getEdgeDistanceFromNode

      protected double getEdgeDistanceFromNode(int i)
      This method calculates the energy of the distance between Cells and Edges. This version of the edge distance cost calculates the energy cost from a specified node. The distance cost to all unconnected edges is calculated and the total returned.
      Parameters:
      i - the index of the node in the array v
      Returns:
      the total edge distance energy of the node

    • getEdgeDistanceAffectedNodes

      protected double getEdgeDistanceAffectedNodes(int node)
      Obtains the energy cost function for the specified node being moved. This involves calling getEdgeDistanceFromEdge for all edges connected to the specified node
      Parameters:
      node - the node whose connected edges cost functions are to be calculated
      Returns:
      the total edge distance energy of the connected edges

    • getEdgeDistanceFromEdge

      protected double getEdgeDistanceFromEdge(int i)
      This method calculates the energy of the distance between Cells and Edges. This version of the edge distance cost calculates the energy cost from a specified edge. The distance cost to all unconnected nodes is calculated and the total returned.
      Parameters:
      i - the index of the edge in the array e
      Returns:
      the total edge distance energy of the edge

    • getAdditionFactorsEnergy

      protected double getAdditionFactorsEnergy(int i)
      Hook method to adding additional energy factors into the layout. Calculates the energy just for the specified node.
      Parameters:
      i - the nodes whose energy is being calculated
      Returns:
      the energy of this node caused by the additional factors

    • getRelevantEdges

      protected int[] getRelevantEdges(int cellIndex)
      Returns all Edges that are not connected to the specifed cell
      Parameters:
      cellIndex - the cell index to which the edges are not connected
      Returns:
      Array of all interesting Edges

    • getConnectedEdges

      protected int[] getConnectedEdges(int cellIndex)
      Returns all Edges that are connected with the specified cell
      Parameters:
      cellIndex - the cell index to which the edges are connected
      Returns:
      Array of all connected Edges

    • toString

      public String toString()
      Returns Annealing, the name of this algorithm.
      Overrides:
      toString in class Object

    • getAverageNodeArea

      public double getAverageNodeArea()
      Returns:
      Returns the averageNodeArea.

    • setAverageNodeArea

      public void setAverageNodeArea(double averageNodeArea)
      Parameters:
      averageNodeArea - The averageNodeArea to set.

    • getBorderLineCostFactor

      public double getBorderLineCostFactor()
      Returns:
      Returns the borderLineCostFactor.

    • setBorderLineCostFactor

      public void setBorderLineCostFactor(double borderLineCostFactor)
      Parameters:
      borderLineCostFactor - The borderLineCostFactor to set.

    • getEdgeCrossingCostFactor

      public double getEdgeCrossingCostFactor()
      Returns:
      Returns the edgeCrossingCostFactor.

    • setEdgeCrossingCostFactor

      public void setEdgeCrossingCostFactor(double edgeCrossingCostFactor)
      Parameters:
      edgeCrossingCostFactor - The edgeCrossingCostFactor to set.

    • getEdgeDistanceCostFactor

      public double getEdgeDistanceCostFactor()
      Returns:
      Returns the edgeDistanceCostFactor.

    • setEdgeDistanceCostFactor

      public void setEdgeDistanceCostFactor(double edgeDistanceCostFactor)
      Parameters:
      edgeDistanceCostFactor - The edgeDistanceCostFactor to set.

    • getEdgeLengthCostFactor

      public double getEdgeLengthCostFactor()
      Returns:
      Returns the edgeLengthCostFactor.

    • setEdgeLengthCostFactor

      public void setEdgeLengthCostFactor(double edgeLengthCostFactor)
      Parameters:
      edgeLengthCostFactor - The edgeLengthCostFactor to set.

    • getFineTuningRadius

      public double getFineTuningRadius()
      Returns:
      Returns the fineTuningRadius.

    • setFineTuningRadius

      public void setFineTuningRadius(double fineTuningRadius)
      Parameters:
      fineTuningRadius - The fineTuningRadius to set.

    • getInitialMoveRadius

      public double getInitialMoveRadius()
      Returns:
      Returns the initialMoveRadius.

    • setInitialMoveRadius

      public void setInitialMoveRadius(double initialMoveRadius)
      Parameters:
      initialMoveRadius - The initialMoveRadius to set.

    • isFineTuning

      public boolean isFineTuning()
      Returns:
      Returns the isFineTuning.

    • setFineTuning

      public void setFineTuning(boolean isFineTuning)
      Parameters:
      isFineTuning - The isFineTuning to set.

    • isOptimizeBorderLine

      public boolean isOptimizeBorderLine()
      Returns:
      Returns the isOptimizeBorderLine.

    • setOptimizeBorderLine

      public void setOptimizeBorderLine(boolean isOptimizeBorderLine)
      Parameters:
      isOptimizeBorderLine - The isOptimizeBorderLine to set.

    • isOptimizeEdgeCrossing

      public boolean isOptimizeEdgeCrossing()
      Returns:
      Returns the isOptimizeEdgeCrossing.

    • setOptimizeEdgeCrossing

      public void setOptimizeEdgeCrossing(boolean isOptimizeEdgeCrossing)
      Parameters:
      isOptimizeEdgeCrossing - The isOptimizeEdgeCrossing to set.

    • isOptimizeEdgeDistance

      public boolean isOptimizeEdgeDistance()
      Returns:
      Returns the isOptimizeEdgeDistance.

    • setOptimizeEdgeDistance

      public void setOptimizeEdgeDistance(boolean isOptimizeEdgeDistance)
      Parameters:
      isOptimizeEdgeDistance - The isOptimizeEdgeDistance to set.

    • isOptimizeEdgeLength

      public boolean isOptimizeEdgeLength()
      Returns:
      Returns the isOptimizeEdgeLength.

    • setOptimizeEdgeLength

      public void setOptimizeEdgeLength(boolean isOptimizeEdgeLength)
      Parameters:
      isOptimizeEdgeLength - The isOptimizeEdgeLength to set.

    • isOptimizeNodeDistribution

      public boolean isOptimizeNodeDistribution()
      Returns:
      Returns the isOptimizeNodeDistribution.

    • setOptimizeNodeDistribution

      public void setOptimizeNodeDistribution(boolean isOptimizeNodeDistribution)
      Parameters:
      isOptimizeNodeDistribution - The isOptimizeNodeDistribution to set.

    • getMaxIterations

      public int getMaxIterations()
      Returns:
      Returns the maxIterations.

    • setMaxIterations

      public void setMaxIterations(int maxIterations)
      Parameters:
      maxIterations - The maxIterations to set.

    • getMinDistanceLimit

      public double getMinDistanceLimit()
      Returns:
      Returns the minDistanceLimit.

    • setMinDistanceLimit

      public void setMinDistanceLimit(double minDistanceLimit)
      Parameters:
      minDistanceLimit - The minDistanceLimit to set.

    • getMinMoveRadius

      public double getMinMoveRadius()
      Returns:
      Returns the minMoveRadius.

    • setMinMoveRadius

      public void setMinMoveRadius(double minMoveRadius)
      Parameters:
      minMoveRadius - The minMoveRadius to set.

    • getNodeDistributionCostFactor

      public double getNodeDistributionCostFactor()
      Returns:
      Returns the nodeDistributionCostFactor.

    • setNodeDistributionCostFactor

      public void setNodeDistributionCostFactor(double nodeDistributionCostFactor)
      Parameters:
      nodeDistributionCostFactor - The nodeDistributionCostFactor to set.

    • getRadiusScaleFactor

      public double getRadiusScaleFactor()
      Returns:
      Returns the radiusScaleFactor.

    • setRadiusScaleFactor

      public void setRadiusScaleFactor(double radiusScaleFactor)
      Parameters:
      radiusScaleFactor - The radiusScaleFactor to set.

    • getTriesPerCell

      public int getTriesPerCell()
      Returns:
      Returns the triesPerCell.

    • setTriesPerCell

      public void setTriesPerCell(int triesPerCell)
      Parameters:
      triesPerCell - The triesPerCell to set.

    • getUnchangedEnergyRoundTermination

      public int getUnchangedEnergyRoundTermination()
      Returns:
      Returns the unchangedEnergyRoundTermination.

    • setUnchangedEnergyRoundTermination

      public void setUnchangedEnergyRoundTermination(int unchangedEnergyRoundTermination)
      Parameters:
      unchangedEnergyRoundTermination - The unchangedEnergyRoundTermination to set.

    • getMaxDistanceLimit

      public double getMaxDistanceLimit()
      Returns:
      Returns the maxDistanceLimit.

    • setMaxDistanceLimit

      public void setMaxDistanceLimit(double maxDistanceLimit)
      Parameters:
      maxDistanceLimit - The maxDistanceLimit to set.

    • isDeterministic

      public boolean isDeterministic()
      Returns:
      Returns the isDeterministic.

    • setDeterministic

      public void setDeterministic(boolean isDeterministic)
      Parameters:
      isDeterministic - The isDeterministic to set.

    • setLoggerLevel

      public void setLoggerLevel(Level level)
      Sets the logging level of this class
      Parameters:
      level - the logging level to set

    • isApproxNodeDimensions

      public boolean isApproxNodeDimensions()
      Returns:
      the approxNodeDimensions

    • setApproxNodeDimensions

      public void setApproxNodeDimensions(boolean approxNodeDimensions)
      Parameters:
      approxNodeDimensions - the approxNodeDimensions to set