Initial commit

1 files changed, 189 insertions, 0 deletions

diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tp2.cc b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tp2.cc
new file mode 100644
index 0000000..e598127
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tp2.cc
@@ -0,0 +1,189 @@
+#include <cstdlib>
+#include <iostream>
+#include <vector>
+#include <fstream>
+#include <cmath>
+
+typedef struct coord{int abs; int ord;} coord;
+void pointRandom(int n, coord point[]);
+void distances(int n, int m, coord point[], int edge[][3]);
+void tri(int m, int edge[][3]);
+void affichageGraphique(int n, int m, coord point[], int arbre[][2],  const char * filename);
+void kruskal (int n, int edge[][3], int arbre[][2]);
+void fusion(int tableau[][3],int deb1,int fin1,int fin2);
+void tri_fusion(int tableau[][3],int longueur);
+void tri_fusion_bis(int tableau[][3],int deb,int fin);
+using namespace std;
+
+int
+main()
+{
+  int n;            //Le nombre de points.
+  cout << "Entrer le nombre de points: ";
+  cin >> n;
+  int m=n*(n-1)/2;   // Le nombre de paires de points.
+  coord point[n];    // Les coordonnees des points dans le plan.
+  int edge[m][3];    // Les paires de points et le carre de leur longueur.
+  int arbre[n-1][2]; // Les aretes de l'arbre de Kruskal.
+  pointRandom(n,point);
+  distances(n,m,point,edge);
+  tri_fusion(edge,m);
+  // for (int i =0; i < m; i ++){
+  //   cout << "point "<< edge[i][0]<<":"<<edge[i][1]<<" coords : ("<< point[edge[i][0]].abs<<";"<<point[edge[i][0]].ord <<") ; ("<<point[edge[i][1]].abs<<" ; "<<point[edge[i][1]].ord<<") norme : "<<edge[i][2]<< endl;
+  // }
+  int edge2[m][2];
+  for(int i =0; i < m; i ++){
+    edge2[i][0]=edge[i][0];
+    edge2[i][1]=edge[i][1];
+  }
+  affichageGraphique(n,m, point,edge2, "graphe.ps");
+  kruskal(n,edge,arbre);
+  cout<<"Kruskal OK"<<endl;
+  affichageGraphique(n,n-1,point,arbre, "arbre.ps");
+  // system("evince graphe.ps");
+  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;
+    }
+}
+
+void distances(int n, int m, coord point[], int edge[][3]){
+  int k = 0;
+    for (int i =0; i < n; i ++){
+      for(int j = i+1; j < n; j ++){
+        edge[k][0]=i;
+        edge[k][1]=j;
+        edge[k][2]=pow((point[i].abs - point[i].ord)-(point[j].abs - point[j].ord),2);
+        k++;
+      }
+    }
+    cout<<"calcul des distance : OK"<<endl;
+}
+
+void fusion(int tableau[][3],int deb1,int fin1,int fin2)
+        {
+        int table1[fin1-deb1+1][3];
+        int deb2=fin1+1;
+        int compt1=deb1;
+        int compt2=deb2;
+        int i;
+        for(i=deb1;i<=fin1;i++)
+            {
+            swap(table1[i-deb1],tableau[i]);
+            }
+
+        for(i=deb1;i<=fin2;i++)
+            {
+            if (compt1==deb2)
+                {
+                break;
+                }
+            else if (compt2==(fin2+1))
+                {
+                swap(tableau[i],table1[compt1-deb1]);
+                compt1++;
+                }
+            else if (table1[compt1-deb1][2]<tableau[compt2][2])
+                {
+                swap(tableau[i],table1[compt1-deb1]);
+                compt1++;
+                }
+            else
+                {
+                swap(tableau[i],tableau[compt2]);
+                compt2++;
+                }
+            }
+        }
+
+void tri_fusion_bis(int tableau[][3],int deb,int fin)
+        {
+        if (deb!=fin)
+            {
+            int milieu=(fin+deb)/2;
+            tri_fusion_bis(tableau,deb,milieu);
+            tri_fusion_bis(tableau,milieu+1,fin);
+            fusion(tableau,deb,milieu,fin);
+            }
+        }
+
+void tri_fusion(int tableau[][3],int longueur)
+     {
+     if (longueur>0)
+            {
+            tri_fusion_bis(tableau,0,longueur-1);
+            }
+     }
+void tri(int m, int edge[][3]){
+  for (int i = 0 ; i < m ; i ++){
+    for(int j=i+1; j < m; j ++){
+      if ( edge[i][2]>edge[j][2]){
+        swap(edge[i][0],edge[j][0]);
+        swap(edge[i][1],edge[j][1]);
+        swap(edge[i][2],edge[j][2]);
+      }
+    }
+  }
+}
+
+void affichageGraphique(int n, int m, coord point[], int arbre[][2], 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<m;i++)
+   {
+     output << point[arbre[i][0]].abs << " " << point[arbre[i][0]].ord
+	    << " moveto" << endl;
+     output << point[arbre[i][1]].abs << " " << point[arbre[i][1]].ord
+	    << " lineto" << endl;
+     output << "stroke" << endl;
+     output << endl;
+   }
+  output << "showpage";
+  output << endl;
+}
+
+void kruskal (int n, int edge[][3], int arbre[][2]){
+  int comp[n];
+  int indicea=0;
+  for(int i =0; i < n-1; i ++){
+    arbre[i][0]=0;
+    arbre[i][1]=0;
+  }
+  for (int i = 0; i < n; i ++){
+    comp[i]=i;
+  }
+  for(int i = 0 ; i < n*(n-1)/2;i++ ){
+    if ( comp[edge[i][0]]!=comp[edge[i][1]]){
+      int aux = comp[edge[i][0]];
+      arbre[indicea][0]=edge[i][0];
+      arbre[indicea][1]=edge[i][1];
+      for(int j = 0; j < n; j ++){
+        if (comp[j]==aux){
+          comp[j]=comp[edge[i][1]];
+        }
+      }
+      indicea++;
+    }
+  }
+}