User Tools

Site Tools


chicoutimi_2016:implementation_des_doi_graphs_de_van_ham

This is an old revision of the document!


Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / Session by session cutdown

Implémentation des DOI Graphs de van Ham

Vous travaillerez à partir du (des) graphe(s) que vous avez construit pour le devoir maison. Vous pouvez aussi travailler avec un autre graphe, mais celui-là est en principe déjà là, tout bien formaté.

Ce cours contient une suite d'instructions permettant d'implémenter la technique proposée par van Ham calculant pour un sommet choisi (par le billet de la formulation d'un critère, par exemple, ou sélectionné manuellement) un contexte: un sous-graphe contenant et les éléments les plus “intéressants” à proximité.

Calcul du DOI
  • Il vous faudra vous assurer que votre graphe dispose d'un propriété . 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.
  • Nous allons supposer que le focus est pour l'instant choisi en le sélectionnant manuellement.
    • 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.
  • Il faut aussi pouvoir calculer la distance au sommet focus .
    • La fonction max_distance de Tulip fait le travail. La distance à sera alors stockée dans une propriété du graphe.
  • Nous allons dans un premier temps ignorer la fonction 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é).
  • Il vous faudra stocker le calcul du d'un sommet dans une propriété (on suppose le sommet fixé). C'est une propriété qui est à créer et qui stocke un calcul:

Le choix des coefficients reste à déterminer. Notre 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).

Sélection du contexte

C'est l'algorithme vu en cours. On calcule un sous-graphe contenant le focus , d'une taille convenable. Fixons la taille à pour l'instant. L'algorithme est le suivant, qu'il faut implémenter.

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
  • L'implémentation de l'algorithme nécessite
    • 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 et on y ajoute un nouvel élément en temps (autant de fois que le degré de )
  • L'ensemble est un ensemble de sommets. Il nous faut donc calculer le sous-graphe induit sur ces sommets.
    • C'est ce que fait le plugin 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.
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 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.
  • 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é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 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)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, 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 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).

/net/html/perso/melancon/Visual_Analytics_Course/data/attic/chicoutimi_2016/implementation_des_doi_graphs_de_van_ham.1464205060.txt.gz · Last modified: 2016/05/25 21:37 by melancon