Class ForceDirectedLayout

GoDiagram®
v10.0.8
by Northwoods Software®

Force-directed layout treats the graph as if it were a system of physical bodies with repulsive electrical, attractional gravitational, and spring forces acting on them and between them.

Inheritance

object

Layout

NetworkLayout<ForceDirectedNetwork, ForceDirectedVertex, ForceDirectedEdge, ForceDirectedLayout>

ForceDirectedLayout

Namespace: Northwoods.Go.Layouts

Assembly: Northwoods.GoDiagram.WinForms.ForceDirectedLayout.dll

Syntax

public class ForceDirectedLayout : NetworkLayout<ForceDirectedNetwork, ForceDirectedVertex, ForceDirectedEdge, ForceDirectedLayout>

Remarks

Electrical forces come both from the field at the vertex's location as well as from neighboring vertexes and are quadratic by distance. Gravitational forces come from the field at the vertex's location and are constant. Spring forces are only exerted between two different vertexes that are connected by an edge and are linear by distance.

The electrical forces on a vertex are the sum of the electrical charge times the electrical field at that location (ElectricalCharge(ForceDirectedVertex), ElectricalFieldX(double, double), ElectricalFieldY(double, double)) and the electrical forces of all nearby vertexes divided by the square of the distance between them. You can easily assign the electrical charge for all vertexes by assigning DefaultElectricalCharge. By default there is no electrical field, so all forces are due to nearby charged vertexes. For efficiency, InfinityDistance determines a cut-off distance between vertexes for which to consider any influence.

The gravitational forces on a vertex are the sum of the gravitational mass times the gravitational field at that location (GravitationalMass(ForceDirectedVertex), GravitationalFieldX(double, double), GravitationalFieldY(double, double)). You can easily assign the gravitational mass for all vertexes by assigning DefaultGravitationalMass. By default there is no gravitational field.

The spring forces on a vertex are only exerted by the edges connecting it with other vertexes. The force along an edge is the stiffness of the spring times the difference of the distance between the vertexes and the nominal length of the spring (SpringStiffness(ForceDirectedEdge), SpringLength(ForceDirectedEdge)) divided by the distance between the vertexes. When the distance is less than the nominal length, the force pushes the vertexes apart; when the distance is greater, the force pulls them together. You can easily assign the spring length and stiffness for all edges by assigning DefaultSpringLength and DefaultSpringStiffness.

When the distance between two vertexes is less than one unit, this uses a random number generator to decide which direction the forces should go. For layouts that start with all of the vertexes at the same location, this results in potentially dramatically different results. Set RandomNumberGenerator to null in order to produce reproducible results given the same initial vertex locations.

The algorithm seeks a configuration of the bodies with locally minimal energy, i.e. vertex positions such that the sum of the forces on each vertex is zero. This is achieved by repeatedly computing the forces on each vertex, moving them, and repeating. Computations stop when no vertex moves more than EpsilonDistance or when MaxIterations have happened.

The layout cannot guarantee that it provides optimal positioning of nodes. Nodes will normally not overlap each other, but when there is a dense interconnectivity overlaps might not be avoidable.

If you want to experiment interactively with most of the properties, try the Force Directed Layout sample. See samples that make use of ForceDirectedLayout in the samples index.

This layout makes use of a Network<V, E, Y> of ForceDirectedVertexes and ForceDirectedEdges that normally correspond to the Nodes and Links of the Diagram.

Constructors

ForceDirectedLayout()

Constructs a ForceDirectedLayout with no Network and with no owning Diagram.

Declaration

public ForceDirectedLayout()

Properties

ArrangementSpacing

Gets or sets the space between which the layout will position the connected graphs that together compose the network.

Declaration

public Size ArrangementSpacing { get; set; }

Property Value

Type	Description
Size

Remarks

This defaults to Size(100, 100). These distances are used during a clustered layout; afterwards the normal force-directed layout will likely cause the size of any space between connected graphs to change, perhaps considerably.

ArrangesToOrigin

Gets or sets whether CommitNodes() should move all of the nodes so that the nodes all fit with the top-left corner at the ArrangementOrigin.

