Laboratoire 12 : Graphes / Extraction de la principale composante fortement connexe

Lectures préalables

Section 13.2.2 (Extraction des composantes fortement connexes) des notes de cours.

Objectifs

Implémenter une représentation de classe Carte.
Pratiquer l'implémentation d'algorithmes sur les graphes.
Se préparer au TP3 portant sur les graphes.

Observations

Une carte extraite d'OpenStreetMap peut ne pas être un graphe fortement connexe.
La carte ci-dessous (parc_isole.txt | parc_isole.osm extrait le 25 novembre 2013 d'OpenStreetMap) est un exemple de carte non fortement connexe.
On aperçoit un parc déconnecté sur sur l'île de Montréal (voir la région dans OpenStreetMap).
En effet, les nœuds n95 et n100 (les nœuds ont été renumérotés) sont connectés à aucun nœud de Mackle Road.
Par conséquent, un algorithme de recherche de chemin ne trouvera aucun chemin reliant n28 à n101.
Une étape de prétraitement typique est l'élimination des nœuds inaccessibles. C'est le but du Lab12. Cela passe par l'extraction de la de la principale composante connexe. À noter que cela n'est pas requis par le TP3.

Tâches

Début

Récupérez les fichiers du Lab12 : lab12.zip.
Prenez 5-10 minutes pour prendre connaissance de lab12.cpp, carte.h et carte.cpp.

Représentation d'une carte

Vous devez compléter la représentation de la classe Carte. Pour le Lab12, il est suggérer de commencer par la représentation ci-dessous qui est amplement suffisante pour le Lab12.

class Carte{
  public:
    ...
  private:
    class Noeud{ // Un noeud est un sommet dans le graphe
      Coordonnee coor; // variable inutile pour le Lab12, mais utile pour le TP3.
      set<string> voisins; // ensemble des noeuds liés par un segment (tronçon) de route (arête).
    };
    map<string, Noeud> noeuds; // dictionnaire nom de noeud -> objet Noeud
};

Cette représentation n'est peut-être pas la plus efficace. Cependant, elle a pour avantage d'être simple. Visez d'abord un programme fonctionnel. Une fois cet objectif atteint, pensez à une représentation plus efficace.

Chargement de la carte

Le format de carte du Lab12 est identique à celui du TP3. Le code pour lire un objet Carte est fourni dans l'opérateur operator >> (istream& is, Carte& carte) (voir iocarte.cpp). Cet opérateur appelle les fonctions Carte::ajouter_noeud(...) et Carte::ajouter_route(...). Vous devez compléter ces fonctions.

La fonction Carte::ajouter_noeud(...) est plutôt facile à implémenter. Il suffit d'ajouter un noeud dans le vecteur ou l'ensemble noeuds.

La fonction Carte::ajouter_route(...) demande un peu plus d'efforts. Lorsqu'on reçoit une liste de noeuds < n1, n2, n3, ..., nk >, il faut ajouter les arêtes (n1, n2), (n2, n3), (n3, n4), ..., (nk-1, nk). Pour le Lab12, vous n'avez pas besoin de conserver les noms de route. Notez que si on voulait ignorer les sens uniques, il faudrait aussi ajouter les arêtes dans le sens inverse : (n2, n1), (n3, n2), (n4, n3), ..., (nk, nk-1).

Détection des nœuds orphelins

Pour détecter les nœuds orphelins, c'est-à-dire les nœuds inaccessibles à partir de la principale fortement composante connexe de la carte, il suffit de :

partitionner la carte en composantes fortement connexes avec l'algorithme de Tarjan (voir Section 13.2.2 des notes de cours);
conserver la composante connexe qui contient le plus grand nombre de nœuds;
enlever tous les nœuds qui n'appartiennent pas à la plus grande composante connexe.

Pour se faire, complétez la fonction Carte::trouver_noeuds_inutiles(). Vous devrez probablement ajouter une fonction récursive pouvant se nommer Carte::tarjan_parcours_profondeur(...).

Le programme lab12 doit afficher les nœuds à exclure. Le test :

./lab12 parc_isole.txt

doit afficher:

n62 n84 n85 n86 n87 n88 n89 n90 n91 n92 n93 n94 n95 n96 n97 n98 n99 n100 n101 n102 n103 n104 n105 n106 n107 n108 n109 n110 n111 n112 n113 n114 n115 n116 n117 n118 n119 n120 n121 n122 n123
Nombre de noeuds exclus : 41

Vous pouvez également tester avec les deux cartes suivante :

La ville de Montréal [montreal-carte.zip] qui contient 94 863 nœuds, 37 546 et 230 400 références. Vous devriez trouver 1720 nœuds à exclure.
La province Québec [quebec-carte.zip] (39 Mo) qui contient 2 580 388 nœuds, 533 357 routes et 5 758 704 références. Vous devriez trouver 119 229 nœuds à exclure.

/* Fin du Lab12 */

Exercices complémentaires au Lab12

Version non récursive de `parcoursProfondeur()`

En théorie, les fonctions récursives et non récursives sont équivalentes en terme de complexité temporelle. Toutefois, en pratique, l'utilisation de fonctions récursives peut impliquer un surcoût (overhead). En effet, les appels de fonction implique des opérations additionelles. De plus, selon l'environnement utilisée, la pile d'exécution peut avoir une taille fixe, donc limitée. Un grand nombre d'appels récursifs peut entraîner un débordement de la pile d'exécution (stack overflow).

L'exécution d'algorithmes récursif dans un graphe, comme la recherche en profondeur dans une carte, peut impliquer un très grand nombre d'appels récursifs imbriqués. Dans le pire cas, le nombre d'appels récursifs sur la pile d'exécution sera égal au nombre de nœuds de la carte! La carte de Montréal fournie contient plus de 94 000 nœuds. La carte du Québec contient plus de 2 500 000 nœuds!

Sous Linux et Unix, vous pouvez vérifier la taille par défaut de la pile d'exécution avec la commande ulimit -a ou ulimit -s.

$ ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 63518
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 63518
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

Vous pouvez expérimenter l'effet de limiter la taille de la pile d'exécution en spécifiant une petite limite. Essayez :

$ ulimit -s 64
$ ./lab12 montreal-carte.txt
Erreur de segmentation (core dumped)

Cela devrait vous convaincre qu'il peut être intéressant de convertir une fonction récursive en une fonction non récursive. Le prochain exercice consiste à éliminer la récursivité dans la fonction Carte::tarjanParcoursProfondeur(...). Cet exercice est évidemment plus difficile que les exercices précédents. Ainsi, il est recommandé de commencer par un algorithme plus simple, comme la fonction Carte::parcoursProfondeur(...) que vous avez implémentée au Lab11.

Indice : certaines variables locales (incluant les paramètres) de la version récursive doivent être stockées dans un objet de type pile (std::stack).

Une fois que vous avez réussi pour Carte::parcours_profondeur(...), essayez de convertir la fonction Carte::tarjan_parcours_profondeur(...).

Comparaison de l'efficacité des fonctions récursive et non récursive

Pour mieux évaluer la différence entre les deux versions de Carte::tarjan_parcours_profondeur(...), on peut faire quelques petits changements. Par exemple, on peut:

éliminer l'affichage du résultat;
modifier la fonction Carte::trouver_noeuds_inutiles() pour qu'elle ne retourne pas le résultat;
appeler la fonction Carte::trouver_noeuds_inutiles() plusieurs fois pour amortir le temps de chargement de la carte;

    for(int i=0;i<50;i++)
        carte.trouver_noeuds_inutiles();
    //for(set<string>::iterator iter=noeudsinutiles.begin();iter!=noeudsinutiles.end();++iter){
    //    cout << *iter << ' ';
    //}
    //cout << endl;
    // cout << "Nombre de noeuds exclus : " << noeudsinutiles.size() << endl;

Ensuite, exécutez les deux versions du lab12 avec la commande time.

time ./lab12 montreal-carte.txt > /dev/null