﻿ Force Directed Layouts
Nevron Open Vision Documentation
Diagram / Layouts / Graph Layouts / Force Directed Layouts / Force Directed Layouts
In This Topic
Force Directed Layouts
In This Topic

Force directed algorithms use a physical analogy to arrange graphs. All types of force directed layouts derive from the abstract NForceDirectedLayout class.

Force directed layouts view the graph as a system of bodies with forces acting between the bodies. The force directed layout algorithm seeks a configuration of the bodies with locally minimum energy - that is a position for each body, such that the sum of the forces on each body is zero. Such configuration is called equilibrium configuration. Generally all force directed layouts are defined by two parts:

• Model - a force system defined by the vertices and edges, which provides a physical model for the graph.
• Algorithm - the method used to find an equilibrium configuration for the defined system.
Model

The model of a force directed layout consists of forces. All types of forces, which can be used in the force directed layout, derive from the base NForce class. From a force directed layout point of view a force can be of one or more of the following types:

• Edge force - acts on a pair of connected vertices (for example: the spring and the magnetic field forces are edge forces).
• Vertex force - acts on each distinct pair of vertices (for example: the electrical and bounce back forces are vertex forces).
• Global force - acts globally on the graph (for example: the gravity force is a global force).

The force model of each force directed layout can be logically separated in two parts:

• Primary model - the primary force model is the set of forces, which a specific force directed layout has created and enabled by default. For example: the spring layout primary force model consists of an electrical force and a spring force, which are by default enabled.
• Optional model - the optional force model is common for all types of force directed layouts. It consists of forces created by the base NForceDirectedLayout class and is disabled by default. Currently the optional force model contains the following set of forces:

1. Magnetic field force - this is an edge force, which tries to impose an edge orientation constraint. It is represented by the NMagneticFieldForce class, an instance of which is accessible from the MagneticFieldForce property.

2. Gravity force - this is a global force, which simulates a gravity attraction to the current barycenter of the graph. It is represented by the NGravityForce class, an instance of which is accessible from the GravityForce property.

3. Bounce back force - this is a vertices force, which simulates repulsion between overlapping vertices. It is represented by the NBounceBackForce class, an instance of which is accessible from the BounceBackForce property.
Algorithm

The NForceDirectedLayout class implements an iterative algorithm, which tries to reach an equilibrium configuration in a finite set of passes and iterations. Following is a brief description:

1. Fixed vertex placement
The layout starts by placing the fixed vertices first. Fixed vertices are such vertices, which cannot be moved in both the X and Y direction by forces (see Supplemental Data below). The placement of fixed vertices is controlled by an instance of the NFixedVertexPlacement class, accessible from the FixedVertexPlacement property.
2. Free vertex placement
Once the fixed vertices are placed the layout places the free vertices. Free vertices are such vertices, which can be moved in X and/or Y direction by forces. The placement of free vertices is controlled by an instance of the NFreeVertexPlacement class, accessible from the FreeVertexPlacement property. If the X or Y movement of a vertex is locked, the vertex is placed freely only in the other direction.
3. Enabled force model extraction
At this step the force directed layout extracts the force model, which is currently enabled. As mentioned above this is by default the primary model. It then computes the count of needed passes the layout must perform to active all enabled forces.

Whether or not a force is enabled is controlled by the Enabled property of each force.

The activation pass of each force is controlled by the ActivationPass property of each force. By default the primary model is activated on the first pass (0), while the optional model, if enabled is by default activated on the second pass (1). The idea is that if an optional force is enabled the algorithm first gives the graph a single pass to "relax" and then performs the adjustments on the second pass.
4. Iteration phase
The iteration phase is repeated until all enabled forces are activated (one iteration phase for each pass). At each iteration phase the algorithm tries to reach equilibrium in the number of iterations specified by the MaxIterations property.
5. End conditions - the layout ends if one of the following events comes true:
• An equilibrium is found - i.e. when all forces in the system are smaller than the force specified by the StopForce property.
• The number of iterations performed exceeds the value of the MaxIterations property.
• The time elapsed exceeds the value of the MaxTime property (it is specified in milliseconds).
• The user has canceled the Iteration phase in the IterationCompleted event.
At each iteration the algorithm first accumulates the forces acting on all vertices and then ask the environment to apply them (actually move the vertices). The environment is represented by an instance of the NForceEnvironment class, accessible from the ForceEnvironment property (see below).

