diff --git a/Projet/Propagatio.cc b/Projet/Propagatio.cc index b50b8a2..4f0962a 100644 --- a/Projet/Propagatio.cc +++ b/Projet/Propagatio.cc @@ -1,202 +1,204 @@ // 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 Vector; -typedef vector Matrix; +typedef vector> Matrix; int check_bpm(); Matrix make_adj(int n); -void explore(int n, const Matrix &mat, Vector &visited, int l); -void explore(int n, const Matrix &mat, Vector &visited, vector &to_visit_next, - int l, int mode); +void explore(int n, const Matrix &mat, vector &visited, int l); +void explore(int n, const Matrix &mat, vector &visited, int l, int mode, + vector &to_visit_next); void connect_ck(int n, const Matrix &mat); -void propagate(int n, const Matrix &mat); -double degree_ck(int n, const Matrix &mat, int n0); +double propagate(int n, const Matrix &mat, int mode, int n0); +void degree_ck(int n, const Matrix &mat); int main() { // Tâche 1 int n; n=check_bpm(); - Matrix matAdj(n, Vector(n)); + + Matrix matAdj(n, vector(n)); matAdj=make_adj(n); // Tâche 2 connect_ck(n, matAdj); // Tâche 3 - propagate(n, matAdj); + propagate(n, matAdj, 3, 0); // Tâche 4 - double degree(0); - for (int i(0); i> header; if (header != "P1") { cout << P1 << endl; exit(0); } cin >> c; cin >> l; if (l == c) { n=l; } else { cout << MATRIX_SQUARE << endl; exit(0); } if (n == 0) { cout << WRONG_NB_COL_LGN << endl; exit(0); } return n; } Matrix make_adj(int n) { - Matrix mat(n, Vector(n)); + Matrix mat(n, vector(n)); for (int i(0); i < n; i++) { char c; int j(0); cin >> c; while (c != '\n') { if (c == '0' || c == '1') { mat[i][j]=int(c)-int('0'); j++; } else if (! isspace(c)) { cout << IRREGULAR_CONTENT << endl; exit(0); } cin.get(c); } if (j != n) { cout << WRONG_NB_COL_LGN << endl; exit(0); } mat[i][i]=0; } for (int i(0); i < n; i++) { for (int j(0); j < n; j++) { if (mat[i][j] == 1) { mat[j][i]=1; } } } return mat; } -void explore(int n, const Matrix &mat, Vector &visited, int l) { +void explore(int n, const Matrix &mat, vector &visited, int l) { vector dummy; - explore(n, mat, visited, dummy, 0, 2); + + explore(n, mat, visited, 0, 2, dummy); } -void explore(int n, const Matrix &mat, Vector &visited, vector &to_visit_next, - int l, int mode) { +void explore(int n, const Matrix &mat, vector &visited, int l, int mode, + vector &to_visit_next) { visited[l]=1; + for (int c(0); c < n; c++) { if (visited[c] == 0 && mat[l][c] == 1) { if (mode == 2) { - explore(n, mat, visited, to_visit_next, c, 2); + explore(n, mat, visited, c, 2, to_visit_next); } else { to_visit_next.push_back(c); } } } } void connect_ck(int n, const Matrix &mat) { - Vector visited(n); + vector 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, const Matrix &mat) { - Vector visited(n); - vector to_visit({0}), to_visit_next; - string propagation; +double propagate(int n, const Matrix &mat, int mode, int n0) { + vector visited(n); + vector to_visit({n0}), to_visit_next; + string propagation; // Utilisé dans le mode 3 + int i(0); // Utilisés dans le mode 4 + double deg(0); // do { for (int node : to_visit) { if (visited[node] != 1) { - propagation=propagation + to_string(node) + " "; - explore(n, mat, visited, to_visit_next, node, 3); + if (mode == 3) { + propagation=propagation + to_string(node) + " "; + } else { + deg=deg+i; + } + explore(n, mat, visited, node, 3, to_visit_next); } } - propagation.pop_back(); - cout << propagation << endl; - propagation.clear(); + if (mode == 3) { + propagation.pop_back(); + cout << propagation << endl; + propagation.clear(); + } else { + i++; + } 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()); + + if (mode == 4) { + return deg; + } else { + return 0; + } } -double degree_ck(int n, const Matrix &mat, int n0) { - Vector visited(n); - vector to_visit({n0}), to_visit_next; - int i(0); - double deg(0); +void degree_ck(int n, const Matrix &mat) { + double degree(0); - do { - for (int node : to_visit) { - if (visited[node] != 1) { - deg=deg+i; - explore(n, mat, visited, to_visit_next, node, 4); - } - } - - to_visit=to_visit_next; - to_visit_next.clear(); - i++; - } while (find(visited.begin(), visited.end(), 0) < visited.end()); + for (int i(0); i 1) { - deg=deg/(n-1); + degree=degree/(n-1); } - - return deg; + + cout << setprecision(6) << fixed << degree/n << endl; }