com.hp.hpl.guess.layout
Class KamadaGraphLayout

java.lang.Object
  extended byedu.uci.ics.jung.visualization.AbstractLayout
      extended bycom.hp.hpl.guess.layout.KamadaGraphLayout
All Implemented Interfaces:
ChangeEventSupport, Layout, VertexLocationFunction

public class KamadaGraphLayout
extends AbstractLayout

Positions network nodes according to the Kamada-Kawai algorithm. The Kamada-Kawai graph layout class attempts to position nodes on the space so that the geometric (Euclidean) distance between them is as close as possible to the graph-theoretic (path) distance between them. the x and y coordinates of the nodes will be modified by the layout.

The KamadaGraphLayout implements the ActionListener interface to interrupt the layout. This breaks out of the algorithm implementation as soon as possible, but will rescale the display if appropriate. You can have the KamadaGraphLayout listener for RePast toolbar button presses by including something like the following code inside your model class.

 graphLayout = new KamadaGraphLayout(...);
 Controller c = (Controller)getController();
 c.addStopListener(graphLayout);
 c.addPauseListener(graphLayout);
 c.addExitListener(graphLayout);
 
This will cause the KamadaGraphLayout graphLayout to interrupt its layout whenever stop, pause, or exit is pressed.

Note The KamadaGraphLayout is quite slow. It is not meant as a "true" visualization tool, but rather is intended only to provide the modeler with "sense" of the network. Real analysis and visualization should be done in a tool like Pajek.

Version:
$Revision: 1.1 $ $Date: 2005/10/05 20:19:39 $
Author:
Skye Bender-deMoll e-mail skyebend@santafe.edu

Field Summary
 boolean done
           
 
Constructor Summary
KamadaGraphLayout(Graph g, boolean firstLayout, int width, int height)
           
 
Method Summary
 void actionPerformed(ActionEvent evt)
          Implements the ActionListener interface.
 void advancePositions()
          Positions the nodes on the layout according to the results of numerous iterations of the Kamada-Kawai spring-embedding algorithm.
 void circleLayout()
          Positions nodes on layout in a circle for repeatability.
 Coordinates getCoordinates(Node v)
           
 int getHeight()
          Gets the height of the area on which to layout the graph.
 int getWidth()
          Gets the width of the area on which to layout the graph.
 double getX(Vertex n)
           
 double getY(Vertex n)
           
 boolean incrementsAreDone()
           
 void initialize_local_vertex(Vertex v)
           
 void initialize_local()
           
 boolean isIncremental()
           
 void setCircleLayout(boolean eachTime)
          Sets whether circleLayout will be called to arrange nodes before starting each layout.
 void setMaxPasses(int passes)
          Sets the maximum number of passes the inner loop of the KK algorithm will execute.
 void setMinEpsilon(double energy)
          Sets the minimum "spring" energy which the layout attempts to achieve.
 void setPad(int p)
          Sets the number of pixels to shrink the effective window by.
 void setRescaleLayout(boolean rescale)
          Sets whether the completed layout will be resized to exactly fill the display window.
 void setSpringConst(double spring)
          Sets the "springiness" of the imaginary springs connecting the nodes.
 void setUpdate(boolean doUpdate)
           
 void setUpdateEveryN(int updateEveryN)
          Sets how frequently the layout will be redrawn during algorithm convergence.
 
Methods inherited from class edu.uci.ics.jung.visualization.AbstractLayout
addChangeListener, applyFilter, dontMove, fireStateChanged, forceMove, getBaseKey, getChangeListeners, getCoordinates, getCurrentSize, getEdge, getEdge, getGraph, getLocation, getStatus, getVertex, getVertex, getVertexIterator, getVisibleEdges, getVisibleVertices, initialize, initialize, lockVertex, removeChangeListener, resize, restart, unlockVertex
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

done

public boolean done
Constructor Detail

KamadaGraphLayout

public KamadaGraphLayout(Graph g,
                         boolean firstLayout,
                         int width,
                         int height)
Method Detail

setPad

public void setPad(int p)
Sets the number of pixels to shrink the effective window by. Java draws object from top left hand corner and this allows objects drawn on the far right to be visible.

Parameters:
p - the number of pixels to inset by

setUpdateEveryN

public void setUpdateEveryN(int updateEveryN)
Sets how frequently the layout will be redrawn during algorithm convergence. If updateEveryN is greater than 0,the layout will update the display after every Nth pass through the algorithm. Additional updates make the layout take much longer, especially if there are a large number of nodes to draw.

