Initial commit

1 files changed, 182 insertions, 0 deletions

diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/tp4.cc b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/tp4.cc
new file mode 100644
index 0000000..73cdc4f
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/tp4.cc
@@ -0,0 +1,182 @@
+#include <cstdlib>
+#include <iostream>
+#include <vector>
+#include <fstream>
+#include <cmath>
+
+using namespace std;
+
+const int N=10;
+const int M=(N*(N-1))/2;
+
+typedef struct coord{int abs; int ord;} coord;
+typedef struct point{int x; int y;} point;
+
+void pointRandom(int n,coord point[][]);
+float distancexy(coord p1,coord p2);
+void voisins(int n,int dmax,coord point[][],vector<point> 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][N];                  // Les coordonnees des points.
+  vector<point> voisin[N][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 < 10; i ++){
+      for (int j = 0; j < 10; j ++){
+      point[i][j].abs = 60*i;
+      point[i][j].ord = 60*j;
+      cout << "Created point "<<i<<","<<j<<" coords : "<< point[i][j].abs <<" : "<<point[i][j].ord<<endl;
+      k++;
+    }
+    }
+  }
+float distancexy(point p1, point p2){
+  return pow((abs(p2.x-p1.x)+abs(p2.y-p1.y)),2);
+}
+void voisins (int n, int dmax, coord point[][], vector<point> voisins[][], int &m){
+  int arrete = 0;
+  for (int i = 0; i < 10; i ++){
+    for (int j = 0; j < 10; j ++){
+      for (int o = 0; o < 10 ; o ++){
+        for (int k = 0; k < 10; k ++){
+          if (((o==i+1) && (j==k))|| ((k==j+1) && (i==o)) || ((o==i+1) && (k==j+1))){
+            point tmp;
+            tmp.x=o;
+            tmp.y=k;
+            voisins[i][j].push_back(tmp);
+            tmp.x=i;
+            tmp.y=j;
+            voisins[o][k].push_back(tmp);
+          }
+        }
+      }
+      }
+    }
+  }
+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<10;i++)
+  for (int j = 0 ; j < 10; j ++){
+    {
+      output << point[i][j].abs << " " << point[i][j].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<10;i++)
+   {
+     for (int k =0; k < 10; k ++){
+     for (int j =0; j < voisins[i][k].size(); j ++){
+
+         output << point[voisin[i][k][j].x][voisin[i][k][j].y].abs<<" "<<point[voisin[i][k][j].x][voisin[i][k][j].y].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;
+}