1 Objectif du devoir

Le but est de mettre en pratique les concepts de la programmation orientée objet et plus particulièrement :

• définir un ensemble de classes dans le but de réaliser un logiciel et d’en permettre la réutilisation pour d’autres logiciels ;
• implémenter des classes en respectant rigoureusement leur interface (i.e. commentaires et contrat associé à chaque classe) ;
• utiliser correctement l’héritage et le polymorphisme ;
• spécifier aussi précisément que possible le contrat d’une classe ;
• écrire les commentaires d’une classe.

2 Présentation du sujet

Il s’agit de définir un ensemble de classes représentant des graphes, dans le but de réaliser d’une part une bibliothèque de classes basique pour la représentation et la gestion de graphes et, d’autre part, un logiciel utilisant ces classes afin :

• de représenter un plan de métro - y compris le temps de parcours entre 2 stations voisines - et de l’afficher
• de représenter le plan d’une ville avec les sens uniques et la distance entre 2 carrefours voisins et de l’afficher
• de déterminer un chemin (de préférence le plus court possible) entre deux nœuds d’un graphe

3 Travail demandé

Le devoir doit être réalisé individuellement : chaque étudiant devra rendre sa propre version du logiciel ainsi qu’un rapport décrivant le travail réalisé.

3.1 Conception et implémentation d’une bibliothèque de classes sur les graphes

Pour ce travail, vous pourrez vous inspirez de la bibliothèque de classes JGraphT disponible (documentation et code source sous licence GPL) à l’adresse : http://jgrapht.sourceforge.net/

Vous devrez concevoir (i.e. définition de l’interface et du contrat) et implémenter, au minimum :

• Une classe définissant la notion la plus générale possible de graphe, c’est-à-dire, indépendamment du fait que les graphes soient ou non orientés ou que des valeurs numériques soient ou non associées aux arcs ou arêtes ;
• Une classe permettant de représenter des graphes orientés avec des valeurs numériques associées aux arcs ;
• Une classe permettant de représenter des graphes non orientés avec des valeurs numériques associées aux arêtes ;
• Une classe permettant de représenter les arcs ou arêtes d’un graphe ;

Contribuer au projet JGraphT Plutôt que de redéfinir une nouvelle bibliothèque de classes, votre travail pourra prendre la forme d’une contribution au projet JGraphT de la manière suivante :

• sélectionnez parmi les classes de la bibliothèque JGraphT, les classes qui vous seront utiles pour la réalisation du logiciel ;
• ajouter aux classes sélectionnées les assertions correspondant au contrat de ces classes tel qu’il est spécifié dans leur documentation.

3.2 Conception et implémentation de classes pour représenter des plans

Pour la réalisation du logiciel proprement dit, vous devrez concevoir (i.e. définition de l’interface et du contrat) et implémenter - en utilisant la bibliothèque de classes mentionné à la section précédente -, au minimum :

• Une classe permettant de représenter un plan de métro ;
• Une classe permettant de représenter le plan d’une ville ;
• Une classe permettant de tester les principales fonctionnalités des deux classes précédentes.

Ces deux classes devront permettre, au minimum :

• d’accéder à toutes les informations nécessaires à l’affichage d’un plan ;
• de tester l’existence d’un chemin entre deux sommets du graphe correspondant au plan, d’en calculer la longueur et de lister l’ensemble des sommets le constituant ;
• de déterminer le plus court chemin entre deux sommets, s’il existe un chemin entre ces deux sommets.

4 Bonus

En plus du travail demandé ci-dessus, jusqu’à 4 points de bonus (i.e. hors barème) pourront être attribués pour la réalisation d’un logiciel permettant l’affichage de plans de métro et de ville.

Pour ce travail, vous pourrez vous aider du logiciel disponible à l’adresse :

http://marc.champesme.free.fr/POO/source/LogicielGraphes.tar.gz

Ce travail sera évalué selon les critères suivant :

• affichage correct de l’ensemble du plan ;
• qualité du code : commentaires, assertions, respect des consignes sur la visibilité des variables...

5 Evaluation

La qualité de la réalisation sera évaluée selon les critères suivants :

• Qualité de la conception ;
• Conformité de l’implémentation par rapport à l’interface. La conformité de votre implémentation sera évaluée à l’aide de programmes de test permettant de tester chaque méthode sur des données représentant un large éventail de cas ;
• Qualité du rapport rendu

6 Documents à rendre par chaque étudiant

Chaque étudiant rend le code source des classes implémentées et un rapport permettant une compréhension rapide, complète et précise de l’ensemble du travail réalisé.