Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## uchicago.src.sim.gui
Class KamadaGraphLayout

    java.lang.Object
      uchicago.src.sim.gui.AbstractGraphLayout
          uchicago.src.sim.gui.LayoutWithDisplay
              uchicago.src.sim.gui.KamadaGraphLayout

All Implemented Interfaces:
  java.awt.event.ActionListener, java.util.EventListener, GraphLayout

    public class KamadaGraphLayout

extends LayoutWithDisplay
implements java.awt.event.ActionListener

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.10 $ $Date: 2004/11/03 19:50:59 $
Author:
  Skye Bender-deMoll e-mail skyebend@santafe.edu

Field Summary

Fields inherited from class uchicago.src.sim.gui.LayoutWithDisplay
`display, isEventThread`

Fields inherited from class uchicago.src.sim.gui.AbstractGraphLayout
`height, nodeList, update, width`

Constructor Summary
`KamadaGraphLayout(int width, int height)` Creates a KamadaGraphLayout with specified width and height.
`KamadaGraphLayout(java.util.List nodes, int width, int height)` Creates a KamadaGraphLayout with specified width and height, and list of nodes. setDisplay must be called before calling updateLayout().
`KamadaGraphLayout(java.util.List nodes, int width, int height, DisplaySurface surface, int updateEveryN)` If the KamadaGraphLayout is passed a display, and a value for updateEveryN, it will call the display's updateDisplay() method on every Nth pass during the layout to provide visual feedback.

Method Summary
`void` | `actionPerformed(java.awt.event.ActionEvent evt)` Implements the ActionListener interface.
`void` | `circleLayout()` Positions nodes on layout in a circle for repeatability.
`void` | `setAnimateTransitions(boolean animateTrans)` Sets whether the completed layout (and each component as it is finished) will smoothly transition to its new location.
`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` | `setUpdateEveryN(int updateEveryN)` Sets how frequently the layout will be redrawn during algorithm convergence.
`void` | `updateLayout()` Positions the nodes on the layout according to the results of numerous iterations of the Kamada-Kawai spring-embedding algorithm.

Methods inherited from class uchicago.src.sim.gui.LayoutWithDisplay
`setDisplay, updateDisplay`

Methods inherited from class uchicago.src.sim.gui.AbstractGraphLayout
`appendToList, appendToList, getHeight, getNodeList, getUpdate, getWidth, setList, setUpdate`

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

Constructor Detail

### KamadaGraphLayout

    public KamadaGraphLayout(int width,
                             int height)

  Creates a KamadaGraphLayout with specified width and height. setDisplay must be called before calling updateLayout().

  Parameters:
    `width` - the width (in pixels) of the displaySurface
    `height` - the height (in pixels) of the DisplaySurface

### KamadaGraphLayout

    public KamadaGraphLayout(java.util.List nodes,
                             int width,
                             int height)

  Creates a KamadaGraphLayout with specified width and height, and list of nodes. setDisplay must be called before calling updateLayout().

  Parameters:
    `nodes` - the list nodes to layout with this KamadaGraphLayout
    `width` - the width (in pixels) of the DisplaySurface
    `height` - the height (in pixels) of the DisplaySurface

### KamadaGraphLayout

    public KamadaGraphLayout(java.util.List nodes,
                             int width,
                             int height,
                             DisplaySurface surface,
                             int updateEveryN)

  If the KamadaGraphLayout is passed a display, and a value for updateEveryN, it will call the display's updateDisplay() method on every Nth pass during the layout to provide visual feedback. Note: this update occurs within the current tick and is intended to provide visual feedback on the algorithms convergence and the network structure The additional updating will slow the layout down dramatically when displaying large networks.

  Parameters:
    `nodes` - the network to layout.
    `width` - the width (pixels) of the display surface
    `height` - the height (pixels) of the display surface
    `surface` - the displaysurface to update
    `updateEveryN` - determines if/ when layout is redrawn during algorithm

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

### setAnimateTransitions

    public void setAnimateTransitions(boolean animateTrans)

  Sets whether the completed layout (and each component as it is finished) will smoothly transition to its new location. Provides visually pleasing results and makes it easy to track structural changes in the network, especially if updateEveryN is set to zero. In this case, no visual feedback will be provided on layout algorithm convergence, but the comparison of the structure of the network at successive time steps is maximized. The additional redraws required to do the animation will slow down the simulation, especially on large networks. Default is true.

  Parameters:
    `animateTrans` - whether to animate transitions between layouts

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

### updateLayout

    public void updateLayout()

  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

  Specified by:
    `updateLayout` in interface `GraphLayout`
  Specified by:
    `updateLayout` in class `AbstractGraphLayout`

### actionPerformed

    public void actionPerformed(java.awt.event.ActionEvent evt)

  Implements the ActionListener interface. Whenever this is called the layout will be interrupted as soon as possible.

  Specified by:
    `actionPerformed` in interface `java.awt.event.ActionListener`
  Overrides:
    `actionPerformed` in class `AbstractGraphLayout`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD