JGraph
v5.13.0.0


com.jgraph.layout.organic
Class JGraphFastOrganicLayout

java.lang.Object
  extended by com.jgraph.layout.organic.JGraphFastOrganicLayout
All Implemented Interfaces:
JGraphLayout, JGraphLayout.Stoppable
Direct Known Subclasses:
JGraphFRLayout

public class JGraphFastOrganicLayout
extends Object
implements JGraphLayout, JGraphLayout.Stoppable

This layout is an implementation of "Graph Drawing by Force-Directed Placement" by Fruchterman and Reingold (1991). FR layouts are a variation on the basic Eades et al Spring Embedded layout. The paper states that "distributing vertices evenly, making edge lengths uniform, and reflecting symmetry" are its target aims. The variation from the basic embedded is that the attractive force is proportional to the square of the spring length, the natural spring length being zero and the repulsive force is linear with the distance between the nodes. FR layouts are better suited to well connected graphs.
The computational effort per iteration is quadratic, O(|N|^2+|E|). This is due to the way all nodes calculate repulsion from all others. The three user variables are forceConstant,initialTemp and maxIteration.forceConstant is the constant k in the paper and affects the radius around each node around which other nodes would be in equilibrium. initialTemp sets the start temperature of the layout, lower values limit the displacement of each node on each iteration. maxIteration sets the total number of iterations of the layout that occur.


Nested Class Summary
 
Nested classes/interfaces inherited from interface com.jgraph.layout.JGraphLayout
JGraphLayout.Stoppable
 
Field Summary
protected  double[][] cellLocation
          An array of locally stored co-ordinate positions for the vertices
protected  double[] dispX
          An array of locally stored X co-ordinate displacements for the vertices
protected  double[] dispY
          An array of locally stored Y co-ordinate displacements for the vertices
protected  double forceConstant
          The force constant by which the attractive forces are divided and the replusive forces are multiple by the square of.
protected  double forceConstantSquared
          Cache of forceConstant^2 for performance
protected  double initialTemp
          Start value of temperature
protected  boolean[] isMoveable
          Local copy of isMoveable
protected  int iteration
          Current iteration count
protected  int maxIterations
          Total number of iterations to run the layout though
protected  double minDistanceLimit
          prevents from dividing with zero
protected  double minDistanceLimitSquared
          cached version of minDistanceLimit squared
protected  int[][] neighbours
          Local copy of cell neighbours
protected  JGraphLayoutProgress progress
          An object to monitor and control progress.
protected  double[] radius
          The approximate radius of each cell, nodes only
protected  double[] radiusSquared
          The approximate radius squared of each cell, nodes only
protected  double temperature
          Temperature to limit displacement at later stages of layout
protected  Object[] vertexArray
          An array of all vertices to be laid out
 
Fields inherited from interface com.jgraph.layout.JGraphLayout
VERSION
 
Constructor Summary
JGraphFastOrganicLayout()
           
 
Method Summary
 void calcAttraction()
          Calculates the attractive forces between all laid out nodes linked by edges
 void calcPositions()
          Takes the displacements calculated for each cell and applies them to the local cache of cell positions.
 void calcRepulsion()
          Calculates the repulsive forces between all laid out nodes
 double getForceConstant()
           
 double getInitialTemp()
           
 int getMaxIterations()
           
 JGraphLayoutProgress getProgress()
          Returns the progress object that represents the progress of the current layout run.
 void run(JGraphFacade graph)
          Executes the Fruchterman-Reingold layout using the graph description from the specified facade
 void setForceConstant(double forceConstant)
           
 void setInitialTemp(double initialTemp)
           
 void setMaxIterations(int maxIterations)
           
 String toString()
          Returns Fast Organic, the name of this algorithm.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

forceConstant

protected double forceConstant
The force constant by which the attractive forces are divided and the replusive forces are multiple by the square of. The value equates to the average radius there is of free space around each node.


forceConstantSquared

protected double forceConstantSquared
Cache of forceConstant^2 for performance


temperature

protected double temperature
Temperature to limit displacement at later stages of layout


initialTemp

protected double initialTemp
Start value of temperature


iteration

protected int iteration
Current iteration count


maxIterations

protected int maxIterations
Total number of iterations to run the layout though


vertexArray

protected Object[] vertexArray
An array of all vertices to be laid out


dispX

protected double[] dispX
An array of locally stored X co-ordinate displacements for the vertices


dispY

protected double[] dispY
An array of locally stored Y co-ordinate displacements for the vertices


cellLocation

protected double[][] cellLocation
An array of locally stored co-ordinate positions for the vertices


radius

protected double[] radius
The approximate radius of each cell, nodes only


radiusSquared

protected double[] radiusSquared
The approximate radius squared of each cell, nodes only


isMoveable

protected boolean[] isMoveable
Local copy of isMoveable


neighbours

protected int[][] neighbours
Local copy of cell neighbours


progress

protected JGraphLayoutProgress progress
An object to monitor and control progress.


minDistanceLimit

protected double minDistanceLimit
prevents from dividing with zero


minDistanceLimitSquared

protected double minDistanceLimitSquared
cached version of minDistanceLimit squared

Constructor Detail

JGraphFastOrganicLayout

public JGraphFastOrganicLayout()
Method Detail

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)
Executes the Fruchterman-Reingold layout using the graph description from the specified facade

Specified by:
run in interface JGraphLayout
Parameters:
graph - the facade describing the graph to be acted upon

calcPositions

public void calcPositions()
Takes the displacements calculated for each cell and applies them to the local cache of cell positions. Limits the displacement to the current temperature.


calcAttraction

public void calcAttraction()
Calculates the attractive forces between all laid out nodes linked by edges


calcRepulsion

public void calcRepulsion()
Calculates the repulsive forces between all laid out nodes


getForceConstant

public double getForceConstant()
Returns:
Returns the forceConstant.

setForceConstant

public void setForceConstant(double forceConstant)
Parameters:
forceConstant - The forceConstant to set.

getMaxIterations

public int getMaxIterations()
Returns:
Returns the maxIterations.

setMaxIterations

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

getInitialTemp

public double getInitialTemp()
Returns:
Returns the initialTemp.

setInitialTemp

public void setInitialTemp(double initialTemp)
Parameters:
initialTemp - The initialTemp to set.

toString

public String toString()
Returns Fast Organic, the name of this algorithm.

Overrides:
toString in class Object

JGraph
v5.13.0.0


Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.