La visualisation des arborescences. Version avec 3000 espèces (David Hillis, )

La visualisation des arborescences

Version avec 3000 espèces (David Hillis, http://www.zo.utexas.edu/faculty/antisense/DownloadfilesToL.html )

http://www.zo.utexas.edu/faculty/antisense/tree.pdf

http://en.wikipedia.org/wiki/File:Tree_of_life_with_genome_size.svg

Dendrogramme:Montre le résultat d’un “clustering”

Nuage de points (“scatterplot”)

Dendrogramme montrant4 “clusters” principaux

(Merci à Patrick Oesterling pour les images.)

Arbre noeud-lien modifié pour montrer le temps

Venolia et Neustaedter, “Understanding Sequence and Reply Relationships within Email Conversations: A Mixed-Model Visualization”, ACM CHI 2003

Une recette

http://www.cookingforengineers.com/2004/09/recipe-file-basic-tiramisu.html

Filelighthttp://www.methylblue.com/filelight/

http://www.topicscape.com/

Les arborescences

Zhao, McGuffin, et Chignell 2005

Susanne Jürgensmann et Hans-Jörg Schulz,A Visual Survey of Tree Visualization, affiche à InfoVis 2010

http://treevis.shows.it/

Rappel: les parcours d’arbre

• Parcours en profondeur “preorder”: ABDEFICGH

• Parcours en profondeur “postorder”: DEIFBGHCA

• Parcours en largeur: ABCDEFGHI

A

B C

D

I

E GF H

Un layout naïf et facile à programmer: chaque sous-arborescence a un intervalle en x qui n'est pas chevauchée par les sous-arborescences voisines. Un parcours en profondeur "postorder" combine les intervalles des sous-arbres pour donner l’intervalle de chaque parent.

Un layout de style "Reingold Tilford" : économise de l'espace en x en rapprochant les sous-arbres le plus possible. (Pour les détails, voir la section 3 de Christoph Buchheim, Michael Jünger et Sebastian Leipert, "Improving Walker's Algorithm to Run in Linear Time",Proceedings of Symposium on Graph Drawing (GD) 2002, pages 344-353.)

Un autre layout facile à programmer: un parcours en profondeur “preorder” va rencontrer les noeuds en ordre des coordonnées y, tandis que la coordonnée x est proportionnelle à la profondeur de chaque noeud.

Classique/En couches (“layered”) En liste “indentée”









@article{wetherell1979, author = {Charles Wetherell and Alfred Shannon}, title = {Tidy Drawings of Trees}, journal = {IEEE Transactions on Software Engineering}, year = 1979, month = {September}, volume = {SE-5}, number = 5, pages = {514--520}}

@article{reingold1981, author = {Edward M. Reingold and John S. Tilford}, title = {Tidier Drawings of Trees}, journal = {IEEE Transactions on Software Engineering}, year = 1981, month = {March}, volume = {SE-7}, number = 2, pages = {223--228}}

@article{walker1990, author = {{Walker II}, John Q.}, title = {A Node-Positioning Algorithm for General Trees}, journal = {Software---Practice and Experience}, year = 1990, month = {July}, volume = 20, number = 7, pages = {685--705}}

@inproceedings{buchheim2002, author = {Christoph Buchheim and Michael J\"{u}nger and Sebastian Leipert}, title = {Improving {Walker's} Algorithm to Run in Linear Time}, booktitle = conf_gd, year = 2002, pages = {344--353}}

SpaceTree(Catherine Plaisant, Jesse Grosjean, Benjamin Bederson, InfoVis 2002)

http://www.cs.umd.edu/hcil/spacetree/






Treemaps(Ben Shneiderman et d’autres)

Martin Wattenberg, 1998et

http://www.smartmoney.com/map-of-the-market/

Marc Smith et Andrew Fiore, 2001

http://iguide.travel/Philippines/Regions

http://iguide.travel/illustrations/Philippines-8.png

Bruls, Huizing, van Wijk (2000)

http://www.win.tue.nl/~vanwijk/stm.pdf

Treemap dans Konquerorhttp://www.dgp.toronto.edu/~mac/tmp/konqy_space_usage_disp.png

Treemaps (Shneiderman 1992; http://www.cs.umd.edu/hcil/treemap-history/)

Un Treemap « slice-and-dice » (algorithme original, produit beaucoup de rectangles longs et minces):

Algorithme de treemap “slice-and-dice”





Algorithme de treemap “slice-and-dice”

Mosaic plots

http://www.statmethods.net/advgraphs/mosaic.html

Treemaps• Un Treemap « squarified » (algorithme glouton,

temps linéaire*, améliore la proportion (« aspect ratios ») des noeuds):

* Sans compter le temps pour trier les enfants de chaque noeud

Algorithme de treemap “squarified”



8

12

3

4

6



Algorithme de treemap “squarified”,avec marges et lissage



Les arborescences

Michael McGuffin et Jean-Marc Robert, 2010

Aire de chaque feuille proportionnelle à la superficie de l’île

Aire de chaque feuille égale

« Squarified Treemaps »

« Icicle diagrams » (diagrammes à glaçons)

Michael McGuffinet Jean-Marc Robert, 2010

Asymptotic Analysis of the Space-Efficiency of Tree Representations

Key ideas:• Impose a 1×1 bounding square on all representations• Evaluate size of smallest nodes, not just total area• Evaluate size of labels as a function of their aspect ratio L• Examine limits of these sizes as depth D→∞




Squarified treemap “Rectified” treemap


Hans-Jörg Schulz et al., PacificVis 2013








Documents

La visualisation des arborescences. Version avec 3000 espèces (David Hillis, )