prefuse.action.layout.graph
Class ForceDirectedLayout

java.lang.Object
  extended by prefuse.activity.Activity
      extended by prefuse.action.Action
          extended by prefuse.action.GroupAction
              extended by prefuse.action.layout.Layout
                  extended by prefuse.action.layout.graph.ForceDirectedLayout

public class ForceDirectedLayout
extends Layout

Layout that positions graph elements based on a physics simulation of interacting forces; by default, nodes repel each other, edges act as springs, and drag forces (similar to air resistance) are applied. This algorithm can be run for multiple iterations for a run-once layout computation or repeatedly run in an animated fashion for a dynamic and interactive layout.

The running time of this layout algorithm is the greater of O(N log N) and O(E), where N is the number of nodes and E the number of edges. The addition of custom force calculation modules may, however, increase this value.

The ForceSimulator used to drive this layout can be set explicitly, allowing any number of custom force directed layouts to be created through the user's selection of included Force components. Each node in the layout is mapped to a ForceItem instance and each edge to a Spring instance for storing the state of the simulation. See the prefuse.util.force package for more.

Author:
jeffrey heer

Field Summary
static java.lang.String FORCEITEM
          The data field in which the parameters used by this layout are stored.
static Schema FORCEITEM_SCHEMA
          The schema for the parameters used by this layout.
protected  java.lang.String m_edgeGroup
           
protected  java.lang.String m_nodeGroup
           
protected  VisualItem referrer
           
 
Fields inherited from class prefuse.action.layout.Layout
m_anchor, m_bounds, m_bpts, m_insets, m_margin, m_tmpa, m_tmpb
 
Fields inherited from class prefuse.action.GroupAction
m_group
 
Fields inherited from class prefuse.action.Action
m_vis
 
Fields inherited from class prefuse.activity.Activity
DEFAULT_STEP_TIME, INFINITY
 
Constructor Summary
ForceDirectedLayout(java.lang.String graph)
          Create a new ForceDirectedLayout.
ForceDirectedLayout(java.lang.String group, boolean enforceBounds)
          Create a new ForceDirectedLayout.
ForceDirectedLayout(java.lang.String group, boolean enforceBounds, boolean runonce)
          Create a new ForceDirectedLayout.
ForceDirectedLayout(java.lang.String group, ForceSimulator fsim, boolean enforceBounds)
          Create a new ForceDirectedLayout.
ForceDirectedLayout(java.lang.String group, ForceSimulator fsim, boolean enforceBounds, boolean runonce)
          Create a new ForceDirectedLayout.
 
Method Summary
 ForceSimulator getForceSimulator()
          Get the force simulator driving this layout.
 int getIterations()
          Get the number of iterations to use when computing a layout in run-once mode.
protected  float getMassValue(VisualItem n)
          Get the mass value associated with the given node.
 long getMaxTimeStep()
          Get the maximum timestep allowed for integrating node settings between runs of this layout.
 VisualItem getReferrer()
          Get the referrer item to use to set x or y coordinates that are initialized to NaN.
protected  float getSpringCoefficient(EdgeItem e)
          Get the spring coefficient for the given edge, which controls the tension or strength of the spring.
protected  float getSpringLength(EdgeItem e)
          Get the spring length for the given edge.
protected  void initSimulator(ForceSimulator fsim)
          Loads the simulator with all relevant force items and springs.
 void reset()
          Reset the force simulation state for all nodes processed by this layout.
 void run(double frac)
          Runs this Action, triggering whatever processing this Action performs.
 void setDataGroups(java.lang.String nodeGroup, java.lang.String edgeGroup)
          Explicitly sets the node and edge groups to use for this layout, overriding the group setting passed to the constructor.
 void setForceSimulator(ForceSimulator fsim)
          Set the force simulator driving this layout.
 void setIterations(int iter)
          Set the number of iterations to use when computing a layout in run-once mode.
 void setMaxTimeStep(long maxstep)
          Set the maximum timestep allowed for integrating node settings between runs of this layout.
 void setReferrer(VisualItem referrer)
          Set the referrer item to use to set x or y coordinates that are initialized to NaN.
 
Methods inherited from class prefuse.action.layout.Layout
getLayoutAnchor, getLayoutBounds, setLayoutAnchor, setLayoutBounds, setMargin, setX, setY
 
Methods inherited from class prefuse.action.GroupAction
getGroup, setGroup
 
Methods inherited from class prefuse.action.Action
getVisualization, run, setVisualization
 
Methods inherited from class prefuse.activity.Activity
addActivityListener, alwaysRunAfter, cancel, fireActivityCancelled, fireActivityFinished, fireActivityScheduled, fireActivityStarted, fireActivityStepped, getDuration, getNextTime, getPace, getPacingFunction, getStartTime, getStepTime, getStopTime, isEnabled, isRunning, isScheduled, removeActivityListener, run, runAfter, runAt, setDuration, setEnabled, setPacingFunction, setStartTime, setStepTime
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

referrer

protected transient VisualItem referrer

m_nodeGroup

protected java.lang.String m_nodeGroup

m_edgeGroup

protected java.lang.String m_edgeGroup

FORCEITEM

public static final java.lang.String FORCEITEM
The data field in which the parameters used by this layout are stored.

See Also:
Constant Field Values

FORCEITEM_SCHEMA

public static final Schema FORCEITEM_SCHEMA
The schema for the parameters used by this layout.

Constructor Detail

ForceDirectedLayout

public ForceDirectedLayout(java.lang.String graph)
Create a new ForceDirectedLayout. By default, this layout will not restrict the layout to the layout bounds and will assume it is being run in animated (rather than run-once) fashion.

