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 doubleadaption
The current adaption value
protected Rectangle2Dbounds
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 doublecoolingFactor
The rate at which the rate of the change of the graph decreases
protected doubledensityFactor
The factor by which the suggest area of the graph bound is multipled by.
protected intiteration
The current iteration of the layout
protected doublemaxAdaption
The start adaption value
protected intmaxIterationsMultiple
The multiple of the number of vertices to find the total number of iterations of this layout applied.
protected doubleminAdaption
The minimum adaption value
protected intminRadius
The lowest radius value allowed.
protected intnarrowingInterval
The number of iterations after which the radius is decremented.
protected int[][]neighbours
Local copy of cell neighbours
protected intradius
The current radius of the layout.
protected doublerandomX
The X-coordinate of the random point (termed the random vector in the paper)
protected doublerandomY
The Y-coordinate of the random point (termed the random vector in the paper)
protected Stackstack
A stack of nodes to be visited in the adjustment phase
protected intstartRadius
The radius value at on the first iteration.
protected inttotalIterations
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.
Method Summary
doublegetCoolingFactor()
doublegetDensityFactor()
doublegetMaxAdaption()
intgetMaxIterationsMultiple()
doublegetMinAdaption()
intgetMinRadius()
intgetStartRadius()
voidrun(JGraphFacade graph)
Runs the ISOM layout using the graph information specified in the facade.
voidsetCoolingFactor(double coolingFactor)
voidsetDensityFactor(double densityFactor)
voidsetMaxAdaption(double maxAdaption)
voidsetMaxIterationsMultiple(int maxIterationsMultiple)
voidsetMinAdaption(double minAdaption)
voidsetMinRadius(int minRadius)
voidsetStartRadius(int startRadius)
StringtoString()
Returns Self Organizing, the name of this algorithm.
protected voidupdateToRandomNode()
Picks a random point and detemines to the closest nodes to that point

Field Detail

adaption

protected double adaption
The current adaption value

bounds

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

cellLocation

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

coolingFactor

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

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

iteration

protected int iteration
The current iteration of the layout

maxAdaption

protected double maxAdaption
The start adaption value

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.

minAdaption

protected double minAdaption
The minimum adaption value

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.

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.

neighbours

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

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.

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)

stack

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

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.

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

vertexArray

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

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.

vertexVisited

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

Method Detail

getCoolingFactor

public double getCoolingFactor()

Returns: Returns the coolingFactor.

getDensityFactor

public double getDensityFactor()

Returns: Returns the densityFactor.

getMaxAdaption

public double getMaxAdaption()

Returns: Returns the maxAdaption.

getMaxIterationsMultiple

public int getMaxIterationsMultiple()

Returns: Returns the maxIterationsMultiple.

getMinAdaption

public double getMinAdaption()

Returns: Returns the minAdaption.

getMinRadius

public int getMinRadius()

Returns: Returns the minRadius.

getStartRadius

public int getStartRadius()

Returns: Returns the startRadius.

run

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

Parameters: graph the facade describing the input graph

setCoolingFactor

public void setCoolingFactor(double coolingFactor)

Parameters: coolingFactor The coolingFactor to set.

setDensityFactor

public void setDensityFactor(double densityFactor)

Parameters: densityFactor The densityFactor to set.

setMaxAdaption

public void setMaxAdaption(double maxAdaption)

Parameters: maxAdaption The maxAdaption to set.

setMaxIterationsMultiple

public void setMaxIterationsMultiple(int maxIterationsMultiple)

Parameters: maxIterationsMultiple The maxIterationsMultiple to set.

setMinAdaption

public void setMinAdaption(double minAdaption)

Parameters: minAdaption The minAdaption to set.

setMinRadius

public void setMinRadius(int minRadius)

Parameters: minRadius The minRadius to set.

setStartRadius

public void setStartRadius(int startRadius)

Parameters: startRadius The startRadius to set.

toString

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

updateToRandomNode

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.