Helping you to find your way home
L'objectif de ce projet consiste à mettre en place un ensemble
d'algorithmes permettant de manipuler des données cartographiques,
et de fournir un service web pour afficher les résultats. Les
données sont obtenues à partir du
projet OpenStreetMap
(qui possède en particulier
un wiki
assez détaillé).
Les données manipulées par le projet sont des données au
format
osm
, qui est une forme de xml
, un
format de données structurées répandu. Le
fichier
suivant suivant est un exemple très
simple de données au format osm
:
La syntaxe de ces fichiers est décrite dans le wiki, en
particulier
les éléments
principaux ainsi que leurs
attributs.
Principalement, il ne s'agit de manipuler que les
éléments <node>
et <way>
.
Dans un premier temps, il est possible de considérer que les voies
sont systématiquement à double sens.
Graphes
Centrale au sujet est la notion de graphe. Il est nécessaire de
construire un graphe à partir de données au format XML,
d'exploiter un graphe pour calculer des distances et des chemins
particuliers, et de pouvoir transformer un graphe en données
graphiques. Puisque cette notion est centrale, une idée de départ
consiste à spécifier clairement
une interface
suivant permettant de manipuler un
graphe. Cette interface prendrait la forme suivante :
Les contrats permettent de raffiner les
propriétés de ce type abstrait de données. Naturellement, il est
nécessaire d'adapter et d'étendre cette interface pour répondre
aux besoins du sujet.
(require)
(provide (contract-out
;; Predicate identifying the vertices (returns true iff the argument
;; is a vertex)
;; @param v : any/c
;; @return : boolean?
[vertex? (-> any/c boolean?)]
;; Predicate identifying the graphs (returns true iff the argument is
;; a graph)
;; @param g : any/c
;; @return : boolean?
[graph? (-> any/c boolean?)]
;; Constructor of a vertex
;; @param id : exact-nonnegative-integer?
;; @return : vertex?
[vertex-new (-> exact-nonnegative-integer? vertex?)]
))
Description du projet
-
Écrire le code nécessaire pour charger des fichiers au
format
osm
et les transcrire en un format de graphe adéquat. Envisager de construire un ensemble de fonctions pour éliminer les éléments inutiles comme les chaînes de caractères vides et les attributs n'ayant pas d'utilité pour le sujet. -
Écrire le code nécessaire pour construire une version
simplifiée du graphe dans laquelle tous les sommets de
degré
2
ont été éliminés. -
Écrire le code nécessaire pour, étant donné deux sommets du
graphe spécifiés par leurs
id
, calculer un itinéraire (s'il existe) entre ces deux points dans le graphe. -
Écrire le code nécessaire pour, étant donné deux sommets du
graphe spécifiés par leurs
id
dans la même composante connexe, calculer la distance optimale entre ces deux sommets. Les distances seront approximées en utilisant la formule de Haversine (cf. aussi cette page d'explications). - Écrire le code nécessaire au calcul d'un cycle de longueur minimale passant par un ensemble de sommets donnés (cf. le problème du voyageur de commerce, considérer des algorithmes d'insertion avec différentes stratégies : nearest, farthest, random, …).
-
Écrire le code nécessaire pour réaliser un serveur HTTP
écoutant sur le port 9000 et répondant aux urls
suivantes :
- http://localhost:9000 : affiche la carte courante. Le graphe devra être dessiné en construisant un conteneur svg.
-
http://localhost:9000/route?start=<id>&end=<id> :
affiche l'itinéraire entre les deux points spécifiés par
les ids
start
etend
si ils sont dans la même composante connexe, et la phraseDisconnected Universe Error
sinon. -
http://localhost:9000/distance?start=<id>&end=<id> :
affiche la distance entre les deux points spécifiés par
les ids
start
etend
si ils sont dans la même composante connexe, et la phraseDisconnected Universe Error
sinon. -
http://localhost:9000/cycle?nodes=<id>,...,<id> :
affiche un cycle de longueur minimale passant par tous
les points dont les ids sont spécifiés dans la
liste
nodes
.
/ -- Base directory Makefile -- Global Makefile /maps -- Map files /src -- Source files /src/server.rkt -- Server file
Makefile
doit contenir une règle test
permettant d'exécuter les tests propres au projet. Le serveur doit
pouvoir être démarré en utilisant la commande décrite à la
section Ecriture
d'un serveur HTTP en utilisant la syntaxe suivante :
racket src/server.rkt maps/map.osm
server.rkt
ne doit pas être modifié.
Limitations : aucun Javascript
autorisé hors de la bibliothèque
JQuery incluse à partir de l'url suivante :
Considérer que les serveurs seront testés avec un navigateur
possédant l'extension NoScript
configurée en mode paranoïaque. Pas de Javascript démesuré par rapport
au code Racket. Aucune dépendance à un service
externe, quel qu'il soit hormis la bibliothèque précédente. En
particulier, pas de chargement de fichier
<script type="text/javascript" src="http://www.labri.fr/perso/renault/working/teaching/projets/files/projMapping.jquery.min.js"></script>
css
ou d'image
externe. Toutes les pages spécifiées renvoient du texte, du html ou du
json. Elles doivent systématiquement renvoyer un code HTTP
de 200
(Success).
Lecture de fichier XML
En Racket, il est particulièrement simple d'obtenir une structure à
partir d'un fichier au format
Le résultat obtenu à l'aide de cette commande est une structure
arborescente simple en Racket, dans laquelle un noeud est une
liste à au moins deux éléments tels que :
xml
.
|
|
- le premier élément est le nom du tag HTML associé au noeud;
- le second élément est une liste d'attributs sous forme de liste d'association;
- les éléments suivants sont les fils du noeud courant.
Ecriture d'un serveur HTTP
Le
fichier
suivant suivant contient le code
nécessaire à la création d'un serveur HTTP écoutant sur le
port
Un serveur est constitué des éléments suivants :
9000
, et servant soit des pages de texte, soit
des pages HTML selon l'url fournie.
Il est possible de lancer ce serveur à l'aide de la commande
suivante :
racket server.rkt
- un ensemble de pages
(ex. :
main-page
) qui sont des fonctions prenant en paramètre une requête et produisant une page au format désiré (html, texte ou json). - une fonction de routage
(ici :
server-dispatch
) associant une uri à la page correspondante - un appel à une fonction de la bibliothèque
d'applications
web lançant le serveur
(ici :
serve/servlet
), qu'il ne faut a priori pas modifier.
Recommandations
Pour l'ensemble du projet, il est recommandé de
systématiquement :
- Définir formellement les éléments nécessaires pour représenter le jeu, et les relier à leur implémentation.
- Définir formellement les algorithmes proposés, et étudier leur complexité (temps/mémoire). Il est aussi possible de définir une méthode empirique permettant de comparer les différentes algorithmes sur un ensemble de cartes données et de parcours à évaluer.
- Suivre les standards de codage développés dans le cours de programmation fonctionnelle et disponibles à l'adresse suivante.