org.jgraph.layout
Class AnnealingLayoutAlgorithm

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

public class AnnealingLayoutAlgorithm
extends JGraphLayoutAlgorithm

Simulated Annealing Layout Algorithm

Implemented from the paper: "Drawing Graphs Nicely Using Simulated Annealing" from Ron Davidson and David Harel. ACM Transactions on Graphics, Vol. 15, No. 4, October 1996, Pages 301-331.


Nested Class Summary
static class AnnealingLayoutAlgorithm.MathExtensions
           
 
Field Summary
protected  java.util.ArrayList applyCellList
          the list of all cells, a new layout should be calculated for
protected  java.util.ArrayList cellList
          the list of all cells of the graph
static java.lang.String CF_KEY_EDGE_DISTANCE_RELEVANT_EDGES
           
protected static int CONFIG_KEY_LAYOUT_UPDATE
          Key for loading configuration values.
protected static int CONFIG_KEY_RUN
          Key for loading configuration values.
static int COSTFUNCTION_BORDERLINE
           
static int COSTFUNCTION_EDGE_CROSSING
           
static int COSTFUNCTION_EDGE_DISTANCE
           
static int COSTFUNCTION_EDGE_LENGTH
           
static int COSTFUNCTION_NODE_DISTANCE
           
static int COSTFUNCTION_NODE_DISTRIBUTION
           
static int COUT_COSTFUNCTION
           
protected  java.util.ArrayList edgeList
          the list of all edges of the graph
protected  boolean isOptimizer
           
static java.lang.String KEY_CAPTION
           
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_IS_CLUSTER
          Key used only with clusters.
static java.lang.String KEY_POSITION
           
static java.lang.String KEY_RELATIVES
           
protected  double[] lambdaList
          normalizing and priority factors for the costfunctions
protected  java.util.Properties presetConfig
          holds the configuration of the algorithm, gained by the controller
 
Fields inherited from class org.jgraph.layout.JGraphLayoutAlgorithm
LAYOUT_ATTRIBUTES
 
Constructor Summary
AnnealingLayoutAlgorithm()
          Constructor for SimulatedAnnealingAlgorithm.
AnnealingLayoutAlgorithm(boolean isOptimizer)
          Constructor for SimulatedAnnealingAlgorithm.
 
Method Summary
protected  void clusterGraph()
          Clusters a graph.
protected  void computeClusterPosition(VertexView cluster)
          Recalculates the position of a cluster.
 int[] createPermutation(int length)
          Creates a permutation of the Numbers from 0 to a determined value.
 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  double getAdditionalCosts(int cfConfig, double[] lambda)
          Method for classes that extends this Algorithm.
 java.lang.String getHint()
          Get a human readable hint for using this layout.
 java.util.Properties getPresetConfig()
           
 java.awt.geom.Point2D.Double getRandomVector(double maxLength)
          Computes a random Vector with a random direction and a given length.
protected  java.util.ArrayList getRelatives(CellView view)
          Retrieves all Cells that have an edge with the given Cell.
protected  java.util.ArrayList getRelativesFrom(java.util.ArrayList list, CellView view)
          Retrieves the Cells that are directly connected to the given Cell and member of the given list.
 void graphChanged(GraphModelEvent e)
          When a event reaches this method, it will be scanned, if there are Cells removed or Cells inserted.
protected  boolean isCluster(CellView cell)
          Returns true when a cell is a cluster, else false.
 boolean isOptimizer()
           
protected  void loadAdditionalConfiguration(int configSwitch)
          Method of classes extending this class, that want to load their initial values from the configuration.
protected  void moveVerticeToCluster(VertexView vertice, VertexView cluster)
          Moves a vertice from the cluster, it is holded, to another cluster.
 void performOptimization(java.util.ArrayList applyList, java.util.ArrayList allCellList, java.util.ArrayList allEdgeList, java.util.Properties config)
          Runs the Algorithm as a optimization Algorithm of another Algorithm
 void run(JGraph graph, java.lang.Object[] dynamic_cells, java.lang.Object[] static_cells)
          Runs the Algorithm
 void setPresetConfig(java.util.Properties presetConfig)
           
 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

COUT_COSTFUNCTION

public static final int COUT_COSTFUNCTION
See Also:
Constant Field Values

COSTFUNCTION_EDGE_DISTANCE

public static final int COSTFUNCTION_EDGE_DISTANCE
See Also:
Constant Field Values

COSTFUNCTION_EDGE_CROSSING

public static final int COSTFUNCTION_EDGE_CROSSING
See Also:
Constant Field Values

COSTFUNCTION_EDGE_LENGTH

public static final int COSTFUNCTION_EDGE_LENGTH
See Also:
Constant Field Values

COSTFUNCTION_BORDERLINE

public static final int COSTFUNCTION_BORDERLINE
See Also:
Constant Field Values

COSTFUNCTION_NODE_DISTRIBUTION

public static final int COSTFUNCTION_NODE_DISTRIBUTION
See Also:
Constant Field Values

COSTFUNCTION_NODE_DISTANCE

