diff --git a/Projet/Explorer.txt b/Projet/Explorer.txt new file mode 100644 index 0000000..f4648e6 --- /dev/null +++ b/Projet/Explorer.txt @@ -0,0 +1,10 @@ +Explorer +entrée non modifiée : n un entier, M une matrice n*n de booléens, l un entier +entrée modifiée : V une liste d'entiers +sortie : (rien) + Pour c allant de 1 à n + newdeg ← V[l]+1 + Si M[l][c] = 1 + Si V[c] > newdeg + V[c]=newdeg + Explorer(n, M, V, c) diff --git a/Projet/Propagatio.cc b/Projet/Propagatio.cc index 72d2fec..1e31333 100644 --- a/Projet/Propagatio.cc +++ b/Projet/Propagatio.cc @@ -1,179 +1,178 @@ // 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> Matrix; int check_bpm(); Matrix make_adj(int n); void explore(int n, const Matrix &mat, vector &visited, int l); void connect_ck(int n, const Matrix &mat); void propagate(int n, const Matrix &mat); void degree_ck(int n, const Matrix &mat); 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 degree_ck(n, matAdj); return 0; } int check_bpm() { int n,c,l; string header; cin >> 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) { - for (int c(0); c < n; c++) { if (mat[l][c] == 1 && visited[c] > visited[l]+1) { visited[c]=visited[l]+1; explore(n, mat, visited, c); } } } void connect_ck(int n, const Matrix &mat) { vector visited(n, n); visited[0]=0; explore(n, mat, visited, 0); if (find(visited.begin(), visited.end(), n) != visited.end()) { cout << DISCONNECTED_GRAPH << endl; exit(0); } } void propagate(int n, const Matrix &mat) { string propagation; vector visited(n, n); visited[0]=0; explore(n, mat, visited, 0); for (int deg(0); deg <= *max_element(visited.begin(), visited.end()); deg++) { for (int node(0); node < n; node++) { if (visited[node] == deg) { propagation+=to_string(node) + " "; } } propagation.pop_back(); cout << propagation << endl; propagation.clear(); } } void degree_ck(int n, const Matrix &mat) { double degree(0); vector visited(n, n); for (int from_node(0); from_node < n; from_node++) { visited[from_node]=0; explore(n, mat, visited, from_node); for (int &node_deg : visited) { degree+=node_deg; node_deg=n; } } if (n > 1) { degree=degree/(n-1); } cout << setprecision(6) << fixed << degree/n << endl; } diff --git a/Projet/Propagation.txt b/Projet/Propagation.txt new file mode 100644 index 0000000..4866db2 --- /dev/null +++ b/Projet/Propagation.txt @@ -0,0 +1,25 @@ +Propagation +entrée : n un entier, M une matrice n*n de booléens +sortie : (rien) + P ← nouvelle liste () + V ← nouvelle liste () + V[1] ← 0 + Pour i allant de 2 à n + V[i] ← n + + Explorer(n, M, V, 1) + + degmax ← 0 + Pour i allant de 1 à n + Si V[i] > degmax + degmax ← V[i] + + Pour deg allant de 0 à degmax + Pour noeud allant de 1 à n + Si V[noeud] = deg + Ajouter(P, noeud) + Ajouter(P, ' ') + + P[Taille(P)] ← '' + Afficher P + P ← nouvelle liste ()