Balade dans le métro parisien
1.0
- Auteur:
- Jérémie Fouché
- Version:
- 1.0
- Date:
- juin 2009
Introduction
Algorithme
Installation
Tests
Ce projet s'inscrit dans les défis c++ proposés par developpez.com. Le but de ce projet est de proposer un programme permettant de se balader dans le métro parisien, et de trouver le chemin le plus court pour aller d'une station à une autre. Le trajet doit pouvoir passer par des étapes prédéfinies.
L'idée est de se baser sur l'utilisation des graphes. Il faut donc modéliser le plan du métro sous forme de graphe. Le graphe utilisé sera non orienté, car nous pouvons parcourir les lignes dans un sens comme dans l'autre. La méthode est la suivante :
Soit
S1...
Sn les différentes stations d'une ligne de métro, et
d le delai entre 2 stations d'une même ligne. La modélisation choisie est la suivante :
Ligne de métro
Un correspondance est l'endroit ou 2 lignes se rejoignent. Soit
c le delai pour parcourir la correspondance. La modélisation choisie est la suivante :
Correspondance
ou la 2nde station de la ligne 2 correspond avec le 3ème station de la ligne 1 (les 2 stations ont le même nom).
Pour implementer le départ et l'arrivée, je crée 2 stations virtuelles (
D et
A). Je connecte ces stations au graphe via l'ensemble de leurs correspondances.
Départ et arrivée
Pour implementer une étape, je crée une station virtuelle (E sur l'image), connectée au graphe représentant le plan du métro.
Etape
Pour la suite, j'appellerai
G le graph représentant un plan de métro sans étape, et
En l'etape n. Tous les graph G sont identiques.Ce qui donne le graphe simplifié suivant pour une étapes :
Etape
Dans le cas du trajet non optimisé, on doit parcourir l'ensemble des étapes dans l'ordre. Le graphe devient le suivant.
Trajet non optimisé
Dans le cas du trajet optimisé, on doit parcourir l'ensemble des étapes dans un ordre quelconque afin de trouver le chemin le plus court. Le graphe devient le suivant pour 3 étapes.
Trajet optimisé
Le compilateur utilisé est g++. L'environnement de developpement utilisé est
CodeLite. Ce programme s'appuie sur la bibliotheque BOOST, et plus particulierement sur les bibliotheques suivantes :
- boost::graph : pour l'implementation du model de graphe
- boost::multi_index : pour le stockage des informations des stations
- boost::program_options : pour l'analyse de la ligne de commande
- et quelques algorithme sur les chaine de caractere (join, split, ...)
Dans les chapitres suivants, nous verrons l'installation spécifique à une plateforme.
La version de Windows testée est Windows XP SP3 édition familiale , avec 512 Mo de RAM, et processeur Pentium M 1.5 GHz.
Le compilateur utilisé est g++ 3.4.5, issue de la dernière release officielle de MinGW. Assurez vous que le repertoire bin soit dans le PATH de Windows. Je conseil de de mettre le repertoire MinGW à la racine du disque C:.
Pour installer boost, le plus simple est de le télécharger (je me suis basé sur la version 1.39) et de la décompresser dans un dossier de votre choix. Ensuite, placez vous dans le repertoire boost_1_39_0 et invokez la commande suivante pour compiler bjam (l'outil de compilation de boost) :
Editer le fichier project-config.jam, afin de modifier le le toolset initialement à msvc, pour le changer à gcc :
Enfin, on peut compiler la bibliotheque program_options :
bjam --toolset=gcc --with-program_options release stage
Pour être plus compatible avec MinGW, nous allons renommer la bibliotheque générée :
cd stage\lib
ren *.lib *.a
Tout est désormais prêt pour pouvoir générée notre application.
- Lancer CodeLite
- Créer la variable d'environement boost en allant dans le menu Settings -> Environment Variables. Clickez sur le bouton New et ajouter la variable boost, avec pour valeur le repertoire de boost (C:\_Perso\projets\lib\boost_1_39_0 dans mon cas).
- Ouvrir l'espace de travail metro.workspace depuis CodeLite (menu Workspace -> Switch to workspace).
- Selectionner la configuration à compiler. 4 configurations sont disponibles : Debug, Release, WinDebug et WinRelease. Le 2 premieres sont pour Linux, et les 2 suivantes pour Windows. Il suffit de selectionner dans le panel gauche la configuration souhaitée ( WinRelease dans notre cas).
- Il ne reste qu'à compiler le projet en allant dans le menu Build -> Build project, et hop, on attend la fin de la compilation. Un warning est présent, lié au fait que la bibliotheque boost s'appuie sur une fonctionnalité C99, qui provoque un warning avec les options -ansi -pedantic. Ce dernier n'est pas significatif, et peut être ignoré.
Si vous ne souhaitez pas utiliser CodeLite, un makefile est disponible dans le répertoire build : makefile.mingw
mingw32-make -f makefile.gcc
Editer ce fichier afin de mettre la variable boost à la bonne valeur, c'est à dire le repertoire ou vous avez installé boost.
La version de Linux testée est Ubuntu 7.10, avec 256 Mo de RAM, et processeur Athlon 700 MHz.
Le compilateur utilisé est g++ 4.1, disponible sur ma distribution.
Pour installer boost, le plus simple est de le télécharger (je me suis basé sur la version 1.39) et de la décompresser dans un dossier de votre choix. Ensuite, placez vous dans le repertoire boost_1_39_0 et invokez la commande suivante pour compiler bjam (l'outil de compilation de boost) :
Enfin, on peut compiler la bibliotheque program_options :
sudo ./bjam --with-program_options release stage
Tout est désormais prêt pour pouvoir générée notre application.
- Lancer CodeLite
- Créer la variable d'environement boost en allant dans le menu Settings -> Environment Variables. Clickez sur le bouton New et ajouter la variable boost, avec pour valeur le repertoire de boost (/home/jeremie/projets/lib/boost_1_39_0 dans mon cas).
- Ouvrir l'espace de travail metro.workspace depuis CodeLite (menu Workspace -> Switch to workspace).
- Ouvrir l'espace de travail metro.workspace depuis CodeLite (menu Workspace -> Switch to workspace).
- Selectionner la configuration à compiler. 4 configurations sont disponibles : Debug, Release, WinDebug et WinRelease. Le 2 premieres sont pour Linux, et les 2 suivantes pour Windows. Il suffit de selectionner dans le panel gauche la configuration souhaitée ( Release dans notre cas).
- Il ne reste qu'à compiler le projet en allant dans le menu Build -> Build project, et hop, on attend la fin de la compilation. Un warning est présent, lié au fait que la bibliotheque boost s'appuie sur une fonctionnalité C99, qui provoque un warning avec les options -ansi -pedantic. Ce dernier n'est pas significatif, et peut être ignoré.
Si vous n'utilisez pas la version 4.1.x de gcc, il faut modifier le nom de la bibliotheque libboost_program_options-gcc41-mt afin qu'elle soit conforme à votre compilateur.
Si vous ne souhaitez pas utiliser CodeLite, un makefile est disponible dans le répertoire build : makefile
Editer ce fichier afin de mettre la variable boost à la bonne valeur, c'est à dire le repertoire ou vous avez installé boost.
Pour les essais, il suffit d'aller dans le repertoire bin, et lancer l'executable
metro
avec les paramètres qui vont bien.
Exemple :
./metro -f ListeStationsUnicode.txt -d 60 -c 300 -i "jules joffrin" -i "mairie d'ivry" -i "porte de clichy" -o
Le trajet optimal est affiché à l'écran :
Trajet de esplanade de la defense vers raspail
Station de depart :
> esplanade de la defense
Station d'arrivee :
> raspail
Etapes : jules joffrin, mairie d'ivry, porte de clichy
Recherche optimisee
00:00:00 : Prendre la ligne [Ligne 1] direction Château de Vincennes
Sortir a la station Concorde
00:14:00 : Prendre la ligne [Ligne 12] direction Porte de la Chapelle
Sortir a la station jules joffrin
00:23:00 : Arrivee a l'etape jules joffrin
00:28:00 : Prendre la ligne [Ligne 12] direction Mairie d'Issy
Sortir a la station Saint-Lazare
00:40:00 : Prendre la ligne [Ligne 13] direction Châtillon-Montrouge
Sortir a la station Invalides
00:48:00 : Prendre la ligne [RER C] direction Porte de Clichy
Sortir a la station porte de clichy
00:57:00 : Arrivee a l'etape porte de clichy
01:02:00 : Prendre la ligne [RER C] direction Bibliothèque François Mitterrand
Sortir a la station Gare d'Austerlitz
01:19:00 : Prendre la ligne [Ligne 5] direction Place d'Italie
Sortir a la station Place d'Italie
01:27:00 : Prendre la ligne [Ligne 7] direction Mairie d'Ivry
Sortir a la station mairie d'ivry
01:34:00 : Arrivee a l'etape mairie d'ivry
01:39:00 : Prendre la ligne [Ligne 7] direction La Courneuve-8 Mai 1945
Sortir a la station Place d'Italie
01:51:00 : Prendre la ligne [Ligne 6] direction Charles de Gaulle-Étoile
Sortir a la station raspail
01:56:00 : Arrivee