using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Drawing;
using Netron.Diagramming.Core.Analysis;
using Netron.Diagramming.Core.Layout.Force;
namespace Netron.Diagramming.Core {
///
/// 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 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
/// components. Each node in the layout is
/// mapped to a instance and each edge
/// to a instance for storing the state
/// of the simulation. See the namespace for more.
///
class ForceDirectedLayout : LayoutBase {
#region Fields
private ForceSimulator m_fsim;
private long m_lasttime = -1L;
private long m_maxstep = 50L;
private bool m_runonce;
private int m_iterations = 100;
private bool mEnforceBounds;
BackgroundWorker worker;
protected INode referrer;
protected String m_nodeGroup;
protected String m_edgeGroup;
private Dictionary Pars;
#endregion
#region Properties
public long MaxTimeStep {
get { return m_maxstep; }
set { m_maxstep = value; }
}
public ForceSimulator getForceSimulator {
get { return m_fsim; }
set { m_fsim = value; }
}
public int Iterations {
get { return m_iterations; }
set {
if (value < 1)
throw new ArgumentException("The amount of iterations has to be bigger or equal to one.");
m_iterations = value;
}
}
#endregion
#region Constructor
///
///Default constructor
///
public ForceDirectedLayout(IController controller)
: base("ForceDirected Layout", controller) {
}
#endregion
#region Methods
///
/// Handles the DoWork event of the worker control.
///
/// The source of the event.
/// The instance containing the event data.
private void worker_DoWork(object sender, DoWorkEventArgs e) {
this.Controller.View.Suspend();
Init();
Layout();
this.Controller.View.Resume();
}
///
/// Runs this instance.
///
public override void Run() {
Run(2000);
}
///
/// Runs the specified time.
///
/// The time.
public override void Run(int time) {
worker = new BackgroundWorker();
worker.DoWork += new DoWorkEventHandler(worker_DoWork);
worker.RunWorkerAsync(time);
}
///
/// Stops this instance.
///
public override void Stop() {
if (worker != null && worker.IsBusy)
worker.CancelAsync();
}
///
/// Get the mass value associated with the given node. Subclasses should
/// override this method to perform custom mass assignment.
/// @param n the node for which to compute the mass value
/// @return the mass value for the node. By default, all items are given
/// a mass value of 1.0.
///
protected float getMassValue(INode n) {
return 1.0f;
}
///
/// Get the spring length for the given edge. Subclasses should
/// override this method to perform custom spring length assignment.
/// @param e the edge for which to compute the spring length
/// @return the spring length for the edge. A return value of
/// -1 means to ignore this method and use the global default.
///
protected float getSpringLength(IEdge e) {
return -1.0F;
}
///
/// 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.
/// @param e the edge for which to compute the spring coefficient.
/// @return the spring coefficient for the edge. A return value of
/// -1 means to ignore this method and use the global default.
///
protected float getSpringCoefficient(IEdge e) {
return -1.0F;
}
private bool Init() {
mEnforceBounds = false;
m_runonce = true;
m_fsim = new ForceSimulator();
m_fsim.AddForce(new NBodyForce());
m_fsim.AddForce(new SpringForce());
m_fsim.AddForce(new DragForce());
this.Graph = this.Model as IGraph;
if (Graph == null)
throw new InconsistencyException("The model has not been set and the Graph property is hence 'null'");
//Graph.ClearSpanningTree();
//Graph.MakeSpanningTree(LayoutRoot as INode);
if (Graph.Nodes.Count == 0)
return false;
if (Graph.Edges.Count == 0) //this layout is base on embedded springs in the connections
return false;
Pars = new Dictionary();
foreach (INode node in Nodes) {
Pars.Add(node.Uid.ToString(), new ForceItem());
}
return true;
}
///
/// Updates the node positions.
///
private void UpdateNodePositions() {
double x1 = 0, x2 = 0, y1 = 0, y2 = 0;
if (Bounds != null) {
x1 = Bounds.X; y1 = Bounds.Top;
x2 = Bounds.Right; y2 = Bounds.Bottom;
}
// update positions
foreach (INode item in Nodes) {
ForceItem fitem = Pars[item.Uid.ToString()];
if (item.IsFixed) {
// clear any force computations
fitem.Force[0] = 0.0f;
fitem.Force[1] = 0.0f;
fitem.Velocity[0] = 0.0f;
fitem.Velocity[1] = 0.0f;
if (Double.IsNaN(item.X)) {
setX(item, referrer, 0.0D);
setY(item, referrer, 0.0D);
}
continue;
}
double x = fitem.Location[0];
double y = fitem.Location[1];
//do we need to check the bounding constraints
if (mEnforceBounds && Bounds != null) {
double hw = item.Rectangle.Width / 2;
double hh = item.Rectangle.Height / 2;
if (x + hw > x2) x = x2 - hw;
if (x - hw < x1) x = x1 + hw;
if (y + hh > y2) y = y2 - hh;
if (y - hh < y1) y = y1 + hh;
}
// set the actual position
setX(item, referrer, x);
setY(item, referrer, y);
}
}
///
/// Reset the force simulation state for all nodes processed by this layout.
///
public void Reset() {
foreach (INode item in Nodes) {
ForceItem fitem = Pars[item.Uid.ToString()];
if (fitem != null) {
fitem.Location[0] = (float)item.X;
fitem.Location[1] = (float)item.Y;
fitem.Force[0] = fitem.Force[1] = 0;
fitem.Velocity[0] = fitem.Velocity[1] = 0;
}
}
m_lasttime = -1L;
}
///
/// Loads the simulator with all relevant force items and springs.
///
/// the force simulator driving this layout.
protected void InitializeSimulator(ForceSimulator fsim) {
//TODO: some checks here...?
float startX = (referrer == null ? 0f : (float)referrer.X);
float startY = (referrer == null ? 0f : (float)referrer.Y);
startX = float.IsNaN(startX) ? 0f : startX;
startY = float.IsNaN(startY) ? 0f : startY;
if (Nodes != null && Nodes.Count > 0) {
foreach (INode item in Nodes) {
ForceItem fitem = Pars[item.Uid.ToString()];
fitem.Mass = getMassValue(item);
double x = item.X;
double y = item.Y;
fitem.Location[0] = (Double.IsNaN(x) ? startX : (float)x);
fitem.Location[1] = (Double.IsNaN(y) ? startY : (float)y);
fsim.addItem(fitem);
}
}
if (Edges != null && Edges.Count > 0) {
foreach (IEdge e in Edges) {
INode n1 = e.SourceNode;
if (n1 == null) continue;
ForceItem f1 = Pars[n1.Uid.ToString()];
INode n2 = e.TargetNode;
if (n2 == null) continue;
ForceItem f2 = Pars[n2.Uid.ToString()];
float coeff = getSpringCoefficient(e);
float slen = getSpringLength(e);
fsim.addSpring(f1, f2, (coeff >= 0 ? coeff : -1.0F), (slen >= 0 ? slen : -1.0F));
}
}
}
private void Layout() {
// perform different actions if this is a run-once or
// run-continuously layout
if (m_runonce) {
PointF anchor = new PointF(Bounds.Width / 2F, Bounds.Height / 2F);
foreach (INode node in Nodes) {
setX(node, null, anchor.X);
setY(node, null, anchor.Y);
}
m_fsim.Clear();
long timestep = 1000L;
InitializeSimulator(m_fsim);
for (int i = 0; i < m_iterations; i++) {
// use an annealing schedule to set time step
timestep *= Convert.ToInt64(1.0 - i / (double)m_iterations);
long step = timestep + 50;
// run simulator
m_fsim.RunSimulator(step);
// debugging output
//if (i % 10 == 0 ) {Trace.WriteLine("iter: "+i);}
}
UpdateNodePositions();
} else {
// get timestep
if (m_lasttime == -1)
m_lasttime = DateTime.Now.Ticks * 10 - 20;
long time = DateTime.Now.Ticks * 10;//how many milliseconds since the human race started to count things
long timestep = Math.Min(m_maxstep, time - m_lasttime);
m_lasttime = time;
// run force simulator
m_fsim.Clear();
InitializeSimulator(m_fsim);
m_fsim.RunSimulator(timestep);
UpdateNodePositions();
}
//if ( frac == 1.0 ) {
// reset();
//}
}
#endregion
}
}