Class JGraphSelfOrganizingOrganicLayout

java.lang.Object
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.

  • Field Details

    • 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 Details

    • JGraphSelfOrganizingOrganicLayout

      public JGraphSelfOrganizingOrganicLayout()

  • Method Details

    • 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