Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

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.

...

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.

...