Initial commit

5 files changed, 494 insertions, 0 deletions

diff --git a/sem_5/HLIN501_Graphes/TP/TP2/a.out b/sem_5/HLIN501_Graphes/TP/TP2/a.out
new file mode 100644
index 0000000..6742753
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP/TP2/a.out
diff --git a/sem_5/HLIN501_Graphes/TP/TP2/arbre.ps b/sem_5/HLIN501_Graphes/TP/TP2/arbre.ps
new file mode 100644
index 0000000..e0ec867
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP/TP2/arbre.ps
@@ -0,0 +1,46 @@
+%!PS-Adobe-3.0
+%%BoundingBox: 0 0 612 792
+
+553 782 3 0 360 arc
+0 setgray
+fill
+stroke
+
+294 166 3 0 360 arc
+0 setgray
+fill
+stroke
+
+498 380 3 0 360 arc
+0 setgray
+fill
+stroke
+
+191 16 3 0 360 arc
+0 setgray
+fill
+stroke
+
+478 181 3 0 360 arc
+0 setgray
+fill
+stroke
+
+
+294 166 moveto
+191 16 lineto
+stroke
+
+294 166 moveto
+478 181 lineto
+stroke
+
+498 380 moveto
+478 181 lineto
+stroke
+
+553 782 moveto
+498 380 lineto
+stroke
+
+showpage
diff --git a/sem_5/HLIN501_Graphes/TP/TP2/graphe.ps b/sem_5/HLIN501_Graphes/TP/TP2/graphe.ps
new file mode 100644
index 0000000..15ac7b5
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP/TP2/graphe.ps
@@ -0,0 +1,70 @@
+%!PS-Adobe-3.0
+%%BoundingBox: 0 0 612 792
+
+553 782 3 0 360 arc
+0 setgray
+fill
+stroke
+
+294 166 3 0 360 arc
+0 setgray
+fill
+stroke
+
+498 380 3 0 360 arc
+0 setgray
+fill
+stroke
+
+191 16 3 0 360 arc
+0 setgray
+fill
+stroke
+
+478 181 3 0 360 arc
+0 setgray
+fill
+stroke
+
+
+294 166 moveto
+191 16 lineto
+stroke
+
+294 166 moveto
+478 181 lineto
+stroke
+
+498 380 moveto
+478 181 lineto
+stroke
+
+294 166 moveto
+498 380 lineto
+stroke
+
+191 16 moveto
+478 181 lineto
+stroke
+
+553 782 moveto
+498 380 lineto
+stroke
+
+498 380 moveto
+191 16 lineto
+stroke
+
+553 782 moveto
+478 181 lineto
+stroke
+
+553 782 moveto
+294 166 lineto
+stroke
+
+553 782 moveto
+191 16 lineto
+stroke
+
+showpage
diff --git a/sem_5/HLIN501_Graphes/TP/TP2/tp2.cc b/sem_5/HLIN501_Graphes/TP/TP2/tp2.cc
new file mode 100644
index 0000000..8ec3bbc
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP/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[j].abs-point[i].abs,2)+pow(point[j].ord-point[i].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++;
+    }
+  }
+}
diff --git a/sem_5/HLIN501_Graphes/TP/TP2/tribulle.cc b/sem_5/HLIN501_Graphes/TP/TP2/tribulle.cc
new file mode 100644
index 0000000..0266596
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP/TP2/tribulle.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(m,edge);

+  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);

+  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[j].abs-point[i].abs,2)+pow(point[j].ord-point[i].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;

+        //on recopie les éléments du début du tableau

+        for(i=deb1;i<=fin1;i++)

+            {

+            swap(table1[i-deb1],tableau[i]);

+            }

+

+        for(i=deb1;i<=fin2;i++)

+            {

+            if (compt1==deb2) //c'est que tous les éléments du premier tableau ont été utilisés

+                {

+                break; //tous les éléments ont donc été classés

+                }

+            else if (compt2==(fin2+1)) //c'est que tous les éléments du second tableau ont été utilisés

+                {

+                swap(tableau[i],table1[compt1-deb1]); //on ajoute les éléments restants du premier tableau

+                compt1++;

+                }

+            else if (table1[compt1-deb1][2]<tableau[compt2][2])

+                {

+                swap(tableau[i],table1[compt1-deb1]); //on ajoute un élément du premier tableau

+                compt1++;

+                }

+            else

+                {

+                swap(tableau[i],tableau[compt2]); //on ajoute un élément du second tableau

+                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++;

+    }

+  }

+}