com.jgraph.layout.organic

Class JGraphFastOrganicLayout

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.
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 doubleforceConstant
The force constant by which the attractive forces are divided and the replusive forces are multiple by the square of.
protected doubleforceConstantSquared
Cache of forceConstant^2 for performance
protected doubleinitialTemp
Start value of temperature
protected boolean[]isMoveable
Local copy of isMoveable
protected intiteration
Current iteration count
protected intmaxIterations
Total number of iterations to run the layout though
protected doubleminDistanceLimit
prevents from dividing with zero
protected doubleminDistanceLimitSquared
cached version of minDistanceLimit squared
protected int[][]neighbours
Local copy of cell neighbours
protected JGraphLayoutProgressprogress
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 doubletemperature
Temperature to limit displacement at later stages of layout
protected Object[]vertexArray
An array of all vertices to be laid out
Method Summary
voidcalcAttraction()
Calculates the attractive forces between all laid out nodes linked by edges
voidcalcPositions()
Takes the displacements calculated for each cell and applies them to the local cache of cell positions.
voidcalcRepulsion()
Calculates the repulsive forces between all laid out nodes
doublegetForceConstant()
doublegetInitialTemp()
intgetMaxIterations()
JGraphLayoutProgressgetProgress()
voidrun(JGraphFacade graph)
Executes the Fruchterman-Reingold layout using the graph description from the specified facade
voidsetForceConstant(double forceConstant)
voidsetInitialTemp(double initialTemp)
voidsetMaxIterations(int maxIterations)
StringtoString()
Returns Fast Organic, the name of this algorithm.

Field Detail

cellLocation

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

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

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

initialTemp

protected double initialTemp
Start value of temperature

isMoveable

protected boolean[] isMoveable
Local copy of isMoveable

iteration

protected int iteration
Current iteration count

maxIterations

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

minDistanceLimit

protected double minDistanceLimit
prevents from dividing with zero

minDistanceLimitSquared

protected double minDistanceLimitSquared
cached version of minDistanceLimit squared

neighbours

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

progress

protected JGraphLayoutProgress progress
An object to monitor and control progress.

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

temperature

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

vertexArray

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

Method Detail

calcAttraction

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

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.

calcRepulsion

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

getForceConstant

public double getForceConstant()

Returns: Returns the forceConstant.

getInitialTemp

public double getInitialTemp()

Returns: Returns the initialTemp.

getMaxIterations

public int getMaxIterations()

Returns: Returns the maxIterations.

getProgress

public JGraphLayoutProgress getProgress()

Returns: Returns the progress.

run

public void run(JGraphFacade graph)
Executes the Fruchterman-Reingold layout using the graph description from the specified facade

Parameters: graph the facade describing the graph to be acted upon

setForceConstant

public void setForceConstant(double forceConstant)

Parameters: forceConstant The forceConstant to set.

setInitialTemp

public void setInitialTemp(double initialTemp)

Parameters: initialTemp The initialTemp to set.

setMaxIterations

public void setMaxIterations(int maxIterations)

Parameters: maxIterations The maxIterations to set.

toString

public String toString()
Returns Fast Organic, the name of this algorithm.
Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.