JGraph
v5.13.0.0


com.jgraph.layout.organic
Class JGraphSelfOrganizingOrganicLayout

java.lang.Object
  extended by com.jgraph.layout.organic.JGraphSelfOrganizingOrganicLayout
All Implemented Interfaces:
JGraphLayout
Direct Known Subclasses:
JGraphISOMLayout

public class JGraphSelfOrganizingOrganicLayout
extends Object
implements JGraphLayout

This layout is an implementation of inverted self-organising maps as described by Bernd Meyer in his 1998 paper "Self-Organizing Graphs - A Neural Network Perspective of Graph Layout". Self-organizing maps have some similarities with force-directed layouts, linked nodes tends to cluster. However, a difference with the maps is that there is a uniform space filling distrubtion of nodes. This makes the bounds within which the layout takes place important to calculate correctly at the start. The implementation assumes an average density by default. ISOM layouts are better suited to well connected graphs.
The computational effort per iteration is linear, O(|N|). This comes from the effort of finding the closest node to the random point. When JGraph implements the spatial index structure this will improve to O(log|N|). Only a selection of nodes are moved per iteration and so a greater number of iterations are required for larger graphs. Generally, the number of iterations required is proportional to the number of vertices and so the computational effort including the number of iterations will always be O(|N|). The paper describes 500 iterations as being enough for 25 nodes, thus maxIterationsMultiple, which defines the vertices to number of iterations factor, defaults to 20.
This implementation attempt to calculate sensible values for certain configuration parameters, based on the input graph. The number of iterations, the start radius used, the bounds of the end graph and the narrowing interval are calculated for the user, if the user does not set their own values. If a layout is used repeatedly, the values calculated may become less suitable as the graph changes. To make the layout re-calculate it's own suggested values, set the appropriate value to zero. The parameters that can be reset like this are: maxIterationsMultiple,startRadius and narrowingInterval.


Nested Class Summary
 
Nested classes/interfaces inherited from interface com.jgraph.layout.JGraphLayout
JGraphLayout.Stoppable
 
Field Summary
protected  double adaption
          The current adaption value
protected  Rectangle2D bounds
          The bounds of the graph prior to the layout
protected  double[][] cellLocation
          An array of locally stored X co-ordinate positions for the vertices
protected  double coolingFactor
          The rate at which the rate of the change of the graph decreases
protected  double densityFactor
          The factor by which the suggest area of the graph bound is multipled by.
protected  int iteration
          The current iteration of the layout
protected  double maxAdaption
          The start adaption value
protected  int maxIterationsMultiple
          The multiple of the number of vertices to find the total number of iterations of this layout applied.
protected  double minAdaption
          The minimum adaption value
protected  int minRadius
          The lowest radius value allowed.
protected  int narrowingInterval
          The number of iterations after which the radius is decremented.
protected  int[][] neighbours
          Local copy of cell neighbours
protected  int radius
          The current radius of the layout.
protected  double randomX
          The X-coordinate of the random point (termed the random vector in the paper)
protected  double randomY
          The Y-coordinate of the random point (termed the random vector in the paper)
protected  Stack stack
          A stack of nodes to be visited in the adjustment phase
protected  int startRadius
          The radius value at on the first iteration.
protected  int totalIterations
          The layout sets this variable to the number of vertices multipled by maxIterationsMultiple since the number of iterations required in linear with the number of nodes
protected  Object[] vertexArray
          An array of all vertices to be laid out
protected  int[] vertexDistance
          An array of the number of edges any particular node is from the winning node.
protected  boolean[] vertexVisited
          An array of which vertices have been visited during the current iteration.
 
Fields inherited from interface com.jgraph.layout.JGraphLayout
VERSION
 
Constructor Summary
JGraphSelfOrganizingOrganicLayout()
           
 
Method Summary
 double getCoolingFactor()
           
 double getDensityFactor()
           
 double getMaxAdaption()
           
 int getMaxIterationsMultiple()
           
 double getMinAdaption()
           
 int getMinRadius()
           
 int getStartRadius()
           
 void run(JGraphFacade graph)
          Runs the ISOM layout using the graph information specified in the facade.
 void setCoolingFactor(double coolingFactor)
           
 void setDensityFactor(double densityFactor)
           
 void setMaxAdaption(double maxAdaption)
           
 void setMaxIterationsMultiple(int maxIterationsMultiple)
           
 void setMinAdaption(double minAdaption)
           
 void setMinRadius(int minRadius)
           
 void setStartRadius(int startRadius)
           
 String toString()
          Returns Self Organizing, the name of this algorithm.
protected  void updateToRandomNode()
          Picks a random point and detemines to the closest nodes to that point
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

bounds

protected Rectangle2D bounds
The bounds of the graph prior to the layout


