com.hp.hpl.guess.layout
Class FruchGraphLayout

java.lang.Object
  edu.uci.ics.jung.visualization.AbstractLayout
      com.hp.hpl.guess.layout.FruchGraphLayout

All Implemented Interfaces:

ChangeEventSupport, Layout, VertexLocationFunction

public class FruchGraphLayout

extends AbstractLayout

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.1 $ $Date: 2005/10/05 20:19:39 $

Author:

Skye Bender-deMoll email:skyebend@santafe.edu

Field Summary

boolean

done

Constructor Summary

FruchGraphLayout(Graph g, boolean firstLayout, int width, int height)

Method Summary

void	actionPerformed(ActionEvent evt) Implements the ActionListener interface.
void	advancePositions() Positions nodes in layout according to a modified implementation of the Fruchterman-Reingold graph layout algorithm.
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	randomizeLayout() Randomly positions nodes on layout.
double	round(double a, double modx)
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	setUpdate(boolean doUpdate)
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.

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

FruchGraphLayout

public FruchGraphLayout(Graph g,
                        boolean firstLayout,
                        int width,
                        int height)

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

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.

advancePositions

public void advancePositions()

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.

round

public double round(double a,
                    double modx)

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()