INF3105 — Structures de données et algorithmes
Été 2024
UQAM
Département d'informatique

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

Lectures préalables

Objectifs

Motivation

Tâches


Début

  1. Récupérez les fichiers du Lab12 : lab12.zip.
  2. Prenez 5-10 minutes pour prendre connaissance des fichiers sources 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éré de commencer par une représentation simple telle que celle ci-dessous. Elle n'est pas parfaite, mais amplement suffisante pour le Lab12. 

class Carte {
  public:
    ...
  private:
    struct Noeud { // Un noeud est un sommet dans le graphe
      std::string contenu; // variable inutile pour le Lab12.
      set<long> voisins; // ensemble des noeuds liés par un segment (tronçon) de route (arête).
    };
    map<long, Noeud> noeuds; // dictionnaire identifiant 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

Format des fichiers de carte

Un fichier carte.txt est constitué de :

  1. Une liste de noeuds (points). Un noeud est spécifié par :
    • un nom (une chaîne de caractères) commençant par le caractère «n» et suivit d'un numéro unique (un entier 64 bits suffit);
    • une position de la forme «(latitude,longitude)»;
    • un point-virgule (;) marquant la fin d'un noeud.
  2. Trois tirets (---) de séparation.
  3. Une liste de routes. Une route est spécifiée par :
    • un nom de route (une chaîne de caractères sans espaces blancs);
    • un deux-points (:);
    • une liste de noms de noeud;
    • un point-virgule (;) marquant la fin d'un noeud.

À titre d'exemple, voici un extrait du fichier (parc_isole.txt) : 

n1 (45.47821,-73.66648);
n2 (45.4781,-73.66658);
n3 (45.48023,-73.6653);
...
n124 (45.48005,-73.66538);
n125 (45.48122,-73.66446);
---
Davies_Avenue :  n55 n58 n59 n60 n61 ;
Davies_Avenue :  n61 n60 n59 n58 n55 ;
Palmer_Avenue :  n67 n64 n66 n65 n57 n56 ;
Palmer_Avenue :  n56 n57 n65 n66 n64 n67 ;
Wentworth_Avenue :  n62 n36 ;
...

Le code pour lire un objet Carte est fourni dans l'opérateur operator >> (istream& is, Carte& carte) (voir fcarte.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 nœud dans le vecteur ou l'ensemble noeuds.

La fonction Carte::ajouter_route(...) demande un peu plus d'efforts. Lorsqu'on reçoit une séquence d'identificateurs de noeud < 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 problématiques à exclure

Pour détecter les nœuds problématiques à exclure, il suffit de :

  1. partitionner la carte en composantes fortement connexes avec l'algorithme de Tarjan (voir Section 13.2.2 des notes de cours);
  2. conserver la composante fortement connexe qui contient le plus grand nombre de nœuds, c'est-à-dire d'enlever tous les nœuds qui n'appartiennent pas à la plus grande composante fortement connexe et toutes les arêtes rattachées.

Pour se faire, complétez la fonction Carte::trouver_noeuds_problematiques(). 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

Autres tests

Vous pouvez également tester avec les cartes suivantes :

Vous pouvez télécharger ces cartes en lançant le script ./telecharger_tests.bash.
La carte du Canada est commentée dans le script. Vous pouvez la décommenter pour la télécharger (le fichier fait 1 GB une fois décompressé).



/* Fin du Lab12 */

Exercices complémentaires au Lab12

Implémentation 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 additionnelles. 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écursifs dans un graphe, comme la recherche en profondeur dans une grosse 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 100 000 nœuds. La carte du Québec contient plus de 3 000 000 nœuds. Et plus de 16 millions pour celle du Canada!

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::tarjan_parcours_profondeur(...). 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 Lab12.

Indice : certaines variables locales (incluant les paramètres) de l'implémentation récursive doivent être stockées dans un conteneur 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 implémentations de Carte::tarjan_parcours_profondeur(...), on peut faire quelques petits changements. Par exemple, on peut:

  1. éliminer l'affichage du résultat;
  2. modifier la fonction Carte::trouver_noeuds_problematiques() pour qu'elle ne retourne pas le résultat;
  3. appeler la fonction Carte::trouver_noeuds_problematiques() plusieurs fois pour amortir le temps de chargement de la carte;
    for(int i = 0; i < 50; i++)
        carte.trouver_noeuds_problematiques();
    //for(set<string>::iterator iter = noeuds_problematiques.begin(); iter != noeuds_problematiques.end(); ++iter) {
    //    cout << *iter << ' ';
    //}
    //cout << endl;
    // cout << "Nombre de noeuds exclus : " << noeuds_problematiques.size() << endl;

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

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