totalIterations

protected int totalIterations
The layout sets this variable to the number of vertices multipled by maxIterationsMultiple since the number of iterations required in linear with the number of nodes


maxIterationsMultiple

protected int maxIterationsMultiple
The multiple of the number of vertices to find the total number of iterations of this layout applied. Defaults to 20. If the user changes it to any positive integer, that value is used instead.


iteration

protected int iteration
The current iteration of the layout


radius

protected int radius
The current radius of the layout. The radius actually means the number of times neighbours are found from the winning node. For example, if the radius is 2, all of the neighbours of winning node are processed for moving, as well as all the meighbours of those first neighbours. No node is processed twice. The idea of the later stages of the layout is for only linked cells to be drawn into clusters, as the radius reduces down to minRadius as the layout progresses.


startRadius

protected int startRadius
The radius value at on the first iteration. The radius should reflect both the number of vertices and the ratio of vertices to edges. Larger numbers of vertices requires a larger radius ( the relationship is roughly logarithmic ) and higher edge-to-vertex ratio should require a lower radius. The value defaults to 3, unless the user sets it to any positive integer.


minRadius

protected int minRadius
The lowest radius value allowed. A value of 1 is generally recommended. Only use a value of 0 if the adaption is under 0.15 at this point in the layout process, otherwise the symmetry of the layout may be destroyed.


densityFactor

protected double densityFactor
The factor by which the suggest area of the graph bound is multipled by. The suggested value is determined from the number of nodes. This value is only used if set to a value other than zero


narrowingInterval

protected int narrowingInterval
The number of iterations after which the radius is decremented. This value should reflect the total number of iterations, the start radius and minimum radius so that some part of the layout is spent at the minimum radius.


adaption

protected double adaption
The current adaption value


maxAdaption

protected double maxAdaption
The start adaption value


minAdaption

protected double minAdaption
The minimum adaption value


coolingFactor

protected double coolingFactor
The rate at which the rate of the change of the graph decreases


stack

protected Stack stack
A stack of nodes to be visited in the adjustment phase


neighbours

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


vertexArray

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


vertexVisited

protected boolean[] vertexVisited
An array of which vertices have been visited during the current iteration. Avoid the same vertex being processed twice.


vertexDistance

protected int[] vertexDistance
An array of the number of edges any particular node is from the winning node. If a node is not in stack then its corresponding value in this array will not be valid.


cellLocation

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


randomX

protected double randomX
The X-coordinate of the random point (termed the random vector in the paper)


randomY

protected double randomY
The Y-coordinate of the random point (termed the random vector in the paper)

Constructor Detail

JGraphSelfOrganizingOrganicLayout

public JGraphSelfOrganizingOrganicLayout()
Method Detail

run

public void run(JGraphFacade graph)
Runs the ISOM layout using the graph information specified in the facade.

Specified by:
run in interface JGraphLayout
Parameters:
graph - the facade describing the input graph

updateToRandomNode

protected void updateToRandomNode()
Picks a random point and detemines to the closest nodes to that point


getCoolingFactor

public double getCoolingFactor()
Returns:
Returns the coolingFactor.

setCoolingFactor

public void setCoolingFactor(double coolingFactor)
Parameters:
coolingFactor - The coolingFactor to set.

getMaxIterationsMultiple

public int getMaxIterationsMultiple()
Returns:
Returns the maxIterationsMultiple.

setMaxIterationsMultiple

public void setMaxIterationsMultiple(int maxIterationsMultiple)
Parameters:
maxIterationsMultiple - The maxIterationsMultiple to set.

getMinAdaption

public double getMinAdaption()
Returns:
Returns the minAdaption.

setMinAdaption

public void setMinAdaption(double minAdaption)
Parameters:
minAdaption - The minAdaption to set.

getStartRadius

public int getStartRadius()
Returns:
Returns the startRadius.

setStartRadius

public void setStartRadius(int startRadius)
Parameters:
startRadius - The startRadius to set.

getMaxAdaption

public double getMaxAdaption()
Returns:
Returns the maxAdaption.

setMaxAdaption

public void setMaxAdaption(double maxAdaption)
Parameters:
maxAdaption - The maxAdaption to set.

getMinRadius

public int getMinRadius()
Returns:
Returns the minRadius.

setMinRadius

public void setMinRadius(int minRadius)
Parameters:
minRadius - The minRadius to set.

getDensityFactor

public double getDensityFactor()
Returns:
Returns the densityFactor.

setDensityFactor

public void setDensityFactor(double densityFactor)
Parameters:
densityFactor - The densityFactor to set.

toString

public String toString()
Returns Self Organizing, the name of this algorithm.

Overrides:
toString in class Object

JGraph
v5.13.0.0


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