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 FruchGraphLayout

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

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

    public class FruchGraphLayout

extends LayoutWithDisplay

Positions nodes in layout according to iterations of an implementation of the Fruchmen-Reingold graph layout algorithm. See the docs to `updateLayout` for the details.

The FruchGraphLayout 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 FruchGraphLayout listener for RePast toolbar button presses by including something like the following code inside your model class.

``

     graphLayout = new FruchGraphLayout(...);
     Controller c = (Controller)getController();
     c.addStopListener(graphLayout);
     c.addPauseListener(graphLayout);
     c.addExitListener(graphLayout);

This will cause the FruchGraphLayout graphLayout to interrupt its layout whenever stop, pause, or exit is pressed.

Note The FruchGraphLayout is not particularly fast, although it is faster than the KamadaGraphLayout. 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.14 $ $Date: 2004/11/03 19:50:59 $
Author:
  Skye Bender-deMoll email: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
`FruchGraphLayout(int width, int height)` Constructs new FruchGraphLayout.
`FruchGraphLayout(java.util.List nodes, int width, int height)` Constructs new FruchGraphLayout.
`FruchGraphLayout(java.util.List nodes, int width, int height, DisplaySurface surface, int updateEveryN)` Constructs new FruchGraphLayout.

Method Summary
`void` | `actionPerformed(java.awt.event.ActionEvent evt)` Implements the ActionListener interface.
`void` | `randomizeLayout()` Randomly positions nodes on layout.
`void` | `setAnimateTransitions(boolean animateTrans)` Sets whether the completed layout (and each component as it is finished) will smoothly transition to its new location.
`void` | `setPad(int p)` Sets the number of pixels to shrink radius by.
`void` | `setRandomSeed(int seed)` Sets the Random seed used in the intial random placement of the nodes.
`void` | `setRescaleLayout(boolean rescale)` Sets whether the completed layout will be resized to exactly fill the display window.
`void` | `setUpdateEveryN(int updateEveryN)` If the layout has been passed a display to update, and updateEveryN is greater than 0, the layout will update the display after every Nth pass through the algorithm.
`void` | `updateLayout()` Positions nodes in layout according to a modified implementation of the Fruchterman-Reingold graph layout 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

### FruchGraphLayout

    public FruchGraphLayout(int width,
                            int height)

  Constructs new FruchGraphLayout. Set Display must be called to pass in a display before update display is called

  Parameters:
    `width` - the width of the display in pixels
    `height` - the height of the display in pixels

### FruchGraphLayout

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

  Constructs new FruchGraphLayout. Set Display must be called to pass in a display before update display is called

  Parameters:
    `nodes` - the list of nodes to be optimised
    `width` - the width of the display in pixels
    `height` - the height of the display in pixels

### FruchGraphLayout

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

  Constructs new FruchGraphLayout. If the FruchGraphLayout is passed a display, and a value for updateEveryN, it will call the display's updateDisplay() method updateEveryN on every Nth pass of the layout algorithm. This updating occurs within the current tick and is intended to provide visual feedback on the algorithm's convergence. However, this additional updating will slow the layout down dramatically when displaying large networks.

  Parameters:
    `surface` - the display surface to update
    `updateEveryN` - how often to update the display
    `nodes` - the list of nodes to be optimised
    `width` - the width of the display in pixels
    `height` - the height of the display in pixels

Method Detail

### setPad

    public void setPad(int p)

  Sets the number of pixels to shrink radius 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 shrink by

### setUpdateEveryN

    public void setUpdateEveryN(int updateEveryN)

  If the layout has been passed a display to update, and updateEveryN is greater than 0, the layout will update the display after every Nth pass through the algorithm.

  Parameters:
    `updateEveryN` - how often to update the display

### 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` - sets if layout will be rescaled

### 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` - sets if transitions will be animated

### setRandomSeed

    public void setRandomSeed(int seed)

  Sets the Random seed used in the intial random placement of the nodes. If the seed is not set, the current timestamp is used as the seed.

  Parameters:
    `seed` - the random seed for the initial random placement of the nodes

### randomizeLayout

    public void randomizeLayout()

  Randomly positions nodes on layout. Called internally before update layout is called for the first time to insure that nodes have starting coordinates. This uses a random generator stream separate from the default RePast random stream. You can set the seed for this stream using the setRandomSeed method.

### updateLayout

    public void updateLayout()

  Positions nodes in layout according to a modified implementation of the Fruchterman-Reingold graph layout algorithm. Nodes are positioned according to an iterative algorithm that assumes that nodes repel each other when close, but are attracted to connected nodes. Convergence is obtained by using a "simulated annealing"-style technique with an arbitrary cooling function. Acts on existing node positions, so randomizeLayout() will be called before first update. The default random seed for this initial layout is the current timestamp. The seed can, however, be set with the `setRandomSeed` method. The random stream for this initial layout is separate from RePast's default random stream.

  See, Fruchterman, T.M.J and Reingold, E.M. (1991) "Graph Drawing by Force-directed Placement" in Software-Practice and Experience, Vol 21(11), 1129-1164 Modified for code optimization. (Skye Bender-deMoll) Note at this point, this implementation does not take into account edge strengths

  ``

       pseudo code of implementation of Furchterman-Reingold Algorithm
       -----------------------------------------

       As implemented in Pajek, the algorithm makes initialIter (10) through
       the algorithm before starting the cooling function.  If this is the
       first layout, each nodes is given a random initial position.

       while temp > 0.5 and passes < maxIterations (500)
        //calculate repulsive forces between each node
        for v = 0 to numberOfNodes
          for u = v+1 to numberOfNodes
            calculate the distance vector between the positions of v and u
            calculate a displacement displaceVec = (distVec/|distVec|)
                                                     * repulsion(|distVec|)
            add displaceVec vector to v's displacement vector
            subtract displaceVec from u's displacement vector
          end
        end

        //calculate attractive forces
        for e = 0 to numberOfEdges
          get the nodes attached to the edge (v and u)
          calculate the distance vector between the positions of v and u
          calculate a displacement displaceVec = (distVec/|distVec|) * attraction(|distVec|)
          subtract displaceVec vector from v's displacement vector
          add displaceVec to u's displacement vector
        end

        calculate each nodes's displacement, but limit max displacement to temp

        //decrease temperature parameter
        coolTemp()

        if this is an Nth pass, update the layout on screen

        at the end, go over all the nodes to find the max and min of the coords,
        rescale all coords so that network will fill the display
       end while

        //repulsion function
        repulsion(distance) = (distance^2)/optimalDistance

       //attraction function attraction(distance) =
       (optimalDistance^2)/distance^2 (formula used in pajek)

        //cooling function
        coolTemp(temp) = unchanged for initialIter iterations, temp/1.1

       //optimal distance optimalDistance = 0.46*Math.sqrt(((width *
       height) / (nodeList.size()+1)))

  Additional comments: Because the original algorithm repositions the nodes in a deterministic order, highly structured / regular networks may exhibit rotations drift during the layout.

  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