java.lang.Object
- diva.graph.layout.AbstractGlobalLayout
- - diva.graph.layout.GridAnnealingLayout

All Implemented Interfaces:

GlobalLayout
```
public class GridAnnealingLayout
extends AbstractGlobalLayout
```
A simple layout which places nodes on a grid using a cost function. It performs the following simple-minded algorithm:
1. defines a grid based on the number of nodes in the graph and randomly assigns the nodes to vertices on the grid.
2. randomly swaps nodes on the grid and picks a good settling point based on a cost function which favors short edges over long ones, straight edges over diagonal ones, and generally tries not to put edges through nodes.
3. distorts the grid based on the relative sizes of the nodes, and finally places the nodes according to this distortion. *
This class is implemented as a large template method, so it should be relatively easy to extend or modify.
Version:

$Id$

Author:

Michael Shilman

Pt.AcceptedRating:

Red

Field Summary

Fields
Modifier and Type	Field	Description
`protected double`	`_cool`	The cooling constant.
`protected int`	`_gh`	The grid height.
`protected java.lang.Object`	`_graph`	The original graph that is passed in by the user on which the layout is applied.
`protected java.lang.Object[][]`	`_grid`	The current grid configuration as the algorithm progresses.
`protected int`	`_gw`	The grid width.
`protected java.util.HashMap`	`_map`	A mapping from nodes to their corresponding logical grid positions, stored as integer arrays of length 2.
`protected double`	`_minCost`	The relative cost of the best grid configuration so far as the algorithm progresses.
`protected java.lang.Object[][]`	`_minGrid`	The best grid configuration so far as the algorithm progresses.
`protected int`	`_numIters`	The number of iterations to cool over.
`protected int`	`_numMoves`	The number of moves per iteration.
`protected java.util.Random`	`_random`	The random number generator used in choosing which nodes to swap.
`protected double`	`_sparseness`	A sparseness measure for the layout.

Constructor Summary

Constructors
Constructor Description

GridAnnealingLayout(LayoutTarget target)

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`protected double`	`edgeCost(java.lang.Object edge)`	Return the absolute cost of an individual edge.
`double`	`getCoolingFactor()`
`int`	`getIterationCount(int cnt)`
`int`	`getMoveCount(int cnt)`
`double`	`getSparseness()`	Return the sparseness value of this layout; the default value is 1.0.
`protected int[]`	`getXY(java.lang.Object node)`	Return the logical X, Y positions of the given node as an integer array of length 2.
`protected void`	`initGrid()`	Initialize the grid and randomly assign nodes to vertices of the grid.
`void`	`layout(java.lang.Object composite)`	Perform the annealing layout algorithm on the given graph in the context of the given layout target.
`protected double`	`nodeCost(java.lang.Object node)`	Return the absolute cost of an individual node.
`protected int`	`numCrossings(java.lang.Object inEdge, java.lang.Object composite)`	Return the number of crossings between this edge and other edges in the graph.
`protected int`	`numOverlaps(java.lang.Object inEdge, java.lang.Object composite)`	Return the number of overlaps between this edge and other edges in the graph.
`protected int`	`numTees(java.lang.Object composite)`	Return the number of instances of nodes that are being placed on top of edges that they are not connected to.
`void`	`setCoolingFactor(double val)`	Set the cooling factor to be a value greater than 0 and less than or equal to 1.
`void`	`setIterationCount(int cnt)`	Set the number of iterations to cool over.
`void`	`setMoveCount(int cnt)`	Set the number of moves per iteration.
`void`	`setSparseness(double val)`	Set the sparseness of this layout.
`protected void`	`setXY(java.lang.Object node, int x, int y)`	Set the logical X, Y positions of the given node.

Methods inherited from class diva.graph.layout.AbstractGlobalLayout
getLayoutTarget, setLayoutTarget

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - _random
```
protected java.util.Random _random
```
    The random number generator used in choosing which nodes to swap.
  - _graph
```
protected java.lang.Object _graph
```
    The original graph that is passed in by the user on which the layout is applied.
  - _gw
```
protected int _gw
```
    The grid width.
  - _gh
```
protected int _gh
```
    The grid height.
  - _grid
```
protected java.lang.Object[][] _grid
```
    The current grid configuration as the algorithm progresses.
  - _minGrid
```
protected java.lang.Object[][] _minGrid
```
    The best grid configuration so far as the algorithm progresses.
  - _minCost
```
protected double _minCost
```
    The relative cost of the best grid configuration so far as the algorithm progresses.
  - _map
```
protected java.util.HashMap _map
```
    A mapping from nodes to their corresponding logical grid positions, stored as integer arrays of length 2.
  - _sparseness
