L’objectif est de réaliser une librairie de classes et fonctions permettant de manipuler des graphes.
Dans ce projet tuteuré, nous allons mettre en place toutes les classes permettant de créer, modifier et accéder à un graphe orienté. Pour cela nous allons créer 4 classes :
- La classe CException : qui permettra de lever des exceptions,
- La classe CArc : qui représentera des arcs dans le graphe,
- La classe CSommet : qui représentera des sommets dans le graphe,
- La classe CGraphe : qui représentera un graphe.
Dans votre projet on supposera qu’aucune information particulière n’est stockée au niveau des sommets et des arcs.
Dans la classe Carc, il n’y a qu’un seul attribut : le numéro du sommet destination (nommons le Destination).
Dans la classe Csommet, il y a trois attributs : le numéro du sommet, la liste des arcs partants du sommet et la liste des arcs arrivants au sommet. Ces deux listes d’objets devront être gérées dynamiquement. Je vous propose l’implémentation suivante :
Vous devrez développer une fonction qui permet de lire le contenu d’un graphe dans un fichier texte et créer un objet graphe en mémoire pour stocker les données lues dans le fichier. Le format du fichier texte (imposé) est donné ci-dessous
NBSommets=<Nombre_de_Sommets_du_graphe>
NBArcs=< Nombre_d_arcs_du_graphe >
Sommets=[
Numero=<Numéro_sommet >
Numero=<Numéro_sommet>
…
Numero=<Numéro_sommet>
]
Arcs=[
Debut=<Sommet_départ_arc>, Fin=<Sommet_arrivée_arc>
Debut=<Sommet_départ_arc>, Fin=<Sommet_arrivée_arc>
…
Debut=<Sommet_départ_arc>, Fin=<Sommet_arrivée_arc>
]
Un exemple :
NBSommets=3
NBArcs=3
Sommets=[
Numero=1
Numero=2
Numero=3
]
Arcs=[
Debut=1, Fin=2
Debut=2, Fin=3
Debut=3, Fin=1
]
N.B. : Le format du fichier contenant le graphe doit alors correspondre à l'expression régulière :
/NBSommets[ \t]*=[ \t]*([0-9]+)[ \t]*\nNBArcs[ \t]*=[ \t]*([0-9]+)[ \t]*\nSommets[ \t]*=[ \t]*(\[)[ \t]*\n((?:Numero[ \t]*=[ \t]*[0-9]+\n)*)\][ \t]*\nArcs[ \t]*=[ \t]*(\[)[ \t]*\n((?:Debut[ \t]*=[ \t]*[0-9]+[ \t]*,[ \t]*Fin[ \t]*=[ \t]*([0-9]+)[ \t]*\n)*)\]\s*/Utiliser regexr.com/5rvv4 pour vérifier qu'un fichier convient au format demandé.
Plus d'exemples sont disponibles dans le dossier Fichiers Test/.
Les fichiers TestX_OK.txt sont des fichiers bien formattés pour la création d'un graphe selon le modèle vu précédemment. Ce n'est en revanche pas le cas des fichiers TestX_KO.txt qui crérons une erreur lors de leur traitement.
Après analyse du sujet, nous avons réaliser le schéma UML suivant :
| Nom de classe | Description |
|---|---|
CGraphe |
Cette classe nous permet de gérer directement tout ce qui concerne un graphe, à savoir :
|
CSommet |
Cette classe nous permet de gérer directement tout ce qui concerne un sommet, à savoir :
|
CException |
Cette classe sert à créer des exceptions personnalisées |
CArc |
Cette classe nous permet de gérer directement tout ce qui concerne un arc |
Il suffit simplement de passer un ou plusieurs chemins vers un/plusieurs fichier(s) contenant un graphe au format spécifié dans la partie "1.2. Spécifications lecture d'un graphe depuis un fichier".
Par exemple si vous vous placez dans C:/some/path/to/projet/projet-tutore-3-graphes/ProjetGraphes/Release/ vous pouvez lancer la commande :
start ProjetGraphes "../Fichiers Test/Test1_OK.txt" "../Fichiers Test/Test2_OK.txt" "../Fichiers Test/Test3_OK.txt" "../Fichiers Test/Test1_KO.txt" "../Fichiers Test/Test2_KO.txt" "../Fichiers Test/Test3_KO.txt" ""