KLay Mr. Tree - The Four Phases 

Page / - last modified by Alexander Schulz-Rosengarten on 2023/07/11 10:33 

The Four Phases 
last modified by Alexander Schulz-Rosengarten
on 2023/07/11 10:33

Table of Contents
Phase 1: Treeifying
Phase 2: Node Ordering
Phase 3: Node Placement
Phase 4: Edge routing

This page describes the main phases of the Mr. Tree. A short overview of all processors that operate in between these phases can be found here.
Phase 1: Treeifying
This phase should create a tree, if a graph is hardly a tree.
It should for example look for cycles in a tree and remove that cycles. This cycle breaking is done through eliminating the edge that destroys the tree property and putting that edge into a list. So this phase builds up a list with removed edges, so that the tree algorithm can operate on the newly constructed graph which is now a tree. The previously removed edges could be reinserted during a post-processing.
Phase 2: Node Ordering
This phase orders the nodes of each level by separating the children of nodes into leaves and inner nodes.  Inner nodes are arranged near the middle of the level, with the heaviest node in the middle. It then fills whitespaces in the levels with corresponding leaves. It starts two levels above the deepest level, because the deepest level contains only nodes and therefore no reordering is necessary. And the level above the deepest level contains only children of the level above, which are ordered by the their parents.
Phase 3: Node Placement
The algorithm comes from "A Node-Positioning Algorithm for General Trees, John Q.Walker II" with some small fixes in the actual code.
This algorithm utilizes two concepts developed in previous positioning algorithms. First is the concept of building subtrees as rigid units. When a node is moved, all of its descendants (if it has any) are also moved--the entire subtree being thus treated as a rigid unit. A general tree is positioned by building it up recursively from its leaves toward its root.
Second is the concept of using two fields for the positioning of each node. These two fields are:
•	a preliminary x-coordinate
•	a modifier field
Two tree traversals are used to produce the final x-coordinate of a node. The first traversal assigns the preliminary x-coordinate and modifier fields for each node; the second traversal computes the final x-coordinate of each node by summing the node's preliminary x-coordinate with the modifier fields of all of its ancestors. The final y-coordinate of the node is the height of the node's ancestors levels and the height nodes level and the adjust of the root location.
Phase 4: Edge routing
For now the edges are routed simple directly by setting source and target position of the edges on the corresponding nodes.