User Tools

Site Tools


chicoutimi_2016:implementation_des_doi_graphs_de_van_ham

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

    • Reste encore à proposer une vue avec “contexte élargi”; et la prise en compte d'une fonction 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).

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é.

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
  • 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).
  • 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 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 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/pages/chicoutimi_2016/implementation_des_doi_graphs_de_van_ham.txt · Last modified: 2016/05/28 15:29 by melancon