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

Both sides previous revision Previous revision
Next revision
Previous revision
chicoutimi_2016:implementation_des_doi_graphs_de_van_ham [2016/05/25 21:07]
melancon
chicoutimi_2016:implementation_des_doi_graphs_de_van_ham [2016/05/28 15:29] (current)
melancon
Line 10: Line 10:
 === Implémentation des DOI Graphs de van Ham === === Implémentation des DOI Graphs de van Ham ===
 --- ---
 +
 +  * [[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 Ham, F. and A. Perer (2009). ""​Search,​ Show Context, Expand on Demand":​ Supporting Large Graph Exploration with Degree-of-Interest."​ IEEE Transactions on Visualization and Computer Graphics 15(6): 953-960.}}   * {{:​chicoutimi_2016:​van_ham_2009_search_show_context_.pdf|van Ham, F. and A. Perer (2009). ""​Search,​ Show Context, Expand on Demand":​ Supporting Large Graph Exploration with Degree-of-Interest."​ IEEE Transactions on Visualization and Computer Graphics 15(6): 953-960.}}
   
Line 16: Line 20:
 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ère, par exemple, ou sélectionné manuellement) un //​contexte//:​ un sous-graphe contenant $u$ et les éléments les plus "​intéressants"​ à proximité. 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ère, par exemple, ou sélectionné manuellement) un //​contexte//:​ un sous-graphe contenant $u$ et les éléments les plus "​intéressants"​ à proximité.
  
 +== 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 == == Calcul du DOI ==
  
Line 64: Line 71:
 == Affichage du contexte == == Affichage du contexte ==
  
-  * 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 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 pourrionsplus 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.   * Je supposerai aussi que vous avez une deuxième vue noeud-lien.
Line 72: Line 79:
     * Une vue noeud-lien pour afficher le sous-graphe ''​context''​.     * 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épart, et le sous-graphe ''​context''​ que vous avez calculé.   * Positionnez ces trois vues à la main à partir des graphes que vous avez maintenant sous la main: le graphe de départ, et le sous-graphe ''​context''​ que vous avez calculé.
 +
 +== 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).
 +
 +  * La manière douce:
 +    * Observez ce qui se passe si vous modifiez (par script) le sous-graphe,​ en 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.1464203272.txt.gz · Last modified: 2016/05/25 21:07 by melancon