Initial commit

1 files changed, 170 insertions, 0 deletions

diff --git a/sem_5/HLIN501_Graphes/TP/TP4/tp4.cc b/sem_5/HLIN501_Graphes/TP/TP4/tp4.cc
new file mode 100644
index 0000000..40fd343
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP/TP4/tp4.cc
@@ -0,0 +1,170 @@
+#include <cstdlib>
+#include <iostream>
+#include <vector>
+#include <fstream>
+#include <cmath>
+
+using namespace std;
+
+const int N=1400;
+const int M=(N*(N-1))/2;
+
+typedef struct coord{int abs; int ord;} coord;
+
+void pointRandom(int n,coord point[]);
+float distancexy(coord p1,coord p2);
+void voisins(int n,int dmax,coord point[],vector<int> voisin[],int &m);
+void voisins2arete(int n,vector<int>voisins[],int arete[][2]);
+void affichageGraphique(int n,int m,coord point[],vector<int> voisins[],const char * name);
+bool existe(int n,int dis[],bool traite[]);
+int searchsmallest(int n, int dist[],bool traite[]);
+void dijkstra(int n,vector<int> voisin[],coord point[],int pere[], int m);
+int construireArbre(int n,vector<int> voisin[],int pere[]);
+
+int
+main()
+{
+  int n;                           // Le nombre de points.
+  cout << "Entrer le nombre de points: ";
+  cin >> n;
+  int dmax=50;                     // La distance jusqu'a laquelle on relie deux points.
+  coord point[N];                  // Les coordonnees des points.
+  vector<int> voisin[N];
+  vector<int> voisinbis[N];           // Les listes de voisins.
+  int arbre[N-1][2];               // Les aretes de l'arbre de Dijkstra.
+  int pere[N];                     // La relation de filiation de l'arbre de Dijkstra.
+  int m;                           // Le nombre d'aretes
+  int arete[M][2];                 // Les aretes du graphe
+  pointRandom(n,point);
+  voisins(n,dmax, point, voisin, m);
+  const char * filename = "affichage.ps";
+  affichageGraphique(n,m,point,voisin,filename);
+  cout<<"Graphe de base créé et exporté vers "<<filename<<endl;
+  dijkstra(n,voisin,point,pere,m);
+  construireArbre(n,voisinbis,pere);
+  const char * filename2 = "affichagefin.ps";
+  affichageGraphique(n,m,point,voisinbis,filename2);
+
+  return EXIT_SUCCESS;
+}
+
+void pointRandom(int n, coord point[]){
+    srand(time(NULL));
+    for (int i =0; i < n; i ++){
+      point[i].abs = rand()%612;
+      point[i].ord =rand()%792;
+      cout << "Created point "<<i<<" coords : "<< point[i].abs <<" : "<<point[i].ord<<endl;
+    }
+}
+float distancexy(coord p1,coord p2){
+  return sqrt((pow(p1.abs-p2.abs,2)+pow(p1.ord-p2.ord,2)));
+}
+void voisins (int n, int dmax, coord point[], vector<int> voisins[], int &m){
+  int arrete = 0;
+  for (int i = 0; i < n; i ++){
+    for (int j = i+1; j < n; j ++){
+      if ( sqrt(pow(point[i].abs-point[j].abs,2)+pow(point[i].ord-point[j].ord,2))<=dmax){
+        voisins[i].push_back(j);
+        voisins[j].push_back(i);
+        arrete++;
+      }
+    }
+  }
+  m=arrete;
+}
+
+void affichageGraphique(int n, int m, coord point[], vector<int> voisins[], const char * filename)
+// Cree le fichier Exemple.ps qui affiche
+// les points et l'arbre de Kruskal.
+{
+  ofstream output;
+  output.open(filename,ios::out);
+  output << "%!PS-Adobe-3.0" << endl;
+  output << "%%BoundingBox: 0 0 612 792" << endl;
+  output << endl;
+  for(int i=0;i<n;i++)
+    {
+      output << point[i].abs << " " << point[i].ord << " 3 0 360 arc" <<endl;
+      output << "0 setgray" <<endl;
+      output << "fill" <<endl;
+      output << "stroke"<<endl;
+      output << endl;
+    }
+  output << endl;
+  for(int i=0;i<n;i++)
+   {
+     for (int j =0; j < voisins[i].size(); j ++){
+       if (voisins[i][j] >= i){
+         output << point[i].abs<<" "<<point[i].ord << " moveto"<<endl;
+         output<<point[voisins[i][j]].abs << " " << point[voisins[i][j]].ord << " lineto"<<endl;
+         output<< "stroke"<<endl;
+         output << endl;
+       }
+     }
+   }
+     output<<"showpage";
+     output<<endl;
+}
+bool existe(int n,int dis[],bool traite[]){
+  bool test = true;
+  bool ret = false;
+  int i = 0;
+  while (test && i < n){
+    if (!traite[i] && (dis[i]!=-1)){
+      test = false;
+      ret = true;
+    }
+    i++;
+  }
+  return ret;
+}
+int searchsmallest(int n, int dist[],bool traite[]){
+  int ret=-1;
+  int retdist = 10000;
+  for (int i = 0 ; i < n; i ++){
+    // cout<<"i :"<< i << " Dist de i "<< dist[i]<<" traite de i "<<traite[i]<<endl;
+    if (traite[i]==false){
+      if (dist[i]!= -1){
+        if (dist[i]<=retdist){
+          retdist=dist[i];
+          ret =i;
+        }
+      }
+    }
+  }
+  // cout<<"Lancment du traitement de :" << ret<<endl;
+  return ret;
+}
+void dijkstra(int n, vector<int> voisin[], coord point[], int pere[], int m){
+  int d[n];
+  bool traite[n];
+  for (int i =0; i < n; i ++){
+    d[i]= -1;
+    traite[i]=false;
+  }
+  pere[0]=0;
+  d[0]=0;
+  while (existe(n,d,traite)){
+    int current = searchsmallest(n,d,traite);
+    //cout<<"C'est ti-par avec current = "<< current <<endl;
+    traite[current]=true;
+    // cout<<"traite current : " << traite[current]<<endl;
+    for (int i =0; i < voisin[current].size();i ++){
+      int x = current;
+      int y = voisin[current][i];
+      //cout<<"Traitement de l'arete "<<x<<";"<<y<<endl;
+      //cout << d[y] << "versus " << d[x]<< " + " <<distancexy(point[x],point[y])<<endl;
+      if (!traite[y] && ((d[y]==-1) || (d[y]>(d[x]+distancexy(point[x],point[y]))))){
+        d[y]=d[x]+distancexy(point[x],point[y]);
+        pere[y]=x;
+      }
+    }
+  }
+}
+int construireArbre(int n,vector<int> voisin[],int pere[]){
+  for ( int i = 0; i < n; i ++){
+    voisin[i].push_back(pere[i]);
+    voisin[pere[i]].push_back(i);
+  }
+  return n;
+}