diff options
Diffstat (limited to 'sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tribulle.cc')
| -rw-r--r-- | sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tribulle.cc | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tribulle.cc b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tribulle.cc new file mode 100644 index 0000000..0266596 --- /dev/null +++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/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++;
+ }
+ }
+}
|