The Effect of the Layout Algorithms

Next: Tree Layout Up: GDL Examples Previous: Control Flow Graph

The Effect of the Layout Algorithms

The following sequence of layouts shows the same graph visualized by different layout algorithms. The graph is cyclic, so the algorithm tree can't be used.

A key problem is selecting the nodes that appear at the top level of the graph. The layout algorithm looks for candidates that have no incoming edges yet at least one outgoing edge. If such nodes do not exist as in the following example, the algorithms mindegree, minindegree, maxoutdegree are the most appropriate algorithms.

The fine-tuning phase eliminates long edges, meaning the tuned graph is more compact. Note that the tuned graph created by maxdephtslow need not be of maximum depth because fine-tuning may have reduced the depth further. The tuned graph created by mindepthslow needn't be of minimum depth, either. All these partitioning algorithms are heuristics.

Example 10: A Cyclic Graph

graph: {

node: {title:"S"  label: " Start " }
node: {title:"1"}  node: {title:"2"}
node: {title:"3"}  node: {title:"4"}
node: {title:"5"}  node: {title:"6"}
node: {title:"7"}  node: {title:"8"}
node: {title:"9"}  node: {title:"0"}

edge: {source:"S" target:"1"}
edge: {source:"S" target:"2"}
edge: {source:"S" target:"3"}
edge: {source:"S" target:"4"}
edge: {source:"S" target:"5"}
edge: {source:"S" target:"9"}
edge: {source:"1" target:"3"}
edge: {source:"2" target:"4"}
edge: {source:"3" target:"5"}
edge: {source:"5" target:"0"}
edge: {source:"9" target:"0"}
edge: {source:"S" target:"6"}
edge: {source:"6" target:"7"}
edge: {source:"7" target:"8"}
edge: {source:"8" target:"S"}

}

Here follows a discussion of all the different hierarchical layout algorithms with and without fine-tuning for this example.

normal, finetuning: no The normal layout algorithm breaks the cycle so that only one reverted edge is necessary.
normal, finetuning: yes Compared to the previous layout, the fine-tuning phase has balanced the position of the node 9 . The long edge 8 Start is not balanced since this would create additional reverted edges.
maxdegree, finetuning: no The Start node has the maximum number of incoming and outgoing edges, so it is selected as the start node of the spanning tree, i.e. it appears at the topmost level. The layout algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout.
maxdegree, finetuning: yes Compared to the previous layout the long edge 8 Start is eliminated. The algorithms dfs, mindepth, minindegree, maxoutdegree and maxdegree happen to result in the same layout.
minbackward, finetuning: no This is almost the same layout as for the normal layout algorithm. Again only one reverted edge is necessary. The layout algorithm maxdepth without fine-tuning results in the same layout.
minbackward, finetuning: yes Compared to the layout without fine-tuning, here the long edge 8 Start is partially eliminated and the position of node 9 is balanced again.
maxdepth, finetuning: no Same as minbackward without fine-tuning.
maxdepth, finetuning: yes The long edge 8 Start is now fully eliminated. Here, the fine-tuning phase is allowed to revert additional edges.
maxdepthslow, finetuning: no This depth six layout is in fact of maximum depth as compared to all the other variants.
maxdepthslow, finetuning: yes The fine-tuning phase eliminates the long edge Start 6 . Thus, the layout is no longer of maximum depth. Fine-tuning may destroy the maximum depth property.
mindepthslow, finetuning: no Graphs that are of minimum depth tend to have many nodes at the top level. Compared to all untuned graphs, this layout is of minimum depth. It should be noted, however, that the algorithm mindepth with fine-tuning is able to produce a flatter layout.
mindepthslow, finetuning: yes Compared to the previous layout, the long edge 8 Start is balanced again.
maxindegree, finetuning: no Here node 3 is placed at the level zero because it has the maximum indegree. Node 0 is not chosen for level zero because it doesn't have any outgoing edges.
maxindegree, finetuning: yes Once again the long edge 8 Start of the previous algorithm is eliminated by balancing the position of node 8 . The algorithms dfs, mindepth and minindegree happen to result in the same layout.
minoutdegree, finetuning: no Nodes 4 and 0 with a minimum outdegree of zero cannot be start nodes because start nodes have to have at least one successor otherwise they would create single-node components of the spanning tree. Start nodes can be any other nodes except Start, from which 1 , 2 , and 6 happen to be selected.
minoutdegree, finetuning: yes The long edges Start 1 , Start 2 and Start 6 are eliminated.
mindegree, finetuning: no The candidates for start nodes of the spanning tree are 1 , 2 , 6 , 7 , 8 and 9 because they have a minimum degree of two. 1 , 2 and 6 happen to be selected as the start nodes. Note that nodes 4 and 0 are not candidates for start nodes because they do not have outgoing edges. The layout algorithms minoutdegree and mindegree happen to result in the same layout.
mindegree, finetuning: yes Compared to the previous layout, the long edges Start 1 , Start 2 and Start 6 are eliminated. This changes the structure of the layout entirely.