public static final int COSTFUNCTION_NODE_DISTANCE
See Also:
Constant Field Values

KEY_CAPTION

public static final java.lang.String KEY_CAPTION
See Also:
Constant Field Values

KEY_POSITION

public static final java.lang.String KEY_POSITION
See Also:
Constant Field Values

KEY_RELATIVES

public static final java.lang.String KEY_RELATIVES
See Also:
Constant Field Values

CF_KEY_EDGE_DISTANCE_RELEVANT_EDGES

public static final java.lang.String CF_KEY_EDGE_DISTANCE_RELEVANT_EDGES
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

CONFIG_KEY_RUN

protected static final int CONFIG_KEY_RUN
Key for loading configuration values. Indicates to load values for a normal run.

See Also:
Constant Field Values

CONFIG_KEY_LAYOUT_UPDATE

protected static final int CONFIG_KEY_LAYOUT_UPDATE
Key for loading configuration values. Indicates to load values for a layout update.

See Also:
Constant Field Values

lambdaList

protected double[] lambdaList
normalizing and priority factors for the costfunctions


cellList

protected java.util.ArrayList cellList
the list of all cells of the graph


edgeList

protected java.util.ArrayList edgeList
the list of all edges of the graph


applyCellList

protected java.util.ArrayList applyCellList
the list of all cells, a new layout should be calculated for


presetConfig

protected java.util.Properties presetConfig
holds the configuration of the algorithm, gained by the controller


isOptimizer

protected boolean isOptimizer
Constructor Detail

AnnealingLayoutAlgorithm

public AnnealingLayoutAlgorithm()
Constructor for SimulatedAnnealingAlgorithm.


AnnealingLayoutAlgorithm

public AnnealingLayoutAlgorithm(boolean isOptimizer)
Constructor for SimulatedAnnealingAlgorithm.

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)
Runs the Algorithm

Specified by:
run in class JGraphLayoutAlgorithm
Parameters:
graph - JGraph to be altered by layout
dynamic_cells - Cells that are to be moved by the layout
static_cells - Cells that are not to be moved, but allowed for by the layout
See Also:
org.jgraph.layout.LayoutAlgorithm#perform(JGraph, boolean, Properties)

performOptimization

public void performOptimization(java.util.ArrayList applyList,
                                java.util.ArrayList allCellList,
                                java.util.ArrayList allEdgeList,
                                java.util.Properties config)
Runs the Algorithm as a optimization Algorithm of another Algorithm

Parameters:
applyList - List of all Cells, a new Layout should be found for.
allCellList - List of all Cells of the Graph
allEdgeList - List of all Edges of the Graph

loadAdditionalConfiguration

protected void loadAdditionalConfiguration(int configSwitch)
Method of classes extending this class, that want to load their initial values from the configuration.

Parameters:
configSwitch - Determines which configurationvalues have to be loaded Possible values are CONFIG_KEY_RUN and CONFIG_KEY_LAYOUT_UPDATE
See Also:
#loadConfiguration(int)

getAdditionalCosts

protected double getAdditionalCosts(int cfConfig,
                                    double[] lambda)
Method for classes that extends this Algorithm. Calls the Costfunctions of the extending class.

Returns:
costs generated with the additional costfunctions
See Also:
#getGlobalCosts(double[])

createPermutation

public int[] createPermutation(int length)
Creates a permutation of the Numbers from 0 to a determined value.

Parameters:
length - Number of Numbers and maximal distance to 0 for the Numbers filling the permutation
Returns:
Permutation of the Numbers between 0 and length

getRandomVector

public java.awt.geom.Point2D.Double getRandomVector(double maxLength)
Computes a random Vector with a random direction and a given length.


getRelativesFrom

protected java.util.ArrayList getRelativesFrom(java.util.ArrayList list,
                                               CellView view)
Retrieves the Cells that are directly connected to the given Cell and member of the given list.

Parameters:
list - Only relatives from this List are allowed
view - Relatives from this view are requested
Returns:
Relatives from view that are in the list
See Also:
getRelatives(CellView)

getRelatives

protected java.util.ArrayList getRelatives(CellView view)
Retrieves all Cells that have an edge with the given Cell.

Parameters:
view - Cell, the relatives are requested from
Returns:
Relatives of view

graphChanged

public void graphChanged(GraphModelEvent e)
When a event reaches this method, it will be scanned, if there are Cells removed or Cells inserted. When there are Cells removed from the graph, they have to be removed from cellList, edgeList and from applyCellList. If there are Cells added, the layout update process starts. This triggers the algorithm to try to find a suitable layout for the inserted cells, by layouting them and some of the cells, available in cellList. The algorithm tries to stimulate the cells from cellList to make place for the layout of the inserted Cells.


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.

isOptimizer

public boolean isOptimizer()
Returns:
Returns the isOptimizer.

getPresetConfig

public java.util.Properties getPresetConfig()
Returns:
Returns the presetConfig.

setPresetConfig

public void setPresetConfig(java.util.Properties presetConfig)
Parameters:
presetConfig - The presetConfig to set.