User Tools

Site Tools


chicoutimi_2016:may_6_1pm_course

Visual Analytics Course

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

Chicoutimi Summer 2016 roadmap / Session by session cutdown

May 6, 1pm course -- Exercices

La séance sera consacré à l'implémentation de différents algorithmes vus au cours de la matinée.

Arbres

Vous implémentez les algorithmes suivants, en python, sous Tulip. (La séance ne suffira pas, il nous faudra faire des choix.) Il vous sera probablement utile de vous documenter sur celui-ci. Aller voir du côté de d3js.org.

  • Icicle plot. Une variation de l'algorithme vu ce matin en cours – à la différence que les arêtes ne sont pas rectilignes, que les sommets ont une épaisseur.
  • Onion Graph, où les sommets sont représentés par des rectangles. Un sommet interne contient les rectangles associés à ses fils. Les feuilles de l'arbre sont représentés par des rectangle de taille égales (pour simplifier).
  • Radial tree. Similaire à l'algorithme de ce matin, à l'exception que les sommets sont disposés sur des cercles concentriques – une version polaire de l'algorithme classique.
  • Sunburst, qui correspond à une version radiale des icicle plot.

Graphes planaires

Donnez une implémentation de l'algorithme de test de planarité présenté en cours.

  • On supposera d'abord le graphe biconnexe.
    • Le travail consiste d'abord à trouver un cycle dans ce graphe. On procède en traversant le graphe en profondeur (ou en largeur, comme on veut):
F file
V (visited nodes) map
P parent map

# on choisit un sommet de depart quelconque du graphe et on l'insère dans la file
sommet_depart = choix_sommet()
F.enfiler(sommet_depart)
tant que la file F n'est pas vide
    u = F.defiler()
    V[u] = True (marquer u comme visite)
    iterer sur les voisins v de u
        si V[v] = True (v a deja ete visite) -- on tient notre cycle
        # puisqu'on a deux chemins allant de u a v
        # on s'arete
        # reste a extraire un cycle elementaire du cycle qu'on a trouve
        sinon F.enfiler(v)
  • Avec ce cycle en main, on calcule les classes d'arêtes (des sous-graphes)
  • On calcule pour chaque classe ses points d'ancrage sur le cycle (les sommets membres à la fois de la classe et du cycle)
  • On instancie le graphe sur l'ensemble des classes (on fabrique un autre graphe)
    • Chaque sommet de ce graphe correspond à une classe
    • Deux sommets sont liés si les classes associées se chevauchent
  • On teste pour savoir si ce graphe est biparti. On utilise un algorithme simple et facilement implémentable: un graphe est biparti s'il est 2-coloriable.
  • Tulip possède des routines (plugins) qui testent si un graphe est connexe. On peut donc ainsi tester à la manière brutale pour trouver les points d'articulations d'un graphe connexe.
    • Les plus courageux (raffinés ?) implémenteront le calcul à partir d'un arbre couvrant DFS.
    • Après avoir trouvé les points d'articulations, on les supprime et on calcule les composantes connexes qui sont les composantes biconnexes du graphe de départ.
  • Si vous en avez le temps, le courage, la motivation, vous pouvez aller jusqu'à donner un dessin du graphe – lorsque votre test est positif (!)
    • D'abord d'une composante biconnexe – à partir du cycle dessiné sur un cercle et en agrégeant les classes qu'il faut disposer à l'intérieur ou à l'extérieur du cercle.
    • Puis en assemblant les dessins des différentes composantes biconnexes.
    • Puis en juxtaposant les dessins des composantes connexes.

Spring embedders fournis par Tulip (GEM, FM^3, LinLog, …)

  • Prenez le temps de fouiller Tulip et de tester les différents algorithmes masses-ressorts disponibles. Arrpetez-vous sur FM^3, GEM, LinLog.
  • Implémentez par vous-mêmes la version basique présentée en cours. Expérimentez avec les paramètres contrôlant la simulation, proposez des améliorations.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/may_6_1pm_course.txt · Last modified: 2016/05/05 18:16 by melancon