Parameters:
graph - the data group to layout. Must resolve to a Graph instance.

ForceDirectedLayout

public ForceDirectedLayout(java.lang.String group,
                           boolean enforceBounds)
Create a new ForceDirectedLayout. The layout will assume it is being run in animated (rather than run-once) fashion.

Parameters:
group - the data group to layout. Must resolve to a Graph instance.
enforceBounds - indicates whether or not the layout should require that all node placements stay within the layout bounds.

ForceDirectedLayout

public ForceDirectedLayout(java.lang.String group,
                           boolean enforceBounds,
                           boolean runonce)
Create a new ForceDirectedLayout.

Parameters:
group - the data group to layout. Must resolve to a Graph instance.
enforceBounds - indicates whether or not the layout should require that all node placements stay within the layout bounds.
runonce - indicates if the layout will be run in a run-once or animated fashion. In run-once mode, the layout will run for a set number of iterations when invoked. In animation mode, only one iteration of the layout is computed.

ForceDirectedLayout

public ForceDirectedLayout(java.lang.String group,
                           ForceSimulator fsim,
                           boolean enforceBounds)
Create a new ForceDirectedLayout. The layout will assume it is being run in animated (rather than run-once) fashion.

Parameters:
group - the data group to layout. Must resolve to a Graph instance.
fsim - the force simulator used to drive the layout computation
enforceBounds - indicates whether or not the layout should require that all node placements stay within the layout bounds.

ForceDirectedLayout

public ForceDirectedLayout(java.lang.String group,
                           ForceSimulator fsim,
                           boolean enforceBounds,
                           boolean runonce)
Create a new ForceDirectedLayout.

Parameters:
group - the data group to layout. Must resolve to a Graph instance.
fsim - the force simulator used to drive the layout computation
enforceBounds - indicates whether or not the layout should require that all node placements stay within the layout bounds.
runonce - indicates if the layout will be run in a run-once or animated fashion. In run-once mode, the layout will run for a set number of iterations when invoked. In animation mode, only one iteration of the layout is computed.
Method Detail

getMaxTimeStep

public long getMaxTimeStep()
Get the maximum timestep allowed for integrating node settings between runs of this layout. When computation times are longer than desired, and node positions are changing dramatically between animated frames, the max step time can be lowered to suppress node movement.

Returns:
the maximum timestep allowed for integrating between two layout steps.

setMaxTimeStep

public void setMaxTimeStep(long maxstep)
Set the maximum timestep allowed for integrating node settings between runs of this layout. When computation times are longer than desired, and node positions are changing dramatically between animated frames, the max step time can be lowered to suppress node movement.

Parameters:
maxstep - the maximum timestep allowed for integrating between two layout steps

getForceSimulator

public ForceSimulator getForceSimulator()
Get the force simulator driving this layout.

Returns:
the force simulator

setForceSimulator

public void setForceSimulator(ForceSimulator fsim)
Set the force simulator driving this layout.

Parameters:
fsim - the force simulator

getIterations

public int getIterations()
Get the number of iterations to use when computing a layout in run-once mode.

Returns:
the number of layout iterations to run

setIterations

public void setIterations(int iter)
Set the number of iterations to use when computing a layout in run-once mode.

Parameters:
iter - the number of layout iterations to run

setDataGroups

public void setDataGroups(java.lang.String nodeGroup,
                          java.lang.String edgeGroup)
Explicitly sets the node and edge groups to use for this layout, overriding the group setting passed to the constructor.

Parameters:
nodeGroup - the node data group
edgeGroup - the edge data group

run

public void run(double frac)
Description copied from class: Action
Runs this Action, triggering whatever processing this Action performs. Subclass this method to create custom Actions.

Specified by:
run in class GroupAction
Parameters:
frac - the fraction of this Action's duration that has elapsed.
See Also:
Action.run(double)

reset

public void reset()
Reset the force simulation state for all nodes processed by this layout.


initSimulator

protected void initSimulator(ForceSimulator fsim)
Loads the simulator with all relevant force items and springs.

Parameters:
fsim - the force simulator driving this layout

getMassValue

protected float getMassValue(VisualItem n)
Get the mass value associated with the given node. Subclasses should override this method to perform custom mass assignment.

Parameters:
n - the node for which to compute the mass value
Returns:
the mass value for the node. By default, all items are given a mass value of 1.0.

getSpringLength

protected float getSpringLength(EdgeItem e)
Get the spring length for the given edge. Subclasses should override this method to perform custom spring length assignment.

Parameters:
e - the edge for which to compute the spring length
Returns:
the spring length for the edge. A return value of -1 means to ignore this method and use the global default.

getSpringCoefficient

protected float getSpringCoefficient(EdgeItem e)
Get the spring coefficient for the given edge, which controls the tension or strength of the spring. Subclasses should override this method to perform custom spring tension assignment.

Parameters:
e - the edge for which to compute the spring coefficient.
Returns:
the spring coefficient for the edge. A return value of -1 means to ignore this method and use the global default.

getReferrer

public VisualItem getReferrer()
Get the referrer item to use to set x or y coordinates that are initialized to NaN.

Returns:
the referrer item.
See Also:
PrefuseLib.setX(VisualItem, VisualItem, double), PrefuseLib.setY(VisualItem, VisualItem, double)

setReferrer

public void setReferrer(VisualItem referrer)
Set the referrer item to use to set x or y coordinates that are initialized to NaN.

Parameters:
referrer - the referrer item to use.
See Also:
PrefuseLib.setX(VisualItem, VisualItem, double), PrefuseLib.setY(VisualItem, VisualItem, double)


Copyright 2007 Regents of the University of California