com.jgraph.layout.organic
Class JGraphSelfOrganizingOrganicLayout
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
.
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. |
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.
The suggested value is determined from the number of nodes. This value is
only used if set to a value other than zero
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. Defaults to 20. If the user changes it
to any positive integer, that value is used instead.
protected double minAdaption
The minimum adaption value
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.
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.
protected int[][] neighbours
Local copy of cell neighbours
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.
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. 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.
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. If a node is not in stack
then its corresponding
value in this array will not be valid.
protected boolean[] vertexVisited
An array of which vertices have been visited during the current
iteration. Avoid the same vertex being processed twice.
public double getCoolingFactor()
Returns: Returns the coolingFactor.
public double getDensityFactor()
Returns: Returns the densityFactor.
public double getMaxAdaption()
Returns: Returns the maxAdaption.
public int getMaxIterationsMultiple()
Returns: Returns the maxIterationsMultiple.
public double getMinAdaption()
Returns: Returns the minAdaption.
public int getMinRadius()
Returns: Returns the minRadius.
public int getStartRadius()
Returns: Returns the startRadius.
Runs the ISOM layout using the graph information specified in the facade.
Parameters: graph
the facade describing the input graph
public void setCoolingFactor(double coolingFactor)
Parameters: coolingFactor
The coolingFactor to set.
public void setDensityFactor(double densityFactor)
Parameters: densityFactor
The densityFactor to set.
public void setMaxAdaption(double maxAdaption)
Parameters: maxAdaption
The maxAdaption to set.
public void setMaxIterationsMultiple(int maxIterationsMultiple)
Parameters: maxIterationsMultiple
The maxIterationsMultiple to set.
public void setMinAdaption(double minAdaption)
Parameters: minAdaption
The minAdaption to set.
public void setMinRadius(int minRadius)
Parameters: minRadius
The minRadius to set.
public void setStartRadius(int startRadius)
Parameters: startRadius
The startRadius to set.
public 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
Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.