#include <stdio.h> #include <stdlib.h> #include <math.h> #include <assert.h> #include <stdbool.h> /* noeud : identifiant entre 0 et N-1 */ typedef int nodeID; /* représente une ville */ struct node_s { char nom[100]; // nom float x; // longitude float y; // latitude int hab; // nombre d'habitants }; typedef struct node_s node; /* représente une liaison possible */ struct edge_s { nodeID i; nodeID j; float d; bool selected; // pour l'algorithme de Kruskal (ou Prim) }; typedef struct edge_s edge; /* import : lit le fichier filename contenant des descriptions de villes et alloue dans le tas un tableau de n villes NB : n est renvoyé via le pointeur n */ node* lireFichier(const char* filename, int* n) { FILE* f = fopen(filename, "r"); if (f != NULL) { int nv; if (fscanf(f, "%d\n", &nv) == 1){ printf("il y a %d villes\n", nv); // on crée le tableau des villes // node* villes = // A COMPLETER // on lit les informations pour chaque ville // A COMPLETER // on ferme le fichier ouvert // on renvoie les résultats } } printf("Erreur de lecture 1\n"); exit(0); // erreur de lecture return NULL; } // Calcule la distance entre deux villes float dist(node n, node m) { // A COMPLETER return 0.; } /* crée l'ensemble des arêtes susceptibles de relier les villes les arêtes sont allouées dans le tas. Leur nombre na est renvoyé via pointeur */ edge* creerAretes(node* villes, int nv, int* na){ // edge* aretes = ... // A COMPLETER // ........... return NULL; } /* Code trouvé sur internet ... void q....(int* tab, int taille) { // ......... if (taille > 1){ int pivot = tab[0]; // ......... tab[0] = tab[taille-1]; tab[taille-1] = pivot; // .......... int isep = 0; // ....... for (int i = 0; i < taille - 1; i += 1){ int elt = tab[i]; if (elt < pivot) { tab[i] = tab[isep]; tab[isep] = elt; } } // .......... int tmp = tab[isep]; tab[isep] = pivot; tab[taille-1] = tmp; // q......(tab, isep); q......(.........); } } */ /* export : écrit dant le fichier filename les informations nécessaires à l'affichage des arêtes sélectionnées au format geojson */ void exporter(const char* filename, edge* aretes, int na, node* villes, int nv){ FILE* f = fopen(filename, "w"); fprintf(f,"{\"type\": \"FeatureCollection\",\"features\": [\n"); // A COMPLETER // ...........pour chaque arête e sélectionnée, on doit écrire dans f : // fprintf(f, "{\"type\": \"Feature\", \"geometry\": {\"type\": \"LineString\","); // fprintf(f, "\"coordinates\": [[%f, %f], [%f, %f]]}},\n", // villes[e.i].x, villes[e.i].y, villes[e.j].x, villes[e.j].y); // ...... et entre chaque écriture, on doit mettre une virgule "," fprintf(f,"]}"); fclose(f); } int main(){ printf("Yaourtophone project !\n"); const char* fichier_in = "villes20.txt"; const char* fichier_out = "villes20.geojson"; /* lecture du fichier */ int n; node* villes; // A FAIRE /* affichage des villes */ /* for (int i = 0; i < n; i++) { node v = villes[i]; printf("ville%d : %s (%d hab) %f %f\n", i, v.nom, v.hab, v.x, v.y); }*/ /* création du tableau d'arêtes */ int na; edge* aretes; // A FAIRE /* algorithme de Kruskal */ /* tri du tableau d'arêtes */ // A FAIRE // composantes connexes de chaque sommet int* cc = (int*) malloc(n * sizeof(int)); for (int i = 0; i < n; i += 1){ cc[i] = i; } // algo glouton // A FAIRE /* export geojson */ // A FAIRE return 0; }