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://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”

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”

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/

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

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

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

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

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

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

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”

Bruls, Huizing, van Wijk (2000)

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

Bruls, Huizing, van Wijk (2000)

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

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”

Bruls, Huizing, van Wijk (2000)

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

8

12

3

4

6

Bruls, Huizing, van Wijk (2000)

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

Algorithme de treemap “squarified”,avec marges et lissage

Bruls, Huizing, van Wijk (2000)

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

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→∞

Michael McGuffin et Jean-Marc Robert, 2010

Michael McGuffin et Jean-Marc Robert, 2010

Michael McGuffin et Jean-Marc Robert, 2010

Squarified treemap “Rectified” treemap

Michael McGuffin et Jean-Marc Robert, 2010

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

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

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

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

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

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

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

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