org.jgraph.layout
Class GEMLayoutAlgorithm

java.lang.Object
  extended byorg.jgraph.layout.JGraphLayoutAlgorithm
      extended byorg.jgraph.layout.GEMLayoutAlgorithm

public class GEMLayoutAlgorithm
extends JGraphLayoutAlgorithm

GEM Layout Algorithm

Based on the work of Arne Frick, Andreas Ludwig, Heiko Mehldau: "A Fast Adaptive Layout Algorithm for Undirected Graphs"; Extended Abstract and System Demonstration; Faculty of Informatik of the University Karlsruhe; 1994

This Algorithm works by giving every cell a position and a temperature. Then for every cell forces are computed. Every other cell repulses the actual calculated cell away. On the other hand, cells, connected by edges are attracted, until a minimum distance is reached. The result of this forces is a move of the position of the actual cell in the direction of the force and with the length of the temperature. Then the temperature will be decreased, if the last impulse and the current impulse looks like a rotation or a oscillation. this is done for every cell until the temperature of all cells or the average of the temperature of every cell is until a given minimum value or a maximum of rounds is reached.


Field Summary
protected  double alphaOsc
          opening angle in radiant, that detects oscillations
protected  double alphaRot
          opening angle in radiant, that detects rotations
protected  java.util.Properties config
          the configuration of this algorithm
protected  double gravitation
          the strength of the gravitation force, directed to the barycenter of the graph, added to all cells.
protected  double initTemperature
          starting value for the temperatures of the cells
static java.lang.String KEY_CAPTION
          Key used on every cell.
static java.lang.String KEY_CLUSTER
          Key used only with clusters.
static java.lang.String KEY_CLUSTER_INIT_POSITION
          Key used only with clusters.
static java.lang.String KEY_CLUSTERED_VERTICES
          Key used only with clusters.
static java.lang.String KEY_CURRENT_IMPULSE
          Key used on every cell.
static java.lang.String KEY_IS_CLUSTER
          Key used only with clusters.
static java.lang.String KEY_LAST_IMPULSE
          Key used on every cell.
static java.lang.String KEY_MASSINDEX
          Key used on every Cell.
static java.lang.String KEY_POSITION
          Key used on every cell.
static java.lang.String KEY_RELATIVES
          Key used on every Cell.
static java.lang.String KEY_SKEWGAUGE
          Key used on every cell.
static java.lang.String KEY_TEMPERATURE
          Key used on every cell.
protected  double maxTemperature
          temperature will never be over this value
protected  double minTemperature
          if the temperature of all cells or the average of the temperatures of all cells is below this value, the algorithm stops
protected  double prefEdgeLength
          the length of the Edges in Pixel, the algorithm tries to keep
protected  double randomImpulseRange
          length of a force vector with a random direction, added to all cells.
protected  double sigmaOsc
          penalty value for a detected oscillation
protected  double sigmaRot
          penalty value for a detected rotation
protected static int VALUES_INC
          to identify for the method loadRuntimeValues(int), that the algorithm wants to perform a layout update
protected static int VALUES_PUR
          to identify for the method loadRuntimeValues(int), that the algorithm wants to perform a new run
 
Fields inherited from class org.jgraph.layout.JGraphLayoutAlgorithm
LAYOUT_ATTRIBUTES
 
Constructor Summary
GEMLayoutAlgorithm(AnnealingLayoutAlgorithm optimizer)
          Constructs a new GEM Layout Algorithm.
 
Method Summary
 void addApplyableVertices(VertexView[] vertexList)
          Method for the process of layout update.
protected  void clusterGraph()
          Clusters a graph.
protected  void computeClusterPosition(VertexView cluster)
          Recalculates the position of a cluster.
 JGraphLayoutSettings createSettings()
          Returns an new instance of SugiyamaLayoutSettings
protected  void declusterGraph()
          Moves all clusters from #cellList and #applyCellList, extracts their clustered vertices and adds them to #cellList.
