# Wiki source code of Architecture

Last modified by Alexander Schulz-Rosengarten on 2023/07/11 10:33
Export
Office Formats
Export as PDF Export as ODT Export as RTF
Other Formats

Select the pages to export:

select all/ none

Legend:
  Created Page
  Modified Extension Page
  Clean Extension Page

Export as HTML

Show last authors

author | version | line-number | content
--- | --- | --- | ---
|  | 1 | Mr. Tree is structured the same as its big brother KLay Layered. It consists of layout phases, intermediate processors, and a connected components processor. The picture below describes the control flow and therefore what is done when the tree algorithm operates.
|  | 2 |
|  | 3 | [[image:attach:Phases_Complete_Tree.png]]
|  | 4 |
|  | 5 | This structure allows it to create independently phases for different aspects of the algorithm and to connect the phases through lightweight processors. (% lang="en" class="hps" %)In addition this structure allows it to optimize(% lang="en" %) (% class="hps" %)and replace(%%) (% class="hps" %)parts of the(%%) (% class="hps" %)algorithm(%%) (% class="hps" %)independently,(%%) (% class="hps" %)and so(%%) (% class="hps" %)to simplify the(%%) (% class="hps" %)future development of the(%%) (% class="hps" %)algorithm(%%).
|  | 6 |
|  | 7 | (% lang="en" class="hps" %)The architecture(% lang="en" %) (% class="hps" %)aims(%%) (% class="hps" %)to separate(%%) (% class="hps" %)most main steps(%%) for layouting a tree a(% lang="en" class="hps" %)nd(% lang="en" %) (% class="hps" %)to solve the layout taks by(%%) (% class="hps" %)the(%%) (% class="hps" %)divide and conquer(%%) (% class="hps" %)principle. The (% class="hps short_text hps" %)individual(% class="hps" %) steps are structured as following.(%%)
|  | 8 |
|  | 9 | The first thing that is done is the graph import. Since the algorithm works with KIML, it is necessary to import the graph that should be layouted with Mr. Tree. The important data structure (KGraph) is a comparatively complex structure. The tree algorithm does not need all parts of this data structure, so the parts that are necessary are converted into a less complex data structure, the [[MrTGraph data structure>>doc:KIELER.Discontinued Projects.Layout Algorithms (KLay).KLay Mr\. Tree.Data Structure.WebHome]] (TGraph), which is described through a class diagram at its corresponding page. As mentioned before, Mr. Tree runs on that data structure. After execution of the tree algorithm, the TGraph gets reconverted to a KGraph in a graph export phase, so that everything works fine with KIML.
|  | 10 |
|  | 11 | The heart of Mr. Tree are the following phases. They are described in more details on [[this page>>doc:KIELER.Discontinued Projects.Layout Algorithms (KLay).KLay Mr\. Tree.The Four Phases.WebHome]].
|  | 12 |
|  | 13 | The first phase is named which the comparatively unfamiliar term "treeifying". "Treeifying" is a word that describes a process that builds a tree out of a graph that is no tree. In other words: Mr. Tree should also operate on graphs that are no trees, but that can be converted into trees. Imagine a graph that is nearly a tree. It contains one cycle that destroys the tree property. Now the first phase should detect that cycle, destroy it by removing the edge that destroys the tree property and reinsert that edge again after the tree algorithm was able to operate on that newly build tree.
|  | 14 |
|  | 15 | Phase two and three calculate a place for every node in the layout. In phase two the nodes are ordered. Their ordering depends on the weighting of each nodes. That means that nodes with many offspring and many following levels should be placed before nodes that do not have that many offspring or following levels. Phase two computes such a node ordering. Phase three then places the nodes. For placing the nodes, we use the algorithm developed by Walker et al. They developed a node positioning algorithm for general trees, that calculates x-coordinates for each node. This coordinates depend on many factors, such as position in a tree, number of offspring/ancestors and so on. A more detailed look can be found in the [[paper of Walker et al.>>url:http://www.cs.unc.edu/techreports/89-034.pdf||shape="rect"]] which we also referenced in the Literature Section of this page.
|  | 16 |
|  | 17 | The last phase of Mr. Tree is a simple edge-routing that simply connects the previously placed nodes directly.

# Quick Links

KIELER on GitHub
RTSYS Homepage

XWiki 14.4.7