Lab 11 : Graphes / Représentation et algorithmes de base

Lectures préalables

Section 12 (Graphes) des notes de cours.
Section 13.1 (Parcours) et 13.2 (Extraction composantes connexes) des notes de cours.
Diapositives de graphes.

Objectifs

Implémenter une représentation de classe Graphe.
Implémenter des algorithmes de base pour les graphes.
Mettre en pratique les conteneurs de la librairie standard C++.
Se préparer au TP5 portant sur les graphes.

Tâches

Code source de départ

Récupérez les fichiers du Lab11 : lab11.zip.
Prenez 5-10 minutes pour prendre connaissance de lab11.cpp et graphe.h.
Le premier et troisième graphes dans lab11.cpp sont ceux de la Figure 58 à la page 122 des notes de cours.


Graphe 1 (Figure 58a)	Graphe 3 (Figure 58b)

À partir du code source lab11.cpp, dessinez le 2e graphe sur papier.

Construction du graphe

Complétez la fonction void Graphe<S>::ajouterSommet(const S& s).
Complétez la fonction void Graphe<S>::ajouterAreteNonOrientee(const S& s).
Complétez la fonction void Graphe<S>::ajouterAreteOrientee(const S& s).
Simulez le code de construction du graphe1 et dessinez sa représentation en mémoire.
Simulez le code de construction du graphe3 et dessinez sa représentation en mémoire.

Marqueurs de sommets visités

Les algorithmes travaillant sur les graphes ont souvent besoin de mémoriser des informations à propos des sommets. Par exemple, les algorithmes recherche en profondeur (page 129) et recherche en largeur (page 130) ont besoin d'un marqueur visité. Vous en aurez besoin pour ce lab. Voici trois options pour implémenter des marqueurs visité.

Option 1 - Ajout d'une variable booléenne `visité` dans le sommet

L'option 1 est la plus simple. Elle consiste à ajouter une variable booléenne visité dans la classe Graphe::Sommet : mutable bool visite. Un premier désavantage est que cette variable consomme de la mémoire, et ce, durant toute la vie du graphe. Un deuxième désavantage est qu'elle ne permet pas plusieurs fils d'exécution (threads) sur un même objet. Dans le cadre du cours, ces désavantages ne sont aucunement problématiques. Évidemment, il ne faut pas oublier de remettre la variable visite à false au début ou à la fin de l'algorithme.

Le mot clé mutable permet de rendre une variable «modifiable» même si elle est modifiée dans un contexte constant. Par exemple, les fonctions parcoursRechercheProfondeur et trouverMeilleurChemin seront généralement constantes, car elles ne devraient pas modifier le graphe.

class Graphe {
  public:
    void parcoursRechercheLargueur(const S& s) const;
    ...
  private:
    struct Sommet {
       bool bidon;
       mutable bool visite;
       ...
    }
    Structure<Sommet> sommets;
    ...
};
...
template <class S>
void Graphe<S>::parcoursRechercheProfondeur(const S& s) const {
    Sommet& sommet = sommets[s];
    // ...
    sommet.bidon = true;  // Erreur de compilation, car *this est const.
    sommet.visite = true; // OK, même si *this est const.
    // ...
}

Option 2 - Tableau temporaire de marqueurs

L'option 2 consiste à stocker les marqueurs visités à l'extérieur de la structure Graphe::Sommet. Une façon simple est de créer un tableau de booléens dans la portée de fonction. Cette option a pour avantage de supporter des implémentations multi-thread où plusieurs opérations de recherche peuvent s'effectuer simultanément dans le même objet Graphe. Voici un exemple.

template <class S>
void Graphe<S>::parcoursRechercheProfondeur(const S& s) const {
    Tableau<bool> visite(n);
    for(int i = 0; i < n; i++)
      visite.ajouter(false);

    /* Implémenter l'algorithme ici. */
}

Option 3 - Ensemble (set) temporaire énumérant les sommets visités.

L'option 3 est avantageuse lorsque le nombre de sommets à marquer sera significativement plus petit que le nombre total de sommets du graphe. Par exemple, si on lance une recherche en largeur pour trouver un sommet à proximité d'un autre, il est possible qu'une faible portion du graphe soit effectivement visitée. Plus concrètement, si on recherche un chemin entre deux pavillons de l'UQAM, il est inutile de créer un tableau de marqueurs pour tous les sommets de l'Amérique du Nord! Ainsi, au lieu d'attacher une variable visite à chaque sommet, on énumère uniquement les sommets visités.