protected  java.util.ArrayList getAdditionalForces(VertexView view)
          Method for Classes that extend this Algorithm.
 java.util.Properties getConfig()
           
 java.lang.String getHint()
          Get a human readable hint for using this layout.
 AnnealingLayoutAlgorithm getOptimizationAlgorithm()
           
 void graphChanged(GraphModelEvent e)
          Will be called, when cells are inserted or removed.
protected  boolean isCluster(CellView cell)
          Returns true when a cell is a cluster, else false.
protected  boolean isTrue(java.lang.String boolValue)
          Helping method.
protected  void loadRuntimeValues(int valueID)
          Loads the actual desired values from the configuration to the fields, where they are used later.
protected  void moveVerticeToCluster(VertexView vertice, VertexView cluster)
          Moves a vertice from the cluster, it is holded, to another cluster.
 void run(JGraph graph, java.lang.Object[] dynamic_cells, java.lang.Object[] static_cells)
          Starts the Calculation of a new layout with the GEM-Algorithm
 void setConfig(java.util.Properties configuration)
           
 java.lang.String toString()
          Returns the name of this algorithm in human readable form.
 
Methods inherited from class org.jgraph.layout.JGraphLayoutAlgorithm
applyLayout, applyLayout, createDialog, createDialog, getMaximumProgress, getProgress, isAllowedToRun, populateDialog, run, setAllowedToRun, setMaximumProgress, setProgress
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

KEY_CAPTION

public static final java.lang.String KEY_CAPTION
Key used on every cell. This key indicates that in the cell are attributes stored by this algorithm. The algorithm itself never asks for this key. This is for others developers only, using this algorithm, to find out, where sometimes approaching attributes come from.

See Also:
Constant Field Values

KEY_TEMPERATURE

public static final java.lang.String KEY_TEMPERATURE
Key used on every cell. Under this key every cell stores temporary the temperature of itself. Temperature is a indicator how far a cell can move and all temperatures together indicating how long the algorithm will run.

See Also:
Constant Field Values

KEY_CURRENT_IMPULSE

public static final java.lang.String KEY_CURRENT_IMPULSE
Key used on every cell. Under this key every cell stores temporary the current force impulse affecting the cell.

See Also:
Constant Field Values

KEY_LAST_IMPULSE

public static final java.lang.String KEY_LAST_IMPULSE
Key used on every cell. Under this key every cell stores temporary the last impulse. This is the value of the previous KEY_CURRENT_IMPULSE.

See Also:
Constant Field Values

KEY_POSITION

public static final java.lang.String KEY_POSITION
Key used on every cell. Under this key every cell stores the temporary position on the display, while the calculation is running. This makes the algorithm faster, than asking the Cell everytime for its position. So the algorithm can anytime be canceled, whithout changing something.

See Also:
Constant Field Values

KEY_SKEWGAUGE

public static final java.lang.String KEY_SKEWGAUGE
Key used on every cell. Under this key every cell stores the temporary skew gauge. This value is for punish rotations of the cells.

See Also:
Constant Field Values

KEY_RELATIVES

public static final java.lang.String KEY_RELATIVES
Key used on every Cell. Under this key every cell stores the cells, that are only one edge away from it. The relatives are stored, after the first time, they are desired and calculated by #getRelatives(CellView).

See Also:
Constant Field Values

KEY_MASSINDEX

public static final java.lang.String KEY_MASSINDEX
Key used on every Cell. This indicates a weight for the number of edges received by #getNodeWeight(CellView)

See Also:
Constant Field Values

KEY_CLUSTERED_VERTICES

public static final java.lang.String KEY_CLUSTERED_VERTICES
Key used only with clusters. Under this key a cluster has an ArrayList. This list is filled with the clustered vertices.

See Also:
clusterGraph(), #moveVerticeToCluster(CellView,CellView), Constant Field Values

