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: GridAnnealingLayout.java 40701 2006-02-07 00:50:57Z cxh $

Author:

Michael Shilman

Accepted Rating:

Red

Field Summary

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.
private static double	CROSSING_PENALTY The penalty for crossings with other edges in the graph.
private static double	EDGE_OVERLAP_PENALTY The penalty for overlaps with other edges in the graph.
private static double	ELBOW_PENALTY The penalty for elbow-shaped edges, i.e ones which have height and width.
private static double	HEIGHT_FACTOR The penalty for each unit of height in an edge.
private static double	TEE_PENALTY The penalty for tees, where a node lands ON another edge that is not connected to it.
private static double	WIDTH_FACTOR The penalty for each unit of width in an edge.

Fields inherited from class diva.graph.layout.AbstractGlobalLayout

_layoutTarget

Constructor Summary

GridAnnealingLayout(LayoutTarget target)

Method Summary

private java.lang.Object	_getParentInGraph(java.lang.Object node)
private void	anneal() Perform simulated annealing using the cost function.
private void	ASSERT(boolean b, java.lang.String err) Assert the given condition and throw a runtime exception with the given string if the assertion fails.
private void	assignLayout() Assign layout positions to the nodes in the graph based on the logical grid positions determined in the annealing process.
private void	cleanupStructures() Cleanup the data structures used in the layout so that they are empty next time the layout is called.
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.
private void	snapMin() Take a snapshot of the minimum cost arrangement of the nodes, so that we can backtrack to it later.
private void	swap(java.lang.Object node1, java.lang.Object node2) Swap the two nodes' grid positions.

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

HEIGHT_FACTOR

private static final double HEIGHT_FACTOR

The penalty for each unit of height in an edge.

See Also:

Constant Field Values

WIDTH_FACTOR

private static final double WIDTH_FACTOR

The penalty for each unit of width in an edge.

See Also:

Constant Field Values

ELBOW_PENALTY

private static final double ELBOW_PENALTY

The penalty for elbow-shaped edges, i.e ones which have height and width.

See Also:

Constant Field Values

EDGE_OVERLAP_PENALTY

private static final double EDGE_OVERLAP_PENALTY

The penalty for overlaps with other edges in the graph.

See Also:

Constant Field Values

TEE_PENALTY

private static final double TEE_PENALTY

The penalty for tees, where a node lands ON another edge that is not connected to it.

See Also:

Constant Field Values

CROSSING_PENALTY

private static final double CROSSING_PENALTY

The penalty for crossings with other edges in the graph.

See Also:

Constant Field Values

_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

anneal

private void anneal()

Perform simulated annealing using the cost function.

ASSERT

private final void ASSERT(boolean b,
                          java.lang.String err)
                   throws java.lang.RuntimeException

Assert the given condition and throw a runtime exception with the given string if the assertion fails.

Throws:

java.lang.RuntimeException

assignLayout

private void assignLayout()

Assign layout positions to the nodes in the graph based on the logical grid positions determined in the annealing process.

cleanupStructures

private void cleanupStructures()

Cleanup the data structures used in the layout so that they are empty next time the layout is called.

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.

snapMin

private void snapMin()

Take a snapshot of the minimum cost arrangement of the nodes, so that we can backtrack to it later.

swap

private void swap(java.lang.Object node1,
                  java.lang.Object node2)

Swap the two nodes' grid positions.

_getParentInGraph

private java.lang.Object _getParentInGraph(java.lang.Object node)