diff --git a/Projet/Propagatio.cc b/Projet/Propagatio.cc index 0319979..44976fd 100644 --- a/Projet/Propagatio.cc +++ b/Projet/Propagatio.cc @@ -1,195 +1,195 @@ // 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, Matrix mat, Vector &visited, int l); -void connect_ck(int n, Matrix mat); -void visit_node_and(int n, Matrix &mat, Vector &visited, +void explore(int n, const Matrix &mat, Vector &visited, int l); +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, Matrix mat); -double degree_ck(int n, Matrix mat, int n0); +void propagate(int n, const Matrix &mat); +double degree_ck(int n, const Matrix &mat, int n0); int main() { int n; n=check_bpm(); Matrix matAdj(n, Vector(n)); matAdj=make_adj(n); connect_ck(n, matAdj); propagate(n, matAdj); double degree(0); for (int i(0); i> 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) { 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, Matrix mat, Vector &visited, int l) { +void explore(int n, const Matrix &mat, Vector &visited, int l) { visited[l]=1; for (int c(0); c < n; c++) { if (visited[c] == 0 && mat[l][c] == 1) { explore(n, mat, visited, c); } } } -void connect_ck(int n, Matrix mat) { +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, Matrix &mat, Vector &visited, +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, Matrix mat) { +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); } } 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, Matrix mat, int n0) { +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); } } 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; }