aiSee User Manual: Rank Assignment

After the folding phase, all the visible nodes are determined. If all the visible nodes have been specified by the user using valid coordinates, the graph is drawn immediately. However, if the coordinates of at least one node are missing, an appropriate layout has to be calculated. The first pass places the nodes in discrete ranks. All nodes of the same rank appear at the same vertical position.

There are many possibilities for assigning rank. The normal method is to calculate a spanning tree by determining the strongly connected components of the graph. All edges should be oriented top-down. A heuristic tries to find a minimum set of edges that cannot be oriented top-down.

A faster method is to calculate the spanning tree of a graph by depth first search (DFS). However, the order in which the nodes are visited has a substantial influence on the layout. The initial order of the nodes is the order given by the graph specification. aiSee offers various versions of the DFS method:

dfs calculates the spanning tree by one single DFS traversal. This is the fastest method, but the quality of the result might be poor for some graphs.
maxdepth calculates the spanning tree by DFS using the initial order and the reverted initial order, followed by choosing the deepest spanning tree. This results in more levels, i.e. the graph is larger in the y direction.
mindepth takes the flatter spanning tree of both DFS’s. This results in fewer levels, or more nodes at the same levels, meaning the graph is larger in the x direction.
maxdepthslow, mindepthslow: Whereas the above algorithms are fast heuristics for increasing or decreasing the depth of the layout, maxdepthslow and mindepthslow actually calculate a good order so as to obtain a maximum or minimum spanning tree. However, they are rather slow. Please note that a minimum spanning tree does not necessarily mean that the depth of the layout is minimal. However, good heuristics involves obtaining a flat layout (see the effect of the layout algorithms).
maxdegree, mindegree, maxindegree, minindegree, maxoutdegree, minoutdegree: These algorithms combine DFS with node sorting. The sorting criteria are the number of incoming edges, the number of outgoing edges, and the number of edges all at the same node. Node sorting may have various effects and can sometimes be used as a fast alternative to maxdepthslow or mindepthslow.
minbackward: Instead of calculating strongly connected components, aiSee can also perform topological sorting to assign ranks to nodes. This is much faster, however it requires the graph to be acyclic.
tree: This method is very fast, however it can’t be used unless the graph is a forest of downward laid-out trees. A downward laid-out tree has the following structure: Each node at rank n has at most one adjacent edge coming from a node of an upper rank m < n. A node may have edges pointing to nodes at the same level and edges coming from nodes of lower ranks p > n. The direction of the edges may be arbitrary, but the picture of the layout (if the arrow heads are ignored) has to be a tree (see example). The assignment of ranks is done by DFS. Then, the graph is checked to determine whether it is a forest of downward laid-out trees. If this is not the case, the standard layout is used as a fallback solution. Crossing reduction is not necessary for downward laid-out trees, meaning a very fast positioning algorithm can be used.

A further possibility for influencing the layout is edge priority. Higher priority edges are preferable when calculating the spanning tree. After partitioning, an optional fine-tuning phase tries to improve the ranks in order to avoid very long edges. See graph attribute finetuning.

Next: crossing reduction
Prev.: overview of the layout phases