User Tools

Site Tools


chicoutimi_2016:implementation_des_doi_graphs_de_van_ham

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
chicoutimi_2016:implementation_des_doi_graphs_de_van_ham [2016/05/25 19:41]
melancon created
chicoutimi_2016:implementation_des_doi_graphs_de_van_ham [2016/05/28 15:29] (current)
melancon
Line 8: Line 8:
   * [[chicoutimi_2016:​session_by_session_cutdown|Back to course start page]]   * [[chicoutimi_2016:​session_by_session_cutdown|Back to course start page]]
  
-=== DOI trees de George W. Furnas ​===+=== Implémentation des DOI Graphs ​de van Ham ===
 --- ---
-  ​* {{:furnas_fisheyechi86.pdf|FurnasGW. (1986). Generalized Fisheye Views. Human Factors in Computing Systems CHI '86ACM Press16-23.}}+ 
 +  * [[chicoutimi_2016:​focus_context_graph|Une solution à cet exercice est proposée ici.]] 
 +    * Reste encore à proposer une vue avec "​contexte élargi";​ et la prise en compte d'une fonction $UI$ modélisant l'​intérêt de l'​utilisateur pour un sommet du graphe (un ranking des sommets selon un critère venant de l'​utilisateur). 
 + 
 +  ​* {{:chicoutimi_2016:​van_ham_2009_search_show_context_.pdf|van HamFand APerer (2009). ""​SearchShow ContextExpand on Demand":​ Supporting Large Graph Exploration with Degree-of-Interest."​ IEEE Transactions on Visualization and Computer Graphics 15(6): 953-960.}}
   
-Dans son articledont le titre évoque peu ou mal son propos, Furnas développe une approche ​pour gérer ​le //niveau de détail// affiché d'un objet, en fonction du //point d'​intérêt//​ de l'​utilisateur.+Vous travaillerez à partir du (des) graphe(s) $G = (VE)$ que vous avez construit ​pour le devoir maison. Vous pouvez aussi travailler avec un autre graphemais celui-là est en principe déjà là, tout bien formaté.
  
-C'est l'utilisateur qui manifeste son intérêt ​pour un élément ou une région des données; c'​est ​le système qui fournit le détail sur cet élémentet un contexte ​global dans lequel s'​inscrit cet élément.+Ce cours contient une suite d'instructions permettant d'implémenter la technique proposée par van Ham calculant ​pour un sommet $u \in V$ choisi (par le billet de la formulation d'un critèrepar exemple, ou sélectionné manuellement) ​un //contexte//: un sous-graphe contenant $u$ et les éléments les plus "​intéressants"​ à proximité.
  
-D'​autres systèmes laissent à l'​utilisateur de gérer et construire le contexte.+== First things first ==
  
----+Parce que nous allons manipuler, créer, supprimer des sous-graphes, il nous faut préserver les données de départ, et les mettre elles-mêmes dans un sous-graphe "​clone"​ du graphe de départ pour qu'il reste intact. C'est ce clone que nous appellerons par la suite le graphe de départ (ou graphe original). 
 +== Calcul du DOI ==
  
-Furnas se penche sur la visualisation de documents dont la structure est arborescente.+  * Il vous faudra vous assurer que votre graphe dispose d'un propriété $API: V \to \mathbb R^+$. Ce sera vraisemblablement une propriété donnée en paramètre aux différentes fonctions que vous écrirez. 
 +    * Vous pourrez varier ​la propriété ''​API''​ pour observer l'​impact sur la sélection du contexte.
  
-  * La plupart des documents ont des des chapitres, des sections, titres, des sous-titres,​ etc+  * Nous allons supposer que le //focus// est pour l'​instant choisi en le sélectionnant manuellement
-  Le code est structuré par blocs imbriqués.+    C'est le sommet dont la propriété ''​viewSelection''​ est à ''​True''​. 
 +    * Ecrivez une fonction ''​focus_node''​ (ou une méthode si vous construisez une classe ''​python''​) qui fouille un graphe et retourne le sommet sélectionné dans un graphe.
  
-{{ :furnas_code_plain.png?link&​300 ​|}}+  * Il faut aussi pouvoir calculer la distance au sommet focus $d_G(u, f)$. 
 +    * La fonction [[http://tulip.labri.fr/​Documentation/​current/​tulip-python/​html/​tulipreference.html?highlight=maxdistance#​tulip.tlp.maxDistance|max_distance]] de Tulip fait le travail. La distance ​ à $f$ sera alors stockée dans une propriété du graphe.
  
-Furnas propose de calculer pour chaque élément de la hiérarchie du document, un indice reflétant son degré d'​intérêt ​DOI (degree of interest). On peut ensuite imposer un seuil au-delà duquel on décide d'​afficher ​l'élément -- sinon, soit il est masqué, soit on en affiche un résumé ​(le titre seulou la première ligne, ​par exemple).+  * Nous allons dans un premier temps ignorer ​la fonction $UI$ calculant l'​intérêt ​utilisateur ​(User Interest) (nous y reviendrons). Il suffira pour l'instant de stocker dans une propriété une valeur constante ​(par exemple 0, la valeur ​par défaut lors de la création d'une propriété). 
  
-{{ :​furnas_code_doi.png?​link&​300 |}} 
  
----+  * Il vous faudra stocker le calcul du $DOI(u, f)$ d'un sommet $u \in V$ dans une propriété $DOI: V \to \mathbb R^+$ (on suppose le sommet $f$ fixé). C'est une propriété qui est à créer et qui stocke un calcul:
  
-Furnas had a very clever idea applied to the visualization and edition of code. Because code is organized into a hierarchy of blockswhy not only show the headings of a block while the user is not interested in having a detailed look at the details of that block. For instanceonly showing the name and signature of a function might be enoughshowing the first line of a loop might be sufficient to indicate what the loop is performing at that location in the code.+$$DOI(uf) = \alpha \cdot API(u) + \beta \cdot UI(uz) + \gamma \cdot d_G(u,f)$$
  
-{{::​furnas_code_plain.png?​direct&​300 }} {{ ::​furnas_code_doi.png?​direct&​300}}+Le choix des coefficients $\alpha, \beta, \gamma$ reste à déterminerNotre expérience permettra d'​expérimenter et de juger de leur impact, ou des choix de prédilections pour leur valeurs (van Ham n'en dit pas grand chose dans son article).
  
-The left figure show a portion of a file. The right figure show the same file where some blocks have been shrunk to a single line. (Click on the images to access an enlarged view.) So the problem we need to solve is to decide what blocks should be shrunk or not. Observe also that blocks residing within a shrunked blocks will not be shown at all.+== Sélection du contexte ==
  
-Nowwe may assume the blocks to form a hierarchy, that is they implicitly defined a tree structure ​$(V, E)$. We may also assume the tree implicitly defines the a priori importance of a node in the tree. That isa leaf node corresponding to a single instruction is of a lesser importance than an ancestor node corresponding to the function containing this line, for instance. As a consequence,​ the root node $r \in V$ has the greatest //a priori// importance value.+C'est l'​algorithme vu en cours. On calcule un sous-graphe $F$ contenant le focus $f$d'une taille convenable. Fixons la taille à $20pour l'​instantL'​algorithme est le suivantqu'il faut implémenter.
  
-{{ ::​api.png?​direct&​300|}} This leads to define the //a priori/importance function:+<​code>​ 
 +u <-- f 
 +F <-- empty set 
 +C <​-- ​{u} 
 +tant que (C != empty set) et (|F| < S) faire 
 +    x = candidat de C de DOI maximum 
 +    ajouter x à F 
 +    supprimer x de C 
 +    ajouter à C les voisins de x (qui ne sont pas déjà dans F) 
 +retourner F 
 +</code>
  
-$$ +  * L'​implémentation de l'​algorithme nécessite 
-API: T \to \mathbb Z \qquad T: v \mapsto T(v=  - d_T(v, r+    * De stocker les éléments sélectionnés dans un ensemble ​(et pas une propriété booléenne sur le graphe, par exemple; on va voir pourquoi c'est la bonne façon de faire plus bas)
-$$+    * De noter une propriété booléenne sur les sommets déjà visités ​(une propriété booléenne sur le graphe). 
 +    * De pouvoir trouver l'​élément de DOI maximum dans ''​C'';​ on peut donc parcourir les éléments de C (un ensemble) pour trouver son élément maximum. Mieux (si vous en avez le temps, et si vous devez traiter de grands ensemble), il faut stocker ''​C''​ dans un tas max; on obtient la valeur maximum en temps constant, on la supprime en temps $\log |C|et on y ajoute un nouvel élément en temps $\log |C|$ (autant de fois que le degré de $x$)
  
-so the //a priori// importance of a node equals minus its distance to the root in the tree.+  * L'​ensemble $F$ est un ensemble de //sommets//. Il nous faut donc calculer le sous-graphe induit sur ces sommets. 
 +    * C'est ce que fait le plugin [[http://​tulip.labri.fr/​Documentation/​current/​tulip-python/​html/​tulipreference.html?​highlight=induced#​tulip.tlp.Graph.inducedSubGraph|Induced Sub-Graph]]. Le plugin attend en paramètre un ensemble de sommets. ​ Le résultat du calcul de cette fonction est un sous-graphe,​ c'est précisément le contexte que l'on souhaitait calculer. 
 +    * Nommez ce sous-graphe (''​setName''​) ''​context''​.
  
-Now, suppose the user is editing a particular line in the file. This translate into the fact that a node of the tree momentarily becomes //a node of interest//. Given a node of interest $f$, we  call the //focus node//, we may compute the distance from any other node $v$ to this focus node $d_T(v, f)$. {{ ::​distance_to_focus.png?​direct&​300|}} ​+== Affichage du contexte ==
  
-The combination of these two functions may now be used to define what is called the degree of interest of a node (with respect to a focus node $f$):+  * Je supposerai ici que vous avez au départ une vue noeud-lien sur le graphe original. Cette vue ne servira qu'à sélectionner le sommet ​focus $f$ pour l'​instant. Nous pourrions, plus tard, nous en passer -- et c'est le but du jeu, si par exemple ce graphe est trop grand pour être visualisé dans sa totalité (bien qu'il puisse être stocké en mémoire).
  
-$$ +  * Je supposerai aussi que vous avez une deuxième vue noeud-lien. 
-DOI: V \times V \to \mathbb Z \qquad DOI(vf) = API(v) ​d_T(v, fd_T(vr) d_T(v, f) +  * Vous serez donc en visualisation "trois panneaux"​avec les deux vues noeuds-liens en haut, disons, et le code python en bas (mais cela n'a pas d'​importance)
-$$+    * Une vue noeud-lien pour sélectionner. 
 +    * Une vue python pour lancer le script. 
 +    * Une vue noeud-lien pour afficher le sous-graphe ''​context''​. 
 +  * Positionnez ces trois vues à la main à partir des graphes que vous avez maintenant sous la main: le graphe de départet le sous-graphe ''​context''​ que vous avez calculé.
  
-{{::doi.png?direct&​300|}} Observe how the values distribute in the treeNodes with higher values either are closer to the focus nodeor have relatively high a priori importance.+== Changement de contexte == 
 +  * Vous allez maintenant calculé un nouveau contexte à partir d'une sélection que l'​utilisateur pourra faire dans le sous-graphe ''​context''​ (dans la vue qui le présente à lui seul). 
 +    * Cela demande à ce que votre code soit bien organisé, qu'il reçoive en paramètre les propriétés définies sur le graphe original, bien que la sélection soit effectuée dans un sous-graphe (héritage des propriétés). 
 +  * Cela demande aussi de changer le graphe à afficher, dans la vue noeud-lien qui montre le contexte. ​  
 +  * La manière forte: 
 +    * On peut mettre la main sur toutes les vues disponibles dans une session''​tlpgui.getOpenedViews()''​. 
 +    * Une vue est [[http://​tulip.labri.fr/​Documentation/​current/​tulip-python/​html/​tulipguireference.html?highlight=view#​tulipgui.tlpgui.View|un objet View]] de Tulip). 
 +    * On peut demander à avoir le graphe qui est visible dans une vue ''​v'':​ ''​v.graph()''​et son nom ''​v.graph().getName()''​. On peut donc trouver la vue où le contexte est visible. 
 +    * On peut affecter un autre graphe à une vue (comme lorsqu'​on effectue un drag&​drop à la main): ''​v.setGraph(sg)''​ où ''​sg''​ est un sous-graphe (ou un graphe).
  
-Nextwe need to threshold the DOI values to obtain a partial view of the tree with more details around the focus node.+  * La manière douce: 
 +    * Observez ce qui se passe si vous modifiez (par script) le sous-grapheen supprimant un de ses sommets, par exemple: la vue est automatiquement mise à jour; idem si on ajoute un sommet ou une arête. 
 +    * On peut donc penser effectuer une transition "​douce"​ en supprimant les choses à supprimer du contexte, et en ajoutant ce qui doit l'​être. 
 +    * Bien entendu, [[http://​tulip.labri.fr/​Documentation/​current/​tulip-python/​html/​search.html?​q=tlpgui.GlMainView&​check_keywords=yes&​area=default|la vue devra vraisemblablement être recentrée]]:​ ''​v.centerView()''​.
  
----+== Elargir le contexte ==
  
 +Le sous-graphe affiché est limité en taille, et comme le souligne van Ham, il peut être intéressant de suggérer à l'​utilisateur des directions où poursuivre l'​exploration.
 +
 +  * On peut donc choisir, parmi les sommets du sous-graphe contexte, ceux dont les voisins sont des candidats de $C$ qui n'ont pas eu le "​bonheur"​ d'​être sélectionnés. (D'​autres approches sont possibles.)
 +  * Ces voisins se divisent en plusieurs composantes:​ il serait étonnant qu'ils soient tous connectés les uns aux autres -- mais cela peut arriver).
 +  * Il nous faut mettre la main sur ces composantes connexes, chacune dans un sous-graphe (du graphe original).
 +  * La routine ''​Connected Components''​ fait ce travail.
 +  * Nous allons construire pour chacune de ces composantes un méta-sommet.
 +  * La routine ''​Equal Value''​ permet de construire les sous-graphes induit du calcul de la routine ''​Connected Components''​. Mais attention, les sous-graphes qui donneront naissance aux méta-sommets ne peuvent pas être des sous-graphes du contexte (puisque l'on souhaite qu'ils y soient ajouter).
 +  * Reste ensuite à visiter chacun de ces sous-graphes et à les utiliser pour créer des méta-sommets dans le contexte.
 +
 +  * Une bonne idée est de bien nommer les choses (les métriques confiées aux routines de Tulip) pour que les sous-graphes construits aient des noms qui permettent ensuite de les localiser.
 +    * On peut en effet fouiller les sousgraphes d'un graphe: ''​g.getSubGraphs()'',​ c'est utile de décider selon le nom du sous-graphe s'il fait partie de ceux qui demandent un traitement particulier.
 +
 +== Et l'​utilisateur ? ==
 +
 +Retour à la fonction $UI$ de van Ham. Avant la sélection du focus, on peut imaginer donner un critère qui permet d'​ordonner les sommets (ranking).
 +
 +  * Par exemple, si on cherche plutôt les sommets qui s'​éloigne de la valeur moyenne, on convertira ce critère en une métrique $UI$ qui stocke l'​écart à la moyenne (en valeur absolue).
 +  * Si les sommets contiennent des champs textes, on pourra effectuer une recherche sur ce champ et attribuer une valeur aux sommets en focntion de la présence de mots-clés, ou d'une distance à un ensemble de mots-clés (vecteur de mots, distance cosinus, ...).
 +  * Etc.
 +
 +---
/net/html/perso/melancon/Visual_Analytics_Course/data/attic/chicoutimi_2016/implementation_des_doi_graphs_de_van_ham.1464198119.txt.gz · Last modified: 2016/05/25 19:41 by melancon