diff --git a/Projet/Propagatio.cc b/Projet/Propagatio.cc index f87067a..6a4e1e4 100644 --- a/Projet/Propagatio.cc +++ b/Projet/Propagatio.cc @@ -1,173 +1,190 @@ +// Propagatio.cc +// Auteur : Quentin Berling +// Version : 1.0 #include #include #include #include #include using namespace std; const string P1("P1 missing or incorrect"); const string WRONG_NB_COL_LGN("Nb columns and/or nb lines incorrect"); const string MATRIX_SQUARE("Matrix is not square"); const string IRREGULAR_CONTENT("Matrix description with incorrect content"); const string DISCONNECTED_GRAPH("Matrix corresponds to a disconnected graph"); +typedef vector Vecteur; +typedef vector Matrice; + + void check_bpm(int &n); +void make_adj(int n, Matrice &mat); +void explore(int n, Matrice mat, Vecteur &visited, int l); +void connect_ck(int n, Matrice mat); +void visit_node_and(int n, Matrice &mat, Vecteur &visited, + vector &to_visit_next, int node); +void propagate(int n, Matrice mat); +double degree_ck(int n, Matrice mat, int n0); + + void check_bpm(int &n) { string header; // cout << "Header P1 ?" << endl; cin >> header; if (header != "P1") { cout << P1 << endl; exit(0); } int c,l; // cout << "Nombre de colonnes ?" << endl; cin >> c; // cout << "Nombre de lignes ?" << endl; cin >> l; - if (l == c) + if (l == c) { n=l; + } else { cout << MATRIX_SQUARE << endl; exit(0); } if (n == 0) { cout << WRONG_NB_COL_LGN << endl; exit(0); } } -void make_adj(int n, vector> &tab); -void make_adj(int n, vector> &tab) { +void make_adj(int n, Matrice &mat) { for (int i(0); i < n; i++) { char c; int j(0); cin >> c; while(c != '\n') { if (c == '0' || c == '1') { - tab[i][j]=int(c)-int('0'); + mat[i][j]=int(c)-int('0'); j++; } else if (isspace(c)) { } else { cout << IRREGULAR_CONTENT << endl; exit(0); } cin.get(c); } if (j != n) { cout << WRONG_NB_COL_LGN << endl; exit(0); } - tab[i][i]=0; + mat[i][i]=0; } for (int i(0); i < n; i++) { for (int j(0); j < n; j++) { - if (tab[i][j] == 1) - tab[j][i]=1; + if (mat[i][j] == 1) { + mat[j][i]=1; + } } } } -void explore(int n, vector> mat, vector &visited, int l); -void explore(int n, vector> mat, vector &visited, int l) { +void explore(int n, Matrice mat, Vecteur &visited, int l) { visited[l]=1; for (int c(0); c < n; c++) { - if (visited[c] == 0 && mat[l][c] == 1) + if (visited[c] == 0 && mat[l][c] == 1) { explore(n, mat, visited, c); + } } } -void connect_ck(int n, vector> mat); -void connect_ck(int n, vector> mat) { - vector visited(n); +void connect_ck(int n, Matrice mat) { + Vecteur visited(n); explore(n, mat, visited, 0); if (find(visited.begin(), visited.end(), 0) != visited.end()) { cout << DISCONNECTED_GRAPH << endl; exit(0); } } -void propagate(int n, vector> mat); -void propagate(int n, vector> mat) { - vector visited(n); +void visit_node_and(int n, Matrice &mat, Vecteur &visited, + vector &to_visit_next, int node) { + visited[node]=1; + for (int c(0); c < n; c++) { + if (visited[c] == 0 && mat[node][c] == 1) { + to_visit_next.push_back(c); + } + } +} + + +void propagate(int n, Matrice mat) { + Vecteur visited(n); vector to_visit({0}), to_visit_next; string propagation; do { for (int node : to_visit) { if (visited[node] != 1) { propagation=propagation + to_string(node) + " "; - visited[node]=1; - for (int c(0); c < n; c++) { - if (visited[c] == 0 && mat[node][c] == 1) { - to_visit_next.push_back(c); - } - } + visit_node_and(n, mat, visited, to_visit_next, node); } } propagation.pop_back(); cout << propagation << endl; propagation.clear(); to_visit=to_visit_next; to_visit_next.clear(); sort(to_visit.begin(), to_visit.end()); } while (find(visited.begin(), visited.end(), 0) < visited.end()); } -double degree_ck(int n, vector> mat, int n0); -double degree_ck(int n, vector> mat, int n0) { - vector visited(n); +double degree_ck(int n, Matrice mat, int n0) { + Vecteur visited(n); vector to_visit({n0}), to_visit_next; int i(0); double deg(0); do { for (int node : to_visit) { if (visited[node] != 1) { deg=deg+i; - visited[node]=1; - for (int c(0); c < n; c++) { - if (visited[c] == 0 && mat[node][c] == 1) { - to_visit_next.push_back(c); - } - } + visit_node_and(n, mat, visited, to_visit_next, node); } } to_visit=to_visit_next; to_visit_next.clear(); i++; } while (find(visited.begin(), visited.end(), 0) < visited.end()); - if (n > 1) + if (n > 1) { deg=deg/(n-1); - + } + return deg; } int main() { int n; check_bpm(n); - vector> matAdj(n, vector(n)); + Matrice matAdj(n, Vecteur(n)); make_adj(n, matAdj); connect_ck(n, matAdj); propagate(n, matAdj); double degree(0); - for (int i(0); i