KEY_CLUSTER

public static final java.lang.String KEY_CLUSTER
Key used only with clusters. Under this key vertices have the cluster they belong to.

See Also:
clusterGraph(), #moveVerticeToCluster(CellView,CellView), Constant Field Values

KEY_IS_CLUSTER

public static final java.lang.String KEY_IS_CLUSTER
Key used only with clusters. Under this key a cluster has a boolean value indicating that this vertice is a cluster (clusters are VertexView-instances like every other cell).

See Also:
clusterGraph(), #isCluster(), Constant Field Values

KEY_CLUSTER_INIT_POSITION

public static final java.lang.String KEY_CLUSTER_INIT_POSITION
Key used only with clusters. Under this key every cluster has a position, which represents the position of the cluster, right after the clustering process. After the layout update process is finished, the move, resulting of subtracting the position under KEY_POSITION from the position under this value, will be performed to all vertices in the cluster. By holding the initial position here clustering becomes possible.

See Also:
clusterGraph(), declusterGraph(), Constant Field Values

initTemperature

protected double initTemperature
starting value for the temperatures of the cells


minTemperature

protected double minTemperature
if the temperature of all cells or the average of the temperatures of all cells is below this value, the algorithm stops


maxTemperature

protected double maxTemperature
temperature will never be over this value


prefEdgeLength

protected double prefEdgeLength
the length of the Edges in Pixel, the algorithm tries to keep


gravitation

protected double gravitation
the strength of the gravitation force, directed to the barycenter of the graph, added to all cells.


randomImpulseRange

protected double randomImpulseRange
length of a force vector with a random direction, added to all cells.


alphaOsc

protected double alphaOsc
opening angle in radiant, that detects oscillations


alphaRot

protected double alphaRot
opening angle in radiant, that detects rotations


sigmaOsc

protected double sigmaOsc
penalty value for a detected oscillation


sigmaRot

protected double sigmaRot
penalty value for a detected rotation


config

protected java.util.Properties config
the configuration of this algorithm


VALUES_PUR

protected static final int VALUES_PUR
to identify for the method loadRuntimeValues(int), that the algorithm wants to perform a new run

See Also:
Constant Field Values

VALUES_INC

protected static final int VALUES_INC
to identify for the method loadRuntimeValues(int), that the algorithm wants to perform a layout update

See Also:
Constant Field Values
Constructor Detail

GEMLayoutAlgorithm

public GEMLayoutAlgorithm(AnnealingLayoutAlgorithm optimizer)
Constructs a new GEM Layout Algorithm.

Method Detail

toString

public java.lang.String toString()
Returns the name of this algorithm in human readable form.


getHint

public java.lang.String getHint()
Get a human readable hint for using this layout.

Overrides:
getHint in class JGraphLayoutAlgorithm

createSettings

public JGraphLayoutSettings createSettings()
Returns an new instance of SugiyamaLayoutSettings

Overrides:
createSettings in class JGraphLayoutAlgorithm

run

public void run(JGraph graph,
                java.lang.Object[] dynamic_cells,
                java.lang.Object[] static_cells)
Starts the Calculation of a new layout with the GEM-Algorithm

Specified by:
run in class JGraphLayoutAlgorithm
Parameters:
graph - JGraph instance
dynamic_cells - List of all nodes the layout should move
static_cells - List of node the layout should not move but allow for
See Also:
#initialize(), #calculate(), de.fzi.echidna.layout.LayoutAlgorithm#perform(MyJGraph,List,Properties)

loadRuntimeValues

protected void loadRuntimeValues(int valueID)
Loads the actual desired values from the configuration to the fields, where they are used later.

Parameters:
valueID - VALUES_PUR for a normal run or VALUES_INC for a layout update process.

isTrue

protected boolean isTrue(java.lang.String boolValue)
Helping method. Transforms a String, containing only the characters "true" or "false", regardless if upper or lower case, into a boolean value.

