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.