Il progetto utilizza le mappe stradali disponibili sul sito Open Street Map (OMS) e richiede di rappresentare una mappa come un grafo orientato. In particolare vengono fornite una mappa stradale di Pisa e le seguenti dieci piazze in ordine alfabetico:
Il progetto richiede di scrivere un programma per trovare un ordine di visita delle piazze in modo che la distanza totale percorsa a piedi sia breve, rispettando i sensi unici delle strade percorse: la distanza tra due piazze deve essere calcolata utilizzando la mappa di Pisa indicata sopra. Il programma prende in ingresso tale mappa e fornisce in uscita, oltre alla distanza totale percorsa, la sequenza dei nomi delle corrispondenti vie (chiaramente in ordine di percorrenza).
Per facilitare l’accesso ai dati codificati nella mappa, sono disponibili delle API (application program interface) scritte in linguaggio C da Luca Versari. In particolare, il file parse_osm.h contiene la descrizione di una mappa. Una mappa è costituita da
I tag usati per i nodi e le way nella mappa sono piuttosto numerosi, e sono raccolti qui. Il loro significato è descritto in http://wiki.openstreetmap.org/wiki/Tags.
Il programma test.c mostra un esempio d’uso. Per creare una rappresentazione interna della mappa con le API, a partire dal file pisa.osm fornito sopra, il programma utilizza la funzione osm_parse che restituisce una mappa struct come quella definita in parse_osm.h. Quindi il programma itera su tutti i nodi presenti nella mappa e, per ogni nodo, ne stampa l’ID, le coordinate e i tag.
#include "parse_osm.h"
int main() {
FILE *fd = fopen("pisa.osm", "r");
osm_map_t* map = osm_parse(fd);
unsigned i;
for (i=0; i<dyn_size(map->nodes); i++) {
osm_node_t* node = dyn_get(map->nodes, i);
printf("%lu (%lf, %lf)", node->id, node->lat, node->lon);
unsigned j=0;
for (j=0; j<dyn_size(node->tags); j++) {
osm_tag_t* tag = dyn_get(node->tags, j);
printf(" %s='%s'", tag->key, tag->value);
}
printf("\n");
}
osm_free_map(map);
return 0;
}
Occorre compilare con gcc dynarray.c dynstring.c parse_osm.c xml.c test.c -o test -O2 -Wall e lanciare ./test | more oppure test.exe | more da terminale (a seconda del sistema operativo).