Declaration

public bool ArrangesToOrigin { get; set; }

Property Value

Type	Description
bool

Remarks

By default this is false -- the ArrangementOrigin is ignored. When this is true, nodes are moved even though IsFixed(ForceDirectedVertex) was true.

Comments

Gets or sets whether this layout should find all Nodes whose category is "Comment" and whose anchors are nodes represented in the network, and add ForceDirectedVertexes representing those balloon comments as nodes in the network.

Declaration

public bool Comments { get; set; }

Property Value

Type	Description
bool

Remarks

The default value is false.

CurrentIteration

This read-only property returns the current iteration count, valid during a call to DoLayout(IEnumerable<Part>).

Declaration

public int CurrentIteration { get; }

Property Value

Type	Description
int

DefaultCommentElectricalCharge

Gets or sets the default value computed by ElectricalCharge(ForceDirectedVertex).

Declaration

public double DefaultCommentElectricalCharge { get; set; }

Property Value

Type	Description
double

Remarks

The initial value is 5.

DefaultCommentSpringLength

Gets or sets the default value computed by SpringLength(ForceDirectedEdge).

Declaration

public double DefaultCommentSpringLength { get; set; }

Property Value

Type	Description
double

Remarks

The initial value is 10.

DefaultElectricalCharge

Gets or sets the default value computed by ElectricalCharge(ForceDirectedVertex).

Declaration

public double DefaultElectricalCharge { get; set; }

Property Value

Type	Description
double

Remarks

The initial value is 150.

DefaultGravitationalMass

Gets or sets the default value computed by GravitationalMass(ForceDirectedVertex).

Declaration

public double DefaultGravitationalMass { get; set; }

Property Value

Type	Description
double

Remarks

The initial value is zero.

DefaultSpringLength

Gets or sets the default value computed by SpringLength(ForceDirectedEdge).

Declaration

public double DefaultSpringLength { get; set; }

Property Value

Type	Description
double

Remarks

The initial value is 50.

DefaultSpringStiffness

Gets or sets the default value computed by SpringStiffness(ForceDirectedEdge).

Declaration

public double DefaultSpringStiffness { get; set; }

Property Value

Type	Description
double

Remarks

The initial value is 0.05.

EpsilonDistance

Gets or sets approximately how far a node must move in order for the iterations to continue.

Declaration

public double EpsilonDistance { get; set; }

Property Value

Type	Description
double

Remarks

The default value is 1. The value must be larger than zero.

InfinityDistance

Gets or sets a threshold for the distance beyond which the electrical charge forces may be ignored.

Declaration

public double InfinityDistance { get; set; }

Property Value

Type	Description
double

Remarks

The default value is 1000. The value must be larger than 1.

MaxIterations

Gets or sets the maximum number of iterations to perform when doing the force-directed auto layout.

Declaration

public int MaxIterations { get; set; }

Property Value

Type	Description
int

Remarks

The default value is 100. The value must be non-negative.

MoveLimit

Gets or sets how far a vertex may be moved in an iteration.

Declaration

public double MoveLimit { get; set; }

Property Value

Type	Description
double

Remarks

The default value is 10. The value must be larger than 1.

RandomNumberGenerator

Gets or sets a random number generator.

Declaration

public Random RandomNumberGenerator { get; set; }

Property Value

Type	Description
Random

Remarks

The default value is a Random. Change this to null in order to use an instance of an internal repeatable pseudo-random number generator, which will become the new value of this property.

The new value must be either null or a Random object.

SetsPortSpots

Gets or sets whether the fromSpot and the toSpot of every Link should be set to Default.

Declaration

public bool SetsPortSpots { get; set; }

Property Value

Type	Description
bool

Remarks

The default value is true.

Methods

AddComments(ForceDirectedVertex)

Find any associated objects to be positioned along with the Node.

Declaration

public virtual void AddComments(ForceDirectedVertex v)

Parameters

Type	Name	Description
ForceDirectedVertex	v

Remarks

