diff --git a/Projet/Propagatio.cc b/Projet/Propagatio.cc index 1166ba4..b50b8a2 100644 --- a/Projet/Propagatio.cc +++ b/Projet/Propagatio.cc @@ -1,202 +1,202 @@ // 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; 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 connect_ck(int n, const Matrix &mat); -void visit_node_and(int n, const Matrix &mat, Vector &visited, - vector &to_visit_next, int node); void propagate(int n, const Matrix &mat); double degree_ck(int n, const Matrix &mat, int n0); int main() { // Tâche 1 int n; n=check_bpm(); Matrix matAdj(n, Vector(n)); matAdj=make_adj(n); // Tâche 2 connect_ck(n, matAdj); // Tâche 3 propagate(n, matAdj); // 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)); 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) { + vector dummy; + explore(n, mat, visited, dummy, 0, 2); +} + + +void explore(int n, const Matrix &mat, Vector &visited, vector &to_visit_next, + int l, int mode) { visited[l]=1; for (int c(0); c < n; c++) { if (visited[c] == 0 && mat[l][c] == 1) { - explore(n, mat, visited, c); + if (mode == 2) { + explore(n, mat, visited, to_visit_next, c, 2); + } else { + to_visit_next.push_back(c); + } } } } void connect_ck(int n, const Matrix &mat) { Vector visited(n); explore(n, mat, visited, 0); if (find(visited.begin(), visited.end(), 0) != visited.end()) { cout << DISCONNECTED_GRAPH << endl; exit(0); } } -void visit_node_and(int n, const Matrix &mat, Vector &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, const Matrix &mat) { Vector 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) + " "; - visit_node_and(n, mat, visited, to_visit_next, node); + explore(n, mat, visited, to_visit_next, node, 3); } } 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, const Matrix &mat, int n0) { Vector 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; - visit_node_and(n, mat, visited, to_visit_next, node); + 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()); if (n > 1) { deg=deg/(n-1); } return deg; }