Balade dans le métro parisien

1.0

Auteur:
Jérémie Fouché
Version:
1.0
Date:
juin 2009

Sommaire

Introduction

Algorithme

Installation

Tests


Introduction

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.

Algorithme

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 :

Modélisation d'une ligne

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 :

graph_ligne.dot.png

Ligne de métro

Modélisation d'une correspondance

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 :

graph_correspondance.dot.png

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).

Modélisation du départ et de l'arrivéé

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.

graph_depart.dot.png

Départ et arrivée

Modélisation d'une etape

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.

graph_etape_1.dot.png

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 :

graph_etape_2.dot.png

Etape

Modélisation du trajet non optimisé

Dans le cas du trajet non optimisé, on doit parcourir l'ensemble des étapes dans l'ordre. Le graphe devient le suivant.

graph_non-optimise.dot.png

Trajet non optimisé

Modélisation du trajet 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.

graph_optimise.dot.png

Trajet optimisé

Installation

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 :

Dans les chapitres suivants, nous verrons l'installation spécifique à une plateforme.

MS Windows

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) :

 bootstrap.bat 

Editer le fichier project-config.jam, afin de modifier le le toolset initialement à msvc, pour le changer à gcc :

 using 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.

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.

Linux

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) :

 ./bootstrap.sh 

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.

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

 make -f makefile 

Editer ce fichier afin de mettre la variable boost à la bonne valeur, c'est à dire le repertoire ou vous avez installé boost.

Tests

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

Généré le Sun Jun 14 14:02:24 2009 pour Balade dans le métro Parisien par  doxygen 1.5.9