This method is called for each vertex in the network, when Comments is true. The standard behavior is to look for Nodes whose Category is "Comment" and that refer to the Node. By default this method will not be called unless you set Comments to true.

You may want to override this method in order to customize how any associated objects are found and how a new ForceDirectedVertex and ForceDirectedEdge may be added to the network to represent the (balloon?) comment. This method sets the new vertex's Charge to the value of DefaultCommentElectricalCharge, and sets the new edge's Length to the value of DefaultCommentSpringLength.

CommitLayout()

Set the FromSpot and ToSpot on each Link, position each Node according to the vertex position, and then position/route the Links.

Declaration

protected override void CommitLayout()

Overrides

Northwoods.Go.Layouts.NetworkLayout<Northwoods.Go.Layouts.ForceDirectedNetwork, Northwoods.Go.Layouts.ForceDirectedVertex, Northwoods.Go.Layouts.ForceDirectedEdge, Northwoods.Go.Layouts.ForceDirectedLayout>.CommitLayout()

Remarks

This calls the CommitNodes() and CommitLinks() methods, the latter only if IsRouting is true. You should not call this method -- it is a "protected virtual" method. Please read the Introduction page on Extensions for how to override methods and how to call this base method.

CommitLinks()

Routes the links.

Declaration

protected virtual void CommitLinks()

Remarks

This is called by CommitLayout(). This is only called if IsRouting is true. Please read the Introduction page on Extensions for how to override methods and how to call this base method.

Declaration

protected virtual void CommitNodes()

Remarks

This is called by CommitLayout(). Please read the Introduction page on Extensions for how to override methods and how to call this base method.

DoLayout(IEnumerable<Part>)

Perform the force-directed layout.

Declaration

public override void DoLayout(IEnumerable<Part> coll = null)

Parameters

Type	Name	Description
IEnumerable<Part>	coll

Overrides

Layout.DoLayout(IEnumerable<Part>)

Remarks

This removes any reflexive edges in the network, since they should be ignored.

For each vertex this calls and remembers the result of ElectricalCharge(ForceDirectedVertex) as the Charge and the result of GravitationalMass(ForceDirectedVertex) as the Mass.

For each edge this calls and remembers the result of SpringStiffness(ForceDirectedEdge) as the Stiffness and the result of SpringLength(ForceDirectedEdge) as the Length.

This then iterates, updating the position of each vertex according to the forces upon it, until reaching MaxIterations or until no vertex moves more than about EpsilonDistance.

Finally this calls UpdateParts() to commit the Node positions from the vertex positions. UpdateParts() calls CommitLayout() within a transaction.

ElectricalCharge(ForceDirectedVertex)

Returns the charge of the vertex, the value of Charge if it's a number, or else the value of DefaultElectricalCharge.

Declaration

public virtual double ElectricalCharge(ForceDirectedVertex v)

Parameters

Type	Name	Description
ForceDirectedVertex	v

Returns

Type	Description
double

Remarks

The electrical forces between two vertexes decrease by the square of the distance between them. Vertexes that are more than InfinityDistance apart are assumed to have no electrical charge effect on each other.

Please read the Introduction page on Extensions for how to override methods and how to call this base method.

ElectricalFieldX(double, double)

Returns the electrical field in the X direction acting on a vertex at the given point.

Declaration

protected virtual double ElectricalFieldX(double x, double y)

Parameters

Type	Name	Description
double	x
double	y

Returns

Type	Description
double	the default implementation returns zero.

Remarks

By default there is no electrical field at any location.

Used to define an external electrical field at a point independent of the vertex charges. A vertex L is acted upon by a force in the X direction of proportional to ElectricalFieldX(L.Center.X, L.Center.Y) * ElectricalCharge(L). Please read the Introduction page on Extensions for how to override methods and how to call this base method.

ElectricalFieldY(double, double)

Returns the electrical field in the Y direction acting on a vertex at the given point.

Declaration

protected virtual double ElectricalFieldY(double x, double y)

Parameters

Type	Name	Description
double	x
double	y

Returns

Type	Description
double	the default implementation returns zero.

Remarks

By default there is no electrical field at any location.

