Le but de ce TD est d'implémenter une structure de graphe générique et de manipuler quelques structures de la bibliothèque standard du C++. Les graphes implémentés ici seront non orientés et simple (pour chaque paire de sommet, il y a au plus une seule arête qui les relie).
Sommets du graphe
Créez une classe Sommet, représentant un sommet d'un graphe. Elle devra comporter :
-
le label du sommet, du type choisi par l'utilisateur (template),
-
un numéro permettant d'identifier le sommet,
-
des fonctions d'accès en lecture et écriture au label,
-
une fonction d'accès au numéro, en lecture uniquement.
Arêtes du graphe
Créez une classe Arete, qui comportera :
-
un poids, dont le type est passé en paramètre template,
-
les numéros de deux sommets,
-
un numéro, identifiant unique,
-
une fonction retournant les deux extrémités de l'arête.
Pour stocker les extrémités de l'arête, utilisez la classe std::pair. Les deux membres de cette classe sont publiques et se nomment first et second.
Graphe
Créez une classe Graphe, comportant :
-
un ensemble d'arêtes et un ensemble de sommets,
-
une fonction
ajouteSommet, -
une fonction
ajouteArete, -
deux fonctions retournant le nombre de sommets et le nombre d'arêtes,
-
deux fonctions retournant le sommet et l'arête ayant un numéro donné,
-
une fonction donnant le degré d'un sommet.
Utilisez la classe std::vector pour stocker les sommets et les arêtes. L'ajout d'un élément à la fin d'un vecteur se fait avec la fonction membre push_back qui redimensionne si besoin, l'accès aux éléments se fait comme pour un tableau classique.
Tramway
Utilisez votre classe graphe pour créer un plan simplifié du réseau de tram strasbourgeois :