```
protected double _sparseness
```
    A sparseness measure for the layout.
    
    See Also:
    
    setSparseness(double)
  - _numIters
```
protected int _numIters
```
    The number of iterations to cool over.
  - _numMoves
```
protected int _numMoves
```
    The number of moves per iteration.
  - _cool
```
protected double _cool
```
    The cooling constant.
- Constructor Detail
  - GridAnnealingLayout
```
public GridAnnealingLayout(LayoutTarget target)
```
- Method Detail
  - edgeCost
```
protected double edgeCost(java.lang.Object edge)
```
    Return the absolute cost of an individual edge. By default the cost function is:
    EDGE_COST(e) = [ HEIGHT(e) + WIDTH(e) + ELBOW_PENALTY(e) + EDGE_OVERLAP_PENALTY * num_overlap(e) + CROSSING_PENALTY * num_crossing(e) ]
  - getCoolingFactor
```
public double getCoolingFactor()
```
    See Also:
    
    setCoolingFactor(double)
  - getIterationCount
```
public int getIterationCount(int cnt)
```
    See Also:
    
    setIterationCount(int)
  - getMoveCount
```
public int getMoveCount(int cnt)
```
    See Also:
    
    setMoveCount(int)
  - getSparseness
```
public double getSparseness()
```
    Return the sparseness value of this layout; the default value is 1.0.
    
    See Also:
    
    setSparseness(double)
  - getXY
```
protected int[] getXY(java.lang.Object node)
```
    Return the logical X, Y positions of the given node as an integer array of length 2.
  - initGrid
```
protected void initGrid()
```
    Initialize the grid and randomly assign nodes to vertices of the grid. The grid initialization is based on the aspect ratio of the viewport in which the layout is being performed. In particular the following algorithm is used:
    GH = H/W * sqrt(N) * SPARSENESS
    Where H and W are the height and width of the viewport, N is the number of nodes in the graph, and SPARSENESS is some measure of the sparseness of the layout. A SPARSENESS of 1 will mean that the graph is tightly packed, and the packing amount decreases linearly with the SPARSENESS value.
    See Also:
    
    setSparseness(double)
  - layout
```
public void layout(java.lang.Object composite)
```
    Perform the annealing layout algorithm on the given graph in the context of the given layout target.
    
    Specified by:
    
    layout in interface GlobalLayout
    
    Specified by:
    
    layout in class AbstractGlobalLayout
  - nodeCost
```
protected double nodeCost(java.lang.Object node)
```
    Return the absolute cost of an individual node. By default the cost function is:
    NODE_COST(n) = SUM [ EDGE_COST(n.edge(i)) ] + TEE_PENALTY * num_tee(g)
  - numCrossings
```
protected final int numCrossings(java.lang.Object inEdge,
                                 java.lang.Object composite)
```
    Return the number of crossings between this edge and other edges in the graph.
  - numTees
```
protected final int numTees(java.lang.Object composite)
```
    Return the number of instances of nodes that are being placed on top of edges that they are not connected to.
  - numOverlaps
```
protected final int numOverlaps(java.lang.Object inEdge,
                                java.lang.Object composite)
```
    Return the number of overlaps between this edge and other edges in the graph. For now, simply test to see if the lines are horizontal or vertical and overlap with each other.
  - setCoolingFactor
```
public void setCoolingFactor(double val)
```
    Set the cooling factor to be a value greater than 0 and less than or equal to 1. The cooling factor determines how quickly the annealing "settles"; the lower the factor, the faster the annealing settles. The Default value is .95.
  - setIterationCount
```
public void setIterationCount(int cnt)
```
    Set the number of iterations to cool over. Default value is 100.
  - setMoveCount
```
public void setMoveCount(int cnt)
```
    Set the number of moves per iteration. Default value is 10.
  - setSparseness
```
public void setSparseness(double val)
```
    Set the sparseness of this layout. A sparseness of 1.0 will mean that the graph is tightly packed, and the packing amount decreases linearly with the SPARSENESS value.
  - setXY
```
protected void setXY(java.lang.Object node,
                     int x,
                     int y)
```
    Set the logical X, Y positions of the given node.

Class GridAnnealingLayout

Field Summary

Constructor Summary

Method Summary

Methods inherited from class diva.graph.layout.AbstractGlobalLayout

Methods inherited from class java.lang.Object

Field Detail

_random

_graph

_gw

_gh

_grid

_minGrid

_minCost

_map

_sparseness

_numIters

_numMoves

_cool

Constructor Detail

GridAnnealingLayout

Method Detail

edgeCost

getCoolingFactor

getIterationCount

getMoveCount

getSparseness

getXY

initGrid

layout

nodeCost

numCrossings

numTees

numOverlaps

setCoolingFactor

setIterationCount

setMoveCount

setSparseness

setXY