package flare.vis.operator.layout
{
import flare.animate.Transitioner;
import flare.physics.Particle;
import flare.physics.Simulation;
import flare.physics.Spring;
import flare.vis.data.Data;
import flare.vis.data.DataSprite;
import flare.vis.data.EdgeSprite;
import flare.vis.data.NodeSprite;
/**
* Layout that places nodes 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 (set <code>Visualization.continuousUpdates = true
* </code>).
*
* <p>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 forces to the simulation may affect this.</p>
*
* <p>The force directed layout is implemented using the physics simulator
* provided by the <code>flare.physics</code> package. The
* <code>Simulation</code> used to drive this layout can be set explicitly,
* allowing any number of custom force directed layouts to be created
* through the selection of <code>IForce</code> modules. Each node in the
* layout is mapped to a <code>Particle</code> instance and each edge
* to a <code>Spring</code> in the simulation. Once the simulation has been
* initialized, you can retrieve these instances through the
* <code>node.props.particle</code> and <code>edge.props.spring</code>
* properties, respectively.</p>
*
* @see flare.physics
*/
public class ForceDirectedLayout extends Layout
{
private var _sim:Simulation;
private var _step:Number = 1;
private var _iter:int = 1;
private var _gen:uint = 0;
private var _enforceBounds:Boolean = false;
private var _mass:Number = 1;
private var _restLength:Number = 30;
private var _tension:Number = 0.3;
private var _damping:Number = 0.1;
/** The default mass value for node/particles. */
public function get defaultParticleMass():Number { return _mass; }
public function set defaultParticleMass(v:Number):void { _mass = v; }
/** The default spring rest length for edge/springs. */
public function get defaultSpringLength():Number { return _restLength; }
public function set defaultSpringLength(v:Number):void { _restLength = v; }
/** The default spring tension for edge/springs. */
public function get defaultSpringTension():Number { return _tension; }
public function set defaultSpringTension(v:Number):void { _tension = v; }
/** The number of iterations to run the simulation per invocation
* (default is 1, expecting continuous updates). */
public function get iterations():int { return _iter; }
public function set iterations(iter:int):void { _iter = iter; }
/** The number of time ticks to advance the simulation on each
* iteration (default is 1). */
public function get ticksPerIteration():int { return _step; }
public function set ticksPerIteration(ticks:int):void { _step = ticks; }
/** The physics simulation driving this layout. */
public function get simulation():Simulation { return _sim; }
/** Flag indicating if the layout bounds should be enforced.
* If true, the layoutBounds will limit node placement. */
public function get enforceBounds():Boolean { return _enforceBounds; }
public function set enforceBounds(b:Boolean):void { _enforceBounds = b; }
/**
* Creates a new ForceDirectedLayout.
* @param iterations the number of iterations to run the simulation
* per invocation
* @param sim the physics simulation to use for the layout. If null
* (the default), default simulation settings will be used
*/
public function ForceDirectedLayout(enforceBounds:Boolean=false,
iterations:int=1, sim:Simulation=null)
{
_enforceBounds = enforceBounds;
_iter = iterations;
_sim = (sim==null ? new Simulation(0, 0, 0.1, -10) : sim);
}
/** @inheritDoc */
protected override function layout():void
{
++_gen; init();
_sim.bounds = _enforceBounds ? layoutBounds : null;
for (var i:uint=0; i<_iter; ++i) {
_sim.tick(_step);
}
visualization.data.nodes.visit(update); updateEdgePoints(_t);
}
/**
* Transfer the physics simulation results to an item's layout.
* @param d a DataSprite
* @return true, to signal a visitor to continue
*/
protected function update(d:DataSprite):void
{
var p:Particle = d.props.particle;
if (!p.fixed) {
var o:Object = _t.$(d);
o.x = p.x;
o.y = p.y;
}
}
/**
* Initializes the Simulation for this ForceDirectedLayout
*/
protected function init():void
{
var data:Data = visualization.data, o:Object;
var p:Particle, s:Spring, n:NodeSprite, e:EdgeSprite;
for each (n in data.nodes) {
p = n.props.particle;
o = _t.$(n);
if (p == null) {
n.props.particle = (p = _sim.addParticle(_mass, o.x, o.y));
p.fixed = o.fixed;
} else {
p.x = o.x;
p.y = o.y;
p.fixed = o.fixed;
}
p.tag = _gen;
}
for each (e in data.edges) {
s = e.props.spring;
if (s == null) {
e.props.spring = (s = _sim.addSpring(
e.source.props.particle, e.target.props.particle,
_restLength, _tension, _damping));
}
s.tag = _gen;
}
if (mass != null) {
for each (n in data.nodes) {
p = n.props.particle;
p.mass = mass(n);
}
}
for each (e in data.edges) {
s = e.props.spring;
if (restLength != null)
s.restLength = restLength(e);
if (tension != null)
s.tension = tension(e);
if (damping != null)
s.damping = damping(e);
}
for each (p in _sim.particles)
if (p.tag != _gen) p.kill();
for each (s in _sim.springs)
if (s.tag != _gen) s.kill();
}
/**
* Function for assigning mass values to particles. By default, this
* simply returns the default mass value. This function can be replaced
* to perform custom mass assignment.
*/
public var mass:Function = function(d:DataSprite):Number {
return _mass;
}
/**
* Function for assigning rest length values to springs. By default,
* this simply returns the default rest length value. This function can
* be replaced to perform custom rest length assignment.
*/
public var restLength:Function = function(e:EdgeSprite):Number {
return _restLength;
}
/**
* Function for assigning tension values to springs. By default, this
* method computes spring tension adaptively, based on the connectivity
* of the attached particles, to create more stable layouts. More
* specifically, the tension is computed as the default tension value
* divided by the square root of the maximum degree of the attached
* particles. This function can be replaced to perform custom tension
* assignment.
*/
public var tension:Function = function(e:EdgeSprite):Number {
var s:Spring = Spring(e.props.spring);
var n:Number = Math.max(s.p1.degree, s.p2.degree);
return _tension / Math.sqrt(n);
}
/**
* Function for assigning damping constant values to springs. By
* default, this simply uses the spring's computed tension value
* divided by 10. This function can be replaced to perform custom
* damping assignment.
*/
public var damping:Function = function(e:EdgeSprite):Number {
return Spring(e.props.spring).tension / 10;
}
} }