|Critères & points attribués (/10)|
|Rappel du contexte||8|
|Qualité du code (commentaires, structures utilisées, …)||7|
|Animation du dessin||5|
|Explication en dehors du code||6|
B.P. : Excellent rappel du contexte du travail. Le code fournit fonctionne comme présenté mais le résultat n'est pas celui attendu. Vos explications du fonctionnement de l'algorithme sont incompréhensibles... De plus vos animations sont bien trop rapides.
This layout is called H-tree because its pattern ressembles the letter H.
Only binary trees are taken into account by the algorithm.
H-tree are based on bounding boxes that goes smaller and smaller as you go down to the leaves.
The nodes are placed in their bounding box, but on some trees, the visual aspect obtained can be improved.
In order to do this, we perform a “bottom to top” tree traversal to compute characteristics for each node based on the characteristics of its descendants.
These characteristics allow then to place each node in its box so as to obtain a pleasing visual difference.
Thus, the risk of obtaining an unbalanced layout from an incomplete binary tree is reduced.
We know that we need to calculate values for each node of the tree starting from the leaves and then back to the root. This will provide us with a better layout.
This part is well documented and equations for calculating the characteristics of each node are provided.
Then we descend the tree to deduce the position of each node. We do not know how to calculate and put our bounding boxes.
As the position of each node is relative to its bounding box, the slightest change in the calculation part of the layout can change the whole look of the graph.
We will see that this point remains unsolved, and what results we obtained from our implementation.
In order to test the animations in Tulip, we based our implementation on the simplest case: the complete binary tree.
In practice, an H-tree algorithm should be able to compute on an unbalanced binary tree.
Here are the results we got from a complete binary tree of depth 5:
We can guess the H.
B.P. oui, mais très déformé...
There is a problem of overlapping nodes. The root seems misplaced towards its descendants.
We added support for smooth nodes translations in order to see the transition between layouts.
Note that with the python implementation provided above, you can't see the animations by default. The reason for this is simple: at the time of writing, a call to “updateVisualization ()”, which allows you to animate the graph changes, would crash Tulip.
To take advantage of animations, prefer this script, similar to the previous one but using the “animateNodeTranslation ()” function.
We did not find any useful information about the way to compute the bounding boxes in accordance with the rules defined by Eades.
Gaps in Eades' research paper and our lack of culture on the H-tree layout were probably the cause of the rendering errors in our layout implementation.
Note that Eades characterizes his article on H-tree as a “discussion”. So we can't blame him for these gaps.
We would enhance the animations by adding colorization to the edges and the nodes while we traverse the tree in order to see the progression of the algorithm
and where the calculation are done at a given time (See the srn project that illustrates it well).
We would also draw the bounding boxes in order to see if everything goes well.