User Tools

Site Tools


Solution to homerwork 2

Critères & points attribués (/10)
Rappel du contexte 8
Résultats 6
Qualité du code (commentaires, structures utilisées, …) 7
Animation du dessin 5
Explication en dehors du code 6
Total (/50) 32

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.

We propose an implementation of the H-tree layout by Eades written in Python and working inTulip.
Get it here

See the example of an H-tree on the image below.

This layout is called H-tree because its pattern ressembles the letter H.
Only binary trees are taken into account by the algorithm.

What does Eades states

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.

The starting material

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.

Our algorithm

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.

How it works

  • Step 1: we traverse the tree in depth (suffix) in order to compute the leaves first and then back to the root of the tree. For each node,
    we calculate its relative position to its future bounding box (east, west, south and
    north distances from the border of the bounding box) and its bounding box's orientation (vertical or horizontal).
  • Step 2: We traverse the tree in depth beginning from root and going to the leaves in order to compute the bounding boxes nested inside each other.
    If a node possesses two son, then the father's bounding box will contain these three nodes.
    The first will possess a bounding box containing the first half of the father's bounding box and the second will have a bounding box containing the other half.
    Note that the root is a special case that requires its own computations.
  • Step 2': During step 2, we also adapt the characteristics of each node (north, south, east and west) at its bounding box so that it does not exceed the size of the box.
    Indeed, the bounding boxes are based on the size of the first box, not on the characteristics calculated in step 1. Only the bounding box of the tree's root depends on the characteristics of its node.
    So node.East + node.West could exceed box.width if this step was not performed.
  • Step 2'': Once a bounding box was calculated, the node is placed inside based on its attributes (east, west, south, north).
    Please take a look at Eades' paper about H-trees if you don't get the idea behind north, south, east and west.

About the animations

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.

If we had more time

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.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/cbadiola/solution_homework2.txt · Last modified: 2012/10/22 12:06 by bpinaud