Diagram > Layouts > Graph Layouts > 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.
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.
The result of the layout and the aesthetic criteria for the final drawing can be controlled through the following properties:
Direction – determines how the drawing is oriented in the 2D drawing space. By default it is oriented from Top to Bottom. Other possible orientations are: from Bottom to Top, from Left to Right and from Right to Left.
The image below demonstrates the effect of the different node rank settings on a drawing. Look at the positions of shape 1 and shape 2 for the different NodeRank modes.
LayerSpacing and VertexSpacing – determine the spacing between the layers and the vertices.
EdgeRouting – determines whether to use polyline or orthogonal edge routing. The following images illustrate the two possible edge routing modes.
Layered graph layout with polyline edge routing |
Layered graph layout with orthogonal edge routing |
PlugSpacing – determines the spacing between the plugs of a node. You can set a fixed amount of spacing or a proportional spacing, which means that the plugs are distributed along the whole side of the node.
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.
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.