Page History

...

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 (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.

The heart of Mr. Tree are the following phases. They are described in more details on this page.

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.

...