Initial commit

2 files changed, 223 insertions, 0 deletions

diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3 b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3
new file mode 100644
index 0000000..31f4a09
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3
diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3.cc b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3.cc
new file mode 100644
index 0000000..67644a4
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3.cc
@@ -0,0 +1,223 @@
+#include <cstdlib>
+#include <iostream>
+#include <vector>
+#include <fstream>
+#include <cmath>
+#include<vector>
+#include<queue>
+#include<stack>
+
+typedef struct coord{int abs; int ord;} coord;
+bool search (std::vector<int> vec, int x);
+void ecritureNiveaux(int n, int niveau[]);
+void voisinsRandom(int n, int m, std::vector<int>voisins[]);
+void afficheGraph (int n, std::vector<int>voisins[]);
+void parcoursLargeur(int n, std::vector<int>voisins[],int niveau[], int ordre[], int pere[]);
+void afficheArbre(int n, int pere[], int ordre[]);
+void pacoursProf(int n, int r, std::vector<std::stack<int>*> voisins, int debut[],int fin[], int pere[], int niveau[]);
+void vectortostack(int n,std::vector<int> arch[], std::vector<std::stack <int>* > young);
+void afficheArbrebis(int n, int pere[]);
+int sommeniveau(int n, int niveau[]);
+using namespace std;
+
+void voisinsRandom(int n, int m, vector<int>voisins[]){
+  srand(time(NULL));
+  int x=1; int y=0;
+  for (int i = 0; i < m; i ++){
+    do {
+    x = rand()%n;
+    y = rand()%n;
+    while (x==y){
+      y = rand()%n;
+    }
+  } while (search(voisins[x],y));
+    voisins[x].push_back(y);
+    voisins[y].push_back(x);
+  }
+}
+bool search (vector<int> vec, int x){
+  int i = 0;
+  if (vec.size()==0){
+    return false;
+  }
+  while (vec[i]!=x){
+    i ++;
+    if (i>vec.size()){
+      return false;
+    }
+  }
+  return true;
+}
+int main() {
+  int n;            //Le nombre de points.
+  int m; // nb aretes
+  cout << "Entrer le nombre de points: ";
+  cin >> n;
+  cout << "Entrer le nombre d'aretes: ";
+  cin>>m;
+  if (m > n*(n-1)/2){
+    cout<<"Nombre d'aretes trop grand, cap à : "<< n*(n-1)/2<<endl;
+    m=n*(n-1)/2;
+  }
+  vector<int> voisins[n];
+  int pere[n];
+  int pere2[n];
+  int ordre[n];
+  int niveau[n];
+  int niveau2[n];
+  int debut[n];
+  int fin[n];
+  vector<stack < int >* > piledevoisins = vector< stack < int > * >(n);
+  for (int i =0; i < n; i ++){
+    piledevoisins[i]=new stack<int>;
+  }
+  // for (int i = 0; i < n ; i ++){
+  //   piledevoisins[i]=new stack<int>;
+  // }
+  voisinsRandom(n,m,voisins);
+  //afficheGraph(n,voisins);
+  parcoursLargeur(n,voisins,niveau,ordre,pere);
+  //afficheArbre(n, pere, ordre);
+  //ecritureNiveaux(n,niveau);
+  cout<<"Parcours en largeur OK"<<endl;
+  vectortostack(n, voisins, piledevoisins);
+  pacoursProf(n,0,piledevoisins, debut, fin, pere2, niveau2);
+  //afficheArbrebis(n,pere);
+  //ecritureNiveaux(n,niveau2);
+  cout<<"Parcours Prof OK"<<endl;
+  cout<<"Smax larg vaut : "<< sommeniveau(n,niveau)<<endl;
+  cout<<"Smax prof vaut : "<< sommeniveau(n,niveau2)<<endl;
+  return EXIT_SUCCESS;
+}
+
+int sommeniveau(int n, int niveau[]){
+  int ret = 0;
+  for (int i =0; i < n; i ++){
+      ret+=niveau[i];
+      // cout << niveau[i]<<" + ";
+  }
+  cout<<endl;
+  return ret;
+}
+void afficheGraph (int n, vector<int>voisins[]){
+  for (int i =0; i < n; i ++){
+    int j = 0;
+    cout<<"Sommet "<<i<< " Voisins : ";
+    while (voisins[i].size()>j){
+      cout<< " "<<voisins[i][j];
+      j ++;
+    }
+    cout<<endl;
+  }
+}
+void afficheArbre(int n, int pere[], int ordre[]){
+  for (int i =0; i < n; i  ++ ){
+    cout << "Pere de "<<i<<" : "<<pere[i]<<endl;
+    cout << "Ordre de "<<i<<" : "<<ordre[i]<<endl;
+
+  }
+}
+void afficheArbrebis(int n, int pere[]){
+  for (int i =0; i < n; i  ++ ){
+    cout << "Pere de "<<i<<" : "<<pere[i]<<endl;
+  }
+}
+void parcoursLargeur(int n, vector<int>voisins[],int niveau[], int ordre[], int pere[]){
+  int dejavu[n];
+  for (int i =0; i < n; i ++ ){
+    dejavu[i]=0;
+    niveau[i]=0;
+  }
+  int r=0;
+  dejavu[r]=1;
+  ordre[r]=1;
+  pere[r]=r;
+  niveau[r]=0;
+  queue<int> AT;
+  AT.push(r);
+  int t = 2;
+  while (!AT.empty()){
+    int v = AT.front();
+    AT.pop();
+    for (int i =0; i < voisins[v].size();i ++){
+      int x = voisins[v][i];
+      if (!dejavu[x]){
+        dejavu[x]=1;
+        AT.push(x);
+        ordre[x]=t;
+        t ++;
+        pere[x]=v;
+        niveau[x]=niveau[v]+1;
+      }
+    }
+  }
+}
+void pacoursProf(int n, int r, vector<stack<int>* > voisins, int debut[],int fin[], int pere[] ,int niveau[]){
+  bool dejavu[n];
+  for (int i =0; i < n; i ++ ){
+    dejavu[i]=false;
+    niveau[i]=0;
+  }
+  dejavu[r]=1;
+  debut[r]=1;
+  pere[r]=r;
+  niveau[r]=0;
+  stack<int> AT;
+  AT.push(r);
+  int t = 2;
+  while (!AT.empty()){
+    int x = AT.top();
+    if (voisins[x]->empty()){
+      AT.pop();
+      fin[x]=t;
+      t ++;
+    }
+    else {
+      int y = voisins[x]->top();
+      voisins[x]->pop();
+      if (!dejavu[y]){
+        dejavu[y]=true;
+        AT.push(y);
+        debut[y]=t;
+        t++;
+        pere[y]=x;
+        niveau[y]=niveau[x]+1;
+        cout << "Niveau de "<<y << " = "<<niveau[x]+1<<endl;
+      }
+    }
+  }
+}
+void vectortostack(int n,vector<int> arch[], vector<stack <int>* > young){
+  for (int i = 0; i < n; i ++ ){
+    for (int j =0; j < arch[i].size(); j++){
+      young[i]->push(arch[i][j]);
+    }
+  }
+}
+void ecritureNiveaux(int n, int niveau[]){
+  int tmp[n];
+  for (int i =0; i < n; i ++){
+    tmp[i]=0;
+  }
+  for (int i = 0 ; i < n; i ++ ){
+    tmp[niveau[i]]++;
+  }
+  for (int i = 0; i < n; i ++){
+    if (tmp[i]==0){
+      return;
+    }
+    // cout<< "Il y a "<< tmp[i]<< " sommets de niveau " <<i<<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;
+}