Available nodes

 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 :
(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?)]
))
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.

 Description du projet

  1. É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.
  2. É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.
  3. É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.
  4. É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).
  5. É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, …).
  6. É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 et end si ils sont dans la même composante connexe, et la phrase Disconnected 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 et end si ils sont dans la même composante connexe, et la phrase Disconnected 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.
Pour les besoins du projet, les fichiers devront être organisés de la manière suivante dans le dépôt :
    /               -- Base directory
      Makefile      -- Global Makefile
    /maps           -- Map files
    /src            -- Source files
    /src/server.rkt -- Server file
Le 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
Le nom du fichier server.rkt ne doit pas être modifié.
Limitations : aucun Javascript autorisé hors de la bibliothèque JQuery incluse à partir de l'url suivante :
<script type="text/javascript" src="http://www.labri.fr/perso/renault/working/teaching/projets/files/projMapping.jquery.min.js"></script>
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 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 xml.
(require xml)

(xml->xexpr (document-element
    (read-xml (open-input-file "projMapping.osm"))))
'(osm
  ((version "0.6"))
  (bounds ((maxlat "44.7705300") (maxlon "-0.8510300") (minlat "44.7667500") (minlon "-0.8588800")))
  (node ((id "515330686") (lat "44.7754213") (lon "-0.8587464")))
  (node ((id "2097959544") (lat "44.7216967") (lon "-0.7988466")))
  (way
   ((id "199797372"))
   (nd ((ref "2097959544")))
   (nd ((ref "515330686")))
   (tag ((k "highway") (v "tertiary")))
))
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 :
  • 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 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 serveur est constitué des éléments suivants :
  • 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.