Page MenuHomec4science
Files F61329218

Propagatio.cc
No OneTemporary
Actions

File Metadata

Created
Sun, May 5, 23:57

Propagatio.cc
View Options

// Propagatio.cc
// Auteur : Quentin Berling
// Version : 1.0
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
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<bool>> Matrix;
int check_bpm();
Matrix make_adj(int n);
void explore(int n, const Matrix &mat, vector<int> &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<bool>(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<bool>(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<int> &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<int> 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<int> 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<int> 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;
}

Event Timeline

c4science · Help