Used to define an external electrical field at a point independent of the vertex charges. A vertex L is acted upon by a force in the Y direction of proportional to ElectricalFieldY(L.Center.X, L.Center.Y) * ElectricalCharge(L). Please read the Introduction page on Extensions for how to override methods and how to call this base method.

GravitationalFieldX(double, double)

This returns the gravitational field in the X direction acting on a vertex at the given point.

Declaration

public virtual double GravitationalFieldX(double x, double y)

Parameters

Type	Name	Description
double	x
double	y

Returns

Type	Description
double	the default implementation returns zero.

Remarks

By default there is no gravitational field at any location.

Used to define an external gravitational field at a point independent of the vertex masses. A vertex L is acted upon by a force in the X direction of proportional to GravitationalFieldX(L.Center.X, L.Center.Y) * GravitationalMass(L). Please read the Introduction page on Extensions for how to override methods and how to call this base method.

GravitationalFieldY(double, double)

This returns the gravitational field in the Y direction acting on a vertex at the given point.

Declaration

public virtual double GravitationalFieldY(double x, double y)

Parameters

Type	Name	Description
double	x
double	y

Returns

Type	Description
double	the default implementation returns zero.

Remarks

By default there is no gravitational field at any location.

Used to define an external gravitational field at a point independent of the vertex masses. A vertex L is acted upon by a force in the Y direction of proportional to GravitationalFieldY(L.Center.X, L.Center.Y) * GravitationalMass(L). Please read the Introduction page on Extensions for how to override methods and how to call this base method.

GravitationalMass(ForceDirectedVertex)

Returns the mass of the vertex, the value of Mass if it's a number, or else the value of DefaultGravitationalMass.

Declaration

public virtual double GravitationalMass(ForceDirectedVertex v)

Parameters

Type	Name	Description
ForceDirectedVertex	v

Returns

Type	Description
double

Remarks

Please read the Introduction page on Extensions for how to override methods and how to call this base method.

IsFixed(ForceDirectedVertex)

This predicate returns true if the vertex should not be moved by the layout algorithm but still have an effect on nearby and connected vertexes.

Declaration

public virtual bool IsFixed(ForceDirectedVertex v)

Parameters

Type	Name	Description
ForceDirectedVertex	v

Returns

Type	Description
bool	returns true if the node should not be moved by the layout algorithm.

Remarks

The default implementation returns IsFixed. Please read the Introduction page on Extensions for how to override methods and how to call this base method.

MoveFixedVertex(ForceDirectedVertex)

Maybe move a vertex that IsFixed(ForceDirectedVertex).

Declaration

public virtual void MoveFixedVertex(ForceDirectedVertex v)

Parameters

Type	Name	Description
ForceDirectedVertex	v

Remarks

This is called each iteration on each such vertex. By default this does nothing.

SpringLength(ForceDirectedEdge)

Returns the length of the spring representing an edge.

Declaration

public virtual double SpringLength(ForceDirectedEdge e)

Parameters

Type	Name	Description
ForceDirectedEdge	e

Returns

Type	Description
double	Returns the length of the edge representing a link, the value of Length if it's a number, or else the value of DefaultSpringLength.

Remarks

The two vertexes connected by the edge E are acted upon by a force of proportional to SpringStiffness(E) * (GetNodeDistance(E.FromVertex, E.ToVertex) - SpringLength(E)) divided by the distance between the vertexes. Please read the Introduction page on Extensions for how to override methods and how to call this base method.

SpringStiffness(ForceDirectedEdge)

Returns the stiffness of the spring representing an edge.

Declaration

public virtual double SpringStiffness(ForceDirectedEdge e)

Parameters

Type	Name	Description
ForceDirectedEdge	e

Returns

Type	Description
double	Returns the stiffness of the edge representing a link, the value of Stiffness if it's a number, or else the value of DefaultSpringStiffness.

Remarks

The spring force between two vertexes connected by an edge is linearly proportional by distance to the difference between the SpringLength(ForceDirectedEdge) and the distance. When the distance is greater than the length, the force pulls the vertexes closer to each other. When the distance is less than the length, the force pushes them apart.