Nevron Open Vision Documentation
Layered Graph Layout

 
About Layered Graph Layout

The layered graph layout is represented by the NLayeredGraphLayout class. The layered graph layout algorithm aims to highlight the main direction or flow within a directed graph. Cyclic dependencies of nodes are automatically detected and resolved and nodes are placed in hierarchically arranged layers. Additionally, the ordering of the nodes within each layer is chosen in such a way that the number of edge crossings is small. This layout algorithm is very appropriate for hierarchically organized diagrams, organization charts, etc.

The algorithm maintains the following aesthetic criteria (given by their priority in descending order):
- minimal number of levels
- minimal number of edge crossings (a level by level sweep optimization is used)
- minimal number of bends

Following is a brief description of the algorithm.

 

Algorithm

The input of the layered graph layout algorithm must be a directed acyclic graph (DAG), so if the graph contains cycles a preliminary step that removes them is performed. When we ensure that the input graph is a DAG we may perform the first phase of the algorithm - the Layer Distribution. It distributes the vertices of the graph to layers by using the Longest Path Layering algorithm. All vertices without predecessors are put at level 1 and the other vertices are distributed to the next level / levels in such a way that the following statements are true:
- The final graph must occupy as small area as possible
- The layers must be regular. This can be achieved easily by adding dummy vertices for each edge (u, v) with length more than 1 layer
- The number of added dummy vertices must be minimal

When the vertices are distributed to layers we perform a crossing reduction step which rearranges the vertices on each layer in such way that the number of edge crossings is minimized. Finally we calculate the coordinates of the vertices and edges of the drawing.

Tuning Considerations

The result of the layout and the aesthetic criteria for the final drawing can be controlled through the following properties:

You can set the index of a given node in its layer explicitly using the IndexInLayer property from the LayoutData collection of the node. By default the index is set to -1 which means that the layout will automatically calculate it. If you set a value greater than or equal to 0 the node will be placed at that index. If the index is greater than the total number of nodes in the layer, it will be set equal to the number of vertices - 1.

Self-loops and duplicate edges

The Layered Graph Layout also handles self-loops and duplicate edges in graphs. The size of the self-loops between 2 layers is determined by the available layer spacing, and the size of the self-loops in the layer is determined by the height of the body multiplied by the SelfLoopSpacingFactor property.

Send Feedback