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 25 à 27 de graphes.pdf.

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 TP3 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 115 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 122) et recherche en largeur (page 123) 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 est n'est pas beaucoup plus complexe. Il faut d'abord trouver l'endroit où stocker le tableau temporaire. Généralement, on place ce tableau dans une variable locale de la fonction. Cette option a pour avantage de supporter des implémentations multi-thread où plusieurs opérations de recherche seraient faites sur un même graphe. Voici un exemple.

template <class S>
void Graphe<S>::parcoursRechercheLargueur(const S& s) const{
    int n = sommes.taille();
    bool* visite = new bool[n];
    for(int i=0;i<n;i++)
      visite[i] = false;
    /* Implémenter l'algorithme ici. */
    delete[] visite;
}

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{
    set<S> sommets_visites;
    queue<S> sommets_a_visiter;
    sommets_a_visiter.push(s);
    while(!sommets_a_visiter.empty()){
        S suivant = sommets_a_visiter.front();
        sommets_a_visiter.pop();
        if(sommets_visites.count(suivant)>0) break;
        sommets_visites.insert(sommets_visites);
        ...
    }
}

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
./a.out

Création du graphe non orienté de Figure 58(a) à la page 115
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 111
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
./a.out

Création du graphe non orienté de Figure 58(a) à la page 115
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 111
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 optionnelle.
Compilez et comparez vos résultats.

g++ lab11.cpp
./a.out

Création du graphe non orienté de Figure 58(a) à la page 115
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 111
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}}