diva.graph.layout
Class GridAnnealingLayout

java.lang.Object
  extended by diva.graph.layout.AbstractGlobalLayout
      extended by 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:
$Revision: 1.20 $
Author:
Michael Shilman (michaels@eecs.berkeley.edu)

Field Summary
protected  double _cool
          The cooling constant.
protected  int _gh
          The grid height.
protected  Object _graph
          The original graph that is passed in by the user on which the layout is applied.
protected  Object[][] _grid
          The current grid configuration as the algorithm progresses.
protected  int _gw
          The grid width.
protected  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  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  Random _random
          The random number generator used in choosing which nodes to swap.
protected  double _sparseness
          A sparseness measure for the layout.
 
Constructor Summary
GridAnnealingLayout(LayoutTarget target)
           
 
Method Summary
protected  double edgeCost(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(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(Object composite)
          Perform the annealing layout algorithm on the given graph in the context of the given layout target.
protected  double nodeCost(Object node)
          Return the absolute cost of an individual node.
protected  int numCrossings(Object inEdge, Object composite)
          Return the number of crossings between this edge and other edges in the graph.
protected  int numOverlaps(Object inEdge, Object composite)
          Return the number of overlaps between this edge and other edges in the graph.
protected  int numTees(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(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 Random _random
The random number generator used in choosing which nodes to swap.


_graph

protected 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 Object[][] _grid
The current grid configuration as the algorithm progresses.


_minGrid

protected 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 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(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(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(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(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(Object inEdge,
                                 Object composite)
Return the number of crossings between this edge and other edges in the graph.


numTees

protected final int numTees(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(Object inEdge,
                                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(Object node,
                     int x,
                     int y)
Set the logical X, Y positions of the given node.



Copyright © 2015 Central Laboratory of the Research Councils. All Rights Reserved.