#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){ node* villes = malloc(nv * sizeof(node)); for (int i = 0; i < nv; i += 1) { node v; if (fscanf(f, "%s %d %f %f\n", v.nom, &v.hab, &v.x, &v.y) == 4) { villes[i] = v; } else { printf("Erreur de lecture 2\n"); exit(0); // erreur de lecture return NULL; } } fclose(f); *n = nv; return villes; } } printf("Erreur de lecture 1\n"); exit(0); // erreur de lecture return NULL; } float dist(node n, node m) { return 107 * sqrt(pow(n.x-m.x,2) + pow(n.y-m.y,2)); } /* 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){ *na = (nv * (nv - 1)) / 2; edge* aretes = (edge*) malloc(*na * sizeof(edge)); assert(aretes != NULL); int c = 0; for (int i = 0; i < nv; i += 1){ for (int j = i + 1; j < nv; j += 1){ aretes[c].i = i; aretes[c].j = j; aretes[c].d = dist(villes[i], villes[j]); aretes[c].selected = false; c += 1; } } return aretes; } //* tri */ void quicksort(edge* tab, int taille) { // trie en place les éléments de tab if (taille > 1){ edge pivot = tab[0]; // on place le pivot en fin de tableau (échange) tab[0] = tab[taille-1]; tab[taille-1] = pivot; // on partitionne int isep = 0; // indice de séparation for (int i = 0; i < taille - 1; i += 1){ edge elt = tab[i]; // élément à insérer if (elt.d < pivot.d) { tab[i] = tab[isep]; tab[isep] = elt; isep += 1; // FAIRE AVANCER LE SEPARATEUR } } // on place le pivot à l'emplacement sep edge tmp = tab[isep]; tab[isep] = pivot; tab[taille-1] = tmp; // on trie récursivement quicksort(tab, isep); quicksort(&(tab[isep+1]), taille - isep - 1); } } /* fusionne deux composantes connexes */ void fusion(int* cc, int n, int c0, int c1) { for (int i = 0; i < n; i += 1){ if (cc[i] == c1){ cc[i] = c0; } } } /* 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"); bool first = true; for (int i = 0; i < na; i += 1) { edge e = aretes[i]; if (e.selected) { if (!first) { fprintf(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); first = false; } } 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 = lireFichier(fichier_in, &n); /* 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 = creerAretes(villes, n, &na); /* algorithme de Kruskal */ /* tri du tableau d'arêtes */ quicksort(aretes, na); /* affichage des arètes */ for (int i = 0; i < na; i += 1){ edge e = aretes[i]; printf("%d-%d (%f)\n", e.i, e.j, e.d); } // 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 int nselected = 0; float ltot = 0.0; // pour poids de l'ACM for (int i = 0; i < na; i += 1){ edge e = aretes[i]; if (cc[e.i] != cc[e.j]) { aretes[i].selected = true; ltot += aretes[i].d; printf("arête choisie : %s-%s (%f)\n", villes[e.i].nom, villes[e.j].nom, e.d); fusion(cc, n, cc[e.i], cc[e.j]); nselected += 1; if (nselected == n - 1) { // optim : c'est fini break; } } } printf("longueur totale : %f\n", ltot); /* export geojson */ exporter(fichier_out, aretes, na, villes, n); // libération free(villes); free(aretes); free(cc); return 0; }