template <class S>
void Graphe<S>::parcoursRechercheLargueur(const S& s) const {
    ArbreAVL<S> sommets_visites;
    File<S> sommets_a_visiter;
    sommets_a_visiter.enfiler(s);
    while(!sommets_a_visiter.vide()) {
        S suivant = sommets_a_visiter.tete();
        sommets_a_visiter.defiler();
        if(sommets_visites.contient(suivant)) break;
        sommets_visites.inserer(suivant);
        ...
    }
}

Lien avec le TP5

Pour implémenter l'algorithme nécessaire au TP5, vous aurez besoin de variables distances et parents. Ces dernières peuvent être implémentées de façon similaire aux marqueurs pour nœuds visités.

Parcours recherche en profondeur

Complétez la fonction Graphe<S>::parcoursRechercheProfondeur().
Il faudra peut-être deux fonctions :

La fonction publique parcoursRechercheProfondeur() qui initialise les marqueurs visité à false et appelle une deuxième fonction privée parcoursRechercheProfondeur2().
La fonction parcoursRechercheProfondeur2() est récursive.

Compilez et comparez vos résultats.

g++ lab11.cpp -o lab11
./lab11

Création du graphe non orienté de Figure 58(a) à la page 122
Recherche profondeur : a
a b c d e g h f
Recherche profondeur : c
c a b f d e g h
Recherche largeur : a
a b c e f d g h
Recherche largeur : c
c a b d e f h g
Composantes connexes :
{{a,b,c,e,f,d,g,h}}

Création du graphe non orienté #2
Recherche profondeur : a
a b c
Recherche profondeur : c
c a b
Recherche largeur : a
a b c
Recherche largeur : c
c a b
Composantes connexes :
{{a,b,c},{d,e,f,h,g},{x,y},{z}}

Création du graphe orienté Figure 58(b) de la page 122
Recherche profondeur : a
a b c f d e g h
Recherche profondeur : c
c a b f d e g h
Recherche largeur : a
a b e c f d g h
Recherche largeur : c
c a b e f d g h
Composantes connexes :
{{a,b,e,c,f,d,g,h}}

Parcours recherche en largeur

Complétez la fonction Graphe<S>::parcoursRechercheLargueur().
Il s'agit d'une fonction non récursive. Contrairement à parcoursRechercheProfondeur(), il n'y a pas lieu de créer deux fonctions.
L'usage d'une file (std::queue) est conseillé.
Compilez et comparez vos résultats.

g++ lab11.cpp -o lab11
./lab11

Création du graphe non orienté de Figure 58(a) à la page 122
Recherche profondeur : a
a b c d e g h f
Recherche profondeur : c
c a b f d e g h
Recherche largeur : a
a b c e f d g h
Recherche largeur : c
c a b d e f h g
Composantes connexes :
{{a,b,c,e,f,d,g,h}}

Création du graphe non orienté #2
Recherche profondeur : a
a b c
Recherche profondeur : c
c a b
Recherche largeur : a
a b c
Recherche largeur : c
c a b
Composantes connexes :
{{a,b,c},{d,e,f,h,g},{x,y},{z}}

Création du graphe orienté Figure 58(b) de la page 122
Recherche profondeur : a
a b c f d e g h
Recherche profondeur : c
c a b f d e g h
Recherche largeur : a
a b e c f d g h
Recherche largeur : c
c a b e f d g h
Composantes connexes :
{{a,b,e,c,f,d,g,h}}

Extraction composantes connexes

Complétez la fonction Graphe<S>::extraireComposantesConnexes(). Ne faites que l'extraction simple en premier. L'extraction de composantes «fortement» connexes est l'objet du lab suivant.
Compilez et comparez vos résultats.

g++ lab11.cpp -o lab11
./lab11

Création du graphe non orienté de Figure 58(a) à la page 122
Recherche profondeur : a
a b c d e g h f
Recherche profondeur : c
c a b f d e g h
Recherche largeur : a
a b c e f d g h
Recherche largeur : c
c a b d e f h g
Composantes connexes :
{{a,b,c,e,f,d,g,h}}

Création du graphe non orienté #2
Recherche profondeur : a
a b c
Recherche profondeur : c
c a b
Recherche largeur : a
a b c
Recherche largeur : c
c a b
Composantes connexes :
{{a,b,c},{d,e,f,h,g},{x,y},{z}}

Création du graphe orienté Figure 58(b) de la page 122
Recherche profondeur : a
a b c f d e g h
Recherche profondeur : c
c a b f d e g h
Recherche largeur : a
a b e c f d g h
Recherche largeur : c
c a b e f d g h
Composantes connexes :
{{a,b,e,c,f,d,g,h}}