Nevron .NET Vision Documentation
Force Directed Layouts

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

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:

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

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 MagnetizationType 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 class, accessible from the LayoutData property of each shape. The NShapeBodyAdapter adapts the values of the layout data for you.

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: 

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 layouting 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 layouting 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.

See Also

 

 


©2017. Nevron Software LLC.

Send Feedback