Parameters:
updateEveryN - the N for determining wether to update on the Nth pass

setMinEpsilon

public void setMinEpsilon(double energy)
Sets the minimum "spring" energy which the layout attempts to achieve. Small values mean greater accuracy, and an unknown (but large) amount of additional run time. The algorithm will start with an initially high epsilon value, and keep decreasing it until the layout drops below epsilon, the layout stops improving, or maxPasses is exceeded. Default is 1, so setting to a higher value will speed up layouts.

Parameters:
energy - the value for the minimum epsilon

setSpringConst

public void setSpringConst(double spring)
Sets the "springiness" of the imaginary springs connecting the nodes. Impact on layout is not well understood, seems to control how far nodes are moved each time. Default is 1.

Parameters:
spring - the value for the spring constant in the algorithm

setMaxPasses

public void setMaxPasses(int passes)
Sets the maximum number of passes the inner loop of the KK algorithm will execute. Lower values mean that the layout is more likely to end before arriving at a minima, but it will break more quickly when stuck in a cycle. The number of loops needed to a achieve a layout is roughly proportional to the number of nodes (but not in all cases!). Default is 5000

Parameters:
passes - the maximum number of time the inner loop will execute.

setCircleLayout

public void setCircleLayout(boolean eachTime)
Sets whether circleLayout will be called to arrange nodes before starting each layout. Should be called before first layout to insure repeatability. May make layouts take slightly longer. Default is false, but will still circle the first layout unless explicitly set to false.

Parameters:
eachTime - true = always call circleLayout

setRescaleLayout

public void setRescaleLayout(boolean rescale)
Sets whether the completed layout will be resized to exactly fill the display window. Setting rescale to false may mean that individual nodes or the entire network may drift off the screen, but it will insure maximum visual continuity between layouts, and minimum layout time. default is true.

Parameters:
rescale - whether to rescale the layout

circleLayout

public void circleLayout()
Positions nodes on layout in a circle for repeatability. Can be called internally before each layout by setting circleLayout to true. Useful to insure that nodes have starting coordinates.


advancePositions

public void advancePositions()
Positions the nodes on the layout according to the results of numerous iterations of the Kamada-Kawai spring-embedding algorithm. Essentially, the network is modeled as a collection of nodes connected by springs with resting lengths proportional to the length of the shortest path distance between each node pair. Nodes are normally positioned in a circle, and then each node in sequence is repositioned until the "energy" of all of its springs are minimized to a parameter value epsilon. The location of the local minima for each node is estimated with iterations of a Newtown-Raphson steepest descent method. Repositioning ceases when all nodes have energy below epsilon. In this implementation, epsilon is initialized at a high value, and than decreased as in simulated annealing. the layout SHOULD stop when a low value (epsilon < 1) is reached or when energies of nodes can now longer be decreased.

Note: In the current implementation the layout may not always converge! however, the maxPasses parameter can be set lower to interrupt cycling layouts. Also has not been tested/ implemented on weighted graphs. The Kamada-Kawai algorithm was not intended to run on disconnected graphs (graphs with multiple components. The kludgy solution implemented here is to run the algorithm independently on each of the components (of size > 1). This is somewhat unsatisfactory as the components will often overlap.

The KK algorithm is relatively slow, especially on the first round. However, it often discovers layouts of regularly structured graphs which are "better" and more repeatable than the Fruchmen-Reingold technique. Implementation of the numerics of the Newton-Raphson method follows Shawn Lorae Stutzman, Auburn University, 12/12/96 http://mathcs.mta.ca/research/rosebrugh/gdct/javasource.htm

Kamada, Tomihisa and Satoru Kawai (1989) "An Algorithm for Drawing Undirected Graphs" Information Processing Letters 31:7-15


actionPerformed

public void actionPerformed(ActionEvent evt)
Implements the ActionListener interface. Whenever this is called the layout will be interrupted as soon as possible.


getHeight

public int getHeight()
Gets the height of the area on which to layout the graph.


getWidth

public int getWidth()
Gets the width of the area on which to layout the graph.


setUpdate

public void setUpdate(boolean doUpdate)

getX

public double getX(Vertex n)

getY

public double getY(Vertex n)

getCoordinates

public Coordinates getCoordinates(Node v)

incrementsAreDone

public boolean incrementsAreDone()

initialize_local_vertex

public void initialize_local_vertex(Vertex v)

initialize_local

public void initialize_local()

isIncremental

public boolean isIncremental()