Parameters:
boolValue - String containing a boolean value
Returns:
boolean value represented by the given string

addApplyableVertices

public void addApplyableVertices(VertexView[] vertexList)
Method for the process of layout update. Adds inserted cells to #applyCellList and some of their neighbors. Adding of neighbors is deceided by #layoutUpdateMethod. If a method is choosen with perimeter, than the inserted cells are counted, that have a position whithin the basic radius around inserted cells. then a new radius is calculated by multiplying the increasial radius with the number of inserted cells found and adding it to the basic radius. Then all cells, previously layouted whithin this radius are also added to #applyCellList. After this, cells within a given pathlength smaller than #recursionDepth are added to #applyCellList too.

Parameters:
vertexList - List of all inserted Vertices.

getAdditionalForces

protected java.util.ArrayList getAdditionalForces(VertexView view)
Method for Classes that extend this Algorithm. Will be called when performing #computeImpulse(CellView).


graphChanged

public void graphChanged(GraphModelEvent e)
Will be called, when cells are inserted or removed. When cells are removed, they are also removed from #cellList, #applyCellList and #edgeList. If cells are inserted a new layout update process starts.


clusterGraph

protected void clusterGraph()
Clusters a graph. Cells, contained in #cellList and not contained in #applyCellList are clustered by this short algorithm. The algorithm first tries to identify how many cells it should cluster. This is calculated by subtracting the size of #applyCellList from the size of #cellList and dividing the result by the #clusteringFactor. In the next step, the identified number of clusters are created, and their position is initialised by random. Then every clusterable cell is added to the cluster where the distance of the vertex and the cluster is minimal. After adding a cell, the clusters position is recalculated. Finishing this step, the algorithm tries to minimize the number of clusters, by sorting the clustered vertices, if there is another cluster, that distance is shorter than the distance to the cluster, the vertice is actually in. This can happen, because by moving vertices into the clusters, the position of the clusters are changed. The minimization runs until no vertice can be moved anymore. empty clusters are removed and finaly the clusters are added to #applyCellList, because they should move while the upcoming next calculations. That move can later be retrieved by subtracting the attributes KEY_POSITION and KEY_CLUSTER_INIT_POSITION.

See Also:
declusterGraph(), #computeClusterPosition(CellView), #moveVerticeToCluster(CellView)

moveVerticeToCluster

protected void moveVerticeToCluster(VertexView vertice,
                                    VertexView cluster)
Moves a vertice from the cluster, it is holded, to another cluster. This implies that the vertice is removed from the old cluster and added to the new. After this, the positions of the old and the new cluster are recalculated.

Parameters:
vertice - Vertex that should be moved
cluster - Cluster the vertex should be moved

computeClusterPosition

protected void computeClusterPosition(VertexView cluster)
Recalculates the position of a cluster. The position of a cluster is defined by the barycenter of the clustered vertices.

Parameters:
cluster - Cell, that has to be a cluster, should be repositioned.

declusterGraph

protected void declusterGraph()
Moves all clusters from #cellList and #applyCellList, extracts their clustered vertices and adds them to #cellList. While doing this, it repositions the clustered vertices with the move, the cluster has made during the calculation.

See Also:
clusterGraph()

isCluster

protected boolean isCluster(CellView cell)
Returns true when a cell is a cluster, else false. A cell is a cluster when it has under it's attributes a attribute with the boolean value true under the key KEY_IS_CLUSTER.

Parameters:
cell - cell, that should be researched wheather it is a cluster or not.
Returns:
true if cell is a cluster, else false.

getOptimizationAlgorithm

public AnnealingLayoutAlgorithm getOptimizationAlgorithm()
Returns:
Returns the optimizationAlgorithm.

getConfig

public java.util.Properties getConfig()
Returns:
Returns the config.

setConfig

public void setConfig(java.util.Properties configuration)