Graphes et algorithmes - TP 2

Michel Couprie, Gilles Bertrand

Préliminaires

Avant tout, récupérez le fichier graphestp2.tar.gz et décompressez-le :

    gunzip graphestp2.tar.gz
    tar xvf graphestp2.tar
    rm graphestp2.tar
    cd GraphesTp2; ls

Cette archive contient des programmes en langage C pour manipuler des graphes, la documentation de ces programmes se trouve ici :

Documentation

Rappel du premier TP : description des structures de données utilisée pour représenter un graphe sous la forme Γ (application successeurs). Pensez également à vous référer à la documentation du code source, en particulier :

source des définitions des principales structures (graphe, cell...)
description des fonctions de base pour la manipulation de graphes (voir en particulier AjouteArc, EstSuccesseur)
description des fonctions de gestion de listes (LIFO) et de tableaux booléens (voir en particulier CreeLifoVide, EnsembleVide)

Analyse de trajectoires dans une chambre à bulles

L'image ci-dessus à gauche (source CERN) est extraite d'une photographie de chambre à bulles. A droite, l'image a été seuillée pour détecter les régions les plus claires (image bs0). Le fichier bs0.list contient les coordonnées des barycentres de ces régions (la première ligne du fichier indique le nombre de points). Deux autres images sont à votre disposition : bs1 et bs2, dont les fichiers de coordonnées sont respectivement bs1.list et bs2.list. Notre but dans ce TP est de reconstituer au mieux les trajectoires des particules (ensembles de points plus ou moins alignés) en négligeant les points isolés.

1. Écrire un programme qui lit un fichier de points, et construit un graphe antisymétrique⁽¹⁾ sans boucle⁽²⁾ tel que :

à chaque point correspond un sommet du graphe,
deux sommets sont reliés par un arc si la distance entre les points correspondants est inférieure à un seuil d.

Pour la suite du travail, ce graphe devra être représenté en mémoire, à la fois sous la forme "successeurs" (utiliser la fonction AjouteArc) et sous la forme "liste d'arcs" (champs tete et queue de la structure graphe). De plus, on associera aux arcs (champ v_arcs de la structure graphe) les distances entre les points correspondant aux extrémités.

Pour vous aider, voici un programme qui lit un fichier de points, construit un graphe vide (sommets seulement, pas d'arcs) dont les sommets correspondent aux points contenus dans le fichier, et permet la visualisation de ce graphe en générant un fichier PostScript. Les coordonnées des sommets sont stockées dans les champs x et y de la structure graphe.

⁽¹⁾ : G est un graphe antisymétrique si pour tout sommet x et pour tout sommet y de G, [ (x,y) arc de G ] implique [ (y,x) non arc de G ].

⁽²⁾ : G est un graphe sans boucle (ou antiréflexif) si pour tout sommet x de G, (x,x) n'est pas un arc de G.

2. Visualiser les graphes obtenus pour différentes valeurs de d. Peut-on trouver une valeur qui permette d'isoler les ``points de bruit'' des ``trajectoires de particules'', dans les trois images bs0, bs1, bs2 ?

3. Quelle est (approximativement) la valeur minimale d_min de d telle que le graphe obtenu à partir de bs0.list soit connexe ?

Proposez (sans l'implémenter) une méthode pour trouver la valeur exacte de d_min pour un ensemble quelconque de points. Complexité de la méthode ?

4. On suppose que les trajectoires se coupent entre elles et ne forment pas de cycle. Calculez, sur le graphe valué par les distances, un arbre de poids minimum. Pour cela, on utilisera l'un des algorithmes étudiés en cours (Kruskal 1). Voici une implémentation de l'algorithme Kruskal 1. Avant de l'utiliser, prenez le temps de bien le comprendre. En particulier, observez comment le test pour éviter la formation d'un cycle est effectée. Commentez les résultats obtenus sur les trois images bs0, bs1, bs2, en particulier : quels sont les défauts de la méthode ? Illustrez ces défauts par des exemples précis.

Note : Le tri ne s'effectue pas sur les valeurs du tableau v_arcs de la structure graphe, sinon les poids des arcs ne correspondraient plus aux données des tableaux tete et queue. La fonction TriRapideStochastique effectue le tri dans un tableau auxiliaire, qui sert d'index aux données du tableau v_arcs.

5. On voit sur certaines configurations qu'il est nécessaire de tenir compte du fait que des points appartenant à une même trajectoire sont approximativement alignés.

On se propose de redéfinir la nature des poids associés aux arcs, de façon à favoriser la sélection des arcs qui non seulement sont courts, mais sont également alignés avec des arcs adjacents. De plus, cette définition devra être relativement simple à implémenter.

Proposez plusieurs idées, confrontez-les avec celles de vos voisins et soumettez-les au professeur responsable du TP. Retenez la meilleure et implémentez-la. Résultat ?

Bonus (travail personnel après le TP)

6. Proposez et implémentez une stratégie pour éliminer les points de bruit, c'est-à-dire les points qui ne font clairement partie d'aucune trajectoire.

Dernière mise à jour : par Michel Couprie.