diva.graph.layout

Class GridAnnealingLayout

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 and 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.

Fields inherited from class diva.graph.layout.AbstractGlobalLayout

_layoutTarget

Constructor Summary

Constructors

Constructor and Description
GridAnnealingLayout(LayoutTarget target)

Method Summary

Modifier and Type	Method and 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.