The layout will raise the IterationCompleted event after each iteration. This is a cancelable event. Canceling this event aborts the current iteration phase.

It also raises the PassCompleted event after each pass. This is a cancelable event. Canceling this event aborts the current pass.
Supplemental Data

The supplemental data supported by force directed layouts is split into two parts:

1. Common data
The common data is used by all types of force directed layouts regardless of the current set of enabled forces. Following is a list of the common data body properties:

ForceXMoveable - a boolean value, which indicates whether forces can move the body in the X direction. In the shape layout data it is controlled by the ForceXMoveable property.

ForceYMoveable - a boolean value, which indicates whether forces can move the body in the Y direction. In the shape layout data it is controlled by the ForceYMoveable property.
2. Force data
The force data is the supplemental data, which each force may support, if enabled. It is force specific. Following is a list of the force data body properties:

SpringStiffness - a single value, which defines the spring stiffness of an edge. Supported by spring force. If not specifies the default stiffness is used.

SpringLength - a single value, which defines the spring length of an edge. Supported by spring force. If not specifies the default spring length is used.

MagnetizationType - a value from the ENMagnetizationType enumeration, which defines the way in which an edge interacts with a magnetic field. Supported by magnetic field force. If not specifies the default magnetization type is used.

ElectricalCharge - a single value, which defines the electrical charge of a vertex. Supported by electrical force. If not specified the default electrical charge of 1.0f will be used.

Mass - a single value, which defines the mass (weight) of a vertex. Supported by barycenter force. If not specified the default mass of 1.0f will be used.

In Nevron Diagram these properties are members of the NLayoutData element, accessible from the LayoutData property of each shape.

Force Environment

The environment in which forces operate is encapsulated in the NForceEnvironment class, an instance of which can be obtained from the Environment property of the NForceDirectedLayout class.

The primary goal of the environment is to determine what fraction of the force accumulated on each iteration phase must be applied to the vertices. This is controlled in three ways:

• Magnitude
The magnitude factor is controlled by the XMagnitudeFactor and YMagnitudeFactor properties of the environment. The magnitude is constant throughout each iteration and is generally chosen to be in the range (0-1]. Small magnitude factors are used when you want to ensure the stability of the layout. Large magnitude factors must be used when you want to speed up the layout.
• Local temperature
If the UseLocalTemperature property is set to true, a local temperature is assigned to each vertex. The local temperature of each vertex is updated on each iteration. The local temperature varies in the range [0, MaxLocalTemperature]. If the angle between the previous and current vertex vectors is smaller than the LocalDirectionDeviation the vertex will speed up (increase its local temperature with the step specified by the  LocalWarmingStep property). Otherwise the vertex is considered "unstable" and it will slow down (decrease its local temperature with the step specified by the LocalCoolingStep property). Local temperature decreases the number of iterations in which the layout reaches equilibrium and also greatly improves the stability of the layout.
• Global temperature
If the UseGlobalTemperature property is set to true, the layout will perform the so called "global cooling". Global cooling refers to the clamping of the force by value to be in a specific range. If there is no global cooling by default the layout clamps each force to the MaxForce value. In the case of global cooling the clamping force decreases as the layout iterations progress - that is with each subsequent iterations vertices are allowed to move in progressively smaller regions. This ensures that the layout finally "freezes" at the last iteration step.
Self-Loops and Duplicate Edges
The Force Directed Layouts also handle self-loops and duplicate edges in graphs. They integrate them into the drawing after all nodes are placed trying to avoid overlaps if possible.
Performance Considerations

When arranging very large graphs (i.e. graphs with hundreds or thousands of vertices and edges) the force directed layouts will need more time to compute and apply the forces for each iteration. This will increase the total arrange time. If you want the layout to complete faster you can either decrease the maximum iterations that the layout should perform trying to find equilibrium or set the maximum time the layout is allowed to work. The layout stops if equilibrium is found or if the maximum number of iterations or the maximum time is exceeded.